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

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

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

3. Проверяется условие оптимальности плана Ui+Vj£Cij для пустых клеток.

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

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. Для получения невырожденного плана вводим нулевую перевозку таким образом, чтобы не получилось цикла. Помещаем ее в клетку А3В4 (см. Табл.5.3)

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

U4+V2=7; U4+V5=12;

U2+V3=11; U3+V4=3;

U4+V3=13; U3+V5=3;

U2+V1=2; U1+V4=1.

 

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

Из 3-го уравнения V5 = 12 , подставляя V5 в 4-е уравнение, находим U3=-9 и, далее, из 5- го и 6-го уравнения U2=-2 и V1=4. Наконец, из 7-го уравнения получаем V4=12, а из 8-го U1=-11. Найденные значения потенциалов указаны в столбце Ui и строке Vj табл.5. 2.

Проверяем условие оптимальности Ui+Vj£Cij

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

 

U1+V2=-11+4=-7£11; U1+V5=-11+12=1£4;

U2+V2=-2+7=5£8; U2+V5=-2+12=10£12;

U2+V4=-2+12=10>7; U3+V1=-9+4=-5£9;

U3+V2=-9+7=-2£6; U3+V3=-9+13=4£4;

U4+V1=0+4=4>3; U4+V4=0+12=12>10.

 

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

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

 

Цикл: А2В4, А3В4, А3В5, А4В5, А4В3, А2В3, А2В4.

 

Метим вершины цикла поочередно знаками «+» и «-», начиная с клетки А2В4 (табл. 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  
Потребности

 

А2В4, А3В4, А3В5, А4В5, А4В3, А2В3, А2В4.

+ - + - + - +

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

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

Следовательно, нулевую перевозку из клетки А3В4 надо переместить в клетку А2В4, при этом клетка А3В4 станет пустой. Получим новый опорный план (см. Табл.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  
Потребности

 

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

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

 

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

А4В1, А2В1, А2В3, А4В3, А4В1.

+ - + - +

Из минусовых клеток находим q=min(50, 200)=50 и делаем перераспределение в цикле. В минусовых клетках вычитаем по 50 единиц, в плюсовых клетках увеличиваем на 50 единиц груза. В результате пересчета клетка А4В1 будет иметь 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 потенциал V1 и проведем связанные с этим изменения других потенциалов. Получим:

V1=3, U4=0, V2=7, V5=12, U3=-9, U2=-1, V3=12, V4=8, U1=-7

Проверяя условие оптимальности Ui+Vj£Cijдля свободных клеток, замечаем, что в клетке А1В5 условие оптимальности нарушено. Сумма потенциалов в этой клетке больше на единицу стоимости перевозки единицы груза, метим клетку А1В5 знаком плюс и строим цикл.

Вершины цикла: А1В5, А4В5, А4В1, А2В1, А2В4, А1В4, А1В5

+ - + - + - +

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

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

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

U4 + V1 = 0 +3 = 3 ; U4 +V2 = 0 +7 = 7 ;

U2 + V1 = 3 -1 = 2 ; V3 +U2 = 12 - 1 = 11 ;

V4 + U2 = 8 - 1 = 7 ; V4 + U1 = 8 - 7 = 1 ;

V5 + U3 = 11 - 8 = 3; V5 + U1 = 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  
Потребности

 

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

V1 + U 1 = 3 - 7 = - 4 < 11; U1 + V2 = 7 - 7 = 0 < 8 ;

V3 + U1 = 12 - 7 = 5 = 5 ; V2 + U2 = 7 - 1 = 6 < 8 ;

V5 +U2 =11-1=10 < 12 ; V1 + U3 = 3 - 8 = -5 < 9;

V2 + U3 = 7 - 8 = -1 < 6; V3 + U3 = 12 - 8 = 4 = 4;

V4 + U3 = 8 - 8 = 0 < 3 ; V3 + U4 = 12 + 0 = 12 < 13;

V4+ U4 = 8 + 0 = 8 < 10 ; V5 + U4 = 11 + 0 = 11 < 12.

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

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

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