Транспортная задача перевозки неоднородного груза

Сущность, характеристика метода и аналитическое решение транспортной задачи перевозки неоднородного груза. Анализ процесса обработки информации и выбор структур данных для ее хранения. Проектирование интерфейса пользователя, формы ввода-вывода информации.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 22.01.2016
Размер файла 329,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

21

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

КОМПЛЕКСНАЯ КУРСОВАЯ РАБОТА

На тему «Транспортная задача перевозки неоднородного груза»

Содержание

  • Введение
  • Сущность математического метода
    • 1. Характеристика метода перевозки неоднородного груза
    • 2. Аналитическое решение задачи перевозки неоднородного груза
  • Анализ и уточнение требований к программе
    • 1. Анализ процесса обработки информации и выбор структур данных для ее хранения
    • 2. Разработка основных алгоритмов решения задачи
  • Проектирование интерфейса пользователя
    • 1. Граф состояния интерфейса
    • 2. Формы ввода-вывода информации
  • Контрольный пример
  • Заключение
  • Список литературы
  • Приложение A

Введение

транспортная задача неоднородный груз

Тема курсовой работы - транспортная задача перевозки неоднородного груза.

Транспортная задача является разновидностью линейного программирования. Возникновение и развитие линейного программирования связано с экономикой. В экономике задачи математического программирования, и в частности линейного, возникают в связи с многочисленностью вариантов создания или функционирования определенной экономической системы, с возможностью применения различного сырья, материалов, технологии для производства одной и той же продукции.

Линейное программирование является наиболее развитым и широко используемым на практике разделом математического программирования. Предложение о линейности экономических зависимостей несколько ограничивает возможности линейного программирования, однако простота и наглядность линейных моделей, с достаточной степенью точности описывающих экономические процессы, позволяет применять эти модели в различных видах экономической деятельности.

Основы линейного программирования были заложены советским математиком Л.В. Канторовичем в конце 30-х годов.

В 1949 г. Л.В.Кантоновичем и М,К. Гавуриным предложен новый точный метод для решения транспортной задачи - метод потенциалов. В последующие годы вклад в развитие теории линейного программирования внесли ученые многих стран мира.

Цель данной работы заключается в создании программного продукта для решения задач по теме: «Транспортная задача перевозки неоднородного груза».

Задачи курсовой работы:

- изучить теоретический материал по данной теме;

- изучить методы решения задач;

- создать алгоритм для решения данной задачи;

- создать программу для решения задач данного класса.

Программа будет разработана в среде Delphi.

Системные требования: Win 98/SE/2000/ME/XP, 256 RAM.

Сущность математического метода

1. Характеристика метода перевозки неоднородного груза

Иногда встречаются задачи перевозки неоднородного груза к таким, например, относится планирование перевозок угля разных сортов, цемента разных марок, сортового железа и т.д. Характерной чертой всех этих задач является условие взаимозаменяемости различных сортов перевозимого груза при удовлетворении потребностей. Это означает, иными словами, что некоторая часть потребностей может быть удовлетворена различными видами имеющегося в наличии груза и характера потребностей. Мы рассмотрим, каким образом подобные задачи могут быть приведены к задачам о перевозках некоторого условного однородного груза.

Пусть, например, имеются два поставщика - А1и А2 и два потребителя В1и В2.

У каждого поставщика имеется груз двух сортов (например, бурый уголь и антрацит, цемент марок 500 и 600 и т.д.). Обозначим ресурсы 1-го поставщика по каждому из сортов груза через а11 и a111 и аналогично, 2-го поставщика - через а12 и a112.

В дальнейшее мы будем рассматривать не два, а как бы четыре поставщика, ресурсы которого соответственно равны а11, а111, а12 и а112. Теперь перейдем к анализу потребностей каждого потребителя. Очевидно, в условиях данной задачи эти потребности у каждого потребителя могут быть трех видов.

1 Потребности только на первый сорт груза. Обозначим их соответственно для 1-го потребителя через b11и для второго через b12.

2 Потребности только на второй сорт груза (соответственно b111и b112).

3 Взаимозаменяемые потребности на любой из сортов груза (соответственно b1111и b1112).

Будем полагать, что b1111и b1112означают потребности 1-го и 2-го потребителя, выраженные в единицах первого сорта груза.

Вместо каждого из двух потребителей В1 и В2 будем в дальнейшем рассматривать три потребителя с потребностями b1, b11 и b111.

Занесем все перечисленные исходные данные и, кроме того, коэффициенты затрат Cik на перевозку единицы груза в таблицу №1.

Таблица 1 Оформление таблицы в методичке

b11

a11

B1

B2

b11

b111

b1111

b12

b112

b1112

a11

c11

c11

c11

c12

c12

c12

a111

c11

c11

c11

c12

c12

c12

a12

c21

cc1

c21

c22

c22

c22

a112

c21

c21

c21

c22

c22

c22

Будем полагать, что коэффициенты затрат от сорта перевозимого груза, а определяются только тем, «откуда» и «куда» он перевозится.

Пусть p - единицы груза первого сорта могут быть замены при удовлетворении 3-й категории потребностей q - единиц второго сорта. Тогда отношение назовем коэффициентом взаимозаменяемости. Он показывает, сколько единиц груза второго сора могут заменить единицу груза первого сорта.

Приведем все данные таблицы к одному условному грузу, например грузу второго сорта, с помощью коэффициента взаимозаменяемости.

Так ресурсы а11 и а12 единиц первого сорта эквивалентны соответственно ба11 и ба12 единиц второго сорта. Аналогично, потребность b11, b12, b1111 и b1112 эквивалентны соответственно бb11, бb12, бb1112, бb1111. Однако затраты связаны с перевозками реального груза и зависят от его реального веса, а не от потребительских свойств.

Поэтому, увеличив искусственные ресурсы первого сорта в б раз, необходимо соответственно в этих строках уменьшить в б раз коэффициенты затрат. Наконец, следует предусмотреть, чтобы потребности 1-й и 2-й категории удовлетворялись только определенным допустимым сортом груза. Для этого производится блокировка недопустимых перевозок с помощью искусственно завышенных коэффициентов затрат М.

В результате внесения всех указанных изменений получим распределенную таблицу №2, в которой фигурирует однородный условный груз.

Таблица 2 Оформление таблицы в методичке

bk

ai

B1

B2

b11

b111

b1111

b12

b112

b1112

бa11

c11

M

c11

c12

M

c12

a111

M

c11

c11

M

c12

c12

бa12

c21

M

c21

c22

M

c22

a112

M

c21

c21

M

c22

c22

Условие для закрытой модели будет в данном случае выглядеть так:

а111 + а112 +б(а11 + а12) = b111 + b112 +б(b11 + b12) + б(b1111 + b1112).

Однако этого условия не достаточно. Очевидно, запасы ресурсов груза первого и второго сорта должны быть не меньше потребностей в этих сортах

a11 + a12 ? b11 + b12

a111 + a111? b111+ b112

Дальнейшее решение задач можно производить обычно распределительным методом, рассматривая условно четырех поставщиков груза и шесть потребителей.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ “северо-западного угла”, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.

Простейшим способом является метод «северо-западного угла», в этом случае заполняют таблицу перевозками постепенно, начиная с левой верхней ячейки (“северо-западного угла“ таблицы).

Но такой способ не является оптимальным по стоимости, так как при его построении совсем не учитывается стоимость перевозок Сi,j.

Другой способ -- способ минимальной стоимости по строке -- основан на том, что распределяется продукция от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом “северо-западного угла”. При этом методе может получиться, что стоимости перевозок Ci,j и Ci,k от пункта Ai к пунктам Bj и Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше.

Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов Bi к пунктам Aj по минимальной стоимости Cj,i. Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению.

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Составляя план по способам минимальных стоимостей в отличии от плана по способу “северо-западного угла” мы учитываем стоимости перевозок Ci,j, но все же не можем утверждать, что составленный нами план является оптимальным.

Следующий шаг - это улучшение план.

На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90.

Существует несколько вариантов цикла:

1) 2) 3)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком “-“ те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-то количество единиц груза по означенному циклу -- это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце -- заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком “+”, а в отрицательных со знаком “-“. Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор пока циклов с отрицательной ценой уже не останется. При улучшении плана циклическими переносами, как правило, пользуются приёмом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, то есть заполняют одну свободную клетку и взамен того освобождают одну из базисных клеток. При этом общее число базисных клеток остаётся неизменным и равным m + n - 1

2. Аналитическое решение задачи перевозки неоднородного груза

Задача:

