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

Цільова функція
Обмеження
(2)
(3)
(4)
Математична модель ЗЦЛП

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

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

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

Проблеми, що виникають при округленні розв’язку ЗЛП (2)

Випадок 2.1
Вихідні обмеження є обмеженнями-нерівностями.
Усі округлені точки можуть виявитися
не допустимими (не задовольнятимуть усім обмеженням )
Проблеми, що виникають при округленні розв’язку ЗЛП (3)

Випадок 2.1
Вихідні обмеження є обмеженнями-нерівностями.
Усі округлені точки можуть виявитися
не допустимими (не задовольнятимуть усім обмеженням )
Проблеми, що виникають при округленні розв’язку ЗЛП (3)
Оптимум ЗЦЛП

Випадок 2.2
Вихідні обмеження є обмеженнями-нерівностями.
Округлена допустима точка може виявитися
не оптимальною.
Приклад
Проблеми, що виникають при округленні розв’язку ЗЛП (4)

Проблеми, що виникають при округленні розв’язку ЗЛП (5)
Округлений розв’язок ЗЛП
Оптимум ЗЦЛП

Методи відсікань Гоморі
Метод гілок та меж
Методи розв’язання ЗЦЛП

Алгоритм Гоморі
Дослідження операцій

Цільова функція
Обмеження
(2)
(3)
(4)
Математична модель ЗЦЛП
Існує принципова можливість звести розв’язання ЗЦЛП (1) - (4) до знаходження оптимального розв’язку деякої ЗЛП

Теорема (про оптимальність вершини цілочислового багатогранника)
(5)
(6)

Доказательство теоремы (1)
(5)
(6)

Доказательство теоремы (2)
(5)
(6)

Доказательство теоремы (2)
(5)
(6)

Доказательство теоремы (2)
(5)
(6)

Отже, в основі методів відсікань лежить заміна розв’язання ЗЦЛП (6) деякою процедурою побудови і розв’язання допоміжної ЗЛП (5).
(5)
(6)

Визначення. Послабленою називається задача ЛП, яка отримана з ЗЦЛП шляхом відкидання умов цілочисловості.
Властивості ПосЗ
1) якщо ПосЗ не має допустимих розв’язків, їх не має і вихідна задача;
2) оптимальне значення ЦФ послабленої задачі визначає нижню (верхню) границю оптимального значення ЦФ вихідної задачі на min (max)
3) якщо оптимальний розв’язок ПосЗ є допустимим для вихідної ЗЦЛП, то він є і оптимальним для неї.
Послаблена задача (ПосЗ)

ЗЦЛП
ПосЗ (ЗЛП)
Вихідна задача Послаблена задача

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

Графічна ілюстрація процесу розв’язання

Графічна ілюстрація процесу розв’язання
Вихідною точкою є оптимальний розв’язок відповідної послабленої задачі

Графічна ілюстрація процесу розв’язання
На кожній ітерації додається лінійне обмеження, яке задовольняє цілочисловим розв’язкам вихідної задачі, але виключає поточний нецілочисловий розв’язок

Графічна ілюстрація процесу розв’язання
На кожній ітерації додається лінійне обмеження, яке задовольняє цілочисловим розв’язкам вихідної задачі, але виключає поточний нецілочисловий розв’язок (багатогранник стискується).

Графічна ілюстрація процесу розв’язання

Графічна ілюстрація процесу розв’язання

Графічна ілюстрація процесу розв’язання

Графічна ілюстрація процесу розв’язанням
Обчислювальний процес припиняється, як тільки буде досягнуто будь-який цілочисловий розв’язок

Графічна ілюстрація процесу розв’язання
Оптимум ЗЦЛП знайдено.

Метод відсікань для розв’язання повністю цілочислових задач
Метод відсікань для розв’язання частково цілочислових задач
Будемо розглядати перший з методів
Існуючі методи відсікань

ЗЦЛП

Приклад
Канонічна форма
ЗЦЛП

Початковий крок
Спочатку розв’язуємо послаблену задачу.
Якщо її розв’язок цілочисловий, то він же є і розв’язком ЗЦЛП
Інакше – реалізуємо ідею відсікання.

1) знаходження універсального правила формування додаткових обмежень;
2) доведення скінченності відповідного процесу відсікання;
3) боротьба з надмірним «розростанням» задачі при додаванні додаткових обмежень.
Для реалізації ідеї відсікань необхідно визначитись з:

Як побудувати додаткове лінійне обмеження, якому задовольняє кожний розв’язок, допустимий за умовами (2) - (4)?
Виведення рівняння-відсікання
Стартовою точкою є оптимальна симплекс-таблиця послабленої задачі.
Наприклад:

Виведення рівняння-відсікання
Символом [α] позначатимемо цілу частину дійсного числа α: найбільше ціле, менше або рівне за α, тобто [α] ≤ α.
- рівняння в цілих частинах
Дробовою частиною числа α називається величина f, що визначається рівністю [α] + f = α
(7)
(8)
(8)-(7):
де
- рівняння в дробових частинах

