2. Теоретические основы методов отсечения
Запишем общую задачу целочисленного программирования: в области, определенной условиями
(11)
(12)
- целые, (13)
максимизировать функцию
(14)
Назовем для кратности задачу (11-14) (?ц, C) - задачей. Соответствующую ей задачу без требования целочисленности переменных, т.е. задачу (11, 12, 14) назовем (?, C) - задачей. Поставим вопрос: нельзя ли решение (?ц, C) - задачи получить путем решения некоторой специальным образом построенной задачи без требования целочисленности переменных и такой, что оптимальные решения исходной (?ц, C) - задачи и задачи без требований целочисленности переменных будут совпадать. Другими словами: нельзя ли хорошо изученный аппарат решения задач линейного программирования приспособить к решению целочисленных задач. Принципиальный ответ на этот вопрос дает следующая теорема.
Теорема. Пусть ? - многогранник, ?ц - множество его целых точек, R - выпуклая, линейная оболочка множества ?ц, тогда:
1) R=Rц - целочисленный многогранник;
2) Rц = ?ц;
3) R* - множество опорных решений задачи (?ц, C) содержится в многограннике Rц.
Доказательство. Докажем, что R - целочисленный многогранник. По условию теоремы ? - многогранник, поэтому множество его целых точек (оно обозначено через ?ц) конечно. Поскольку R - выпуклая линейная оболочка этого конечного множества точек, R - тоже многогранник.
По самому определению выпуклой линейной оболочки, она содержит все опорные планы множества, на которое она натянута, т.е. многогранник R содержит все целочисленные точки ?ц. Поэтому R - целочисленный многогранник. Обозначим его через Rц. Первая часть теоремы доказана.
Докажем, что Rц совпадает с ?ц. Так как R - выпуклая оболочка точек множества ?ц, то ?ц Rц.
Покажем, что справедливо также и противоположное неравенство-включение, т.е. Rц?ц. Для этого выберем некоторый произвольный элемент х°Rц. Поскольку Rц содержит все опорные решения задачи (?ц, C), то х° удовлетворяет условиям задачи (?ц, C), т.е. х°?ц. Но поскольку произвольный элемент из Rц принадлежит ?ц, то очевидно, что справедливоRц?ц. Сопоставляя противоположные включения Rц?ц и ?цRц приходим к выводу: что ?ц=Rц. Вторая часть теоремы также доказана.
Доказательство 3-го пункта теоремы является совершенно очевидным. Так как R* - множество опорных решений задачи (?ц, C), то R*?ц но ?ц=Rц, поэтому R*Rц
Теорема доказана.
Следствием из этой теоремы является тот вывод, что оптимальное решение задачи, областью определения которой является выпуклая оболочка, натянутая на область поиска целочисленного решения, совпадает с оптимальным решением исходной целочисленной задачи.
Доказанная теорема и следствие из нее показывают принципиальную возможность замены решения задачи типа (?ц, C) некоторой процедурой построения и решения вспомогательной задачи типа (?, C), однако не дают алгоритма решений. К тому же построение выпуклой оболочки множества ?ц реальных задач - чрезвычайно сложная, а подчас практически неразрешимая задача,
В 1954 г. Дж. Данциг высказал идею о том, что построение выпуклой оболочки целочисленной области для задачи (?ц, C) можно осуществлять поэтапно и решать получаемые при этом задачи. Однако при этом возникли вопросы как строить ограничения новой задачи и как обеспечить конечность процесса.
Ответ на эти вопросы был впервые получен Р. Гомори, который предложил алгоритмы решения целочисленных и. частично целочисленных задач.
Алгоритм Р. Гомори состоит из следующих процедур:
1. Решается (?, C) - задача, соответствующая исходной (?ц, C) - задаче.
2. Полученное оптимальное решение (?, C) - задачи, если оно существует, проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение (?, C) - задачи есть оптимальное решение (?ц, C) - задачи. Если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу. Если (?, C) - задача, оказывается неразрешимой, то (?ц, C) - задача тоже решения не имеет.
3. Строится дополнительное ограничение, обладающее тем свойством, что с его помощью отсекается часть области, в которой содержится оптимальное решение (?, C) - задачи и не содержится ни одного допустимого решения (?ц, C) - задачи. Процесс построения дополнительных ограничений и решения получаемых при этом (?, C) - задач продолжается до тех пор, пока не получим целочисленного решения или не убедимся в неразрешимости задачи.
При этом свойства, которыми должно обладать каждое из дополнительных ограничений при переходе от одной задачи к другой следующие:
1) дополнительное ограничение должно быть линейным, чтобы оставаться в области применимости аппарата линейного программирования;
2) дополнительное ограничение должно отсекать часть области, в которой не содержится допустимых решений целочисленной (?ц, C) - задачи, но есть найденное оптимальное решение нецелочисленной (?, C) - задачи, т.е. ограничение должно обладать свойством правильности, которое не позволяет потерять оптимальное решение исходной (?ц, C) - задачи.
Пусть х (?, C) - оптимальное решение (?, C) - задачи, которое является недопустимым решением для (?ц, C) - задачи. Неравенство
(15)
определяет правильное отсечение, если удовлетворяет
а) условию отсечения: x(?, C) удовлетворяет неравенству (15)
б) условию правильности: любое допустимое решение задачи (?ц, C), удовлетворяет неравенству (15).
Методы, основанные на использовании процедуры построения правильных отсечений, получили название методов отсечения.