Південно-Уральський Державний Університет
Кафедра АМУ
реферат на тему:
Нелінійне програмування
Виконав: Пушник А. А., ПС-263.
Перевірив: Різностатевих О.А.
Челябінськ - 2003.
Зміст
1. Постановка задачі нелінійного програмування
2. Критерії оптимальності в задачах з обмеженнями
2.1. Завдання з обмеженням у вигляді рівностей
2.2. Множники Лагранжа
3. Умови Куна-Таккера
3.1. Умови Куна-Таккера і завдання Куна-Таккера
3.2. Інтерпретація умов Куна-Таккера
3.3. Теореми Куна-Таккера
4. Функції декількох змінних
4.1. Методи прямого пошуку
4.1.1. Метод пошуку по симплекс (S2 - метод)
4.1.2. Метод пошуку Хука-Дживса
1. Постановка задачі нелінійного програмування.
В задачі нелінійного програмування (НЛП) потрібно знайти значення багатовимірної змінної х = (), що мінімізує цільову функцію f (x) при умовах, коли на змінну х накладені обмеження типу нерівностей
, i = 1,2, ..., m (1)
а змінні, тобто компоненти вектора х, ненегативні:
(2)
Іноді у формулюванні задачі обмеження (1) мають протилежні знаки нерівностей. Враховуючи, однак, що якщо, то, завжди можна звести задачу до нерівностям одного знака. Якщо деякі обмеження входять в задачу зі знаком рівності, наприклад, то їх можна представити у вигляді пари нерівностей, , Зберігши тим самим типову формулювання завдання.
2. Критерії оптимальності в задачах з обмеженнями.
Ряд інженерних задач пов'язаний з оптимізацією за наявності деякої кількості обмежень на керовані змінні. Такі обмеження суттєво зменшують розміри області, в якій проводиться пошук оптимуму. На перший погляд може здатися, що зменшення розмірів допустимої області повинно спростити процедуру пошуку оптимуму. Тим часом, навпаки, процес оптимізації стає більш складним, оскільки встановлені вище критерії оптимальності не можна використовувати при наявності обмежень. При цьому може порушуватися навіть основна умова, в відповідно до якого оптимум має досягатися в стаціонарній точці, характеризується нульовим градієнтом. Наприклад, безумовний мінімум функції має місце в стаціонарній точці х = 2. Але якщо завдання мінімізації вирішується з урахуванням обмеження, то буде знайдений умовний мінімум, якому відповідає точка x = 4. Ця точка не є стаціонарної точкою функції f, так як (4) = 4. Далі досліджуються необхідні і достатні умови оптимальності рішень задач з обмеженнями. Виклад починається з розгляду завдань оптимізації, які містять тільки обмеження у вигляді рівностей.
2.1. Завдання з обмеженнями у вигляді рівностей
Розглянемо загальну задачу оптимізації, що містить кілька обмежень у вигляді рівностей:
Мінімізувати
при обмеженнях, k = 1, ..., n
Ця задача в принципі може бути вирішена як задача безумовної оптимізації, отримана шляхом виключення з цільової функції k незалежних змінних за допомогою заданих рівностей. Наявність обмежень у вигляді рівностей фактично дозволяє зменшити розмірність вихідної завдання з n до n-k .. В Для ілюстрації розглянемо наступний приклад.
Приклад 1
Мінімізувати
при обмеження
Виключивши змінну, за допомогою рівняння, отримаємо
оптимізаційну задачу з двома змінними без обмежень
min
Метод виключення змінних застосуємо лише в тих випадках, коли рівняння, що представляють обмеження, можна дозволити щодо деякого конкретного набору незалежних змінних. За наявності великого числа обмежень у вигляді рівностей, процес виключення змінних стає вельми трудомісткою процедурою. Крім того, можливі ситуації, коли рівняння не вдається розв'язати відносно змінної. Зокрема, якщо в прикладі 1 обмеження задати у вигляді
то одержати аналітичний вираз небудь із змінних через інші не представляється можливим. Таким чином, при вирішенні завдань, що містять складні обмеження у вигляді рівностей, доцільно використовувати метод множників Лагранжа, опис якого поданий у наступному розділі.
2.2. Множники Лагранжа
З допомогою методу множників Лагранжа по суті встановлюються необхідні умови, що дозволяють ідентифікувати точки оптимуму в задачах оптимізації з обмеженнями у вигляді рівностей. При цьому задача з обмеженнями перетвориться в еквівалентну задачу безумовної оптимізації, в якій фігурують деякі невідомі параметри, звані множниками Лагранжа.
Розглянемо задачу мінімізації функції n змінних з урахуванням одного обмеження у вигляді рівності:
Мінімізувати (3)
при обмеженнях (4)
В Відповідно до методу множників Лагранжа ця задача перетворюється в наступну задачу безумовної оптимізації:
мінімізувати L (x, u) = f (x)-u * h (x) (5)
Функція L (х; u) називається функцією Лагранжа, u - невідома постійна, яка носить назву множника Лагранжа. На знак u ніяких вимог не накладається.
Нехай при заданому значенні u = u 0 безумовний мінімум функції L (x, u) по х досягається в точці і задовольняє рівнянню. Тоді, як неважко бачити, x 0 мінімізує (1) з урахуванням (4), оскільки для всіх значень х, що задовольняють (4), і L (x, u) = min f (x).
Зрозуміло, необхідно підібрати значення u = u В° таким чином, щоб координата точки безумовного мінімуму х В° задовольняла рівності (4). Це можна зробити, якщо, розглядаючи u як змінну, знайти безумовний мінімум функції (5) у вигляді функції u, а потім вибрати значення u, при якому виконується рівність (4). Проілюструємо це на конкретному прикладі.
Приклад 2
Мінімізувати
при обмеженні = 0
Відповідна задача безумовної оптимізації записується в наступному вигляді:
мінімізувати L (x, u) =-u
Рішення. Прирівнявши дві компоненти градієнта L до нуля, отримаємо
Для того щоб перевірити, чи відповідає стаціонарна точка х В° мінімуму, обчислимо елементи матриці Гессе функції L (х; u), що розглядається як функція х,
,
яка виявляється позитивно визначеною. Це означає, що L (х,, u) - опукла функція х. Отже, координати, визначають точку глобального мінімуму. Оптимальне значення u знаходиться шляхом підстановки значень і в рівняння = 2, звідки 2u + u/2 = 2 або. Таким чином, умовний мінімум досягається при і і дорівнює min f (x) = 4/5.
При вирішенні задачі з прикладу 2 ми розглядали L (х; u) як функцію двох змінних і і, крім того, припускали, що значення параметра u вибрано так, щоб виконувалася обмеження. Якщо ж рішення системи
, j = 1,2,3, ..., n
в вигляді явних функцій u отримати не можна, то значення х і u знаходяться шляхом вирішення наступної системи, що складається з n +1 рівнянь з n +1 невідомими:
, j = 1,2,3, ..., n
Для знаходження всіх можливих рішень даної системи можна використовувати чисельні методи пошуку (наприклад, метод Ньютона). Для кожного з рішень () слід обчислити елементи матриці Гессе функції L, розглянутої як функція х, і з'ясувати, є Чи ця матриця позитивно певної (локальний мінімум) або негативно певної (локальний максимум).
Метод множників Лагранжа можна поширити на випадок, коли задача має кілька обмежень у вигляді рівностей. Розглянемо загальну задачу, в якій вимагається
Мінімізувати f (x)
при обмеженнях = 0, k = 1, 2, ..., К.
Функція Лагранжа приймає наступний вигляд:
L (x, u) = f (x) -
Тут -Множники Лагранжа, тобто невідомі параметри, значення яких необхідно визначити. Прирівняні-вая приватні похідні L по х до нуля, отримуємо наступну систему n рівнянні з n невідомими:
...........
Якщо знайти рішення наведеної вище системи у вигляді функцій вектора u виявля...