1-й склад (А1) имеет сталь двух марок: 3000т. марки «а» и 4000т. марки «б». 2-й склад (А2) имеет сталь марки «а» - 5000т. и марки «б» - 2000т. Сталь должна быть вывезена в два пункта потребления: в пункт В1 необходимо поставить 2000т. стали марки «а», 3000т. - марки «б» и остальные 2000т. стали любой марки.

Аналогично, второй пункт потребления В2 должен получить 8250т. стали, из них 1000т. марки «а» и 1500т. марки «б».

Известно, что 2т. стали марки «а» могут заменить 1,6тю марки «б».

Стоимость перевозок в рублях за тонну составляют: из А1 в В1 и В2 1руб. и 1,5руб. соответственно и из А2 в В1 и В2 2руб. м 1 руб.

Составить оптимальный план.

Решение:

Прежде всего, необходимо вычислить коэффициент взаимозаменяемости:

Исходя из этого коэффициента пересчитаем все данные:

Потреб.

ресурсы

В1

В2

2000

2400

1600

1000

1200

4600

А1

3000

1

1

1

1,5

1,5

1,5

3200

1,25

1,25

1,25

1,875

1,875

1,875

А2

5000

2

2

2

1

1

1

1600

2,5

2,5

2,5

1,25

1,25

1,25

Кроме того, выполняются условия:

3000+3200+5000+1600 = 2000+2400+1600+1000+1200+4600;

3000+5000 > 2000+1000;

3200+1600 > 2400+1200.

Следовательно, задача разрешима.

В связи с тем, что в 1-м и 3-м столбцах указаны потребности только на груз Ic., они не могут быть удовлетворены из ресурсов А12=3200 и А22=1600 груза IIс. Поэтому клетки (2,1), (2,3), (4,1) и (4,3) блокируются с помощью произвольно больших затрат М. Аналогично блокируются клетки, через которые ресурсы Iс. не могут удовлетворить потребности в грузе IIс., т.е. клетки (1,2), (1,4), (3,2) и (3,4).

После всех преобразований получим таблицу:

Потреб.

ресурсы

В1

В2

2000

2400

1600

1000

1200

4600

А11

3000

1

М

1

1,5

М

1,5

А12

3200

М

1,25

1,25

М

1,875

1,875

А21

5000

2

М

2

1

М

1

А22

1600

М

2,5

2,5

М

1,25

1,25

После всех выполненных операций данную задачу можно решать как обычную транспортную задачу, рассматривая условно четырех поставщиком и шести потребителей.

Составление опорного плана:

Потреб.

ресурсы

В1

В2

2000

2400

1600

1000

1200

4600

А11

3000

1 2000

М

1 1000

1,5

М

1,5

А12

3200

М

1,25 2400

1,25 600

М

1,875 200

1,875

А21

5000

2

М

2

1 1000

М

1 4000

А22

1600

М

2,5

2,5

М

1,25 1000

1,25 600

После составления получаем: количество заполненных ячеек m+n-1 (где m -количество строк, а n - количество столбцов) 4+6-1. Минимальные затраты на этом шаге равны:

1*2000 + 1,25*2400 + 1*1000 + 1,25*600 + 1*1000 + 1,875*200 + 1,25*1000 + 1*4000 + 1,25*600 =14125

Оценка критерий оптимальности решения:

Добавим дополнительную строку и столбец

Потреб.

ресурсы

В1

В2

2000

2400

1600

1000

1200

4600

А11

3000

1 2000

М

1 1000

1,5

М

1,5

-1

А12

3200

М

1,25 2400

1,25 600

М

1,875 200

1,875

-1,25

А21

5000

2

М

2

1 1000

М

1 4000

-1

А22

1600

М

2,5

2,5

М

1,25 1000

1,25 600

-1,25

0

0

0

0

-0,625

0

А11

3000

0 2000

М-1

0 1000

0,5

М

0,5

-1

А12

3200

М-1,25

0 2400

0 600

М-1,25

0 200

0

-1,25

А21

5000

1

М-1

1

0 1000

М-1,625

0 4000

-1

А22

1600

М-1,25

1,25

1,25

М-1,25

-0,625

1000

0 600

-1,25

0

0

0

0

-0,625

0

После ввода всех значений пересчитаем результат и произведем цикл пересчета поставок:

Пересчитав поставки получаем оптимальное решение:

Потреб. ресурсы

В1

В2

2000

2400

1600

1000

1200

4600

А11

3000

0 2000

М

