Читайте также:
|
Клетки, которые располагаются в некотором прямоугольном цикле (замкнутом), можно переставлять. У каждого цикла есть стоимость:
В этом методе нужно искать циклы, у которых положительная цена.
Аналогично этот метод может быть использован, для перехода от одного опорного плана к другому.
Возможны следующие варианты:
если данный опорный план не оптимален, то следовательно хотя бы одну клетку можно заменить на другую пустую, чтобы стоимость всего плана стала меньше.
Нам выгодно отсортировать клетки по стоимости, чтобы они находились в разных столбцах. Внутри оптимального плана возможны перестановки между четырьмя заполненными.
Замечание: Недостатком метода циклов является неопределенность с клетками, которые необходимо использовать в цикле, поэтому Контарович предложил метод, с помощью которого можно находить такие клетки.
Дата добавления: 2015-07-11; просмотров: 115 | Нарушение авторских прав