Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Методи синтезу та оптимізації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Методи умовної оптимізації
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 6
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САПР
Протокол № 1 від 28.08.2008 р.
ЛЬВІВ 2008
Методи умовної оптимізації. Методичні вказівки до лабораторної роботи № 6 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к.т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. н., доцент.
Відповідальний за випуск: Ткаченко С. П., к.т. н., доцент.
Рецензенти: Каркульовський В. І., к.т. н., доцент,
Стех Ю. В., к.т. н., доцент.
1. МЕТА РОБОТИ
Навчитися використовувати методи умовної оптимізації при знаходженні екстремумів функцій багатьох змінних з обмеженнями
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Критерії оптимальності в задачах з обмеженнями
У методичних вказівках до лабораторної роботи № 4 було розглянуто необхідні і достатні умови оптимальності рішень оптимизаційних задач без обмежень. Однак ряд інженерних задач пов'язаний з оптимізацією при наявності деякої кількості обмежень на керовані змінні. Такі обмеження істотно зменшують розміри області, у якій проводиться пошук оптимуму. На перший погляд може здаатися, що зменшення розмірів доустимої області повинне спростити процедуру пошуку оптимуму. Тим часом, навпаки, процес оптимізації стає більш складним, оскільки установлені вище критерії оптимальності не можна використовувати при наявності обмежень. При цьому може порушуватися навіть основна умова, відповідно до якого оптимум повинний досягатися в стаціонарній точці, що характеризується нульовим градієнтом. Наприклад, безумовний мінімум функції f(x)=(x—2)2 має місце в стаціонарній точці х=2. Але якщо задача мінімізації розв’язується з урахуванням обмеження х>4, то буде знайдений умовний мінімум, якому відповідає точка х=4. Ця точка не є стаціонарною точкою функції f, тому що f’(4)=4. Нижче досліджуються необхідні і достатні умови оптимальності рішень задач з обмеженнями. Виклад починається з розгляду, задач оптимізації, що містять тільки обмеження у виді рівностей.
Задачі з обмеженнями у виді рівностей
Розглянемо загальну задачу оптимізації, що містить декілька обмежень у виді рівностей:
мінімізувати
при обмеженнях . . (1)
Ця задача в принципі може бути вирішена як задача безумовної оптимізації, отримана шляхом виключення з цільової функції незалежних змінних за допомогою заданих рівностей. Наявність обмежень у виді рівностей фактично дозволяє зменшити розмірність вихідної задачі з N до N-K. Оскільки при цьому виникає задача безумовної оптимізації, то для ідентифікації точки оптимуму можна використовувати методи для оптимізації без обмежень. Як ілюстрацію, розглянемо наступний приклад.
Приклад 1.
Мінімізувати
при обмеженні .
Виключивши змінну x3 за допомогою рівняння , одержимо оптимізаційну задачу з двома змінними без обмежень
.
Для ідентифікації точки оптимуму досліджуваної функції можна використовувати один з методів безумовної мінімізації.
Метод виключення змінних можна застосувати лише в тих випадках, коли рівняння, що представляють обмеження, можна розв’язати щодо деякого конкретного набору незалежних змінних. При наявності великого числа обмежень у виді рівностей процес виключення змінних стає дуже трудомісткою процедурою. Крім того, можливі ситуації, коли рівняння не вдається розв’язати щодо змінної. Зокрема, якщо в Прикладі 1 обмеження задати у виді
,
то одержати аналітичнийе вираз якої-небудь зі змінних через інші неможливо. Таким чином, при рішенні задач, що містять складні обмеження у виді рівностей, доцільно використовувати метод множників Лагранжа, опис якого дається в наступному розділі.
Множники Лагранжа
За допомогою методу множників Лагранжа власне кажучи встановлюються необхідні умови, що дозволяють ідентифікувати токи оптимуму в задачах оптимізації з обмеженнями у виді рівностей. При цьому задача з обмеженнями перетвориться в еквівалентну задачу безумовної оптимізації, у якій фігурують деякі невідомі параметри, які називаються множниками Лагранжа.
Розглянемо задачу мінімізації функції N змінних з врахуванням одного обмеження у виді рівності:
мінімізувати (2)
при обмеженні . (3)
Відповідно до методу множників Лагранжа ця задача перетвориться в наступну задачу безумовної оптимізації:
мінімізувати
(4)
Функція L(x; v) називається функцією Лагранжа, v - невідома постійна, яка називається множником Лагранжа. На знак v ніяких вимог не накладається.
Нехай при заданому значенні безумовний мінімум функції по х досягається в точці і задовольняє рівнянню . Тоді, як неважко бачити, мінімізує з врахуванням , оскільки для всіх значень х, що задовольняють , і minL(x; v) = minf(x).
Зрозуміло, необхідно підібрати значення, таким чином, щоб координата точки безумовного мінімуму задовольняла рівності (3). Це можна зробити, якщо, розглядаючи v як змінну, знайти безумовний мінімум функції (4) у виді функції v, а потім вибрати значення v, при якому виконується рівність (2). Проілюструємо це на конкретному прикладі.
Приклад 2.
Мінімізувати
при обмеженні
Відповідна задача безумовної оптимізації записується в наступному виді:
Мінімізувати .
Розв’язок. Прирівнявши дві компоненти градієнта L до нуля, одержимо
,
.
Для того щоб перевірити, чи відповідає стаціонарна точка х° мінімуму, обчислимо елементи матриці Гессе функції L(x; v), розглянутої як функції від х,
,
яка виявляється додатно визначеною. Це означає, що L(x; v) - опукла функція х. Отже, координати і визначають точку глобального мінімуму. Оптимальне значення v знаходиться шляхом підстановки значень у рівняння , звідки 2v+v/2=2 чи . Таким чином, умовний мінімум досягається при , і дорівнює .
При рішенні задачі з Приклада 2 ми розглядали L(x; v) як функцію двох змінних і і, крім того, припускали, що значення параметра v обрано так, щоб виконувалося обмеження. Якщо ж рішення системи
у виді явних функцій v одержати не можна, то значення х і v знаходяться шляхом рішення наступної системи, яка складається з N+1 рівнянь з N +l невідомими:
, .
Для знаходження всіх можливих розв’язків даної системи можна використовувати чисельні методи одномірного пошуку (наприклад, метод Ньютона). Для кожного з розв’язків (, ) необхідно обчислити елементи матриці Гессе функції L, розглянутої як функція х, і з'ясувати, чи є ця матриця додатно визначеною (локальний мінімум) чи від’ємно визначеною (локальний максимум).
Приклад 3.
Мінімізувати
при обмеженні .
Рішення
,
Ця система трьох рівнянь із трьома невідомими має два рішення:
,
Матриця Гессе функції L(x; v), розглянутої як функція , дорівнює
.
Обчисливши елементи матриці для кожного з двох рішень, знаходимо, що матриця
додатно визначена, а матриця-
від’ємно визначена.
Отже, відповідає максимуму функції L, розглянутої як функція х; оптимальне рішення . (Зауважимо, що відповідає мінімуму L).
Тут необхідно підкреслити, що якщо ми розглянемо L як функцію трьох змінних, а саме змінних і v, то точки і не виявляться точками мінімуму чи максимуму L як функції х і v. Насправді вони є сідловими точками функції L(x; v).
Метод множників Лагранжа можна поширити на випадок, коли задача має декілька обмежень у виді рівностей. Розглянемо загальну задачу, у якій потрібно
мінімізувати
при обмеженнях . (5)
Функція Лагранжа приймає наступний вид:
(6)
Тут - множники Лагранжа, тобто невідомі параметри, значення яких необхідно визначити. Прирівнюючи часткові похідні L по х до нуля, одержуємо наступну систему N рівнянь з N невідомими:
,
, (7)
......................
.
Якщо знайти рішення наведеної вище системи у виді функцій вектора v виявляється неможливим, то можна розширити систему шляхом включення в неї обмежень у виді рівностей
,
, (8)
.................
.
Рішення розширеної системи, що складається N+K рівнянь з N+K невідомими, визначає стаціонарну точку функції L. Потім реалізується процедура перевірки на мінімум чи максимум, що проводиться на основі обчислення елементів матриці Гессе функції L, розглянутої як функція х, подібно тому, як це було пророблено у випадку задачі з одним обмеженням. Для деяких задач розширена система N+K рівнянь з N+K невідомими може не мати рішень, і метод множників Лагранжа виявляється непридатним. Слід, однак, відзначити, що такі задачі на практиці зустрічаються досить рідко.
Умови Куна-Таккера
У попередньому розділі було встановлено, що множники Лагранжа можна використовувати при побудові критеріїв оптимальності для задач оптимізації з обмеженнями у виді рівностей. Кун і Таккер узагальнили цей підхід на випадок загальної задачі нелінійного програмування з обмеженнями як у виді рівностей, так і у виді нерівностей. Розглянемо наступну загальну задачу нелінійного програмування
мінімізувати f(x) (9)
при обмеженнях , (10)
. (11)
Обмеження у виді нерівності називається активним чи зв’язуючим у точці х, якщо g}(x)=0, і неактивним, чи незв’язуючим, якщо .
Якщо існує можливість знайти обмеження, що неактивні в точці оптимуму, до безпосереднього рішення задачі, то ці обмеження можна виключити з моделі і тим самим зменшити її розмірність. Основні труднощі полягають при цьому в ідентифікації неактивних обмежень, що передує рішенню задачі.
Кун і Таккер побудували необхідні і достатні умови оптимальності для задач нелінійного програмування, виходячи з припущення про диференційованість функцій , і . Ці умови оптимальності, широко відомі як умови Куна-Таккера, можна сформулювати у виді задачі знаходження рішення деякої системи нелінійних рівнянь і нерівностей, чи, як іноді говорять, задачі Куна-Таккера.
Умови Куна - Таккера і задача Куна - Таккера
Знайти вектори , , , що задовольняють наступним умовам:
, (12)
, (13)
, (14)
, (15)
. (16)
Спочатку проілюструємо умови Куна - Таккера на прикладі.
Приклад 4.
Мінімізувати
при обмеженнях , , .
Рішення. Записавши дану задачу у виді задачі нелінійного програмування (9)-(11), одержимо
, ,
, ,
,
, .
Рівняння (12), що входить до складу умов Куна Таккера, приймає наступний вид:
,
звідки
,
.
Нерівності (13) і рівняння (14) задачі Куна-Таккера в даному випадку записуються у виді
, , .
Рівняння (15), відомі як умова нежорсткості, що доповнює, приймають вид
, .
Зауважимо, що на змінні і накладається вимога невід’ємності, тоді як обмеження на знак відсутнє.
Таким чином, для задачі з приклада 4 умови Куна-Таккера записуються в наступному виді:
,
,
, , ,
, ,
, ,
обмежень на знак немає.
Інтерпретація умов Куна — Таккера
Для того щоб інтерпретувати умови Куна-Таккера, розглянемо задачу нелінійного програмування з обмеженнями у виді рівностей:
мінімізувати
при обмеженнях .
Запишемо умови Куна-Таккера
, (17)
. (18)
Далі розглянемо функцію Лагранжа для задачі нелінійного програмування з обмеженнями у виді рівностей
.
Для цієї функції умови оптимальності першого порядку записуються у виді
,
.
Неважко бачити, що умови Куна-Таккера (17) і (18) збігаються з умовами оптимальності першого порядку для задачі Лагранжа.
Розглянемо задачу нелінійного програмування з обмеженнями у виді нерівностей:
мінімізувати
при обмеженнях .
Запишемо умови Куна-Таккера
.
, .
Відповідна функція Лагранжа має вид
.
Умови оптимальності першого порядку записуються як
,
.
Зауважимо, що - множник Лагранжа, що відповідає обмеженню . У попередньому розділі було показано, що представляє неявну ціну, асоційовану з обмеженням ; іншими словами, величина відбиває зміну мінімального значення цільової функції , викликану одиничним збільшенням правої частини -го обмеження.
Якщо припустити, що -е обмеження є неактивним (тобто ), то і . З іншого боку, якщо -е обмеження активне (тобто ), то відповідна неявна ціна не обов'язково дорівнює нулю, однак тому що . Таким чином,
для всіх значень .
Для того щоб визначити знак (неявної ціни, асоційованої з обмеженням ), варто збільшити праву частину обмеження від 0 до 1. Ясно, що при цьому область припустимих рішень звужується, оскільки будь-яке рішення, що задовольняє обмеженню автоматично задовольняє нерівності . Отже, розміри допустимої області зменшуються, і мінімальне значення поліпшити неможливо (тому що взагалі воно може тільки зростати). Іншими словами, неявна ціна , асоційована з -м обмеженням, повинна бути додатною, що відповідає умовам Куна-Таккера.
Теореми Куна-Таккера
У попередньому розділі побудовані умови Куна-Таккера для задач умовної оптимізації. За допомогою методу множників Лагранжа отримане інтуїтивне представлення про те, що умови Куна-Таккера тісно пов'язані з необхідними умовами оптимальності. У даному розділі розглядаються строгі формулювання необхідних і достатніх умов оптимальності рішення задачі нелінійного програмування.
Теорема 1. Необхідність умов Куна-Таккера.
Розглянемо задачу нелінійного програмування (9) - (11). Нехай , g і h - диференційовані функції, а х* - допустиме рішення даної задачі. Покладемо . Далі нехай при і при лінійно незалежні. Якщо х* - оптимальне рішення задачі нелінійного програмування, то існує такая пари векторів (і*, v*), що ( *, і*, v*) є рішенням задачі Куна - Таккера (12) - (16).
Умова, відповідно до якої при і при повинні бути лінійно незалежними, відома як умова лінійної незалежності і власне кажучи являє собою деяку умову регулярності допустимої області, що майже завжди виконується для задач, що зустрічаються на практиці. Однак взагалі перевірка виконання умови лінійної незалежності дуже тяжка, тому що потрібно, щоб оптимальне рішення задачі було відоме заздалегідь. Разом з тим умова лінійної незалежності завжди виконується для задач нелінійного програмування, що володіють наступними властивостями.
Всі обмеження у виді рівностей і нерівностей містять лінійні функції.
Всі обмеження у виді нерівностей містять увігнуті функції, всі обмеження-рівності - лінійні функції, а також існує принаймні одна допустима точка х, що розташована у внутрішній частині області, обумовленої обмеженнями-нерівностями. Іншими словами, існує така точка х, що при і при .
Якщо умова лінійної незалежності в точці оптимуму не виконується, то задача Куна-Таккера може не мати рішення.
Приклад 5.
Мінімізувати
при обмеженнях ,
, .
Рішення. На рис. 1 зображена область допустимих рішень сформульованої вище нелінійної задачі. Ясно, що оптимальне рішення цієї задачі є , і . Покажемо, що умова лінійної незалежності не виконується в точці оптимуму.
1
Рис. 1. Допустима область у задачі з приклада 5.
Тому що , і , то I= {1,3}.
Далі , .
Легко бачити, що вектори і лінійно залежні, тобто умова лінійної незалежності в точці х*=(1, 0) не виконується.
Запишемо умови Куна-Таккера і перевіримо, чи виконуються вони в точці (1, 0). Умови (12), (15) і (16) приймають наступний вид:
, (19)
, (20)
, (21)
, (22)
, (23)
, (24)
При х* = (1, 0) з рівняння (19) випливає, що , тоді як рівняння (22) дає . Отже, точка оптимуму не є точкою Куна - Таккера.
Зауважимо, що порушення умови .лінійної незалежності не обов'язково означає, що точка Куна-Таккера не існує. Для того щоб підтвердити це, замінимо цільову функцію з приклада 2 функцією . При цьому оптимум як і раніше досягається в точці (1,0), у якій умова лінійної незалежності не виконується. Умови Куна-Таккера (20) - (24) залишаються незмінними, а рівняння (19) приймає вид
.
Неважко перевірити, що точка х*=(1, 0), u*=(0, 0, 0) є точкою Куна-Таккера, тобто задовольняє умовам Куна-Таккера.
Теорема про необхідність умов Куна-Таккера дозволяє ідентифікувати неоптимальні точки. Іншими словами, теорему 1 можна використовувати для доказу того, що задана припустима точка, що задовольняє умові лінійної незалежності, не є оптимальною, якщо вона не задовольняє умовам Куна-Таккера. З іншого боку, якщо в цій точці умови Куна-Таккера виконуються, то немає гарантії, що знайдене оптимальне рішення нелінійної задачі. Як приклад розглянемо наступну задачу нелінійного програмування.
Приклад 6
Мінімізувати
при обмеженні .
Рішення. Тут , .
Запишемо умови Куна-Таккера:
, (25)
(26)
, (27)
, (28)
, (29)
Тому що обмеження містять лінійні функції, умова лінійної незалежності виконується у всіх допустимих точках. Легко бачити, що х=3 - точка оптимуму. Розглянемо допустиме рішення х=2. Для того щоб довести його неоптимальність, перевіримо виконання умов Куна-Таккера (25) - (29). З рівнянь (27) і (28) випливає, що , однак значення х=2; не задовольняють рівнянню (25). Отже, по теоремі 1 точка не може бути оптимальною.
З іншого боку, рішення задовольняє системі (25) - (29) і, отже, визначає точку Куна-Таккера, однак оптимальним не є. Відповідно до теореми 1, умови Куна-Таккера повинні виконуватися в точці оптимуму х=3. Неважко перевірити, що рішення задовольняє умовам Куна-Таккера.
Наступна теорема встановлює умови, при виконанні яких точка Куна - Таккера автоматично відповідає оптимальному рішенню- задачі нелінійного програмування.
Теорема 2. Достатність умов Куна-Таккера
Розглянемо задачу нелінійного програмування (9)-(11). Нехай цільова функція f(x) опукла, всі обмеження у виді нерівностей містять увігнуті функції , a обмеження у виді рівностей містять лінійні функції . Тоді якщо існує рішення (х*, і*, v*), що задовольняє умовам Куна-Таккера (12) - (16), то х* - оптимальне рішення задачі нелінійного програмування.
Якщо умови теореми 2 виконуються, то знаходження точки Куна-Таккера забезпечує одержання оптимального рішення задачі нелінійного програмування. Теорему 2 можна також використовувати для доказу оптимальності даного рішення задачі нелінійного програмування. Як ілюстрацію знову розглянемо приклад 6:
мінімізувати
при обмеженнях ,
,
.
За допомогою теореми 2 доведемо, що рішення , є оптимальним. Маємо
, .
Тому що матриця додатно напіввизначена при всіх х, функція f(x) виявляється опуклою. Перше обмеження у виді нерівності містить лінійну функцію , що одночасно є як опуклою, так і увігнутою. Для того щоб показати, що функція є увігнутою, обчислимо
, .
Оскільки матриця від’ємно визначена, функція є увігнутою. Функція входить у лінійне обмеження у виді рівності. Отже, всі умови теореми 2 виконані; якщо ми покажемо, що х*=(1, 5) - точка Куна-Таккера, то дійсно встановимо оптимальність рішення х*. Умови Куна-Таккера для приклада 4 мають вид
, (30)
(31)
, (32)
, (33)
, (34)
, (35)
(36)
, (37)
Точка х* = (1, 5) задовольняє обмеженням (32) - (34) і, отже, є припустимої. Рівняння (30) і (31) приймають наступний вид:
,
Поклавши , одержимо і . Таким чином, рішення х*=(1, 5), і* = (2.2, 0.1) і задовольняє умовам Куна-Таккера. Оскільки умови теореми 2 виконані, то х*=(1, 5) - оптимальне рішення задачі з приклада 4. Зауважимо існують також і інші значення і , що задовольняють системі (30) - (37).
Зауваження
Для задач, що зустрічаються на практиці, умова лінійної незалежності, як правило, виконується. Якщо в задачі усі функції диференційовані, то точку Куна-Таккера варто розглядати як можливу точку оптимуму. Таким чином, багато з методів нелінійного програмування сходяться до точки Куна-Таккера. (Тут доречно провести аналогію з випадком безумовної оптимізації, коли відповідні алгоритми дозволяють визначити стаціонарну точку).
Якщо умови теореми 2 виконані, точка Куна-Таккера в той же час виявляється точкою глобального мінімуму. На жаль, перевірка достатніх умов дуже тяжка, і, крім того, прикладні задачі часто не мають необхідних властивостей. Слід зазначити, що наявність хоча б одного нелінійного обмеження у виді рівності приводить до порушення припущення теореми 2.
Достатні умови, встановлені теоремою 2, можна узагальнити на випадок задач з неопуклими функціями, що входять в обмеження у виді нерівностей, неопуклими цільовими функціями і нелінійними обмеженнями-рівностями. При цьому використовуються такі узагальнення опуклих функцій, як квазіопуклі і псевдоопуклі функції.
Методи штрафних функцій
Існування ефективних алгоритмів рішення безумовних задач оптимізації є передумовою використання цих методів для рішення умовних задач після деякого перетворення умовної задачі до еквівалентній їй безумовній задачі.
Нехай необхідно знайти розв’язок задачі
, (38)
у якій цільова функція і функції в системі обмежень являють собою опуклі функції (бажано).
Основна ідея методу штрафних функцій полягає в наступному. Будують допоміжну функцію
, (39)
таку, що наближене рішення задачі (38) виходить у результаті рішення послідовності задач безумовної мінімізації функції (39)
. (40)
У методі зовнішніх штрафних функцій функції і вибираються таким чином, щоб вони ставали відмінними від нуля (позитивними) при порушенні відповідного обмеження. А тому що ми мінімізуємо (39), то рух убік порушення обмеження стає невигідним. Усередині допустимої області в даному методі функції і повинні бути рівні нулю. Наприклад, для обмежень нерівностей:
при . (41)
Наближене рішення задачі (38) виходить у результаті рішення послідовності задач (40) при , . Відповідні методи називають ще методами зовнішньої точки.
У методі бар'єрних функцій функції і вибираються відмінними від нуля в допустимій області і такими, щоб при наближенні до границі допустимої області (зсере дини) вони зростали, пе реш коджаючи виходу при пошуку за границю області. У цьому випадку ці функції повинні бути малими (додатніми чи від’ємними) усередині допустимої області і великими додатніми поблизу границі (усередині області). Наприклад, для обмежень нерівностей:
при . (42)
Такі методи називають ще методами внутрішньої точки. В алгоритмах, що використовує функції штрафу даного типу, вимагають, щоб у процесі пошуку точка завжди залишалася внутрішньою точкою допустимої області. Наближене рішення задачі (38) виходить у результаті рішення послідовності задач (40) при , .
При виборі функцій штрафів для обмежень рівностей звичайно вимагають, щоб
при . (43)
Це можуть бути, наприклад функції виду:
,
,
, (44)
при парному .
Для обмежень нерівностей функції штрафу підбирають таким чином, щоб
;
. (45)
Цій вимозі відповідають функції виду:
,
,
(46)
, при парному .
Як бар'єрні функції для обмежень нерівностей можуть служити функції виду:
,
. (47)
Послідовність дій при реалізації методів штрафних чи бар'єрних функцій виглядає в такий спосіб:
На підставі задачі (38) будуємо функцію (39). Вибираємо початкове наближення і початкові значення коефіцієнтів штрафу .
Вирішуємо задачу (40).
Якщо отримане рішення не задовольняє системі обмежень у випадку використання методу штрафних функцій, то збільшуємо значення коефіцієнтів штрафу і знову вирішуємо задачу (40). У випадку методу бар'єрних функцій значення коефіцієнтів зменшуються, щоб можна було одержати рішення на границі.
Процес припиняється, якщо знайдене рішення задовольняє системі обмежень з визначеною точністю.
На завершення, розглянемо типовий приклад із завдань лабораторної роботи на знаходження мінімального значення функції двох змінних з використанням умов Куна-Таккера.
Приклад 7.
Знайти мінімум функції двох змінних
(48)
при наступних обмеженнях
(49)
Запишемо дану задачу у стандартному вигляді задачі нелінійного програмування
,
,
,
.
Для отримання розв’язку задачі з використанням умов Куна-Таккера нам необхідно вирахувати наступні значення похідних
,
,
,
.
Умови Куна-Таккера (12) для нашого випадку запишуться у вигляді
Враховуючи дане рівняння, перші дві умови Куна-Таккера запишемо наступним чином
,
.
В загальному, умови Куна-Таккера набувають вигляду
,
,
,
,
,
,
,
,
, , .
Аналізуючи обмеження на , можна покласти , тоді остання рівність виконується для довільного , в тому числі і для . Допустимі рішення і будемо шукати з двох попередніх рівностей. Припустивши, що , ми прийдемо до системи нелінійних рівнянь
,
,
Розв’яжемо цю систему: Підставимо значеня , знайдене з 2-го рівняння, у перше
, тобто , або
.
Зрозуміло, що другий розв’язок не задовільняє умову задачі ( і має бути додатнім).
Отже, маємо наступне допустиме рішення для : Тоді . Аналізуючи обмеження , від’ємне значення відкидаємо. Таким чином, маємо одне допустиме рішення
, .
Підставимо ці значення і в перші дві умови Куна-Таккера і знайдемо і ( ми поклали рівним нулю).
.
Домножимо друге рівняння на і знайдемо , додавши два рівняння системи
.
Нагадаємо, суттєвим є те, що і мають бути більші або рівні нуля.
.
Зрозуміло, що коефіцієнти у цьому рівнянні в лівій частині додатні, отже . Якби було більше нуля, потрібно було б знайти і пересвідчитись, чи воно більше нуля.
Таким чином у даному випадку для еквівалентності початкової задачі задачі Куна-Таккера не виконуються умови теореми необхідності Куна-Таккера. Розв’язок вихідної задачі не може бути розв’язком задачі Куна-Таккера.
У випадку, коли б ми отримали додатні , нам потрібно було б перевірити виконання достатньої умови Куна-Таккера про еквівалентність задач.. Ця умова полягає у додатьній напіввизначеності матриці Гессе функції , тобто визначник цієї матриці повинен бути більший або рівний нулеві. Відомо, матриця Гессе – це матриця других похідних, і для даної функції
,
а її визначник , тобто, вона є додатньо визначеною.
Отже, для даного прикладу матриця Гессе додатньо визначена, але не виконуються необхідні умови Куна-Таккера. Тому для розв’язання даної задачі необхідно використовувати інші методи (наприклад, метод штрафних функцій).
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Поясніть труднощі, які виникають при використанні методу множників Лагранжа для розв’язку задач з невід’ємними змінними.
3.2. Вкажіть, як використовується матриця Гессе для встановлення мінімуму чи максимуму досліджуваної функції.
3.3. Проінтерпретуйте умови Куна-Таккера для задачі нелінійного програмування з обмеженнями у виді рівностей.
3.4. Сформулюйте необхідні і достатні умови оптимальності рішення задачі нелінійного програмування (теореми Куна-Таккера).
3.5. Вкажіть необхідні умови існування точки Куна - Таккера.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
4.1. Набрати, скомпілювати та запустити програму, що розв’язує завдання, видане викладачем.
4.2. Пояснити дії, які виконує програма.
4.3. Перевірити достовірність одержаного результату.
5. ЗМІСТ ЗВІТУ
5.1. Титульний лист.
5.2. Мета роботи, теоретичні відомості.
5.3. Лабораторне завдання.
5.4. Програма і результат її роботи.
5.5. Висновок.
6. ЛІТЕРАТУРА
1. Д. Химмельблау. Прикладное нелинейное программирование . Пер. с англ. М.: Мир, 1975. – 536 с.
2. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1986. – 352 с.
3. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 2. Пер. с англ. – М.: Мир, 1986. – 320 с.
4. Полак Э. Численные методы оптимизации. Пер. с англ. – М.: Мир, 1974. – 376 с.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора