Лекция: Метод отсечения, циклический алгоритм.

Имеем задачу целочисленного программирования записанную в канонической форме:

(1)

при ограничениях:

(2)

(3) (4)

Здесь -исходные переменные задачи;

— дополнительные переменные задачи;

При решение необходимо иметь ввиду, что т.к. оптимальное решение определяется пересечением n гиперплоскостей, то таких гиперплоскостей существует не больше чем это необходимо(часть этих плоскостей могут быть ограничениями исходной задачи). Каждое текущее решение задачи можно представить в виде таблице неравенств:

 
f(X)
………

Предполагается, что все в исходной таблице целыеà все дополнительные переменные также должны быть целыми неотрицательными числами. Можно показать, что если -выпуклый многогранник, -множество его целых точек, -выпуклая линейная оболочка множества, то является целочисленным многогранником. Непосредственно построение — сложная задача, является основной задачей методов отсечения.

Алгоритм состоит из следующих процедур:

1) Решается исходная задача линейного программирования (1)-(3) каким-либо методом

2) Получение оптимального решения ЗЛП(задача линейного программирования), если оно существует- проверить на условие целочисленности. Если условие выполняетсяà оптим. решение ЗЛП является одновременно оптимальным решением целочисленного ЗЛП(ЦЗЛП). Если условия (4) [x-целое] не выполняется хотя бы для одной переменной, то перейдем к следующему этапу

3) Строим специальное дополнительное ограничение, позволяющее отсечь часть области R; в котором содержится оптим. решение ЗЛП и не содержится допустимого ЦЗЛП.

Подобный процесс построения доп. ограничений повторим до тех пор пока :

а) не будет доказана неразрешимость ЦЗЛП

б) либо пока не получим целочисленное решение

Примечание: дополнительные ограничения должны быть линейны;

Таким образом, любое неравенство пригодное для этой цели(см.Примечание) и имеющее вид должно удовлетворять условиям правильного отсечения:

а) условию отсечения, т е оптимальному решению предыдущего ЗЛП не удовлетворяющего этому неравенству

б) любое допустимое решение ЦЗЛП удовлетворяет этому неравенству

Имеем задачу целочисленного программирования записанную в канонической форме:

(1)

при ограничениях:

(2)

(3) (4)

Здесь -исходные переменные задачи;

Алгоритм решение ЦЗПЛ:

1) решим [k соответствует номеру итерации при решения ЦЗЛП]( на первой итерации k=0 т.е решаем исходную ЗЛП). Если все базисные переменные оптим. решения ЗЛП целочисленные, то это решения ЦЗЛП. Если какая-то компонента нецелая то переходим к следующему шагу

2) В случае нескольких нецелых координат, надо выбрать координату с наибольшей дробной частью в качестве строки для построения правильного отсечения. Строим дополнительное ограничение(линейное)

3) Добавим эти условия к условиям; получим. Практически последняя таблица решения для ЗЛП дополняется еще одной строкой с рассмотренным выше дополнительным ограничением. Поскольку в этой таблице все в строке целевой функции (как результат решения оптимального ), а, то полученное можно оптимизировать с помощью двойственного метода последовательного улучшения плана (с выводом из базиса )

4) Переходим к пункту 1)

Примечание: если переменная вошла в базис с отрицательным значением, соответствующую строку следует использовать в качестве ведущей для применения двойственного симплекс-метода. Если становится отрицательным, то нулевая строка не используется для построения дополнительного ограничения; если -нецелое, следует выбрать нулевую строку для построения дополнительного ограничения.

 


еще рефераты
Еще работы по информатике