Приклади знаходження цілих і дробових частин

Визначення
Рівняння в дробових частинах називається рівнянням відсікання (відсіканням Гоморі)
Рівняння (7), за яким побудували рівняння відсікання, називається породжуючим рівнянням
Задача (1) - (3) + додаткове рівняння відсікання називається розширеною.

Схема алгоритму Гоморі

Формування рівняння-відсікання

Формування рівняння-відсікання

Формування рівняння-відсікання

Формування рівняння-відсікання
Рівняння в цілих частинах
Рівняння відсікання (саме його додаємо до оптимальної симплекс-таблиці ПосЗ)

Приклад 1
Оптимальна симплекс-таблиця ПосЗ
Оптимальна симплекс-таблиця розширеноі ЗЛП
Застосо-вуємо двоїстий СМ

Приклад 2
Оптимальна симплекс-таблиця ПосЗ

Приклад 2

Приклад 2

Приклад 2

Приклад 2

Приклад 2

Приклад 2

Приклад 2

Графічна ілюстрація
Приклад 2

Приклад 2

Приклад 2

Приклади побудови рівнянь відсікань

Про розмір розширеної задачі
ЗЦЛП
ЗЛП

Про розмір розширеної задачі (РЗ)
РЗ – розширена задача

Про розмір розширеної задачі

Ефективність відсікань

Приклад 3
Оптимальна СТ послабленої задачі

Приклад 3. Шлях розв’язання 1
Оптимум досягнуто за дві ітерації

Приклад 3. Шлях розв’язання 2
Оптимум досягнуто за одну ітерацію

Ефективність відсікань Гоморі
Одна і та ж оптимальна симплекс-таблиця розширеної ЗЛП породжує різні відсікання.
???? Яке з них є найбільш ефективним?
Ефективність відсікання характеризується розмірами області, що відсікається від багатогранника допустимих розв'язків

Ефективність відсікань Гоморі
Це відсікання ефективніше!

Правило 1.
Відсікання (*) ефективніше відсікання (**), якщо
причому, принаймні, в одному випадку виконується строга нерівність (> або <).

Відсікання (*) ефективніше відсікання (**), якщо
причому, принаймні, в одному випадку виконується строга нерівність (> або <).
Сині відсікання ефективніші за зелені
Правило 1

Правило 1
причому, принаймні, в одному випадку виконується строга нерівність

Задача про фарби
2*x1 + 2*x2 <= 9
x1 + x2 <= 4
Не оптимум((
Оптимум))

Правило 1

Використання Правила 1 пов'язано з істотними труднощами обчислювального характеру
Використання цих двох правил не завжди забезпечує введення найбільш ефективного відсікання.
Правила 2 та 3

Порівняння ефективності рівнянь-відсікань
-9/16x4 -5/16x6 -4/16x7 +s1 =- 9/16
-14/16x4 -3/16x6 -1/16x7 +s2 =- 3/16
-1/16x4 -1/16x6 -3/16x7 +s5 =- 10/16
9/16x4 +5/16x6 +4/16x7 >= 9/16
14/16x4 +3/16x6 +1/16x7 >= 3/16
1/16x4 +1/16x6 +3/16x7 >= 10/16
…

Порівняння ефективності рівнянь-відсікань за правилом 1
9/16x4 +5/16x6 +4/16x7 >= 9/16
14/16x4 +3/16x6 +1/16x7 >= 3/16
1/16x4 +1/16x6 +3/16x7 >= 10/16

Порівняння ефективності рівнянь-відсікань за правилом 2
9/16x4 +5/16x6 +4/16x7 >= 9/16
14/16x4 +3/16x6 +1/16x7 >= 3/16
1/16x4 +1/16x6 +3/16x7 >= 10/16

Порівняння ефективності рівнянь-відсікань за правилом 3
9/16x4 +5/16x6 +4/16x7 >= 9/16
14/16x4 +3/16x6 +1/16x7 >= 3/16
1/16x4 +1/16x6 +3/16x7 >= 10/16

АГ знаходить розв’язок за скінчену кількість ітерацій

Помилки округлення, що виникають в процесі обчислень можуть привести до отримання невірного (не оптимального) цілочислового розв’язку (вихід - зберігати окремо чисельники і знаменники).
Розв’язки, одержувані послідовно в процесі реалізації алгоритму, не є допустимими (в процесі розв’язання усі проміжні розв’язки або нецілочислові або мають від’ємні компоненти). Тобто алгоритм не дозволяє отримати будь-який цілочисловий розв’язок, відмінний від оптимального (у разі вимушеної зупинки через відсутність достатнього часу).
Недоліки АГ

Приклад 3

Приклад 3

Приклад 3 (ітерація 1)

Приклад 3 (ітерація 1)

Приклад 3 (ітерація 2)

Приклад 3 (ітерація 2)

Приклад 3 (графічна ілюстрація)

Яка верхня границя кількості ітерацій АГ?