Решение задач целочисленного программирования методом Гомори
Курсовая работа, 23 Июня 2013, автор: пользователь скрыл имя
Краткое описание
Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.
Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.