Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Варіант типу МНК
- Далі як і в МНК беруться похідні і прирівнюючи їх нулю - одержуємо систему лінійних рівнянь щодо х
У складанні нами таблиці є негативні елементи в стовпці вільних членів, знаходимо серед них максимальний за модулем - це елемент: -6, він задає провідний рядок - X6. У цьому рядку також знаходимо максимальний по модулю негативний елемент: -10 він знаходиться в стовпці X3 який буде ведучим стовпцем. Змінна в провідному рядку виключається з базису, а змінна відповідна ведучому столцю включається в базис. Перерахуємо симплекс-таблицю:
У складанні нами таблиці є негативні елементи в стовпці вільних членів, знаходимо серед них максимальний за модулем - це елемент: -0.4, він задає провідний рядок - X7. У цьому рядку також знаходимо максимальний по модулю негативний елемент: -8.3 він знаходиться в стовпці X2 який буде провідним стовпцем. Змінна в провідній рядку виключається з базису, а змінна відповідна провідному стовпцю включається в базис. Перерахуємо симплекс-таблицю:
Так як в стовпці вільних членів немає негативних елементів, то знайдено допустиме решення.В рядку F є негативні елементи, це означає що отримане рішення не оптимально. Визначимо провідний стовпець. Для цього знайдемо в рядку F максимальний по модулю негативний елемент - це -1.988 Провідним рядком буде той для якого відношення вільного члена до відповідного елементу провідного стовпця буде мінімально. Провідною рядком є X2, а ведучий елемент: 0.313.
Так як в рядку F немає негативних елементів, то знайдено оптимальне рішення. Так як початковим завданням був пошук мінімуму, то оптимальним рішенням буде вільний член рядку F, взятий з протилежним знаком: F = 1.924 при значеннях змінних рівних: x3 = 0.539, x1 = 0.153. Змінні x2 і x4 не входять до базис, тому x2 = 0 x4 = 0. Тема 11. Використання ЛП постановок для вирішення нелінійних оптимізаційних задач Якщо вдається більш складний клас завдань звести до вирішення нехай і багатьох завдань ЛП - це вважається великою вдачею - проблема зазвичай ефективно вирішується Найпростіші ідеї з цього класу: 1 .Апроксимуємо нелінійну опуклу область лінійними обмеженнями: У точках сітки беремо часткові похідні і знаходимо напрямки для аппроксимуючих лінійних обмежень 2. Розбиття нелінійної неопуклої області на кілька опуклих областей Далі їх апроксимація лінійними обмеженнями по п.1 і вирішення ЛП завдань в кожній з них. Далі вибір найкращого з отриманих рішень Матрична постановка канонічної ЛП завдання У матричному вигляді постановкa ЛПЗ має вигляд (*) при обмеженняхx Ax = b (**) Розпишемо: Тут у нас m обмежень та n змінних х при с э Rn , x э Rn, b э Rm , A = A(m,n), rankA =m, (m чи інакше x =(x1,x2,...,xn): 2.1.1 Спільне та відмінне в формалізації ЛП і МНК Спільне: - і МНК і ЛП - різновиди задач оптимізації - і ЛП і МНК застосовуються для вирішення завдань моделювання, але в разі ЛП - ми набагато більше можемо сформулювати різноманітних задач моделювання так як можливо застосувати обмеження на область моделювання (нерівності) - природний елемент ЗЛП - це дуже цікаво, в цьому розділі ми в цьому переконаємося. Відмінності: - Оптимізаційна постановка МНК визначає функціонал завдання як , де складові вектора нев'язок умовної системи рівнянь чи Ця система визначає перевизначену систему – тобто тут число обмежень- вимог m (точок х) до рішення – m > n - число змінних системи, і, тобто, більше ніж число шуканих параметрів при них (тобто розмірності вектора А) Т.ч. в постановці МНК ми маємо таку специфічну форму задачі оптимізації коли у нас немає допустимих рішень - і ми знаходимо найкраще з неприпустимих (далі ми нагадаємо механізм такого підходу) А ось в задачі ЛП коли mобмежень> nзмінних - рішення немає і нічого знайти не можна так як немає допустимої області рішень. Тобто рішення оптимізаційної задачі в формі ЗЛП може бути застосовано тільки при недовизначеною системі типу (0) тобто коли mобмежень< nзмінних Тоді для ЛП задачі є ОДР. 2.2.2 Підходи до вирішення несумісних оптимізаційних задач Розглянемо задачу з лінійним ф-лом б (*) і обмеженнями Ax = b (**) і нехай при цьому маємо ситуацію mобмежень> nзмінних Спроба вирішувати її через ЗЛП в лоб впирається в несумісність (**) і відсутність ОДР так як m> n Тоді ввівши в Ax = * = b невязки - вектор вектор у = Ax - b маємо 2 шляхи вирішенняпроблеми: Варіант типу МНК:Метод безумовної оптимізації при несумісною системі обмеженьСформуємо безумовний критерій L= і будемо вимагати його мінімізації - тут ввели "у2" - так як невязка може бути і + і - або правильнішеДалі як і в МНК беруться похідні і прирівнюючи їх нулю - одержуємо систему лінійних рівнянь щодо хЗалишається питання балансування вимог до нашої задачі – 1.Мінімізаціі вихідного критерію стх і 2. Мінімізації нев'язок у = Ax – b Це питання вибору вектора параметрів , в тривіальному випадку беремо всі Другий варіант – Використання ЗЛП для оптимізації при несумісною системі обмежень І так - маємо лінійний ф-л (*) и обмеження Ax = b (**) при mогр>nпер як ми відмічали вище - при такому випадку нема ОДР так як (**) не можуть бути задовільнені. Але якщо розглянути мінімізацію вхідного функціоналу и модулю вектору нев’язок у =/ Ax - b /----тоді можливо одержати задачу вже в класі вирішуємих ЛП задач. Тут маємо на увазі наступне: 1.Після введення в обмеження Ax = b (**) вектора у в якості невязки у=Ax - b сформуємо завдання вже з цією нев'язкою - ЗЛП (:) (про зміст цього завдання трохи пізніше) 2. І розуміючи, що система (:) може бути еквівалентно приведена до канонічної формі (: *) то для завдання ЛП (: *) ми будемо мати вже кількість mобмежень< nзмінних тобто тут ОДР формально з'явилася !!!!!! (:*) (1***) (:) (2***) Тепер повернемося до (:). Записали таку покручену задачу (:) і розмірковуємо: Нехай одне зі складових векторної нерівності Ax - b >0, тоді щоб виконувалося відповідне обмеження типу (1 ***), відповідний "у" зобов'язаний бути деяким (+) і таким при цьому, щоб у> Ax - b, тільки тоді (1***) буде виконуватися. При цьому відмічаємо, що ЗЛП працює на мінімізацію "у" через верхній нерівності (1***)), а відповідна нижня нерівність (2 ***) виконується автоматично. Зауважимо, що мінімізація "у" працює на максимально можливе виконання (**), а якщо ж виходить так, що одне зі складових нерівності Ax - b <0 то відповідний "у" уже в (2 ***) також зобов'язаний бути (+) і таким (+) щоб «у» був > - (Ax - b), тільки тоді нерівність (2 ***) виконається і при цьому ЗЛП працює на мінімізацію "у" нерівності (2 ***) (також при цьому працюючи на максимально можливе виконання (**)), а відповідне верхнє (1 ***) автоматом виконується Таким чином в (:) мінімізується модуль невязки "у" тому що структура нерівностей системи (:), як бачимо завжди забезпечує Таким чином вбиваємо 2 зайців - здійснюємо мінімізацію вхідного функціонаалу і модуля вектора нев'язок у =/ Ax - b / Виникає однак як і в першому випадку необхідність балансувати вхідний критерій стх з вимогою мінімізації нев'язки у - цей компроміс є питання вибору вектора коефіцієнтів . У тривіальному випадку візьмемо все Далі цікавий окремий випадок вище наведеної задачі жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|