9. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

Предполагается, что сумма всех заявок равна сумме всех запасов:

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

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

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

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

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

или, короче,

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

или, короче,

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

или, гораздо короче,

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

Функция (9.4) линейна, ограничения - равенства (9.2), (9.3) также линейны. Перед нами — типичная задача линейного программирования с ограничениями-равенствами (ОЗЛП).

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

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

Подсчитаем количество свободных переменных. Оно равно:

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

Условимся о терминологии. Значения количества единиц груза, направляемых из пункта в пункт В, мы будем называть перевозками.

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

План будем называть допустимым, если он удовлетворяет условиям (9.2), (9.3) (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны.

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

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

Перейдем к изложению методов решения транспортной задачи (ТЗ).

Эти методы не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия ТЗ. Такую таблицу мы будем называть транспортной таблицей.

В транспортной таблице записываются

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

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

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

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

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

Образец транспортной таблицы дан в табл. 9.1.

Таблица 9.1

Для краткости в дальнейшем будем обозначать пункты отправления — ПО, пункты назначения — ПН. В правом верхнем углу каждой клетки проставлены стоимости перевозки единицы товара (груза) из ПО в ПН . В правом столбце помещены запасы товара в каждом ПО, в нижней строке — заявки, поданные каждым ПН. Для ТЗ сумма запасов равна сумме заявок; общее значение этой суммы записывается в правой нижней ячейке таблицы.

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

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

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

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

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

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

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

При описании этих преобразований нам удобно будет пользоваться нумерацией клеток таблицы (подобной нумерации клеток шахматной доски). Клеткой или, короче, клеткой мы будем называть клетку, стоящую в строке и столбце транспортной таблицы. Например, самая верхняя левая клетка будет обозначаться (1. D. стоящая под ней (2, 1) и т. д.