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

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: опорный план будет являться оптимальным, если существуют система m+n действительных чисел u_i и v _i, называемых потенциалами, удовлетворяющая условиям:

u_i+ v_j =c_ij для занятых клеток, где x_ij >0

u_i+ v_j ≤c_ij для свободных клеток, где x_ij =0

при решении задачи на минимум.

Введём обозначение оценки свободной клетки таблицы

_ij=c_ij – (u_i + v_j)

Теорема. Если среди оценок _ij нет отрицательных, то опорный план является оптимальным и все свободные клетки потенциальны.

Замечание. Потенциалы u_i и v_j могут быть рассчитаны только для невырожденного плана. (План называется невырожденным, если число занятых клеток в таблице равно m + n – 1, в противном случае план – вырожденный). Для вырожденного плана вносим 0 в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным m + n – 1. Этот 0 вводят в клетку с наилучшим тарифом одного из одновременно вычеркиваемых рядов таблицы. При этом фиктивно занятая 0 клетка не должна образовывать замкнутого контура с другими клетками таблицы.