0 1000

0,5

М

0,5

А12

3200

М

0 2400

0 600

М

0,625

0 200

А21

5000

1

М

1

0 1000

М

0 4000

А22

1600

М

1,25

1,25

М

0 1200

0 400

Пересчитав элементы 2-го и 3-го, 5-го и 6-го столбцов в этом решении путем деления их на б=0,8, получим окончательное оптимальное решение, выраженное уже не в условных, а в реальных единицах:

и Z=15 375 руб.

Анализ и уточнение требований к программе

1. Анализ процесса обработки информации и выбор структур данных для ее хранения

Программа для решения задачи перевозки неоднородного груза будет использовать двумерный массив, так как задачи такого типа записываются и решаются в виде таблицы. Тип этих массивов будет дробный, потому что решение требует делить некоторые данные на коэффициент взаимозаменяемости:

1 С - массив для занесения цены перевозок.

2 p - массив со структурой аналогичной массива С, куда будет заноситься распределение поставок груза.

3 cu - массив, в начальной стадии разработки, копия массива С, предназначен для нахождения оптимальности перевозок. Введен для того, что в конечной стадии решения задачи необходимо обратиться к исходным затратам перевозок для подсчета общей стоимости затрат.

Так же в программе будут использоваться одномерные массивы:

1 B - одномерный массив типа real от 1 до 6 для запоминания потребностей каждого потребителя в трех сортах груза.

2 alfa, betta - потенциалы для приближения оптимальности плана; alfa - потенциалы по строкам, betta - потенциалы по столбцам.

3 А - одномерный массив дробного типа из 4 элементов содержащий количество разных сортов на складах поставщиков.

4 f0 - вспомогательный массив дробного типа т.к. присваивает себе элементы массива Р, предназначен для определения цикла передвижения в таблице. Выбран виде массива т.к будет более удобно обращаться к элементам цикла для передвижения поставок.

5 di, dj - массив со структурой аналогичной F0 для запоминания местонахождения элемента массива F0 в массиве Р. Эти массивы введены для того, чтобы после завершения цикла передвижения сохранить эти изменения в массиве Р.

Так же необходимы переменные дробного типа для различных вычислений:

Lqp - для вычисления коэффициента взаимозаменяемости; при этом Lqp = ql/pl, где pl единиц первого сорта заменяют ql единиц второго.

f - переменная для вычисления затрат на перевозку груза.

min - переменная будет необходима для поиска минимального отрицательного числа в массиве cu, чтобы организовать цикл передвижения.

Для организации различных циклов будут необходимы переменные счетчики:l, i, j, n.

Вспомогательные переменные целочисленного типа - x,y,xj,yi.

2. Разработка основных алгоритмов решения задачи

Процесс решения задачи можно рассмотреть пошагово:

1 Ввод данных. Ввод данных будем осуществлять путем присвоения элементам массива значений из ячеек, разработав для этого линейный алгоритм. Ввода цены на перевозку удобно организовать с помощью циклического алгоритма, т.к. значения будут сохраняться в двумерном массиве.

2 Блокировка поставок. Условие задачи требует блокировки некоторых ячеек для того, чтобы не переместились в эти ячейки распределенный груз. Для этого необходимо присвоить, этим ячейкам, реализовав линейный алгоритм, большую цену на перевозку - 100.

3 Распределение поставок. Распределение организуем методом северо-западного угла. Для этого необходимо разработать циклический алгоритм т.к. массив, в котором будет осуществляться распределение - двумерный. Каждый раз в данном цикле будет проверяться условие: сколько нужно переместить и сколько груза есть на складе, для этого задействуем алгоритм проверки условия. Сначала просматриваем количество необходимого груза, затем количество имеющегося груза на складе, если они равны, то количеству груза на складе присваиваем ноль и количество необходимого груза и присваиваем рассматриваемому полю необходимое количество груза. Если же количество имеющегося на складе превышает потребности, то значению количества груза присваиваем разность имеющегося на складе и необходимого груза для потребителей. Иначе, если количество на складе меньше требуемого груза, то рассматриваемому полю присвоим количество имеющегося груза на складе, а потребность в грузе уменьшаем на количество груза на складе.

