Методы отсечения

Идея методов отсечения состоит в следующем. Решается задача ЛП, полученная из целочисленной задачи отбрасыванием условия целочисленности. Если решение вспомогательной задачи ЛП целочисленное, то оно же является и решением исходной задачи. Если оптимальное решение вспомогательной задачи не целочисленное, то к решённой задаче ЛП добавляют новое линейное ограничение; оно удовлетворяет целочисленным решениям исходной задачи, но не удовлетворяет полученному нецелочисленному решению первоначальной задаче ЛП. Указанное дополнительное линейное ограничение определяет некоторую отсекающую плоскость и называется правильным отсечением. Новые правильные отсечения добавляют к первоначальной вспомогательной задаче ЛП до тех пор, пока на некотором шаге не будет получено целочисленное решение вспомогательной задачи, являющееся, очевидно, оптимальным решением исходной задачи целочисленного линейного программирования.

Одним из методов отсечения является методГомори, названный так в честь своего автора (этот метод также носит название метода отсекающих плоскостей).

Решается задача полностью целочисленного линейного программирования:

где

Наряду с ней рассматривается вспомогательная задача ЛП

(2)

Вспомогательная задача ЛП решается симплекс-методом. Пусть на последней итерации ограничения этой задачи приняли вид:

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

Как известно, оптимальным решением задачи будет вектор Пусть существует номер i такой, что β_і – нецелое (в противном случае целочисленный вектор является оптимальным решением и исходной задачи.

Обозначим, как обычно, [z] и {z} соответственно целую и дробную части числа z. Заметим, что если – нецелое число, .

Согласно общей идее метода отсечения необходимо перейти к решению новой вспомогательной задачи ЛП, у которой наряду с исходными ограничениями рассматривается дополнительное ограничение, осуществляющее правильное отсечение. Рассмотрим ограничение

которое соответствует β_i такому, что {β_i}≠0. Имеет место следующее утверждение.

Теорема. Дополнительное линейное ограничение (3) является правильным отсечением для задачи целочисленного линейного программирования (1).

Рассмотрим алгоритм Гомори на примере:

Дата добавления: 2013-12-13