МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт з виконання Лабораторної роботи №6 на тему: МЕТОДИ УМОВНОЇ ОПТИМІЗАЦІЇ з курсу: «Методи синтезу та оптимізації» 1. МЕТА РОБОТИ Навчитися використовувати методи умовної оптимізації при знаходженні екстремумів функцій багатьох змінних з обмеженнями. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ ГРАДІЄНТНІ МЕТОДИ ПОШУКУ ЕКСТРЕМУМІВ Критерії оптимальності в задачах з обмеженнями У методичних вказівках до лабораторної роботи № 4 було розглянуто необхідні і достатні умови оптимальності рішень оптимізаційних задач без обмежень. Однак ряд інженерних задач пов'язаний з оптимізацією при наявності деякої кількості обмежень на керовані змінні. Такі обмеження істотно зменшують розміри області, у якій проводиться пошук оптимуму. На перший погляд може здатися, що зменшення розмірів допустимої області повинне спростити процедуру пошуку оптимуму. Тим часом, навпаки, процес оптимізації стає більш складним, оскільки установлені вище критерії оптимальності не можна використовувати при наявності обмежень. При цьому може порушуватися навіть основна умова, відповідно до якого оптимум повинний досягатися в стаціонарній точці, що характеризується нульовим градієнтом. Наприклад, безумовний мінімум функції f(x)=(x—2)2 має місце в стаціонарній точці х=2. Але якщо задача мінімізації розв’язується з урахуванням обмеження х>4, то буде знайдений умовний мінімум, якому відповідає точка х=4. Ця точка не є стаціонарною точкою функції f, тому що f’(4)=4. Нижче досліджуються необхідні і достатні умови оптимальності рішень задач з обмеженнями. Виклад починається з розгляду, задач оптимізації, що містять тільки обмеження у виді рівностей. Знайти мінімум функції двох змінних
(48) при наступних обмеженнях
(49) Запишемо дану задачу у стандартному вигляді задачі нелінійного програмування
,
,
,
. Для отримання розв’язку задачі з використанням умов Куна-Таккера нам необхідно вирахувати наступні значення похідних
,
,
,
. Умови Куна-Таккера для нашого випадку запишуться у вигляді
Враховуючи дане рівняння, перші дві умови Куна-Таккера запишемо наступним чином
,
. В загальному, умови Куна-Таккера набувають вигляду
,
,
,
,
,
,
,
,
,
,
. Аналізуючи обмеження на
, можна покласти
, тоді остання рівність виконується для довільного
, в тому числі і для
. Допустимі рішення
і
будемо шукати з двох попередніх рівностей. Припустивши, що
, ми прийдемо до системи нелінійних рівнянь
,
, Розв’яжемо цю систему: Підставимо значення
, знайдене з 2-го рівняння, у перше
, тобто
, або

. Зрозуміло, що другий розв’язок
не задовольняє умову задачі (
і має бути додатнім). Отже, маємо наступне допустиме рішення для
:
Тоді
. Аналізуючи обмеження
, від’ємне значення
відкидаємо. Таким чином, маємо одне допустиме рішення
,
. Підставимо ці значення
і
в перші дві умови Куна-Таккера і знайдемо
і
(
ми поклали рівним нулю).
. Домножимо друге рівняння на
і знайдемо
, додавши два рівняння системи

. Нагадаємо, суттєвим є те, що
і
мають бути більші або рівні нуля.

.
Зрозуміло, що коефіцієнти у цьому рівнянні в лівій частині додатні, отже
. Якби
було більше нуля, потрібно було б знайти
і пересвідчитись, чи воно більше нуля. Таким чином у даному випадку для еквівалентності початкової задачі Куна-Таккера не виконуються умови теореми необхідності Куна-Таккера. Розв’язок вихідної задачі не може бути розв’язком задачі Куна-Таккера. У випадку, коли б ми отримали додатні
, нам потрібно було б перевірити виконання достатньої умови Куна-Таккера про еквівалентність задач.. Ця умова полягає у додатній напіввизначеності матриці Гессе функції
, тобто визначник цієї матриці повинен бути більший або рівний нулеві. Відомо, матриця Гессе
– це матриця других похідних, і для даної функції

, а її визначник
, тобто, вона є додатньо визначеною. Отже, для даного прикладу матриця Гессе додатньо визначена, але не виконуються необхідні умови Куна-Таккера. Тому для розв’язання даної задачі необхідно використовувати інші методи (наприклад, метод штрафних функцій). 3. ЛАБОРАТОРНЕ ЗАВДАННЯ # 4 Розв’язати задачу умовної багатопараметричної оптимізації для функції двох змінних
, з наступними обмеженнями
Запишемо дану задачу у стандартному вигляді задачі нелінійного програмування
,
,
,
. Для отримання розв’язку задачі з використанням умов Куна-Таккера нам необхідно вирахувати наступні значення похідних
,
,
,
,
. Умови Куна-Таккера (12) для нашого випадку запишуться у вигляді
Враховуючи дане рівняння, перші дві умови Куна-Таккера запишемо наступним чином
,
. В загальному, умови Куна-Таккера набувають вигляду
,
,
,
,

,
,
,
,
,
. Допустимі рішення
і
будемо шукати з двох попередніх рівностей. Припустивши, що
, та
ми прийдемо до системи нелінійних рівнянь
,
, Виражаємо з другого рівняння
, тоді перше рівняння буде мати вигляд:
,




Отримані значення
,
. Знайдемо матрицю Гессе:
, її визначник
, тобто вона є додатньо визначеною. Отже, для даного прикладу матриця Гессе додатньо визначена. 5. ВИСНОВОК На цій лабораторній роботі, я навчився використовувати методи умовної оптимізації при знаходженні екстремумів функцій багатьох змінних з обмеженнями.