4 Объявление потенциалов. Потенциалы будут находиться в двух массивах: для строк - alfa, для столбцов - betta. Для нахождения этих потенциалов необходимо разработать циклический алгоритм, в котором сначала найдем в каждой строке максимальный по модулю элемент и присвоим соответствующему элементу массива его значение противоположное по знаку. Для нахождения значения по столбцам каждому значению массива будем присваивать сумму всех соответствующих значений цены и элементов массива аlfa.

5 Пересчет цен на перевозку. Для пересчета цен на перевозку необходимо разработать циклический алгоритм, в котором каждому новому значению элементов присваиваем сумму исходного значения и значение потенциалов рассматривая массив Сu = С.

6 Организация цикла передвижения поставок. Разработаем циклический алгоритм, в котором путем сравнения найдем минимальную цену на поставку и от нее начнем вычерчивать цикл передвижения поставок.

7 Проверка плана на оптимальность. В цикле проверим, есть ли отрицательные цены на перевозку и есть ли в них поставки. Если такие ячейки будут, то перейдем к пункту 6. А если таковых не имеется, то переходим на конечный расчет.

8 Расчет затрат на перевозку и вывод результата. С помощью циклического алгоритма подсчитаем затраты путем умножения не пустых ячеек поставок на начальную цену перевозок. Результат распределения поставок выведем в таблицу, а общую сумму в нижнюю часть формы.

Проектирование интерфейса пользователя

1. Граф состояния интерфейса

2. Формы ввода-вывода информации

Главная форма

21

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Из меню «Файл» можно осуществить выход из программы.

1 Поле для ввода количества товара марки А на первом складе.

2 Поле для ввода количества товара марки Б на первом складе.

3 Поле для ввода количества товара марки А на втором складе.

4 Поле для ввода количества товара марки Б на втором складе.

5 Поле для ввода количества необходимого груза марки А для первого потребителя.

6 Поле для ввода количества необходимого груза марки Б для первого потребителя.

7 Поле для ввода количества необходимого груза любой марки для первого потребителя.

8 Поле для ввода количества необходимого груза марки А для второго потребителя.

9 Поле для ввода количества необходимого груза марки Б для второго потребителя.

10 Поле для ввода количества необходимого груза любой марки для второго потребителя.

11 Поле для ввода стоимости перевозки от первого склада в первый пункт.

12 Поле для ввода стоимости перевозки от первого склада во второй пункт.

13 Поле для ввода стоимости перевозки со второго склада в первый пункт.

14 Поле для ввода стоимости перевозки со второго склада во второй пункт.

Чтобы вычислить коэффициент взаимозаменяемости необходимо создать два поля: №15 - для ввода количества единиц первого сорта, которые могут заменить второй сорт, а №16 - для ввода количества единиц второго сорта, которые заменяют первый сорт.

При нажатии на кнопку Старт будет выполняться решение задачи.

При нажатии на Очистить будет обнуляться все ячейки данной формы.

В таблицу будут выводиться результаты решения.

В нижней части формы выводятся затраты на перевозку груза.

Об авторе

Форма об авторе будет содержать поле Panel для информации о программе,

При нажатии на который форма будет закрываться.

Контрольный пример

В этом разделе демонстрируется работа программы.

Для начала необходимо ввести данные в ячейки. При вводе данных можно воспользоваться табулятором для передвижения по ячейкам. Ввод осуществляется с клавиатуры.

После этого можно нажать на кнопку ПУСК либо, если при вводе где-то допущена ошибка ОЧИСТИТЬ. Если выбрана кнопка ПУСК, то осуществится вычисление задачи выведется результат.

При нажатии же на кнопку ОЧИСТИТЬ происходит обнуление всех ячеек для ввода данных:

Так же из главной формы можно перейти в справку об авторе. Она находится на вкладке файл. В справке можно узнать информацию об авторе и о программе:

Заключение

Транспортная задача, и (особенно) ее подвид перевозка неоднородного груза, является важной частью экономики. Решение этих задач требуется, когда необходимо спланировать поставки сырья, или построить план распределения имеющихся ресурсов.

В результате данной работы были достигнуты поставленные цели и задачи, а именно:

1. изучен теоретический материал и методы решения задач по теме: «Транспортная задача перевозки неоднородного груза»;

2. разработан алгоритм решения задачи данного типа;

3. создана программа для решения задачи перевозки неоднородного груза с участием двух поставщиков и двух потребителей.

В будущем можно реализовать программу для решения задачи данного типа с разным количеством поставщиков и потребителей.

