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

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

Числа u_i и v_j называют потенциалами. В распределительную таблицу добавляют строку v_j и столбец u_i. Потенциалы u_i и v_j находят из равенства , справедливого для занятых клеток. Одному из потенциалов даётся произвольное значение, например , тогда остальные потенциалы определяются однозначно.

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

Таблица 5.3

bj ai				ui
					-2
vj

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

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

Для клетки (3, 3):

Для клетки (2, 3):

Для клетки (2, 2):

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

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

Получили одну оценку , следовательно, исходное опорное решение не является оптимальным и его можно улучшить.