2015-03-27
398
Решение целочисленных задач
Методы решения целочисленных задач
Значительная часть задач по смыслу может иметь решения только в целых числах; например, число турбин, судов, животных может быть только целым числом. Такие задачи решаются методами целочисленного программирования. Общая постановка задачи линейного программирования дополняется требованием о том, чтобы найденные переменные в оптимальном плане были целыми.
Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинаторные методы; в) приближённые методы.
Методы отсечения используют оптимальные решения, найденные для задач линейного программирования. Сужая область допустимых планов до целочисленных границ, т. е. отсекая нецелочисленные допустимые планы, методами отсечения получают решения задач целочисленного программирования. Комбинаторные методы достигают решений задач целочисленного программирования, рассматривая возможные варианты целочисленных ограничений для задачи оптимизации. Приближённые методы опираются на приближённые методы нахождения экстремумов функций нескольких переменных и используют различные способы округления полученных нецелочисленных решений до целых значений. Особенно удобно применять приближённые методы в случае решения задачи целочисленного программирования относительно двух переменных.
|
|
|
Метод Гомори
Метод Гомори решения задач целочисленного программированияявляется методом отсечения. Сущность его состоит в том, что сначала задача решается как задача линейного программирования без учета условия целочисленности переменных. Если полученное решение задачи линейного программирования является целочисленным, задача целочисленного программирования также решена и найденное решение является оптимальным и для неё. Если же в найденном решении задачи линейного программирования одна или большее число переменных не целые, то для отыскания целочисленного решения задачи добавляется новое ограничение. Это ограничение линейное, и при продолжении решения дополненной задачи симплексным методом с учетом этого ограничения получается целочисленный план.
