2.1.11. Метод потенциалов.

Метод потенциалов является одним из наиболее распространенных методов нахождения оптимального плана поставок. Суть метода заключается в следующем: выбирается начальный опорный план задачи, например, по правилу "Северо-западного утла". Он имеет не более, чем m+n-1 ненулевых компонент. Введем новые переменные V и U. которые назовем потенциалами складов и пунктов потребления, а их суммы

C1ij=Vi+Uj

псевдостоимостями перевозок.

Двойственная задача к данной транспортной задаче имеет вид:

Мах(a_j*u_j+ Bi*Vi)

при ограничениях:

Vi+Uj=Cij

Пусть вектор У=( V₁… V_m, U₁... U_n) является допустимым планом двойственной задачи. Из второй теоремы двойственности следует, если X и У оптимальные планы прямой и двойственной задач, то

Xij*(Cij-Vi-Uj)=0,

для всех i=1… m, j=1... n.

Тогда либо Xij=0, либо (Vi+Uj=Cij), либо оба сомножителя одновременно равны нулю. Этот вывод можно использовать как признак оптимальности, а именно: если Vi +Uj=Cij, то X оптимальный план транспортной задачи.

Эта модификация симплекс - метода называется методом потенциалов. Для определения двойственных переменных Vi и Uj имеем систему уравнений:

Vi+Uj=Cij

Для занятых клеток, т. е. для X больших либо равных нулю. В системе число уравнений меньше числа неизвестных. Если одно неизвестное Uj или Vi положить равным нулю, то остальные можно легко вычислить. Далее надо проверить соотношение:

(Cij-Vi-Uj)>=0

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

Примечания к методу потенциалов.

1. Систему потенциалов однозначно можно вычислить только для невырожденного ОП, при этом одному из потенциалов нужно придать произвольное значение (обычно u₁=0, т.к. в системе ограничений закрытой ТЗ имеется одно линейно зависимое ограничение).

2. В случае вырожденного ОП нужно ввести фиктивные перевозки с таким расчетом, чтобы из системы (21) однозначно вычислить все потенциалы.

3. Цикл всегда существует и единственен для каждой свободной клетки таблицы (для невырожденного ОП).

4. Если для какой-то свободной клетки (x_ij= 0) оптимального ОП в соотношении (22) достигается строгое равенство, то это говорит о неединственности оптимального ОП.

Вырождения в транспортной задаче. Вырождения в транспортной задаче означает, что число заполненных клеток меньше чем m+n- 1 . В этом случае нарушается правило, что для каждой свободной клетки можно построить цикл.

Для доведения количества заполненных клеток до нужного дадим поставку равную нулю в незаполненную клетку. Выбор такой клетки происходит по принципу восстановления "ступенчатости".

Что Вы должны знать:

(вопросы для самоконтроля)

1. Как формулируется транспортная задача?

2. Как составляется первый опорный план в транспортной задаче?

3. В чем сущность метода потенциалов?

4. Как с помощью метода потенциалов проверяется условие оптимальности?

5. Каков принцип построения циклов передвижения поставки?

6. Как решаются транспортные задачи с нарушением балансов между спросом и предложением?

7. Как разрешается проблема вырождения в транспортных задачах?

Пример решения транспортной задачи

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

Таблица 2.2

Поставщики	Потребители			Запас поставщиков
	1	2	3
1	С11=2	С12=3	С13=2	В1=50
2	С21=2	С22=4	С23=5	В2=70
3	С31=6	С32=5	С33=7	В3=60
Спрос потребителей	А1=60	А2=60	А3=50

Проверим систему на закрытость.

В₁+В₂+В₃=180 А₁+А₂+А₃=170

Система открытая, т. к. 180 не равно 170. Для того ,чтобы система стала закрытой необходимо ввести фиктивного потребителя, которому в качестве спроса назначается разность между суммой запасов и суммой спросов, т.е. 10. Стоимости перевозки груза для фиктивного потребителя равны 0.

Выполним первоначальное распределение поставок по правилу «северо-западного угла». Количество занятых поставками клеток (5) оказалось меньше, чем необходимо для однозначного построения цикла перемещения поставок (4+3-1)=6. Поэтому необходимо добавить 0 в клетку продолжающую ступенчатость распределения поставок.

