Транспортная задача линейного программирования

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

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

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

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

Известна стоимость перевозки единицы товара от каждого пункта отправления до каждого пункта назначения в 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) и т. д.

НАХОЖДЕНИЕ ОПОРНОГО ПЛАНА

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

Пример 1. Условия ТЗ заданы транспортной таблицей (см. табл. 10.1).

Требуется найти опорное решение ТЗ (построить опорный план).

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

Таблица 10.1

Из них 30 покроем за счет пункта, чем его запас будет исчерпан, и еще 9 возьмем из пункта. Из оставшихся 18 единиц пункта выделим пункту оставшиеся 6 единиц назначим пункту что вместе со всеми 20 единицами пункта покроет его заявку (см. табл. 10.2).

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

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

Таблица 10.2

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

Возникает вопрос: а является ли этот план оптимальным по стоимости? Разумеется, нет! Ведь при его построении мы совсем не учитывали стоимостей перевозок Естественно, план не получился оптимальным. Действительно, стоимость этого плана, которая найдется, если умножить каждую перевозку на соответствующую стоимость, равна.

Таблица 10.3

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

Нетрудно убедиться, что стоимость нового плана равна т. е. на 126 единиц меньше стоимости плана, приведенного в табл. 10.3.

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

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

Пример 2. Дана транспортная таблица (без стоимостей перевозок, так как речь идет только о построении опорного плана) — см. табл. 10.4.

Таблица 10.4

Таблица 10.5

Таблица 10.6

Составить опорный план перевозок.

Решение. Применяя способ северо-западного угла, получим табл. 10.5.

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

Нетрудно заметить, отчего это произошло: при распределении запасов по пунктам назначения в некоторых случаях остатки оказывались равными нулю и в соответствующую клетку не попадали.

Такие случаи «вырождения» могут возникать не только при составлении опорного плана, но и при его преобразовании, оптимизации.

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

Покажем, как перейти от вырожденного плана к невырожденному на примере табл. 10.5. Изменим слегка запасы в первой строке и положим их равными. Кроме того, в третьей строке проставим запасы. Чтобы «свести баланс», в четвертой строке ставим запасы 20 — 2е (см. табл. 10.6). Для этой таблицы строим опорный план способом северо-западного угла.

В табл. 10.6 уже содержится столько базисных переменных, сколько требуется:. В дальнейшем, после оптимизации плана, можно будет положить.

УЛУЧШЕНИЕ ПЛАНА ПЕРЕВОЗОК. ЦИКЛ ПЕРЕСЧЕТА

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

Возьмем транспортную таблицу, состоящую, например, из строк и столбцов (число строк и столбцов несущественно).

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

Например, в табл. 11.1 изображены два цикла: первый с четырьмя вершинами (2,1), (2,3), (4,3), (4,1) и второй — с восемью вершинами (1,4), (1,6), (4,6), (4,4), (3,4), (3,5), (5,5), (5,4). Стрелками показано направление обхода цикла.

Таблица 11.1

Таблица 11.2

Нетрудно убедиться, что каждый цикл имеет четное число вершин и, значит, четное число звеньев (стрелок).

Условимся отмечать знаком «+» те вершины цикла, в которых перевозки увеличиваются, а знаком «-» — те вершины, в которых они уменьшаются. Цикл с отмеченными вершинами будем называть «означенным». В табл 11.2 показано два означенных цикла: первый с четырьмя вершинами (1,1), (1,2), (3,2) и (3,1) и второй с восемью вершинами (3, 4), (3,6), (5, 6), (5,3), (2,3), (2,5), (4,5) и (4,4).

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

Назовем ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных — со знаком «-». Например, для цикла в табл. 11.2 цена равна:

а для цикла

Обозначим цену цикла Ц через у. При перемещении одной единицы груза по циклу Ц стоимость перевозок увеличивается на величину у; при перемещении по нему k единиц груза стоимость перевозок увеличивается на

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

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

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

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

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

Пример 1. Найти оптимальный план для транспортной задачи, приведенной в табл. 11.3.

Таблица 11.3

Решение. Составляем опорный план способом северо-западного угла (табл. 11.4).

Стоимость этого плана равна:

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

Попробуем улучшить план, заняв свободную клетку (2,4) с минимальной стоимостью 4. Цикл, соответствующий этой клетке, показан в табл. 11.4. Цена этого цикла равна.

По этому циклу мы можем переместить максимум 20 единиц груза (чтобы не получить в клетке (3,4) отрицательной перевозки) Новый, улучшенный план показан в табл 11.5

Таблица 11.4

Таблица 11.5

Таблица 11.6

Таблица 11.7

Таблица 11.8

Таблица 11.9

Стоимость этого плана. В нем по-прежнему шесть базисных клеток.

Для дальнейшего улучшения плана обратим внимание на свободную клетку стоимостью 5. Цикл, соответствующий этой клетке, показан в табл. 11.5; цена его По этому циклу переместим 22 единицы груза, чем уменьшим стоимость перевозок до (см. табл. 11.6).

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

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

Пример 2. Найти оптимальный план перевозок для ТЗ, условия которой приведены в табл. 11.7.

Решение. Строим опорный план способом северо-западного угла; он получается вырожденным. Чтобы избежать этого, нарушаем баланс запасов и заявок на 8 в первой и третьей строках, не нарушая общего баланса (сумма запасов равна сумме заявок). После этого строим опорный план также способом северо-западного угла (табл. 11.8), в нем ровно столько базисных переменных, сколько нужно: пять. Улучшаем план перевозок переносом единиц груза по циклу, показанному в табл. 11.8; получим новый, лучший план (см. табл. 11.9).

План, приведенный в табл. 10.9, еще не оптимален, так как цикл с началом в свободной клетке (2,1) имеет отрицательную цену:

Перемещаем по этому циклу 20 единиц груза; получим табл. 11.10.

Цена цикла, начинающегося в клетке (2,2) табл. 11.10, также отрицательна: Однако, по этому циклу можно перенести только перевозку, равную е. Тем не менее, сделаем это и получим новый план (Табл. 11.11).

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

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

Таблица 11.10

Таблица 11.11

Таблица 11.12

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