Методы решения транспортной задачи

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

Решение.

Сведем исходные данные в таблицу

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

или

Требуется спланировать перевозки так, чтобы весь груз из пунктов отправления был вывезен. Но поскольку суммарный объем картофеля, вывезенного от каждого фермера, не может превышать собранного урожая, то переменные должны удовлетворять следующим ограничениям по запасам:

Аналогично потребности каждого пункта потребления должны быть полностью удовлетворены. Но поскольку потребность магазинов в картофеле (260 т) больше, чем собранный фермерами урожай (235 т), то спрос не всех магазинов будет полностью удовлетворен. Поэтому должны выполняться ограничения-неравенства по потребностям:

Объем перевозок картофеля не может быть отрицательным, поэтому справедливы условия неотрицательности на переменные,,.

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

Согласно условию запросы 3-го магазина должны быть полностью удовлетворены. Следовательно, стоимость транспортных расходов на доставку, например,. Стоимость транспортных расходов от фиктивного фермера во все другие магазины будем полагать равной нулю:,,.

Получим

3.2.1 Построение начального опорного плана методом «минимального элемента»

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

.

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

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

Пусть. Следовательно загружается клетка, т.е.. Если, то и из рассмотрения исключают столбец с номером k, соответствующий потребителю, спрос которого полностью удовлетворен. А новое значение. Если, то и из рассмотрения исключают строку с номером l, соответствующую поставщику, запасы которого израсходованы полностью. Новое значение. На некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-то одно). Тогда запасы соответствующего пункта отправления или потребности данного пункта назначения полагают равными нулю. Это нуль записывают в очередную заполняемую клетку. Опорный план называется невырожденным, если все его компоненты больше нуля, в противном случае он называется вырожденным.

Дата добавления: 2013-12-13