Автор работы: Пользователь скрыл имя, 24 Ноября 2013 в 14:45, реферат
Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным; - должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
1.Метод Гомори
2.Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения.
3.Для решения целочисленной задачи линейного программирования Р. Гомори предложил метод отсечения плоскостей в 1958 г..
4.Алгоритм Гомори содержит этапы:
Этап 1. Решение непрерывной задачи. Если решение дробное переход на 2 этап.
Этап 2. Решение расширенной задачи.