5.2. Алгоритм решения транспортной задачи методом потенциалов

1. Одним из известных методов получаем первоначальный опорный план.

2. Строим систему потенциалов. Потенциалы поставщиков U_i и потребителей V_j есть некоторые числа, определяющиеся из условия U_i+V_j=C_ij для клеток, в которых имеются перевозки в первоначальном опорном плане. Для невырожденного опорного плана система потенциалов обязана заполняться до конца.

3. Проверяется условие оптимальности плана U_i+V_jC_ij для пустых клеток.

4. Если план неоптимальный, клетку с максимальной положительной разностью U_i+V_j-C_ij метим знаком «+» и считаем ее заполненной.

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

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. Метим вершины попеременно знаками «+» и «-», начиная с клетки, помеченной знаком «+».

6. Делаем перераспределение грузов в цикле. В клетках, помеченных знаком «-», находим минимальную перевозку и из этих клеток вычитаем это количество груза, а к клеткам, помеченным знаком «+», прибавляем такое же количество груза. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел х_ij считается свободной. Получаем новый опорный план, который надо проверить на оптимальность.

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

7. Процедура продолжается до тех пор, пока план не станет оптимальным.

Изложенный метод нахождения оптимального решения ТЗ называют МЕТОДОМ ПОТЕНЦИАЛОВ.

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

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

Таблица 5. 2

Исходная информация ТЗ

Поставщики	Потребители					Запасы
	B1	B2	B3	B4	B5
A1	11	8	5	1	4	150
A2	2	8	11	7	12	250
A3	9	6	4	3	3	200
A4	3	7	13	10	12	300
Потребности	200	200	100	150	250	900

РЕШЕНИЕ

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

На практике принято вычеркивать строку с полностью вывезенным запасом, столбец - с полностью удовлетворенной потребностью.

Получили вырожденный опорный план .

Количество занятых клеток равно семи, а должно быть по определению невырожденного опорного плана m+n-1=4+5-1=8. Для получения невырожденного плана вводим нулевую перевозку таким образом, чтобы не получилось цикла. Помещаем ее в клетку А₃В₄ (см. Табл.5.3)

Строим систему потенциалов. Неизвестных потенциалов 9, а число линейно - независимых уравнений для определения этих потенциалов на 1 меньше, поэтому одно неизвестное всегда оказывается свободным и ему можно придать любое числовое значение, удобнее всего нуль. Положим, U₄=0. Согласно определению, потенциалы U_i и V_j должны удовлетворять равенствам U_i + V_j=0, соответствующим базисным переменным Х_ij в данном опорном решении, в нашем примере получим следующие 8 уравнений:

U₄+V₂=7; U₄+V₅=12;

U₂+V₃=11; U₃+V₄=3;

U₄+V₃=13; U₃+V₅=3;

U₂+V₁=2; U₁+V₄=1.

Из 1-го уравнения получаем V₂=7 и из 2-го V₃=13.

Из 3-го уравнения V₅ = 12 , подставляя V₅ в 4-е уравнение, находим U₃=-9 и, далее, из 5- го и 6-го уравнения U₂=-2 и V₁=4. Наконец, из 7-го уравнения получаем V₄=12, а из 8-го U₁=-11. Найденные значения потенциалов указаны в столбце U_i и строке V_j табл.5. 2.

Проверяем условие оптимальности U_i+V_jC_ij

для пустых клеток:

U₁+V₂=-11+4=-711; U₁+V₅=-11+12=14;

U₂+V₂=-2+7=58; U₂+V₅=-2+12=1012;

U₂+V₄=-2+12=10>7; U₃+V₁=-9+4=-59;

U₃+V₂=-9+7=-26; U₃+V₃=-9+13=44;

U₄+V₁=0+4=4>3; U₄+V₄=0+12=12>10.

План неоптимальный, так как в клетках А₄В₁, А₄В₄, А₂В₄ нарушено условие оптимальности, сумма потенциалов соответственно на одну, две и три единицы больше стоимости единицы перевозки груза.

Для улучшения плана производим пересчет по циклу, который строим, начиная с максимальной разности клетки А₂В₄.

Цикл: А₂В₄, А₃В₄, А₃В₅, А₄В₅, А₄В₃, А₂В₃, А₂В₄.

Метим вершины цикла поочередно знаками «+» и «-», начиная с клетки А₂В₄ (табл. 5.3).

Таблица 5. 3

Первый опорный план

Постав-щики	Потребители						Запа- сы
	Ui	Bi	B2	B3	B4	B5
A1	U1=-11	11	8	5	1 150	4	150
A2	U2=-2	2 200	8	11 50	7 3 +	12	250
A3	U3=-9	9	6	4	3 0	3 200	200
A4	U4=0	3 1	7 200	13 50	10 2	12 50	300
	Vj	V1=4	V2=7	V3=13	V4=12	V5=12
Потребности		200	200	100	150	250	900

А₂В₄, А₃В₄, А₃В₅, А₄В₅, А₄В₃, А₂В₃, А₂В₄.

+ - + - + - +

Количество груза, которое надо перераспределить в цикле, находим как наименьшее из чисел в минусовых клетках цикла

=min (0, 50, 50) = 0

Следовательно, нулевую перевозку из клетки А₃В₄ надо переместить в клетку А₂В₄, при этом клетка А₃В₄ станет пустой. Получим новый опорный план (см. Табл.5.4).

Таблица 5. 4

Второй опорный план

Постав-щики	Потребители						Запа- сы
	Ui	Bi	B2	B3	B4	B5
