Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Обидва завдання можна розвязати
- Зупинка алгоритму
| xk≥βk+1 або xk≤βk.
Це і є додаткові обмеження, що виділяють нові підобласті нашої задачі Введення їх в ЛП завдання в методі гілок і границь на кожному кроці породжує дві не зв'язані між собою підзадачі. Запишемо їх для конкретики. І так нехай вирішена на 1-том кроці ЛП завдання без урахування целочисельності І нехай в цьому завданні всі - повинні бути цілі. Нехай на 1-том кроці розгалуження обрана змінна xk для розгалуження. Тоді 2 породжені ЗЛП завдання матимуть вигляд та (1) Алгоритм розгалуження на області допустимих рішень породжує деяке дерево пошуку. Розглянемо деякий q-тий крок алгоритму розгалуження. Розумно припустити що на попередніх кроках розгалуження вже могло бути отримано деяке целочисельне рішення ЦР, тоді воно було запам'ятовано як "рекорд". Ну а якщо такого ЦР немає, то і "рекорд" порожній. Зупинка алгоритму - переглянуті всі розгалужені області при цьому рішення в "рекорд" є опт рішення ЦЛПЗ. Тоді на довільному q-тому кроці розгалуження можливі наступні чотири випадки при вирішенні деякої розгалудженої пари задач типу (1): 1. Обидва завдання можна розв'язати і 1-ша із задач має целочисельне оптимальне рішення (ЦОР) а рішення 2-гої задачі - нецілочисельне - НЦОР. Тоді обчислюємо значення функціоналу (ЗФ) задач і порівнюємо їх між собою і "рекордом". Якщо рекорд порожній - записуємо ЦОР в рекорд, якщо ЗФ ЦОР > рекорду, записуємо нове ЦОР в рекорд, якщо ні то ні, якщо ЗФ рекорду> ЗФ НЦОР (2-я задача-область) то область ДР другого завдання відсікається, а ми переходимо до розглянення нерозглянутої ще області з найбільшим значенням ЦФ Якщо ж ЗФ рекорду < ЗФ НЦОР то область ДР другої задачі надходить на подальше розгалуження 2. Одне із завдань нерозв'язна, а інша має цілочисельний оптимальний план. Тоді перша область відсікається, друга порівнюється з рекордом і чи перезаписує рекорд чи ні . Далі переходимо до розглядання нерозглянутої області з найбільшим значенням ЦФ 3. Одна із задач нерозв'язна, а інша має нецілочисельний оптимальний план. Тоді перша область відсікається, а у другій задачі в її оптимальному плані вибираємо цілочисельну змінну компонент, значення якої в плані рівно дробовому числу і будуємо дві задачі, аналогічно як раніше. 4. Обидва завдання можна розв'язати, і обидва рішення нецілочисельні. Тоді розглядаємо ту із задач, для якої значення ЦФ більше. І будуємо дві задачі аналогічно як раніше. Зупинка алгоритму: переглянуті всі розгалужені області, при цьому рішення в "рекорд" є оптимальним рішенням ЦЛПЗ Примітка. Здійснюване в процесі розгалуження врахування обмеження на цілочисельність дозволяє виключити частини багатогранника допустимих рішень, що не містять точки з цілими координатами. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|