Равновесие можно сохранить передвижкой того же числа единиц в другой строке из столбца, где предыдущая передвижка завысила возможный выпуск автомобилей, в столбец, где возник их избыток. Сдвижка всегда парная, одного и того же числа единиц. Процедура эта должна быть возможной и эффективной.
Последнее определяется сравнением выигрыша и проигрыша (произведение числа сдвинутых автомобилей на разницу расстояний).
Полученный любым методом исходный план требует проверки на оптимальность. Проверка производится при помощи оценочных индексов.
Проставляются они во вспомогательных строке и столбце.
Будем называть клетки, в которых представлено число автомобилей — загруженными, пустые — незагруженными.
Остальные индексы определяются так, чтобы расстояния, записанные в верхнем правом углу каждой загруженной клетки, были равны сумме индексов, соответствующих строки и столбца.
Фиктивную загрузку можно поставить в любую клетку, имеющую только один индекс. В нашем примере это клетки, помеченные крестиками.
Если бы число загруженных клеток было больше 6 (для нашего примера), для определения индексов пришлось бы одну из загруженных клеток разгрузить.
Для этого в матрице строится замкнутый контур из горизонтальных и вертикальных прямых линий так, чтобы все вершины контура располагались в загруженных клетках. Таких контуров всегда можно построить столько, сколько в матрице двойных связей.
Проверка плана на оптимальность заключается в отыскании незагруженных клеток, в которых расстояние меньше суммы индексов. Если такие клетки есть, план неоптимален, клетки называются потенциальными, а разница между суммой индексов и расстоянием — потенциалами.
Отсутствие потенциальных клеток говорит об оптимальности плана.
В нашем примере потенциальных клеток нет, поэтому план уже после логического улучшения является оптимальным и в улучшении не нуждается.