A1	U1=-8	11	8	5	1 150	4	150
A2	U2=-2	2 200	8	11 50	7 0	12	250
A3	U3=-9	9	6	4	3	3 200	200
A4	U4=0	3 1	7 200	13 50	10	12 50	300
	Vj	V1=4	V2=7	V3=13	V4=9	V5=12
Потребности		200	200	100	150	250	900

Нужно проверить этот план на оптимальность, для этого следует построить систему потенциалов. Систему потенциалов удобнее получить, подправляя старую, чем строить заново. Чтобы сумма потенциалов в клетке А₂В₄ стала равна стоимости, надо уменьшить на три единицы либо потенциал V₄, либо потенциал U₂. Для уменьшения выбирается тот потенциал, который ведет к изменению меньшего числа других потенциалов. Делаем V₄ = 9, при этом изменится лишь потенциал U₁=- 8. Остальные потенциалы останутся прежними.

План не является оптимальным, так как в клетке А₄В₁ сумма потенциалов превосходит стоимость перевозки единицы груза: U_i+V_j=0+4=4>3 (см. табл. 5.4).

Метим знаком «+» эту клетку и строим цикл с вершинами

А₄В₁, А₂В₁, А₂В₃, А₄В₃, А₄В₁.

+ - + - +

Из минусовых клеток находим =min(50, 200)=50 и делаем перераспределение в цикле. В минусовых клетках вычитаем по 50 единиц, в плюсовых клетках увеличиваем на 50 единиц груза. В результате пересчета клетка А₄В₁ будет иметь 50 ед. груза. Получим новый опорный план (см. табл. 5.5)

Таблица 5. 5

Третий опорный план

Постав-щики	Потребители						Запа- сы
	Ui	Bi	B2	B3	B4	B5
A1	U1=-7	^11	8	5	1 150	4	150
A2	U2=-1	2 150	8	11 100	7 0	12	250
A3	U3=-9	9	6	4	3	3 200	200
A4	U4=0	3 1 50	7 200	13	10	12 50	300
	Vj	V1=3	V2=7	V3=12	V4=8	V5=12
Потребности		200	200	100	150	250	900

Проверим новый план на оптимальность. Для этого подправим систему потенциалов. Уменьшим на 1 потенциал V₁ и проведем связанные с этим изменения других потенциалов. Получим:

V₁=3, U₄=0, V₂=7, V₅=12, U₃=-9, U₂=-1, V₃=12, V₄=8, U₁=-7

Проверяя условие оптимальности U_i+V_jC_ij для свободных клеток, замечаем, что в клетке А₁В₅ условие оптимальности нарушено. Сумма потенциалов в этой клетке больше на единицу стоимости перевозки единицы груза, метим клетку А₁В₅ знаком плюс и строим цикл.

Вершины цикла: А₁В₅, А₄В₅, А₄В₁, А₂В₁, А₂В₄, А₁В₄, А₁В₅

+ - + - + - +

Находим  = min (50, 150, 150)=50. В минусовых клетках вычитаем по 50 единиц груза, в плюсовых клетках увеличиваем на 50 единиц. Получаем новый опорный план, в котором клетка А₄В₅ становится свободной:

Проверяем на оптимальность полученный опорный план, подправляя систему потенциалов. Уменьшим потенциал V₅ на 1, причем V₅=11, что вызовет изменение только потенциала U₃ остальные останутся без изменения (см. табл. 5. 6)

Для занятых клеток условие оптимальности выполняется:

U₄ + V₁ = 0 +3 = 3 ; U₄ +V₂ = 0 +7 = 7 ;

U₂ + V₁ = 3 -1 = 2 ; V₃ +U₂ = 12 - 1 = 11 ;

V₄ + U₂ = 8 - 1 = 7 ; V₄ + U₁ = 8 - 7 = 1 ;

V₅ + U₃ = 11 - 8 = 3; V₅ + U₁ = 11 - 7 = 4.

Таблица 5. 6

Оптимальный план поставок

Постав-щики	Потребители						Запа- сы
	Ui	Bi	B2	B3	B4	B5
A1	U1=-7	11	8	5	1 100	4 50	150
A2	U2=-1	2 100	8	11 100	7 50	12	250
A3	U3=-8	9	6	4	3	3 200	200
A4	U4=0	3 100	7 200	13	10	12	300
	Vj	V1=3	V2=7	V3=12	V4=8	V5=11
Потребности		200	200	100	150	250	900

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

V₁ + U ₁ = 3 - 7 = - 4 < 11; U₁ + V₂ = 7 - 7 = 0 < 8 ;

V₃ + U₁ = 12 - 7 = 5 = 5 ; V₂ + U₂ = 7 - 1 = 6 < 8 ;

V₅ +U₂ =11-1=10 < 12 ; V₁ + U₃ = 3 - 8 = -5 < 9;

V₂ + U₃ = 7 - 8 = -1 < 6; V₃ + U₃ = 12 - 8 = 4 = 4;

V₄ + U₃ = 8 - 8 = 0 < 3 ; V₃ + U₄ = 12 + 0 = 12 < 13;

V₄+ U₄ = 8 + 0 = 8 < 10 ; V₅ + U₄ = 11 + 0 = 11 < 12.

Условие выполняется, план оптимальный. Минимальная стоимость перевозок составляет 4250 д.ед. т.е.

S_min = 1·100 + 4·50 + 2·100 + 11·100 + 7·50 + 3·200 + 3·100+ 7·200=4250 д. ед.

Рекомендуется при переходе от одной таблицы к другой проводить контроль вычислений по формуле: .