ммпур методичка

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

Запишем общую задачу целочисленного программирования:

в области, определенной условиями

максимизировать функцию

(17)

Назовем задачу (14—17) (G^ц, Z)-задачей. Соответствующую ей задачу без требования целочисленности переменных, т. е. задачу (14, 15, 17) назовем (G, Z)-задачей. Возникает вопрос: нельзя ли решение (G^ц, Z)-задачи получить путем решения некоторой специальным образом построенной задачи без требования целочисленности переменных и такой, что оптимальные решения исходной (G^ц, Z)-задачи и задачи без требования целочисленности переменных будут совпадать. Другими словами: нельзя ли хорошо изученный аппарат решения задач линейного программирования приспособить к решению целочисленных задач. Принципиальный ответ на этот вопрос дает следующая теорема.

Т е о р е м а 1. Пусть G — многогранник, G^ц — множество его целых точек, R — выпуклая линейная оболочка множества G^ц, тогда:

R= R^ц — целочисленный многогранник;
R^ц= G^ц;
R^* — множество опорных решений задачи (G^ц, Z) содержится в многограннике R^ц.

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

Теорема и следствие из нее показывают принципиальную возможность замены решения задачи типа (G^ц, Z) некоторой процедурой построения и решения вспомогательной задачи типа (G, Z), однако не дают алгоритма решений. К тому же построение выпуклой оболочки множества G^ц реальных задач — чрезвычайно сложная, а подчас практически неразрешимая задача.

Содержание