Последовательность расчетов:
1. Матрица проверяется на вычеркиваемость поочередно: при просмотре матрицы по строкам и столбцам, вычеркивается клетка с поставкой, если она одна в строке или столбце (далее вычеркнутые клетки в расчет не берутся). Если матрица не вычеркивается, тогда задача носит циклический характер и данным методом не решается.
2. Строке, где есть поставка с максимальным критерием оптимальности, присваиваем потенциал 0. Потенциалы вычисляются по занятым клеткам (где есть поставка) столбцов и строк по формулам. Потенциалы — это системы чисел (они могут быть отрицательными).
3. По свободным клеткам проверяется условия: Cij≥Vj – Ui,, где Vj - потенциал столбца, Ui - потенциал строки, Cij - критерий оптимальности.
4. Отмечаем клетку с наибольшим нарушением.
5. Строится замкнутый контур по ходу шахматной ладьи с вершинами: одна в свободной клетке, все остальные в занятых.
6. Вершине в свободной клетке присваивается «+», далее вершины чередуются. В свободную клетку переносим минимальную поставку из отрицательной вершины. Затем эта поставка прибавляется к исходным поставкам в положительных вершинах и отнимается из поставок в отрицательных.
|
|
7. Таким образом, получили новый оптимальный план, который требует решения данным методом начиная с п.2, до тех пор, пока условие оптимальности не будет выполнено.
Грузом для решения данным методом будет уголь каменный.
В матрице нет нарушений, если соблюдаются следующие условия:
1) Vj - Ui =Cij - для занятых клеток
2) Vj - Ui ≤ Cij - для свободных клеток
Таблица 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. Организация вагонопотоков