Задача цілочислового лінійного програмування. Алгоритм Гоморі

1.

Дослідження операцій

2.

Цільова функція
n
min (max) z c j x j ;
(1)
j 1
Обмеження
n
a x
j 1
ij j
bi , i 1, m;
(2)
x j 0, j 1, n;
(3)
x j ціла, j 1, n.
(4)

3.

Один з найпростіших підходів до вирішення ЗЦЛП:
1) вирішити неперервну задачу (ЗЛП)
2) округлити координати отриманого оптимуму до
допустимих цілих значень.

4.

Один з найпростіших підходів до вирішення ЗЦЛП:
1) вирішити неперервну задачу (ЗЛП)
2) округлити координати отриманого оптимуму до
допустимих цілих значень.
АЛЕ
немає гарантії, що округлений розв’язок буде
допустимим і / або оптимальним.

5.

Випадок 1
Серед вихідних обмежень є обмеження-рівності.
В цьому випадку округлений розв’язок (майже)
завжди є недопустимим

6.

Випадок 2
Вихідні обмеження є обмеженнями-нерівностями.
У просторі