Метод Гомори
Метод Гомори Свойства «правильного отсечения (Гомори)»: · линейные · отсекает найденные оптимальные нецелочисленные решения задачи (1)-(3) · не затрагивает ни одной из целочисленных точек задачи (1)-(4)
Найдено оптимальные, нецелочисленные решения ЗЛП (1) - (3)
Пусть
Ι. Полностью целочисленные задачи: Выбор наиболее эффективного отсечения. Пусть - строку, соответствующую
- если
 i – порождающая строка:
(1+0) - [0
ЗЦП не имеет решения, если в симплекс-таблице появляется, хотя бы одна строка с дробным свободным членом (
Строка, соответствующая
отсечение Гомори (для дальнейшего решения применяют двойственный симплекс – метод) Пример 1 (продолжение).
II. Частично целочисленная задача:
Пусть в примере (А) Пример 3:
|
Б (небазисные)
= 
, выбирают строку, которой соответствует:
+ … + 
+…+ 
= 
+ ([ 
) 
+ … + ([ 
) 
+ … ([ 
) 
= [ 
+ … + 
+ … + … + … + 
]+ 
= - 
) и целыми коэффициентами 
при переменных 
(
) (в этом случае соответствующие уравнение не имеет решения в целых числах).
Пример 2:
В
11/8
63
-
3
32/7
Z (условие целочисленности накладывается только на 
