Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
| Загальна ідея підходу МГГ:
Шукаємо мінімум функції f(x) на множині дискретних значень змінної х. Метод комбінує 2 процедури: 1.Розгалуження (розподіл ОДР на підобласті) і 2.Знаходження оцінок функції мети f на границях (верхньої \ нижньої) цих областей. Процедура розгалуження полягає в розбитті множини допустимих значень змінної на підобласті (підмножини) менших розмірів. Процедуру можна рекурсивно застосовувати до підобласті (вкладена в себе процедура). Отримані подобласти утворюють дерево, зване деревом пошуку або деревом гілок і границь. Вузли цього дерева - побудовані нами рекурсивно подобласти (підмножини множини значень змінної х). Процедура знаходження оцінок полягає в пошуку верхніх і нижніх границь для вирішення задачі на під областях допустимих значень змінної х. В основі методу лежить наступна очевидне правило відсіву областей: якщо нижня границя значень функції на поточній підобласти А дерева пошуку більше, ніж верхня границя значень на раніше переглянутій підобласти В, то А може бути виключена з розгляду. Якщо нижня границя для вузла дерева збігається з верхньою границею, то це значення є мінімумом функції і досягається на відповідній підобласти. Якщо вирішується завдання на максимум f(x), то правило маємо таке: якщо верхня границя значень функції на поточній підобласти А дерева пошуку менше, ніж нижня границя значень на раніше переглянутій підобласти В, то А може бути виключена з розгляду Далі розглядаємо завдання на максимум f(x) Будемо вирішувати спочатку задачу без врахування цілочисельних умов - задачу лінійного програмування. При цьому знаходиться верхня межа значення F (x) для всієї ОДР, так як целочисленное рішення не може поліпшити значення функції мети. Далі в МГГ область допустимих значень змінних (ОДЗП) розбивається на ряд непересічних областей (розгалуження), в кожній з яких будемо оцінювати екстремальне значення функції. Якщо ціле рішення не буде знайдено, розгалуження буде тривати. Розгалуження проводиться послідовним введенням додаткових обмежень. Нехай xk - целочисельна змінна, значення якої в оптимальному рішенні вийшло дробовим. Позначимо округлення отриманого значення xk до меншого цілого як βk . Інтервал βk жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|