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

 

Найденное исходное опорное решение проверяется на опти­мальность методом потенциалов по следующему критерию: ес­ли опорное решение транспортной задачи является оптималь­ным, то ему соответствует система т + п действительных чи­сел u_i и v_j, удовлетворяющих условиям u_i + v_j = c_ij для заня­тых клеток и u_i + v_j - с_ij ≤ 0 для свободных клеток.

Числа u_i и v_j называют потенциалами. В распределитель­ную таблицу добавляют строку v_j и столбец u_i.

Потенциалы u_i и v_j находят из равенства u_i + v_j = c_ij, спра­ведливого для занятых клеток. Одному из потенциалов дает­ся произвольное значение, например и₁ = 0, тогда остальные потенциалы определяются однозначно. Так, если известен по­тенциал u_i, то v_j = с_ij — u_i; если известен потенциал v_j, то u_i = c_ij – v_j.

Обозначим Δ_ij = u_i + v_j - c_ij. Эту оценку называют оценкой свободных клеток. Если Δ_ij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δ_ij > 0, то опор­ное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец u_i и строку v_j.

Полагая u₁ = 0, запишем это значение в последнем столбце таблицы.

 

 

Рассмотрим занятую клетку первой строки, которая распо­ложена в первом столбце (1,1), для нее выполняется условие и₁ + v₁ = 2, откуда v₁ = 2. Это значение запишем в послед­ней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.

Рассмотрим занятую клетку (3,1): и₃ + v₁ = 3, v₁ = 2, откуда и₃ = 1.

Для клетки (3,3): и₃ + v₃ = 8, и₃ = 1, v₃ = 7.

Для клетки (2,3): и₂ + v₃ = 5, v₃ = 7, и₂ = -2.

Для клетки (2,2): u₂ + v₂ = 1, и₂ = -2, v₂ = 3.

Найденные значения потенциалов заносим в таблицу.

Вычисляем оценки свободных клеток:

 

 

Получили одну оценку Δ₁₃ = 5 > 0, следовательно, исход­ное опорное решение не является оптимальным и его можно улучшить.