Методы решения задачи целочисленного линейного программирования

Методы решения задач целочисленного программирования можно классифицировать как методы отсечения и комбинаторные методы. Дробный алгоритм (в отечественной литературе этот алгоритм называется первым алгоритмом Гомори или циклическим алгоритмом целочисленного программирования); алгоритм, реализующий метод ветвей и границ(предложен А. Лэндом и А. Дойгом с модификацией по схеме Дейкина). Исходной задачей для демонстрации возможностей методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требование целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется до тех пор, пока координаты оптимального решения не станут целочисленными. Название данного метода связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами.

Известно, что при решении задачи линейного программирования в настоящее время принципиальных трудностей нет. Поэтому возникает вопрос: нельзя ли аппарат линейного программирования применять при решении задач целочисленного линейного программирования? Положительный ответ на этот вопрос дает следующая теорема.

Теорема 13.3. Пусть D – многогранник, – множество его целых точек, – выпуклая линейная оболочка множества . Тогда: 1) R – целочисленный многогранник; 2) ; 3) множество опорных планов многогранника R содержится в многограннике , т.е. .

Доказательство. Докажем, что R – целочисленный многогранник. По условию теоремы D – многогранник, т.е. ограниченное множество, поэтому – конечное множество и – выпуклая линейная оболочка конечного множества точек. Следовательно, R тоже многогранник, причем , т.е. многогранник R целочисленный. Обозначим его через . Докажем, что совпадает с . Из определения выпуклой линейной оболочки следует, что .

Покажем, что справедливо также и противоположное неравенство – включение, т.е. . Пусть . Поскольку , . Следовательно, . Но так как произвольный элемент из принадлежит , очевидна справедливость того, что . Из и следует, что .

Включение очевидно. Поскольку – множество опорных решений задачи , , но и поэтому .

Следствие. Пусть – оптимальный опорный план задачи (R, F). Тогда также является оптимальным планом задачи .

Покажем, что – единственный целочисленный многогранник, для которого множество его целочисленных точек совпадает с .

Теорема 13.4. Пусть D – многогранник, L – целочисленный многогранник и

. (13.8)

Тогда .

Доказательство. Из равенств (13.5) непосредственно следует, что . Покажем, что .

Из целочисленности многогранника L имеем, что . С учетом равенств (13.5) получим . Отсюда Методы решения задачи целочисленного линейного программирования , т.е. .

Теорема 13.3 и следствие из нее показывают принципиальную возможность точной линейной аппроксимации целочисленной задачи линейного программирования Методы решения задачи целочисленного линейного программирования с помощью задачи линейного программирования Методы решения задачи целочисленного линейного программирования ; однако они не дают алгоритма для определения Методы решения задачи целочисленного линейного программирования . Кроме того, построение выпуклой линейной оболочки Методы решения задачи целочисленного линейного программирования – не менее сложная задача, и в настоящее время неизвестны эффективные алгоритмы ее решения. В 1954 г. Дж. Данциг, С. Джонсон и Д. Фалкерсон высказали идею о том, что построение Методы решения задачи целочисленного линейного программирования для задачи Методы решения задачи целочисленного линейного программирования можно осуществить поэтапно и решать полученные при этом задачи.

Введем понятие правильного отсечения. Пусть Методы решения задачи целочисленного линейного программирования – некоторая задача целочисленного линейного программирования и опорный оптимальный план соответствующей задачи линейного программирования (D, F) не удовлетворяет условию целочисленности

Методы решения задачи целочисленного линейного программирования

Неравенство

Методы решения задачи целочисленного линейного программирования(13.9)

называетсяправильным отсечением,если оно удовлетворяет условиям:

1) отсечения: не удовлетворяет неравенству (13.9), т.е. ;

2) правильности: любое допустимое решение задачи удовлетворяет неравенству (13.9), т.е. .

Изложим теперь идею метода.

1. Задача Методы решения задачи целочисленного линейного программирования решается путем не двухэтапного, а многоэтапного процесса, причем:

а) на r-м этапе решается вспомогательная задача линейного программирования , . Здесь ;

б) множество целых точек – одно и то же для всех многогранников: Методы решения задачи целочисленного линейного программирования .

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

в) если не удовлетворяет условию целочисленности, то Методы решения задачи целочисленного линейного программирования не является планом задачи , т.е. .

2. Переход от r-го этапа к (r + 1)-му этапу, т.е. от задачи к задаче , в случае нецелочисленности осуществляется с помощью правильного отсечения , добавление которого к линейным условиям задачи превращает многогранник в многогранник . Построение дополнительных ограничений и решение возникающей при этом задачи продолжается до тех пор, пока не получится целочисленное решение или не убедимся в неразрешимости задачи. Однако при этом возникают вопросы: как строить ограничения задачи и обеспечить конечность процесса? Ответ на этот вопрос был впервые получен Р. Гомори, который предложил алгоритм решения полностью и частично целочисленных задач.

Лекция 2: Задача линейного программирования. Задача о ресурсах


Похожие статьи.

Понравилась статья? Поделиться с друзьями: