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

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. Процедура продолжается до тех пор, пока план не станет оптимальным.

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

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

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

Таблица 5. 2

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

Поставщики	Потребители	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
A4
Потребности

РЕШЕНИЕ

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

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

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

Количество занятых клеток равно семи, а должно быть по определению невырожденного опорного плана 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				1 150
A2	U2=-2	200			3 +
A3	U3=-9				0	3
A4	U4=0				2
	Vj	V1=4	V2=7	V3=13	V4=12	V5=12
Потребности

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

+ - + - + - +

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

q=min (0, 50, 50) = 0

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

Таблица 5. 4

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

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

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

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

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

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

+ - + - +

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

Таблица 5. 5

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

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

Проверим новый план на оптимальность. Для этого подправим систему потенциалов. Уменьшим на 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для свободных клеток, замечаем, что в клетке А₁В₅ условие оптимальности нарушено. Сумма потенциалов в этой клетке больше на единицу стоимости перевозки единицы груза, метим клетку А₁В₅ знаком плюс и строим цикл.

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

+ - + - + - +

Находим q = 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				100	4 50
A2	U2=-1			100
A3	U3=-8					3
A4	U4=0		7
	Vj	V1=3	V2=7	V3=12	V4=8	V5=11
Потребности

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

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 д. ед.

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