- •Графічний метод розв'язування задач лінійного програмування
- •2.5.2. Навчальні завдання. Розв'язування задач графічним методом
- •2 Приклади розв’язування задач цілочислової лінійної оптимізації методом гілок та меж симплекс-методом Економічна і математична постановка цілочислової задачі лінійного програмування
- •8.2 Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині
- •3 Комбінаторні методи розв’язування цілочислових задач лінійної оптимізації Комбінаторні методи. Метод гілок та меж
- •4 Приклади економічних задач, що в математичній постановці зводяться до нелінійних задач оптимізації
- •4. Задача лінійного програмування як задача розподілу обмежених ресурсів.
- •5. Побудова моделі задачі лінійного програмування.
- •1. Класичні задачі оптимізації
3 Комбінаторні методи розв’язування цілочислових задач лінійної оптимізації Комбінаторні методи. Метод гілок та меж
В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої задачі. Кожен з них характеризується певною послідовністю перебору варіантів та правилами виключення, що дають змогу ще в процесі розв’язування задачі виявити неоптимальні варіанти без попередньої їх перевірки. Відносна ефективність різних методів залежить від того, наскільки кожен з них уможливлює скорочення необхідного процесу перебору варіантів у результаті застосування правила виключення.
Розглянемо один із комбінаторних методів. Для розв’язування задач цілочислового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв’язується послаблена (без умов цілочисловості) задача. Потім вводиться правило перебору.
Нехай потрібно знайти хj – цілочислову змінну, значення якої хj= в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Таким проміжком є інтервал між найближчими до цілочисловими значеннями. Можна стверджувати, що на інтервалі цілих значень немає.
Наприклад, якщо =2,7 дістаємо інтервал , де, очевидно, немає хj, яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі , або . Виключення проміжку з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерівностей. Тобто допустиме ціле значення xj має задовольняти одну з нерівностей виду:
або .
Дописавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, початкову задачу цілочислового програмування (7.1)-(7.4) поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:
перша задача:
(8.14)
за умов:
; (8.15)
; (8.16)
– цілі числа, ; (8.17)
, (8.18)
друга задача
(8.19)
за умов:
, ; (8.20)
; (8.21)
— цілі числа ; (8.22)
, (8.23)
де – дробова компонента розв’язку задачі (8.1)-(8.4).
Наведені задачі (8.14)-(8.18) і (8.19)-(8.23) спочатку послаблюємо, тобто розв’язуємо з відкиданням обмежень (8.17) і (8.22). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками задачі (8.1)-(8.4). Інакше пошук розв’язку задачі триває. Для дальшого розгалуження вибираємо розв’язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки – з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв’язку. Здобутий останній план – оптимальний.
Розв’язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв’язування відрізняється від попередньої лише одним обмеженням. Тому за послідовного розв’язування задач немає сенсу розв’язувати їх симплексним методом спочатку. Досить буде почергово приєднати нові обмеження виду (8.18) і (8.23) до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) непотрібні «старі» обмеження.
Геометрично введення додаткових лінійних обмежень виду (8.18) та (8.23) в систему обмежень початкової задачі означає проведення гіперплощин (прямих), що розтинають багатогранник (багатокутник) допустимих планів відповідної задачі лінійного програмування у такий спосіб, що уможливлюється включення в план найближчої цілої точки цього багатокутника (рис.8.4). Допустимо, що А – точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими та +1, що виключає з розгляду точку А, координата якої є не цілим числом.