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

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

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

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

Коротко матрицу (10.2) будем обозначать (с).

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

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

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

которую мы будем коротко обозначать Совокупность чисел (10.3) мы будем называть «планом перевозок», а сами величины - «перевозками».

Эти неотрицательные переменные должны удовлетворять следующим условиям.

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

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

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

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

Мы видим, что перед нами — задача линейного программирования с условиями-равенствами (10.4), (10.5) и минимизируемой линейной функцией (10.6). Особенностью этой задачи является то, что все коэффициенты в условиях (10.4), (10.5) равны единице — это позволяет решать задачу очень простыми способами. О них и пойдет речь.

Прежде всего, замечаем, что условия-равенства (10.4), (10.5) не являются линейно независимыми, так как их правые части связаны условием (10.1). Число линейно независимых среди уравнений (10.4), (10.5) равно не (числу уравнений), а

Общее число переменных в нашей задаче равно как бы ни разрешать уравнения (10.4), (10.5), число базисных переменных будет равно , а число свободных переменных

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

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

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

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

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

Продемонстрируем его непосредственно на конкретных данных таблицы 10.1. Начнем заполнение транспортной таблицы с левого верхнего («северо-западного») угла. Пункт подал заявку на 18 единиц груза; удовлетворим ее из запасов пункта

Таблица 10.1

После этого в нем остается еще единиц груза; отдадим их пункту . Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта и т. д. Рассуждая точно таким же образом, заполним до конца перевозками транспортную таблицу (таблица 10.2). Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения; значит, все в порядке — все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы).

Здесь и в дальнейшем мы проставляем в таблице только отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем «свобод-» ными». Проверим, является ли план перевозок, данный в таблице 10.2, опорным (не слишком ли много там отличных от нуля, «базисных» перевозок?). Число свободных клеток с нулевыми перевозками в таблице 10.2 равно как раз так что план — опорный.

Вот как нам его удалось легко построить!

Таблица 10.2

Теперь пора подумать о том, является ли этот план оптимальным — т. е. минимальна ли для него общая стоимость перевозок? Скорее всего, нет (ведь составляя опорный план, мы совсем не думали о стоимостях). Так и есть —план не оптимальный. Например, сразу видно, что можно его улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12, но зато увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. Чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных — свободной. Сколько единиц груза можем мы перенести по циклу , увеличивая перевозки в нечетных вершинах цикла и уменьшая — в четных? Очевидно, не больше, чем И единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Очевидно, в результате циклического переноса допустимый план остается допустимым — баланс запасов и заявок не нарушается. Ну что же, произведем этот перенос и запишем новый, улучшенный план перевозок в таблице 10.3.

Теперь посмотрим, чего мы добились, сколько сэкономили? Общая стоимость плана, показанного в таблице 10.2, равна общая стоймость плана, показанного в таблице 10.3, равна

Таблица 10.3

Таким образом, нам удалось уменьшить стоимость перевозок на 1442 — 1398 = 44 единицы. Это, впрочем, можно было предсказать и не подсчитывая полную стоимость плана. Действительно, алгебраическая сумма стоимостей, стоящих в вершинах цикла, со знаком плюс, если перевозки в этой вершине увеличиваются, и со знаком минус — если уменьшаются (так называемая «цена цикла»), в данном случае равна: 8 + 10 - 12 = -4. Значит, при переносе одной единицы груза по этому циклу стоимость перевозок уменьшается на четыре. А мы их перенесли целых 11; значит, стоимость должна была уменьшиться на 11•4 = 44 единицы, что и произошло.

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

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

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

Попробуем еще раз улучшить план, приведенный в таблице 10.3. Например, нас «соблазняет» дешевая клетка (1.5) со стоимостью 5. Нельзя ли улучшить план, увеличив перевозки в этой клетке, зато уменьшив в других (при этом, конечно, придется кое-где перевозки тоже увеличить). Давайте разглядим внимательно таблицу 10.3 и найдем в ней цикл, первая вершина которого лежит в свободной клетке (1.5), а остальные — все в базисных клетках. Немного подумав, мы этот цикл обнаружим: это последовательность клеток (1.5) (4.5) (4.4) (2.4) (2.2) (1.2) (и замыкая цикл, снова возвращаемся в (1.5)). Нечетные вершины цикла отмечены плюсом — это значит, что перевозки в этих клетках увеличиваются: четные — знаком минус (перевозки уменьшаются). Цикл показан стрелками в таблице 10.4.

Подсчитаем цену этого цикла. Она равна . Так как цена цикла отрицательна, то переброска перевозок по этому циклу выгодна. Посмотрим, сколько же единиц мы можем по нему перебросить? Это определяется наименьшей перевозкой, стоящей в отрицательной вершине цикла. В данном случае это опять 11 (чистое совпадение!). Умножая 11 на цену цикла — 5 получим, что за счет переброски 11 единиц груза по данному циклу мы еще уменьшим стоимость перевозок на 55 (предоставляем любознательному читателю сделать это самостоятельно).

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

Таблица 10.4

Бесконечно уменьшаться она не может (она никак не может стать меньше нуля!), значит, рано или поздно мы придем к оптимальному плану. Для такого плана уже не остается ни одной свободной клетки с отрицательной ценой цикла. Это — признак того, что оптимальное решение найдено.

В теории линейного программирования существуют способы, позволяющие автоматически, без размышлений, выделять свободные клетки с отрицательной ценой цикла (так называемый «метод потенциалов»), но мы на них останавливаться не будем, так же как и на ряде других способов решения транспортной задачи, с которыми читатель может ознакомиться по специальным руководствам [5, 7, 8].

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

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

Тогда задача сводится к задаче с правильным балансом, так как

Возникает вопрос: а каковы же стоимости перевозок из пунктов отправления в «фиктивный» пункт назначения ? Естественно положить их равными нулю (ведь фактически в пункт ничего перевозиться не будет!). Поэтому для любого пункта отправления стоимость

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

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

Может встретиться также случай (запасов не хватает для удовлетворения всех заявок); в этом случае можно тем или другим способом «срезать» заявки и снова получить транспортную задачу с правильным балансом.

Если нас совершенно не интересует, насколько «справедливо» удовлетворяются заявки, а важно только «подешевле развезти» имеющиеся запасы (все равно, куда), то можно ввести в рассмотрение фиктивный пункт отправления условно приписав ему недостающий запас, равный Подробнее на этих вопросах мы останавливаться не будем (см. [6]).