По данным неоднократной сверки результатов ручного решения задач и прогона ее на компьютере была выявлена идентичность ответов.

Список литературы

1. А.В.Кузнецов, Г.И.Новикова, И.И.Холод - «Сборник задач по математическому программированию». Минск, Высшая школа, 2014г.

2. А.В.Кузнецов, Г.И.Новикова, И.И.Холод - «Высшая математика. Математическое программирование». Минск, Высшая школа, 2011г.

Приложение А

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Menus;

type

TForm1 = class(TForm)

Button1: TButton;

Button3: TButton;

ka11: TEdit;

ka12: TEdit;

ka21: TEdit;

ka22: TEdit;

kb11: TEdit;

kb12: TEdit;

kb13: TEdit;

kb21: TEdit;

kb22: TEdit;

kb23: TEdit;

kc11: TEdit;

kc12: TEdit;

kc21: TEdit;

kc22: TEdit;

kp: TEdit;

kq: TEdit;

StringGrid1: TStringGrid;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

Label10: TLabel;

Label11: TLabel;

Label12: TLabel;

Label13: TLabel;

Label14: TLabel;

Label15: TLabel;

Label16: TLabel;

MainMenu1: TMainMenu;

My1: TMenuItem;

My2: TMenuItem;

My3: TMenuItem;

procedure Button1Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure My2Click(Sender: TObject);

procedure My3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

Type predpr=Array [1..6] of real;

rasp=Array [1..4,1..6] of real;

Var

Lqp:real;

pl,ql:real;

B,alfa,betta,B_d:predpr;

c,p,cu:rasp;

a,f0:array [1..4] of real;

di,dj:array [1..4] of integer;

f,min,Sp:real;

l,i,j,x,y,xj,yi,n,k:byte;

d:char;

Form1: TForm1;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.Button3Click(Sender: TObject);

begin

ka11.Text:=' ';

ka12.Text:=' ';

ka21.Text:=' ';

ka22.Text:=' ';

kb11.Text:=' ';

kb12.Text:=' ';

kb13.Text:=' ';

kb21.Text:=' ';

kb22.Text:=' ';

kb23.Text:=' ';

kc11.Text:=' ';

kc12.Text:=' ';

kc21.Text:=' ';

kc22.Text:=' ';

kp.Text:=' ';

kq.Text:=' ';

end;

procedure TForm1.Button1Click(Sender: TObject);

label l1;

begin

a[1]:=strtoint(ka11.Text);

a[2]:=strtoint(ka12.Text);

a[3]:=strtoint(ka21.Text);

a[4]:=strtoint(ka22.Text);

b[1]:=strtoint(kb11.Text);

b[2]:=strtoint(kb12.Text);

b[3]:=strtoint(kb13.Text);

b[4]:=strtoint(kb21.Text);

b[5]:=strtoint(kb22.Text);

b[6]:=strtoint(kb23.Text);

pl:=strtofloat(kp.Text);

ql:=strtofloat(kq.Text);

Lqp:=ql/pl;{ коэффициент взаимозаменяемости}

a[2]:=a[2]*Lqp;

a[4]:=a[4]*Lqp;

b[2]:=b[2]*Lqp;

b[3]:=b[3]*Lqp;

b[5]:=b[5]*Lqp;

b[6]:=b[6]*Lqp;

for i:=1 to 4 do

for j:=1 to 6 do begin { ввод цен на затраты перевозки}

if (i=1) and (j=1) then begin

c[i,j]:=strtofloat(kc12.Text);

c[i,j+1]:=strtofloat(kc12.Text);

c[i,j+2]:=strtofloat(kc12.Text);

end;

if (i=1) and (j=4) then begin

c[i,j]:=strtofloat(kc11.Text);

c[i,j+1]:=strtofloat(kc11.Text);

c[i,j+2]:=strtofloat(kc11.Text);

end;

if (i=2) and (j=1) then begin

c[i,j]:=strtofloat(kc12.Text)/lqp;

c[i,j+1]:=strtofloat(kc12.Text)/lqp;

c[i,j+2]:=strtofloat(kc12.Text)/lqp;

end;

if (i=2) and (j=4) then begin

c[i,j]:=strtofloat(kc11.Text)/lqp;

c[i,j+1]:=strtofloat(kc11.Text)/lqp;

c[i,j+2]:=strtofloat(kc11.Text)/lqp;

end;

if (i=3) and (j=1) then begin

