mathematicsSimilar presentations:
Задача цілочислового лінійного програмування. Алгоритм Гоморі
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Вихідні обмеження є обмеженнями-нерівностями.
У просторі