Стационарная транспортная задача

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

Классическая транспортная задача линейного программирования формулируется следующим образом.

Имеется пунктов отправления: в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно

единиц. Кроме того, имеется пунктов назначения: подавших заявку соответственно на единиц товара. Предполагается, что сумма всех заявок равна сумме всех запасов: . Известна стоимость перевозки единицы товара от каждого пунктов отправления до каждого пункта назначения . Таблица (матрица) стоимостей перевозки задана

.

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

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

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

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

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

Целевая функция линейна, ограничения-равенства также линейны. Перед нами – типичная задача линейного программирования с ограничениями-равенствами. Как и всякую другую задачу линейного программирования, ее можно было бы решить симплекс-методом, но данная задача имеет некоторые особенности, позволяющие решить ее более просто. Причиной является то, что все коэффициенты при переменных в ограничениях-равенствах равны 1. Кроме того, ограничения-равенства связаны одной линейной зависимостью, а именно, . Фактически из этих уравнений только -1 являются линейно независимыми. Значит ранг системы ограничений равен -1. А, следовательно, можно разрешить эти уравнения относительно -1 базисных переменных, выразив их через остальные, свободные. Подсчитаем количество свободных переменных. Оно равно:

= .

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

Значения количества единиц груза, направляемых из пункта отправления в пункт назначения будем называть перевозками. Любую совокупность значений () ( будем называть планом перевозок или просто планом.

План () будем называть допустимым, если он удовлетворяет ограничениям-равенствам: все заявки удовлетворены, все запасы исчерпаны. Допустимый план будем называть опорным, если в нем отличны от нуля не более базисных перевозок , а остальные перевозки равны 0.

План () будем называть оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

Перейдем к изложению методов решения транспортной задачи (ТЗ).Эти методы сводятся к более простым операциям с таблицей, где в определенном порядке записаны все условия ТЗ. Такую таблицу будем называть транспортной таблицей. В ней записываются:

- пункты отправления и назначения,

- запасы, имеющиеся в пунктах отправления,

- заявки, поданные пунктами назначения,

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

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

ПО / ПН			…………..		Запасы
			……………..
			……………..
………….	…………….	……………	…………..	……………	…………..
			……………
Заявки			……………..

Ранг системы ограничений-уравнений равен , где - число строк, - число столбцов транспортной таблицы. В каждом опорном плане будут отличны от нуля не более перевозок. Ячейки таблицы, в которых будем записывать отличные от нуля перевозки, называются базисными, а остальные (пустые) свободными.

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

- сумма перевозок в каждой строке таблицы должна быть равна запасу данного ПО,

- сумма перевозок в каждом столбце должна быть равна заявке данного ПН,

- общая стоимость перевозок – минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной таблицы. При описании этих преобразований удобно пользоваться нумерацией клеток таблицы. Клеткой () называется клетка, стоящая в - ой строке и -ом столбце транспортной таблицы.

Нахождение опорного плана

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

Условия ТЗ заданы следующей транспортной таблицей.

ПО / ПН						Запасы
Заявки

Будем заполнять таблицу перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта удовлетворена, а в пункте осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта назначим пункту . В составе заявки пункта остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта , чем его запас будет исчерпан, и еще 9 возьмем из пункта . Из оставшихся 18 единиц груза пункта 12 выделим пункту ; оставшиеся 6 единиц назначим пункту , что вместе со всеми 20 единицами пункта покроет его заявку.

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

ПО / ПН						Запасы
	18 10	27 8	3 5
			30 8
			9 10	12 8	6 7
					20 8
Заявки

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию = 8. Остальные клетки – свободные (пустые), в них стоят нулевые перевозки, их число равно = 12. Значит, полученный план – опорный и поставленная задача построения опорного плана решена.

Является ли этот план оптимальным по стоимости? Нет, ведь при его построении не учитывались стоимости перевозок. Поэтому план не получился оптимальным. Стоимость этого плана найдется, если умножить каждую перевозку на соответствующую стоимость и сложить. Имеем 18 10+27 8 +3 5+30 8+9 10+12 8+6 7+20 8=1039.

Попробуем улучшить этот план, перенеся, например, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушить баланса, перенесем те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план

ПО / ПН						Запасы
		27 8	21 5
	18 6		12 8
			9 10	12 8	6 7
					20 8
Заявки

Можно убедиться, что стоимость нового плана равна

27 8+21 5 +18 6+12 8+9 10+12 8+6 7+20 8=913, т.е. на 126 единиц стоимости меньше стоимости полученного ранее плана.

Итак, за счет циклической перестановки 18 единиц груза из одних клеток в другие удалось понизить стоимость плана. На этом основан алгоритм оптимизации плана перевозок.