Проверка оптимальности полученного распределения

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

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

Для загруженной клетки разность между соответствующими этой клетке потенциалами должна быть равна указанному в ней расстоянию, т.е.

Vj - Ui= Lij

Остальные потенциалы определяют по загруженным клеткам, исходя из следующих зависимостей:

Для столбцов Ui = Vj - Lij

Для строк Vj = Ui + Lij

для определения всех потенциалов строк в матрице необходимо соблюдение правила:

N = m + n - 1

где N - число загруженных клеток.

В данном случае правило выполняется: 9 = 5 + 5 - 1

9 = 9

U3=0

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

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

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

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

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

V2=U1 + L12=6+12=18;

U4=V2 –L42 =18 – 11=7;

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

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

Полученные значения потенциалов заносим в таблицу 3.1

Таблица 3.1

После определения потенциалов рассматриваем все незагруженные клетки и среди них отыскивают такие, для которых разность между соответствующим им потенциалам будет больше расстояния, указанного в этой клетке, т.е.:

Vj – Ui > Lij

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

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

V1 – U4=15-8 = 7 < 23;

V2 – U2=18-2 = 16 ˃ 10;

V2 – U3=18-0 = 18 > 14;

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

V3 – U4=13-7 = 6 < 14;

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

V4 – U4=16-7 = 9 < 18;

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

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

V5 – U4=19-7 = 12 < 20;

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

Dij = Vj - Ui - Lij

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

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

D22 =V2 –U2 –L22 =18-2-10=6;