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

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

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

Комментарии запрещены.

Путешествуем по миру
  • Палатка Norfin Bream 3

    18.02.2021

    Выбор палатки – непростое решение. Покупая палатку, нужно учитывать объёмы изделия, его способность защитить от непогоды, износоустойчивость, прочность и, конечно... 
    Читать полностью

  • Климат и погода в Индонезии

    06.10.2020

    Индонезия – крупнейшее островное государство на планете. Территория страны простирается более чем на 5000 км с запада на восток и почти на 2000 км – с севера на юг. Свыше... 
    Читать полностью