Решение транспортной задачи методом потенциала
Одну из матриц, формата 6х6, оптимизируем методом потенциалов (Уголь каменный).
Вначале матрица проверяется на вычеркиваемость:
Поставка вычеркивается, если она является единственной в строке или столбце.
Вычеркнутые поставки не рассматриваются
Если матрица вычеркиваемая, то она является разрешимой.
Потенциалом
называется система чисел: 
и 
.
Решение задачи сводится к отысканию такой системы потенциалов, при которой соблюдаются следующие требования:
(разность потенциалов столбца и строки
должна быть 
критерию
оптимальности)Частный случай для занятых клеток
Невыполнение 1-го условия, является признаком неоптимальности плана.
Используя 2-ое условие через занятые клетки, определяем потенциалы строк и столбцов, для этого в строке с max критерием оптимальности, для занятой клетки, присваивается нулевой потенциал.
Проводится проверка по всем незанятым клеткам, отмечается клетка с наибольшим отклонением.
Улучшение производится путём переноса наибольшей поставки, среди отрицательных вершин цепи, в положительные. Цепь строится по принципу хода шахматной ладьи. По всем занятым клеткам и одной свободной, которая с наибольшим отклонением. В пустой клетке ставится «+», а потом чередуется «+», «-», «+», «-».
Затем наименьшая поставка в отрицательной вершине переносится в свободную клетку, вычитается из отрицательных поставок и прибавляется к положительной, получается новое распределение
-
Поставщики и их грузы
Потребители и их спрос
Потенциал столбца
А
Ж
Г
Р
Н
Д
1151
450
670
700
1300
340
Е
690
670
20
11
М
375
375
18
Б
846
846
31
О
643
643
15
К
785
700
85
14
З
1272
305
450
282
235
0
Потенциал строки
35
5
26
27
23
27
ЕА: 35-11=21>21 – нет БН:23-31=-8<36 – да ЗР: 27-0=27<28 - да
ЕЖ:5-11=-6<19 – да БД: 27-31=-4<20 – да
ЕР: 27-11=16<23 – да ОА: 35-15=20<48 – да
ЕН: 23-11=12<30 – да ОЖ: 5-15=-10<29 – да
МА: 35-18=17<46 – да ОГ: 26-15=11<42 –да
МЖ: 5-18=-13<28 – да ОР: 27-15=12<29 – да
МГ: 26-18=8<39 – да ОД: 27-15=12<25 – да
МР: 27-18=9<26 – да КА: 35-14=21<37 – да
МД: 27-18=9<22 – да КЖ: 5-14=-9<11 - да
БЖ: 5-31=-26<26 – да КГ: 26-14=12<30 – да
БГ: 26-31=-5<20 – да КН: 23-14=9<12 – да
БР: 27-31=-4<30 – да ЗГ: 26-0=26<29 - да
-
Поставщики и их грузы
Потребители и их спрос
Потенциал строки
А
Ж
Г
Р
Н
Д
1151
450
670
700
1300
340
Е
690
20
670
14
М
375
375
18
Б
846
846
31
О
643
643
15
К
785
85
14
З
1272
285
450
282
255
0
Потенциал столбца
35
5
29
27
23
27
ЗР: 27-0=27<28 - да БН:23-31= -8<36 – да
ЕЖ:5-14= -9<19 – да БД: 27-31= -4<20 – да
ЕР: 27-14=13<23 – да ОА: 35-15=20<48 – да
ЕН: 23-14=9<30 – да ОЖ: 5-15= -10<29 – да
МА: 35-18=17<46 – да ОГ: 29-15=14<42 –да
МЖ: 5-18= -13<28 – да ОР: 27-15=12<29 – да
МГ: 29-18=11<39 – да ОД: 27-15=12<25 – да
МР: 27-18=9<26 – да КА: 35-14=21<37 – да
МД: 27-18=9<22 – да КЖ: 5-14= -9<11 - да
БЖ: 5-31= -26<26 – да КГ: 29-14=15<30 – да
БГ: 29-31= -2<20 – да КН: 23-14=9<12 – да
БР: 23-31= -4<30 – да ЗГ: 29-0=29=29 - да