Решение транспортной задачи методом потенциалов

1.3. Распределительный  метод достижения оптимального  плана

 

Теперь попробуем улучшить план, составленный способом “северо-западного  угла”. Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушить баланса, перенесём те же 18 едниц из клетки (2,3) в клетку (1,3). Получим новый план. Подсчитав стоимость опорного плана (она равна 1039) и стоимость нового плана (она равна 913) нетрудно убедиться, что стоимость нового плана на 126 единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана:

Таблица №5

ПН ПО	В1	В2	В3	В4	В5	Запасы аi
А1	10	8           27	5           21	6	9	48
А2	6           18	7	8           12	6	5	30
А3	8	7	10             9	8           12	7             6	27
А4	7	5	4	6	8           20	20
Заявки  bj	18	27	42	12	26	125

 

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

Существует несколько  вариантов цикла:

1.)

2.)

3.)

Нетрудно убедиться, что  каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком “-“ те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-то количество единиц груза по означенному циклу — это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах, уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце — заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными, план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшаться. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком “+”, а в отрицательных – со знаком “-“. Обозначим цену цикла через λ. При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину λ. При перемещении по нему k единиц груза стоимость перевозок увеличиться на k λ . Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину k λ . Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

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

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

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

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

2. Решение транспортной  задачи методом потенциалов.

2.1 Транспортная  задача с правильным балансом (закрытая).

 

Этот метод позволяет  автоматически выделять циклы с  отрицательной ценой и определять их цены.

Пусть имеется транспортная задача с балансовыми условиями:

                             

 

причём

— то есть закрытая задача.

Стоимость перевозки  единицы груза из A_i в B_j равна с_i,j; таблица стоимостей задана. Требуется найти план перевозок (x_i,j), который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим себе, что каждый из пунктов отправления A_i вносит за перевозку единицы груза (всё равно куда) какую-то сумму U_i; в свою очередь, каждый из пунктов назначения B_j также вносит за перевозку груза (куда угодно) сумму V_j . Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим U_i + V_j = с_i,j (i=1..m; j=1..n) и будем называть величину с_i,j “псевдостоимостью” перевозки единицы груза из A_i в B_j. Заметим, что платежи U_i и V_j не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (U_i и V_j) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали  платежи (U_i и V_j) и псевдостоимости c_i,j с истинными стоимостями перевозок с_i,j. Теперь мы установим между ними связь. Предположим, что план (x_i,j) невырожденный (число базисных клеток в таблице перевозок равно (m + n -1). Для всех этих клеток x_i,j > 0. Определим платежи (U_i и V_j) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:

с_i,j = U_i +V_j = с_i,j , при x_i,j > 0.

Что касается свободных  клеток (где x_i,j = 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Оказывается, соотношение  между псевдостоимостями и стоимостями  в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: если для всех базисных клеток плана (x_i,j > 0)

с_i,j= U_i + V_j = с_i,j ,

а для всех свободных  клеток (x_i,j =0)

с_i,j= U_i + V_j < с_i,j,

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

с_i,j = с_i,j (для всех базисных клеток) (1)

с_i,j < с_i,j (для всех свободных клеток) (2)

называется потенциальным планом, а соответствующие ему платежи (U_i и V_j) — потенциалами пунктов A_i и B_j (i=1,...,m; j=1,...,n). Пользуясь этой терминологией, вышеупомянутую теорему можно сформулировать так: всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно — построить потенциальный план. Оказывается, его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получится сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план, следует одновременно менять систему платежей так, чтобы они приближались к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (U_i и V_j), удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: D_i,j= с_i,j - c_i,j.

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

Процедура построения потенциального (оптимального) плана состоит в следующем.

В качестве первого приближения  к оптимальному плану берётся  любой допустимый план (например, построенный методом северо-западного угла). В этом плане m + n - 1 базисных клеток, где m — число строк, n — число столбцов транспортной таблицы. Для этого плана можно определить платежи (U_i и V_j), так, чтобы в каждой базисной клетке выполнялось условие:

U_i + V_j = с_i,j (3)

Уравнений (3) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (3) можно найти остальные платежи U_i и V_j, а по ним вычислить псевдостоимости: c_i,j=U_i + V_j для каждой свободной клетки.

Таблица №6

ПН ПО	В1	В2	В3	В4	В5	Ui
А1	10           18	8           27	5             3	6         c=3	9         c=2	0
А2	6       c=13	7       c=11	8           30	6         c=6	5         c=5	3
А3	8       c=15	7       c=13	10             9	8           12	7             6	5
А4	7       c=16	5       c=14	4       c=11	6         c=9	8           20	6
Vj	10	8	5	3	2

 

Если оказалось, что  все эти псевдостоимости не превосходят  стоимостей: c_i,j ≤ с_i,j , то план потенциален и значит оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.

В таблице №6 мы получили в восьми клетках c_i,j ≤ с_i,j, теперь можно построить цикл в любой из этих восьми клеток. Выгоднее всего строить цикл в той клетке, в которой разность c_i,j-с_i,j максимальна. В нашем случае в двух клетках разность одинакова (равна 9), поэтому для построения выберем, например, клектку (A4, B1):

Таблица №7

ПН ПО	В1	В2	В3	В4	В5	Ui
А1	10 -           18	8           27	5 +             3	6	9	0
А2	6	7	8           30	6	5	3
А3	8	7	10 -             9	8           12	7 +             6	5
А4	7 +           û	5	4	6	8 -           20	6
Vj	10	8	5	3	2

 

Теперь будем перемещать по циклу число 9, так как оно  является минимальным из чисел, стоящих в клетках, помеченных знаком “-“ . При перемещении мы будем вычитать 9 из клеток со знаком “-“ и прибавлять к клеткам со знаком “+”.

После этого необходимо подсчитать потенциалы U_i и V_j и цикл расчетов повторяется.

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

1. Взять любой опорный план перевозок, в котором отмечены m + n - 1 базисных клеток (остальные клетки свободные).

2. Определить для этого плана платежи (U_i и V_j) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.

3. Подсчитать псевдостоимости c_i,j = U_i + V_j для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

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

Так, в нашем примере  после 8 циклов расчетов получим оптимальный  план вида:

Таблица №8

ПН ПО	В1	В2	В3	В4	В5	Ui
А1	10         c=7	8         c=6	5           36	6           12	9         c=6	0
А2	6           18	7        c=5	8         c=4	6         c=5	5           12	-1
А3	8         c=8	7           13	10         c=6	8         c=7	7           14	1
А4	7         c=6	5           14	4            6	6         c=5	8         c=5	-1
Vj	7	6	5	6	6