Улучшение полученного распределения

Определение потенциалов

В данном случае правило не выполняется:

Т.к. N < m + n – 1, то искусственно загружаем недостающее количество клеток матрицы, и указываем количество груза равное 0, и в последующих расчетах оперируем этой клеткой как загруженной. Наличие клетки с нулевой загрузкой не повлияет на сбалансированность матрицы с точки зрения равенства поставляемого и потребляемого груза. Нулевую загрузку следует ставить в клетку, лежащую на пересечении строки и столбца, не имеющих потенциалов, со стрелкой или столбцом, для которых потенциалы уже определены. Искусственно загружаем клетку К2Д3

Для одного из столбцов (поставщиков) принимаем потенциал Ui = 0; приравниваем к нулю потенциал третьего столбца U3 = 0, т.к. в нем имеется загруженная клетка с наибольшим расстоянием.

U 3=0

V1 =U3 + L31 = 0 + 15 = 15;

V4=U3 + L34 =0+16 = 16;

U2=V4 – L24=16–14 = 2;

V2 = U2 + L22 =2+10 = 12;

U4=V2 –L42 =12 – 11 = 1;

V3 =U2 + L23 =2+11 = 13;

U1=V3 –L13 =13 – 7 = 6;

V5 = U3 + L35 =0+19 = 19;

Uф = V5 – Lф5 = 19–0 = 19;

После определения потенциалов рассматриваем все незагруженные клетки и проверяем на условие:

Vj – Ui >Lij

V1 – U1=15-6 = 9 < 80;

V1 – U2= 15-2 = 13 > 12;

V1 – U4=15-1 = 14 < 23;

V2 – U1=12-6 = 6 < 12;

V2 – U3=12-0 = 12 < 14;

V3 – U3=13-0 = 13 < 19;

V3 – U4=13-1 = 12 < 14;

V4 – U1=16-6 = 10 > 23;

V4 – U4=16-1 = 15 < 18;

V5 – U1=19-6 = 13 < 17;

V5 – U2=19-2 = 17 < 20;

V5 – U4=19-1 =18 < 20;

Для каждой такой клетки определяют число

Dij = Vj - Ui - Lij

Наличие Dij свидетельствует, что принятое нами в табл. 4.2 распределение не является оптимальным и его можно улучшить, то есть найти оптимальный вариант доставки грузов.

D21 =V1 –U2 –L24 =15-2-12=1;

Улучшения поставок приводят путем нахождения наибольшего значения Dij. В нашем случае число Dij присуще только одной клетке – К2Д1.

Начиная с этой клетки, строим «контур». Клеткам в вершинах контура попеременно присваивают знаки «+» и «-», начиная с выбранной клетки, которой присваивается знак «-» (см. таблицу 5.1).

Таблица 5.1