Стоимости перевозок разместим в левом верхнем углу, а поставки в центре клеток (см. табл.3.).

Таблица 2.3

Поставщики	Потребители				Запас поставщиков
	1	2	3	4
1	2 50	3	2	0	В1=50
2	2 10	4 60	5 0	0	В2=70
3	6	5	7 70	0 10	В3=60
Спрос потребителей	А1=60	А2=60	А3=50	А4=10

Функция затрат при таком распределении равна:

F=2*50+2*10+4*60+5*0+7*50+0*10=710

Для определения оптимального распределения поставок применим метод потенциалов.

Для занятых поставками клеток и, предполагая V₁=0, сформируем соотношения, из которых определим значения потенциалов.

V₁+U_!=2 U₁=2

V₂+U_!=2 V₂=0

V₂+U₂=4 U₂=4

V₂+U₃=5 U₃=5

V₃+U₃=7 V₃=2

V₃+U₄=0 U₄=-2

Таблица 2.4

Поставщики	Потребители				Потенциалы поставщиков
	1	2	3	4
1	2 50	3 4	2 5	0 -2	V1=0
2	2 10	4 60	5 0	0 -2	V2=0
3	6 4	5 6	7 50	0 10	V3=2
Потенциалы потребителей	U1=2	U2=4	U3=5	U4=-2

В таблице 4 в правом верхнем углу свободных от поставок клеток размещены псевдостоимости, полученные из известных потенциалов С1_ij= V_i+ U_j. В качестве условия выбора свободной клетки для перемещения в нее поставки с целью улучшения плана поставок надо воспользоваться правилом : выбрать ту клетку, для которой С1_ij-C_ij>0 и если таких клеток несколько, то среди них выбрать с максимальной разницей.

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

Цикл для клетки №1 (3,2) выглядит следующим образом:

2,2(60)№4 2,3(0)№3

3,2( )№1 3,3(50)№2

Рис. 2.2.

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

Новое распределение выглядит следующим образом (см. табл. 5):

Таблица 2.5

Поставщики	Потребители				Потенциалы поставщиков
	1	2	3	4
1	2 50	3 4	2 5	0 -1	V1=0
2	2 10	4 10	5 50	0 -1	V2=0
3	6 3	5 50	7 6	0 10	V3=1
Потенциалы потребителей	U1=2	U2=4	U3=5	U4=-1

F=2*50+2*10+4*10+5*50+5*50+0*10=660

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

Для дальнейшей переброски поставки выберем в качестве клетки № 1 (1,3).

1,1(50)№2 1,3( )№1

2,1(10)№3 2,3(50)№4

Таблица 2.6

Поставщики	Потребители				Потенциалы поставщиков
	1	2	3	4
1	2 0	3 4	2 50	0 -1	V1=0
2	2 60	4 10	5 2	0 -1	V2=0
3	6 3	5 50	7 3	0 10	V3=1
Потенциалы потребителей	U1=2	U2=4	U3=2	U4=-1

F=2*0+2*50+2*60+4*10+5*50+0*10=510

Очевидно, что величина «0» поставки, перемещенная в клетку (1,2) из клетки (1,1) не изменит значения целевой функции. Предлагаем читателю убедиться в том ,что значение целевой функции равное 510 является минимальным, а план поставок оптимальный.

Примеры для закрепления:

Найти оптимальное распределение поставок при известных запасах поставщиков, спросе потребителей и стоимости перевозки единицы груза от каждого поставщика каждому потребителю ( см. табл. 7 и 8).

Таблица 2.7.

Поставщики	Потребители			Запас поставщиков
	1	2	3
1	С11=3	С12=5	С13=1	В1=30
2	С21=4	С22=4	С23=2	В2=40
3	С31=2	С32=5	С33=1	В3=30
Спрос потребителей	А1=20	А2=40	А3=50

Таблица 2.8.

Поставщики	Потребители			Запас поставщиков
	1	2	3
1	С11=6	С12=3	С13=7	В1=80
2	С21=6	С22=5	С23=6	В2=70
3	С31=5	С32=4	С33=7	В3=60
Спрос потребителей	А1=100	А2=50	А3=60