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

Получив исходно опорное решение, переходят к построению опорных решений, улучшающих друг друга. Для этого применим метод потенциалов по следующему критерию: если опорное решение ТЗ является оптимальным, то ему соответствует система m + n действительных чисел и , удовлетворяющих условиям:

+ = - для занятых клеток,

+ - 0 – для свободных клеток.

Числа и называются потенциалами. В распределительную таблицу добавляют строку столбец . Потенциалы и находят из равенства + = , справедливого для занятых клеток. Только одному из потенциалов дается произвольное значение, например , тогда остальные потенциалы определяются однозначно. Так, если известен потенциал , то = - ; если известен потенциал , то = - .

Обозначим = + - . Эту оценку называют оценкой свободных клеток.

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

Наличие положительной оценки свободной клетки при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из занятых клеток – свободной.

Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак “+”, затем поочередно проставляют знаки “-” и “+”. У вершин со знаком “-” выбирают минимальный груз; его прибавляют к грузам, стоящим у вершин со знаком “+”, и отнимают от грузов у вершин со знаком “-”.

В результате перераспределения получают новое опорное решение. Это решение проверяют на оптимальность, и т.д. до тех пор, пока не получат оптимальное решение.

Пример.

								-2

(1;1): ;

(3;1): ;

(3;3): ;

(2;3): ;

(2;2): ;

= + - ;

= + - ;

= + - ;

= + - .

Опорное решение не является оптимальным. у.е. Улучшим его. Строим цикл для клетки (1;3), :

- + + -

90 0

Дата добавления: 2014-12-27