c[i,j]:=strtoint(kc21.Text);

c[i,j+1]:=strtoint(kc21.Text);

c[i,j+2]:=strtoint(kc21.Text);

end;

if (i=3) and (j=4) then begin

c[i,j]:=strtofloat(kc22.Text);

c[i,j+1]:=strtofloat(kc22.Text);

c[i,j+2]:=strtofloat(kc22.Text);

end;

if (i=4) and (j=1) then begin

c[i,j]:=strtofloat(kc21.Text)/Lqp;

c[i,j+1]:=strtofloat(kc21.Text)/Lqp;

c[i,j+2]:=strtofloat(kc21.Text)/Lqp;

end;

if (i=4) and (j=4) then begin

c[i,j]:=strtofloat(kc22.Text)/Lqp;

c[i,j+1]:=strtofloat(kc22.Text)/Lqp;

c[i,j+2]:=strtofloat(kc22.Text)/Lqp;

end;

end;

{ блокировка поставок}

c[1,2]:= 100; c[1,5]:= 100; c[2,1]:= 100; c[2,4]:=100;

c[3,2]:= 100; c[3,5]:= 100; c[4,1]:= 100; c[4,4]:= 100;

{ распределение методом северо-западного угла}

for i:=1 to 4 do

for j:=1 to 6 do

if c[i,j]<>100 then begin

if a[i]=b[j] then begin

p[i,j]:=a[i];

b[j]:=0;

a[i]:=0;

end;

if a[i]>b[j] then begin

p[i,j]:=b[j];

a[i]:=a[i]-b[j];

b[j]:=0;

end;

if a[i]<b[j] then begin

p[i,j]:=a[i];

b[j]:=b[j]-a[i];

a[i]:=0;

end;

end;

l1:

for i:=1 to 4 do

for j:=1 to 6 do

if p[i,j]>0 then begin min:=c[i,j]; k:=j;

while k<7 do begin k:=k+1;

if (p[i,k]>0) and(p[i,k]>min) then alfa[i]:=c[i,j] - 2*c[i,j];

end;end;

for i:=1 to 4 do

for j:=1 to 6 do

if p[i,j]>0 then betta[j]:=betta[j]+c[i,j]+alfa[i];

for n:=1 to 6 do

if betta[n]>0 then betta[n]:= betta[n] - 2*betta[n];

for i:=1 to 4 do

for j:=1 to 6 do begin

cu[i,j]:=c[i,j];

cu[i,j]:=cu[i,j]+alfa[i]+betta[j];

end;

for i:=1 to 4 do

for j:=1 to 6 do

if cu[i,j]<0 then begin f0[1]:=p[i,j]; x:=j; y:=i; di[1]:=i; dj[1]:=j; end;

for i:=1 to 4 do

for j:=1 to 6 do

if (i=y)and (j=x) then begin while y>0 do begin

if p[y,j]>0 then begin f0[2]:=p[y,j]; yi:=y; di[2]:=y; dj[2]:=j;end;

y:=y-1;

end;

while x<7 do begin

if p[i,x]>0 then begin f0[4]:=p[i,x];xj:=x; di[4]:=i;dj[4]:=x;end;

x:=x+1;

end;

end;

f0[3]:=p[yi,xj];di[3]:=yi; dj[3]:=xj;

min:=f0[1];

for i:=1 to 4 do if (i mod 2 =0)and (f0[i]<min) then min:=f0[i];

for j:=1 to 4 do if j mod 2 = 0 then f0[j]:=f0[j]-min else f0[j]:=f0[j]+min;

for n:=1 to 4 do p[di[n],dj[n]]:=f0[n];

for i:=1 to 4 do

for j:=1 to 6 do

if (c[i,j]<0) and (p[i,j]>0) then goto l1;

{ вывод}

for i:=1 to 6 do begin

p[2,i]:=p[2,i]/lqp;

p[4,i]:=p[4,i]/lqp;

end;

for j:=1 to 4 do

if j mod 2<>0 then begin

p[j,2]:= p[j,2]/lqp;

p[j,3]:= p[j,3]/lqp;

p[j,5]:= p[j,5]/lqp;

p[j,6]:= p[j,6]/lqp;

end;

for l:=1 to 4 do

for k:=1 to 6 do

if p[l,k]>0 then Form1.StringGrid1.Cells[k,l]:=floattostr(p[l,k]);

f:=0;

for i:=1 to 4 do

