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

Последовательность расчетов:

1. Матрица проверяется на вычеркиваемость поочередно: при просмотре матрицы по строкам и столбцам, вычеркивается клетка с поставкой, если она одна в строке или столбце (далее вычеркнутые клетки в расчет не берутся). Если матрица не вычеркивается, тогда задача носит циклический характер и данным методом не решается.

2. Строке, где есть поставка с максимальным критерием оптимальности, присваиваем потенциал 0. Потенциалы вычисляются по занятым клеткам (где есть поставка) столбцов и строк по формулам. Потенциалы — это системы чисел (они могут быть отрицательными).

3. По свободным клеткам проверяется условия: C_ij≥V_{j –} U_i,, где V_j - потенциал столбца, U_i - потенциал строки, C_ij - критерий оптимальности.

4. Отмечаем клетку с наибольшим нарушением.

5. Строится замкнутый контур по ходу шахматной ладьи с вершинами: одна в свободной клетке, все остальные в занятых.

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

7. Таким образом, получили новый оптимальный план, который требует решения данным методом начиная с п.2, до тех пор, пока условие оптимальности не будет выполнено.

Грузом для решения данным методом будет уголь каменный.

В матрице нет нарушений, если соблюдаются следующие условия:

1) V_j - U_i =C_ij - для занятых клеток

2) V_j - U_i ≤ C_ij - для свободных клеток

Таблица 1.2.1 – Уголь каменный

Поставщики и их мощность	Потребитель и их спрос	Потенциал строки ui = vj - сij
Г	Е	Д	М	Р	Н
К
А
Б
Л
О
В
Потенциал столбца vj = ui + сij

КГ= 10-0=10<15

КЕ=14-0<28

КР=29<43

КН=18=18

АГ=10-7<22

АД=17-7<29

АН=18-7<25

БГ=10-13<14

БЕ=14-13<13

БД=17-13<21

БР=29-13<28

БН=18-13<25

ЛГ=10-20<31

ЛЕ=14-20<6

ЛД=17-20<30

ЛМ=28-20<13

ЛН=18-20<23

ОГ=10-12<21

ОЕ=14-12<24

ОД=17-12<23

ОР=29-12<22

ВЕ=14-2<19

ВМ=28-2=26>2(+4)

ВР=29-2<35

ВН=18-2=16>14(+2)

Таблица 1.2. 2– Уголь каменный

Поставщики и их мощность	Потребитель и их спрос	Потенциал строки ui = vj - сij
Г	Е	Д	М	Р	Н
К								-3
А
Б
Л
О
В								-1
Потенциал столбца vj = ui + сij

КГ= 7+3<15

КЕ=7+3<28

КМ=21+3<28

КР=22+3<43

КН=11+3<18

АГ=7+0<22

АД=14<29

АН=11<25

БГ=7+6<14

БЕ=7+6=13

БД=14-6<21

БР=22-6<28

БН=11-6<25

ЛГ=7-13<31

ЛЕ=7-13<6

ЛД=14-13<30

ЛМ=21-13<13

ЛН=11-13<23

ОГ=7-5<21

ОЕ=7-5<24

ОД=14-5<23

ОР=22-5<22

ВЕ=7+1<19

ВР=22+1<35

ВН=11+1<14

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

Раздел 2. Организация вагонопотоков