 |
Комбінаторні методи. Метод гілок та меж
|
|
|
|
В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої задачі. Кожен з них характеризується певною послідовністю перебору варіантів та правилами виключення, що дають змогу ще в процесі розв’язування задачі виявити неоптимальні варіанти без попередньої їх перевірки. Відносна ефективність різних методів залежить від того, наскільки кожен з них уможливлює скорочення необхідного процесу перебору варіантів у результаті застосування правила виключення.
Розглянемо один із комбінаторних методів. Для розв’язування задач цілочислового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв’язується послаблена (без умов цілочисловості) задача. Потім вводиться правило перебору.
Нехай потрібно знайти хj – цілочислову змінну, значення якої хj = 
в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Таким проміжком є інтервал між найближчими до цілочисловими значеннями. Можна стверджувати, що на інтервалі 
цілих значень немає.
Наприклад, якщо =2,7 дістаємо інтервал 
, де, очевидно, немає хj, яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі 
, або 
. Виключення проміжку з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерівностей. Тобто допустиме ціле значення xj має задовольняти одну з нерівностей виду:
або 
.
Дописавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, початкову задачу цілочислового програмування (6.1)-(6.4) поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:
|
|
|
перша задача:
(6.14)
за умов:
; (6.15)
; (6.16)
– цілі числа, 
; (6.17)
, (6.18)
друга задача
(6.19)
за умов:
, 
; (6.20)
; (6.21)
— цілі числа ; (6.22)
, (6.23)
де – дробова компонента розв’язку задачі (6.1)-(6.4).
Наведені задачі (6.14)-(6.18) і (6.19)-(6.23) спочатку послаблюємо, тобто розв’язуємо з відкиданням обмежень (6.17) і (6.22). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками задачі (6.1)-(6.4). Інакше пошук розв’язку задачі триває. Для дальшого розгалуження вибираємо розв’язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки – з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв’язку. Здобутий останній план – оптимальний.
Розв’язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв’язування відрізняється від попередньої лише одним обмеженням. Тому за послідовного розв’язування задач немає сенсу розв’язувати їх симплексним методом спочатку. Досить буде почергово приєднати нові обмеження виду (6.18) і (6.23) до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) непотрібні «старі» обмеження.
Геометрично введення додаткових лінійних обмежень виду (6.18) та (6.23) в систему обмежень початкової задачі означає проведення гіперплощин (прямих), що розтинають багатогранник (багатокутник) допустимих планів відповідної задачі лінійного програмування у такий спосіб, що уможливлюється включення в план найближчої цілої точки цього багатокутника (рис.6.4). Допустимо, що А – точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими 
та +1, що виключає з розгляду точку А, координата якої 
є не цілим числом.
|
|
|
Рисунок 6.4
Опишемо алгоритм методу гілок та меж:
1. Симплексним методом розв’язують задачу (6.1)-(6.3) (без вимог цілочисловості змінних).
Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей розв’язок є оптимальним планом задачі цілочислового програмування (6.1)-(6.4).
Якщо задача (6.1)-(6.3) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача (6.1)-(6.4) також не має розв’язку.
2. Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних 
і визначають її цілу частину 
.
3. Записують два обмеження, що відтинають нецілочислові розв’язки:
,
.
4. Кожну з одержаних нерівностей приєднують до обмежень початкової задачі. В результаті отримують дві нові цілочислові задачі лінійного програмування.
5. У будь-якій послідовності розв’язують обидві задачі.
У разі, коли отримано цілочисловий розв’язок хоча б однієї із задач, значення цільової функції цієї задачі зіставляють з початковим значенням. Якщо різниця не більша від заданого числа e, то процес розв’язування може бути закінчено. У разі, коли цілочисловий розв’язок одержано в обох задачах, то з розв’язком початкової зіставляється той, який дає краще значення цільової функції. Якщо ж в обох задачах одержано нецілочислові розв’язки, то для дальшого гілкування вибирають ту задачу, для якої здобуто краще значення цільової функції і здійснюють перехід до кроку 2.
Приклад 6.2. Розв’яжемо методом гілок і меж задачу з прикладу 6.1.
Розв’язання. Відкинувши умову цілочисловості, дістанемо розв’язок: х 1=1, х 2= 
. Отже, допустиме ціле значення х 2 має задовольняти одну з нерівностей 
або 
. Приєднуємо до початкової задачі окремо кожне з обмежень, нехтуючи умовою цілочисловості, і розв’язуємо по черзі обидві утворені задачі:
Для задачі І (з обмеженням 
) оптимальним буде розв’язок 
, 
, а для задачі IІ (з обмеженням 
) – розв’язок 
, 
. Оскільки цілочислового плану не знайдено, процес необхідно продовжити, узявши для дальшого розгалуження першу задачу, оптимальний план якої дає більше значення функціонала. Розв’язуємо задачу І, окремо приєднуючи до неї обмеження: 
і 
. Отримуємо такі дві задачі:
|
|
|
Розв’язком задачі ІІІ є план 
, 
, а задачі IV – план 
, 
. Обидва розв’язки є цілочисловими, проте краще значення цільової функції забезпечує розв’язок задачі IV. Тому оптимальним планом початкової цілочислової задачі буде 
, 
, що збігається з розв’язком, отриманим за методом Гоморі.
Схема процесу розв’язування задачі з прикладу 6.1 (рис.6.5) досить наочно пояснює назву методу гілок та меж. Початкова задача розділяється (гілкується) на дві простіші, і, якщо серед них не існує задачі з цілочисловим оптимальним розв’язком, то процес гілкування продовжується. Отже, всі розглянуті дії можна зобразити у вигляді «дерева»:
Рисyнок 6.5
Кожен елемент такого «дерева» – це певна задача, що має відповідний оптимальний план. Після одержання нецілочислового розв’язку послабленої (тобто без умови цілочисловості) початкової задачі ми перетворили її на дві інші з додатковими умовами. З них кращим виявився розв’язок задачі І, однак оскільки він був не цілочисловим, то ми продовжили процес гілкування. Задачу І введенням додаткових обмежень перетворили в задачу ІІІ та задачу IV. Оптимальні плани обох цих задач цілочислові, але план задачі IV дає більше значення функціонала, тому цілочисловим оптимальним планом початкової задачі є розв’язок задачі IV.
Самостійна робота №7 – Наближені методи розв’язування задачі цілочислового лінійного програмування
1. Наближені методи. Метод вектора спаду. Приклад розв’язку задачі цілочислового лінійного програмування методом вектора спаду [4, с.272-276].
2. Приклади розв’язку задачі цілочислового лінійного програмування методом Гоморі та методом гілок і меж [2, с.155-157], [4, с.159-160].
|
|
|
