2. Алгоритм Гоморі
Пусть дана ЗЦЛП.
Один из простейших подходов к решению ЗЦЛП заключается в решении непрерывной задачи с последующим округлением координат полученного оптимума до допустимых целых значений. Округление в данном случае есть не что иное, как приближение. Однако, нет гарантии, что округленное решение будет допустимо и/или оптимально.
Проблемы, возникающие при округлении решения злп
Случай (а): исходные ограничения являются ограничениями-равенствами. В этом случае округленное решение почти всегда недопустимо (рис. 2).
Рис. 2.
Случай (б): исходные ограничения – ограничения – неравенства.
В
пространстве
каждая полностью
нецелочисленная точка имеет
целочисленных точек-соседок
(рис. 3). Так как не известно, в какую
сторону нужно производить округление,
поиск допустимых решений является
достаточно трудоёмким процессом.
Рис. 3
(б1) При этом нет гарантий, что полученное допустимое округленное решение является оптимальным (пример Б1).
Пример
Б1: 
,
6x1
+5x2
15
,
x
,
x
0
, целые.
Рис. 4.
Как
видно из рис. 4, оптимальным решением
непрерывной задачи (задачи
без условий целочисленности) является
точка
.
После округления вниз получаем допустимое
решение
Оптимальным же решением исходной З
ЦЛП
является решение
(б2) Все возможные комбинации округлений вверх или вниз могут не дать допустимого целочисленного решения (рис. 5).
Рис.
5
Итак, подход, заключающийся в решении непрерывной задачи с последующим округлением координат полученного оптимума до допустимых целых значений в общем случае не приводит к желаемому результату.
2.1. Загальна характеристика методів відсікання
Розглянемо задачу цілочислового лінійного програмування (ЗЦЛП):
де
— множина всіх
n-вимірних векторів з
цілочисловими компонентами.
Без урахування цілочисельності задача має звичайну опуклу допустиму область розв’язків. Якщо ж врахувати вимогу цілочисельності, то допустима множина буде являти собою систему точок, як це зображено на рис. 6, і, звичайно, не буде опуклою множиною.
Р
ис.
6. Множина допустимих розв’язків
ЗЦЛП
Однак, якщо б ми могли додати нові граничні лінії, що з'єднують "зовнішні" цілі точки системи, а після цього взяли за допустиму область всю опуклу множину, обмежену осями і новим контуром (рис. 7), то отримали б нову ЗЛП з наступними властивостями:
нова допустима область містить всі цілі точки, які замкнені в первісній допустимій області;
кожна вершина нової допустимої області є цілою.
Оскільки оптимальні розв’язки ЗЛП знаходяться серед вершин, то при використанні симплекс-методу нам забезпечена цілочисельність розв’язків цієї задачі і досяжність розв’язку за кінцеву кількість кроків.
В основу методу відсікань покладено заміну розв’язку задачі (13) - (16) деякою процедурою побудови і розв’язків допоміжної задачі
Р
ис.
7. Множина допустимих розв’язків
нової ЗЛП
Назвемо послабленою задачу ЛП, одержану з ЗЦЛП шляхом відкидання умови цілочисельності. Послаблені задачі мають наступні властивості:
1) в усіх випадках, коли послабленна задача не має допустимих розв’язків, їх немає і у вхідній задачі;
2) оптимальне значення цільової функції послабленої задачі визначає нижня (верхня) границя оптимального значення цільової функції вхідної задачі на мінімум (максимум);
3) якщо оптимальний розв’язок послабленої задачі є допустимим для вхідної задачі, то він є оптимальним і для вхідної ЗЦЛП.
У методі відсікання процес розв’язкання є ітераційним і визначається наступною схемою. Точкою відліку є оптимальний розв’язок відповідної послабленної задачі. На кожній ітераціі додається лінійне обмеження, що задовольняє цілочисловий розв’язок вхідної задачі, але поточний нецілочисловий розв’язок це виключає. Обчислювальний процес припиняється, як тільки буде досягнутий будь-який цілочисловий розв’язок.