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

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

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

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