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

Запасы а_i

Заявки b_j

⇐ ПредыдущаяСтр 9 из 21Следующая ⇒

В предыдущем параграфе мы описали некоторые общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые, в силу особой своей структуры, допускают решение более простыми методами. Из них мы остановимся только на одной — так называемой «транспортной задаче» (ТЗ). Она ставится следующим образом: имеются т пунктов отправления (ПО) A₁, А₂., ..., A_n, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a₁, a₂, ..., a_m единиц. Имеются п пунктов назначения (ПН) В₁, В₂,..., В_n, подавших заявки соответственно на b₁, b₂, ..., b_n единиц груза. Сумма всех заявок равна сумме всех запасов:

(10.1)

Известны стоимости c_ij перевозки единицы груза от каждого пункта отправления A_i до каждого пункта назначения В_j (i=l, 2,..., т; j=1, 2,..., n). Все числа су, образующие прямоугольную таблицу (матрицу), заданы:

(10.2)

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

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

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

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

(10.3)

которую мы будем коротко обозначать (х_ij). Совокупность чисел (х_ij) (10.3) мы будем называть «планом перевозок», а сами величины х_ij — «перевозками». Эти неотрицательные переменные должны удовлетворять следующим условиям.

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

(10.4)

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

(10.5)

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

(10.6)

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

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

Прежде всего, замечаем, что условия-равенства (10.4), (10.5) не являются линейно независимыми, так как их правые части связаны условием (10.1). Число линейно независимых среди уравнений (10.4), (10.5) равно не m + n (числу уравнений), а т + п — 1. Общее число переменных x_ij в нашей задаче равно т • п; как бы ни разрешать уравнения (10.4), (10.5), число базисных переменных будет равно т + п — 1, а число свободных переменных

k = тп – (т + п - 1) = (т - 1) (n - 1).

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

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

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

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

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

Таблица 10.1

А₁ После этого в нем остается еще 30 - 18 =12 единиц груза; отдадим их пункту В₂. Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта A₂ и т. д. Рассуждая точно таким же образом, заполним до конца перевозками x_i_j транспортную таблицу (таблица 10.2). Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения; значит, все в порядке — все заявки удовлетворены, все запасы израсходованы (сумма запасов равнасумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы).

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

Таблица 10.2

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

Теперь посмотрим, чего мы добились, сколько сэкономили? Общая стоимость плана, показанного в таблице 10.2, равна L₁ = 18 • 13 + 12 • 7 + 15 • 8+33 • 12 + +9 • 10+11-8+4-10+26-15 =1442;

Таблица 10.3

ПН ПО	В₁	В₂	В₃	В₄	В₅	Запасы а_i
А₁	18 ¹³	12 ⁷	¹⁴	⁷	⁵
А₂	¹¹	15 ⁸	22 ¹²	11 ⁶	⁸
А₃	⁶	¹⁰	20 ¹⁰	⁸	¹¹
А₄	¹⁴	⁸	¹⁰	4 ¹⁰	26 ¹⁵
Заявки b_j

Общая стоимость плана, показанного в таблице 10.3, равна L₂ = 18∙ 13 +12.7 +15∙ 8 + 22∙ 12 +11∙ 6 +20∙ 10+ 4∙ 10 + 26∙ 15 = 1398.

Таким образом, нам удалось уменьшить стоимость перевозок на 1442 — 1398 = 44 единицы. Это, впрочем, можно было предсказать и не подсчитывая полную стоимость плана. Действительно, алгебраическая сумма стоимостей, стоящих в вершинах цикла, со знаком плюс, если перевозки в этой вершине увеличиваются, и со знаком минус — если уменьшаются (так называемая «цена цикла»), в данном случае равна: 6 - 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.

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

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

Таблица 10.4

ПН ПО	B₁	B₂	B₃	B₄	B₅	Запасы а_i
A₁		12^-			+
A₂		15₊		-
A₃
A₄				4⁺	^-26
Заявки b_j

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

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

(10.7)

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

(10.8)

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