Решение транспортной задачи методом потенциала

Одну из матриц, формата 6х6, оптимизируем методом потенциалов (Уголь каменный).

Вначале матрица проверяется на вычеркиваемость:

1. Поставка вычеркивается, если она является единственной в строке или столбце.

2. Вычеркнутые поставки не рассматриваются

Если матрица вычеркиваемая, то она является разрешимой.

Потенциалом называется система чисел: и .

Решение задачи сводится к отысканию такой системы потенциалов, при которой соблюдаются следующие требования:

1. (разность потенциалов столбца и строки должна быть критерию оптимальности)

2. Частный случай для занятых клеток

Невыполнение 1-го условия, является признаком неоптимальности плана.

Используя 2-ое условие через занятые клетки, определяем потенциалы строк и столбцов, для этого в строке с max критерием оптимальности, для занятой клетки, присваивается нулевой потенциал.

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

Улучшение производится путём переноса наибольшей поставки, среди отрицательных вершин цепи, в положительные. Цепь строится по принципу хода шахматной ладьи. По всем занятым клеткам и одной свободной, которая с наибольшим отклонением. В пустой клетке ставится «+», а потом чередуется «+», «-», «+», «-».

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

Поставщики и их грузы	Потребители и их спрос	Потенциал столбца
А	Ж	Г	Р	Н	Д
Е
М
Б
О
К
З
Потенциал строки

ЕА: 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 - да

Поставщики и их грузы	Потребители и их спрос	Потенциал строки
А	Ж	Г	Р	Н	Д
Е
М
Б
О
К
З
Потенциал столбца

ЗР: 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 - да