for j:=1 to 6 do begin

if (i=2) and (j=1) then begin

c[i,j]:=c[i,j]*lqp;

c[i,j+1]:=c[i,j+1]*lqp;

c[i,j+2]:=c[i,j+2]*lqp;

end;

if (i=2) and (j=4) then begin

c[i,j]:=c[i,j]*lqp;

c[i,j+1]:=c[i,j+1]*lqp;

c[i,j+2]:=c[i,j+2]*lqp;

end;

if (i=4) and (j=1) then begin

c[i,j]:=c[i,j]*Lqp;

c[i,j+1]:=c[i,j+1]*Lqp;

c[i,j+2]:=c[i,j+2]*Lqp;

end;

if (i=4) and (j=4) then begin

c[i,j]:=c[i,j]*Lqp;

c[i,j+1]:=c[i,j+1]*Lqp;

c[i,j+2]:=c[i,j+2]*Lqp;

end;

end;

for i:=1 to 4 do

for j:=1 to 6 do

if p[i,j]>0 then f:=f+c[i,j]*p[i,j];

Form1.Canvas.Font.Name:= 'Tahoma';

Form1.Canvas.Font.Size:= 10;

Form1.Canvas.Font.Style:= [fsitalic,fsBold];

Form1.Canvas.Font.Color:=clBlue;

Form1.Canvas.TextOut(50,500,'F = '+floattostr(f)+' денежных ед.');

end;

procedure TForm1.My2Click(Sender: TObject);

begin

close;

end;

procedure TForm1.My3Click(Sender: TObject);

begin

Form2.Visible:=true;

end;

end.

Размещено на Allbest.ru


Подобные документы

  • Выбор технологии, языка и среды программирования. Анализ процесса обработки информации и выбор структур данных для ее хранения, разработка основных алгоритмов. Проектирование интерфейса пользователя. Выбор стратегии тестирования и разработка тестов.

    курсовая работа [332,3 K], добавлен 09.12.2014

  • Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.

    курсовая работа [476,6 K], добавлен 22.05.2012

  • Выбор технологии, языка и среды программирования. Анализ процесса обработки информации и оценка структур данных для ее хранения. Разработка основных алгоритмов решения и структурной схемы программного продукта. Проектирование интерфейса пользователя.

    курсовая работа [449,8 K], добавлен 14.01.2011

  • Разработка игры, реализующей алгоритмы искусственного интеллекта, позволяющие играть в одиночку. Анализ обрабатываемой информации и структур данных для ее хранения. Разработка интерфейса пользователя, форм вывода данных. Выбор стратегии тестирования.

    курсовая работа [896,5 K], добавлен 19.06.2013

  • Условия математической транспортной задачи для ее решения методом потенциалов. Опорный план и проверка целевой функции. Окончательный вариант плана поставок товара предоставленный программой "АОС транспортная задача". Стоимость доставки единицы груза.

    лабораторная работа [1,4 M], добавлен 15.10.2015

  • Структурная схема компьютера. Основные характеристики процессора - устройства, предназначенного для обработки информации и управления процессом обработки. Способы хранения информации. Описание, назначение и принципы работы устройств ввода и вывода данных.

    презентация [862,1 K], добавлен 20.07.2011

  • Использование программой функции ввода-вывода данных для реализации дружественного интерфейса с пользователем. Функции консоли и особенности их применения для обеспечения аккуратного ввода информации и упорядоченного вывода. Обзор стандартных функций.

    лабораторная работа [40,4 K], добавлен 06.07.2009

  • Разработка информационного обеспечения задачи, определение логической структуры реляционной базы данных. Разработка запросов и отчетов для обработки и отображения информации, интерфейса пользователя. Методика и этапы физического проектирования задачи.

    курсовая работа [33,5 K], добавлен 25.07.2012

  • Разработка сайта для хранения и обработки информации об абитуриентах в среде программирования Delphi 7. Архитектура базы данных. Функциональная схема программы. Даталогическая модель данных. Сущности БД и архива. Элементы пользовательского интерфейса.

    дипломная работа [4,2 M], добавлен 30.03.2015

  • Математическая постановка транспортной задачи открытой модели методом потенциалов при известных показателях запаса груза поставщика и потребности потребителя; ее решение ручным способом и с помощью компьютерной программы, написанной в среде Delphi.

    курсовая работа [167,2 K], добавлен 16.01.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.