Задача математичного програмування Тема 1 Питання термінології, історіографія назв
Ви запитаєте, а наскільки важливий цей клас задач
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Метод Гоморі послідовних відсікань
- Метод гілок і границь . Для загального випадку змішано целочисельної задачі
| Ви запитаєте, а наскільки важливий цей клас задач? – Відповім, - дуже важливий, так як в будь-якій реальній задачі частина змінних завжди цілочисельні. Крім того, за рахунок введення ЦЗ вдаються різні прийоми формалізації різнорідних фізичних (змістовних) постановок в математичну формалізацію задачі оптимізації. До цього ж типу завдань належать і екстремальні комбінаторні задачі (перебірні задачі коли перебираємо дискретні значення ЦЗ).
Ці завдання виникають в різних прикладних областях - задача комівояжера (про находження оптимального маршруту), задача про призначення (оптимізація розподілу обладнання), інше. Різні алгоритми вирішення ЗЦЛП оптимізують розрахунок з урахуванням специфіки завдання. Тут хочу звернути вашу увагу, що значна частина алгоритмів целочисленного і опуклого програмування, так чи інакше використовують, при вирішенні, якісь варіанти ЛП завдань. Це ще раз стверджує важливість вміння формалізовувати і маніпулювати постановками ЛП завдань. Отже, далі, про алгоритми вирішення ЗЦЛП: Метод Гоморі послідовних відсікань. Якщо завдання повністю целочисельне, то частіше застосуємо Метод Гоморі послідовних відсікань (або Метод відсікання.) При вирішенні багатьох завдань (планування дрібносерійного виробництва, розподіл транспорту по шляхах сполучення, вироблення суджень типу "так-ні" і т.п.) нецелочисленное рішення не має сенсу. Спроба тривіального округлення до цілих значень призводить або до порушення обмежень завдання, або до недовикористання ресурсів. Коли перед нами двовимірна задача, проблема вирішується шляхом виявлення всіх цілочисельних точок, близьких до кордону допустимої множини планів, побудови "опуклої целочисельної оболонки" (опуклої множини планів, що містить всі цілочисельні плани) і рішення задачі над цією множиною. B загальному ж випадку висувається ідея послідовного відсікання нецілочисельних оптимальних планів - як це: звичайним симплексним методом відшукується оптимальний план і, якщо він нецілочисельне, будується додаткове обмеження, що відтинає знайдений оптимальний план, але не відтинає жодного цілочисельного плану. Ця ідея, що належить Д. Данцигу і Р.Гоморі, вперше була представлена в формі додаткового обмеження: , де - множина індексів базисних змінних (не нульових), тобто - це небазисні змінні. Зміст додаткового обмеження - сума небазисних компонент даного рішення у оптимальному плані наступного кроку (коли ми одну з небазасних компонент вводимо в базис, це требо зробити так, щоб виконалося (*), тобто хоча б одна компонента повинна стати відмінна від нуля; але при цьому виконуєтся (*)). Дійсно, 1. при такій вимозі та вибору якоїсь змінної з цих до складу базисних (тобто ненульових) оптімальний план з нульовими значеннями небазисних компонент (тобто, який був) цій умові не задовольняє, тобто ми це рішення (де сума небазисних змінних = 0) даним обмеженням відсікаємо від вхідної множини допустимих рішень. 2.Очевідно і те, що відтята область, що обумовлена умовою , не містить цілочисельного рішення, так як в новому плані на відсіченій області хоча б одна з нинішніх небазисних змінних повинна б увійти в базис, проте за умови вона не може бути целочисельною. Даний підхід хоч і теоретично бездоганний, однак, для більшості завдань швидкість збіжності процесу таких відсікань вкрай мала. Тому Р.Гоморі була запропонована інша форма додаткового обмеження. Так, якщо компонента плану, визначається k-им рівнянням системи обмежень - не целочисельна, то додається нове обмеження для значень небазисних змінних де dk - дробова частина правої частини обмеження (компоненти плану), dkj - дробова частина коефіцієнта при Xj (ціла частина числа: - це найбільше ціле, що не перевищує це число; дробова частина числа дорівнює різниці між числом і його цілою частиною), D - нова додаткова змінна. Наприклад, якщо основне обмеження має вигляд то додаткове обмеження приймає вигляд Можна зменшити обсяг перетворень, якщо керуватися наступними правилами: 1. Вибирати в якості базового для побудови додаткового обмеження рівняння, що визначає компоненту плану з найбільшою дробовою частиною; 2. Для введення в базис опорного плану розширеної задачі вибирати змінну, для якої досягається мінімум відношення абсолютних значень j до значень fkj; 3. Якщо одна з раніше введених додаткових змінних увійшла в базис, її і відповідне їй рівняння можна відкинути (така ситуація пов'язана з появою більш жорсткої умови, що перекриває дію раніше введеної). Можуть бути обставини, що виявляють відсутність цілочисельних планів (суперечливість обмежень). Для запропонованого тут методу доведена кінцевість процесу відсікань, але число цих відсікань непередбачувано (цілком може виявитися швидке вирішення задач з десятками змінних і обмежень і фантастично тривале вирішення для задач невеликих розмірів). 2. Метод гілок і границь. Для загального випадку змішано целочисельної задачі частіше працюють методом гілок і границь - МГГ. Зазначимо, що МГГ - це навіть не метод, а деякий загальний принцип, що вдало адаптований до умов ЗЦЛП. Ідея методу може бути застосована до оптимізаційної задачі будь-якого типу, а не тільки ЗЦЛП. По суті метод реалізує обгрунтоване скорочення задачі повного перебору рішень ЗЦП (значень цілочисельних змінних) за рахунок відсіву підмножин допустимих рішень, для яких вдається визначити (без перебору), що вони не містять оптимальних рішень. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|