Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління / Розрахунково-графічна робота з дисципліни «Математичні методи дослідження операцій» на тему «Цілочислове програмування. Метод гілок та границь» Львів 2018 Теоретичні відомості Метод гілок та границь Це загальний метод, застосовний як до лінійних, так і до нелінійних задач дискретного (зокрема, цілочислового) програмування. Це комбінаторний метод, реалізований як спрямований перебір варіантів розв’язків оптимізаційних задач зазначеного типу. Ідея його така: обчислюють якусь нижню (для задачі мінімізації) чи верхню (для задачі максимізації) оцінку цільової функції /на допустимій множині розв’язків/(наприклад, її нижню чи верхню межу), причому спосіб обчислення оцінки для кожної задачі добирають окремо. Множину /певним способом розбивають на дві неперетинні підмножини, на кожній з яких знову обчислюють оцінки цільової функції/. Підмножина з кращою оцінкою перспективніша для пошуку, тому її вибирають для подальшого галуження. Іншу підмножину вважають кінцевою на цьому етапі. Якщо вона має строго більшу (меншу) оцінку, ніж вибрана для галуження, то надалі її вже не розглядають. Якщо ж відмінність в оцінках для обох підмножин нестрога, то на наступних кроках можливе повернення до якоїсь кінцевої підмножини. Якщо з кожним новим галуженням оцінка цільової функції “не погіршується”, то отриманий на певному кроці цілочисловий (дискретний) розв’язок – оптимальний розв’язок відповідної початкової задачі, інакше можливе повернення до однієї з попередніх кінцевих підмножин, що має кращу оцінку, ніж отримана на цьому етапі. Тоді процес поділу виконують для цієї підмножини. Конкретні реалізації методу гілок і меж пов’язані з правилами поділу на підмножини (правилами галуження) та побудови оцінок (меж) значень цільової функції на них. Для задач цілочислового ЛП процедура методу гілок і меж має такий вигляд. Розглянемо частково цілочислову ЗЛП: мінімізувати/ для обмежень: / / / У загальному випадку деякі зі значень /можуть бути нескінченними/. Уважають, що задана так багатогранна множина обмежена. Як і в разі розв’язання подібних задач методом відтинання, розглядають допоміжну ЗЛП, отриману з початкової задачі відкиданням умови цілочисельності змінних /. Нехай /– оптимальний розв’язок цієї задачі. Якщо вектор /цілочисловий, то це оптимальний розв’язок початкової задачі, інакше обчислюють значення цільової функції в точці /, яка стає її оцінкою (нижньою межею) на початковій допустимій множині розв’язків, і виконують галуження цієї множини. Вибирають / – якусь нецілу компоненту вектора /. Оскільки в оптимальному розв’язку вона має бути цілою, то накладають додаткові обмеження / де /ціла частина числа/. Отже, початкова множина допустимих розв’язків розпадається на дві підмножини: одна з яких містить як додаткове обмеження першу нерівність, а інша – другу. Графічно це має вигляд вилучення одиничної смуги з початкової множини. / На кожній із новоутворених підмножин розв’язують задачу мінімізації допоміжної нецілочислової ЗЛП. Значення цільової функції на цих підмножинах вибирають як її оцінки (нижні межі). Якщо якомусь із розв’язків відповідає менше значення цільової функції й до того ж він цілочисловий, то це оптимальний розв’язок початкової частково цілочислової задачі, інакше підмножину з нижчою оцінкою цільової функції так само розбивають на підмножини відносно однієї з нецілих компонент відповідного розв’язку допоміжної ЗЛП. Якщо оцінки цільової функції, отримані на попередніх етапах для кінцевих підмножин (не розгалужуваних), кращі, ніж отримані на останньому етапі для обох підмножин, то для галуження вибирають ту з них, що має найменшу оцінку. Обчислювальний процес ітеративно повторюють починаючи з цієї підмножини. Очевидний недолік методу гілок і меж у разі розв’язання задач із великою розмірністю полягає в тому, що потрібно перебирати багато варіантів допоміжних задач. Однак цю ваду можна перебороти, якщо шукати не оптимальний розв’язок, а який-небудь близький до оптимального. Про ступінь близькості та швидкість збіжності до екстремуму можна зробити висновки за зміною значень оцінок цільової функції: якщо оцінки на наступних ітераціях мало змінюються, то пошук можна припиняти. Індивідуальне завдання Варіант 57 Цільова функція: