Курсовая работа: Методы отсечения
Назовем для кратности задачу (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).
Методы, основанные на использовании процедуры построения правильных отсечений, получили название методов отсечения.
3. Первый алгоритм Гомори