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. Характеристика метода перевозки неоднородного груза

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

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

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

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

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

2 Потребности только на второй сорт груза (соответственно b¹¹₁и b¹¹₂).

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

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

Вместо каждого из двух потребителей В₁ и В₂ будем в дальнейшем рассматривать три потребителя с потребностями b¹, b¹¹ и b¹¹¹.

Занесем все перечисленные исходные данные и, кроме того, коэффициенты затрат C_ik на перевозку единицы груза в таблицу №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 - единиц второго сорта. Тогда отношение назовем коэффициентом взаимозаменяемости. Он показывает, сколько единиц груза второго сора могут заменить единицу груза первого сорта.

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

Так ресурсы а¹₁ и а¹₂ единиц первого сорта эквивалентны соответственно ба¹₁ и ба¹₂ единиц второго сорта. Аналогично, потребность b¹₁, b¹₂, b¹¹¹₁ и b¹¹¹₂ эквивалентны соответственно бb¹₁, бb¹₂, бb¹¹¹₂, бb¹¹¹₁. Однако затраты связаны с перевозками реального груза и зависят от его реального веса, а не от потребительских свойств.

Поэтому, увеличив искусственные ресурсы первого сорта в б раз, необходимо соответственно в этих строках уменьшить в б раз коэффициенты затрат. Наконец, следует предусмотреть, чтобы потребности 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

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

а¹¹₁ + а¹¹₂ +б(а¹₁ + а¹₂) = b¹¹₁ + b¹¹₂ +б(b¹₁ + b¹₂) + б(b¹¹¹₁ + b¹¹¹₂).

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

a¹₁ + a¹₂ ? b¹₁ + b¹₂

a¹¹₁ + a¹¹₁? b¹¹₁+ b¹¹₂

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

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

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

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

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

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

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

Составляя план по способам минимальных стоимостей в отличии от плана по способу “северо-западного угла” мы учитываем стоимости перевозок C_i,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., они не могут быть удовлетворены из ресурсов А₁₂=3200 и А₂₂=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