Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Алгоритм метода Гомори
Шаг 1. Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.
Шаг 2. Пусть оптимальная таблица имеет вид:
| b | 
| … | 
| |
| L | 
| 
| … | 
|
| 
| 
| … | 
|
| … | … | ………….. | ||
/ 
| 
| 
| … | 
|
Если элементы 
– целые, то оптимальное решение 
является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.
Шаг 3. Среди дробных компонент таблицы выбираем элемент 
с максимальной дробной частью 
и по строке i составляем дополнительное ограничение:
Здесь 
- целая часть числа 
(наибольшее целое число, не превышающее число ).
Шаг 4. Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к шагу 2.
| <== предыдущая страница | | | следующая страница ==> |
| Двойственный симплекс-метод | | | Замечания. 1. Признаком отсутствия целочисленного решения служит появление в таблице хотя бы одной строки с дробным свободным членом и целыми остальными коэффициентами |
Дата добавления: 2015-07-26; просмотров: 163; Нарушение авторских прав
Мы поможем в написании ваших работ!