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

Методыотсечения и методы ветвлений и отсечений

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

Методы отсечения опираются на следующее утверждение: если ослабление задачи ЦЛП имеет нецелочисленное оптимальное решение , то существует неравенство

, (7.2)

которому не удовлетворяет, а любое допустимое решение исходной задачи ЦЛП удовлетворяет. Неравенство (7.2) называют правильным отсечением.

Методы отсечения также вкладываются в схему Джеффриона и Марстена, описанную в главе 6. Запишем первый алгоритм Р. Гомори.

Шаги 1,2 — стандартные.

Шаг 3. Формальный (список всегда из одной задачи).

Шаг 4. Релаксация всех условий целочисленности.

Шаг 5. Решение с помощью алгоритма линейного программирования (двойственный симплекс-метод).

Шаг 6. Стандартный.

Шаг 7. Пропускается.

Шаг 8. Стандартный.

Шаг 9. Всегда переход к шагу 10.

Шаг 10. «Сжатие» текущей релаксации путем добавления отсечения.

Шаг 11. Никогда не имеет места.

Шаг 12. Стандартный.

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

, (7.3)

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

, (7.4)

полученное из - го уравнения системы (7.4), обладает всеми свойствами правильного отсечения. Символ {} в (7.4) означает дробную часть [1] соответствующего числа.

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

. (7.5)

Теорема 7.1. Пусть - допустимое решение задачи ЦЛП. Тогда отсечение, сформулированное по правилу

(7.6)

является правильным. Докажем, что значение является целым числом. Перепишем (7.5) в виде:

На основании предположений о допустимости решения - и являются целыми. Остальные части последнего выражения – целые по определению - целое.

Докажем, что . Допустим от противного, что . Тогда:

- не целое. Полученное противоречие свидетельствует о ложности утверждения . Следовательно, при любом допустимом выполняется неравенство .

Докажем, что любое оптимальное решение релаксации задачи ЦЛП, не являющееся решением ЦЛП – не удовлетворяет правильному отсечению (7.6). Пусть в оптимальном решении релаксации значение - й базисной переменной – дробное. Поскольку решение оптимально, то все небазисные переменные равны нулю. Учитывая это: , что свидетельствует о невыполнимости условия правильного отсечения .

Первый этап метода Гомори состоит в определении симплексным методом оптимального решения задачи ЛП – релаксации задачи ЦЛП. После того, как это решение найдено, анализируются его компоненты. Если среди компонент нет дробных чисел, то найденное решение является оптимальным решением задачи ЦЛП. Если же некоторая переменная принимает дробное значение, и в j-м ограничении есть дробные коэффициенты, то к системе ограничений добавляют правильное отсечение (дополнительное ограничение Гомори):

, (7.7)

где и - коэффициенты при неизвестных и свободные члены системы ограничений, взятые из строки, соответствующей переменной , в последней итерации симплекс-таблицы.

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