Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


3.1. Метод отсечений Гомори в задачах линейного программирования


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


Метод Гомори можно разделить на три этапа:


1- й этап. Решение задачи линейного программирования симплекс-методом без учета цело-


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


этапу.


2- й этап. К ограничениям задачи присоединить новое (новые) линейное ограничение, которое называют правильным отсечением со следующими свойствами:


•    этому ограничению не удовлетворяет найденное нецелочисленное оптимальное решение задачи;


•    этому ограничению удовлетворяют все допустимые целочисленные решения задачи, в том числе и оптимальное целочисленное решение, если оно существует.


3- й этап. Решение новой задачи линейного программирования с дополнительными правильными отсечениями симплекс-методом с целью определения целочисленного оптимального решения задачи. Если будет найдено частично целочисленное решение задачи, то следует повторить 2й этап и составить новое правильное отсечение по нецелочисленной переменной оптимального решения. Эту процедуру следует продолжать до тех пор, пока не будет найдено целочисленное оптимальное решение задачи. Конечность алгоритма базируется на теореме, доказанной Р. Гомори: если целевая функция задачи линейного программирования ограничена на множестве допустимых решений, коэффициенты целевой функции — целые числа и у задачи линейного программирования существует хотя бы одно целочисленное допустимое решение, то целочисленное оптимальное решение может быть найдено путем построения конечного числа отсечений (без доказательства).

Скачать в pdf «Экстремальные модели менеджмента и экономики»