МІНІСТЕРСТВО КУЛЬТУРИ УКРАЇНИ

Національна академія керівних кадрів культури і мистецтв

Інститут менеджменту

Кафедра документознавства та управління соціальними комунікаціями

 

 

 

 

 

 

 

 

Реферат

На тему: «Неліній­­не програмування»

 

 

 

 

 

 

 

 

 

 

Роботу виконала:

студентка заочної

форми навчання

групи ДІД-113А

Глущенко Т.В.

Викладач:

доц.Вінічук І.М.

 

 

 

 

Київ-2013

Зміст 1. Постановка задачі нелінійного програмування 2. Критерії оптимальності в задачах з обмеженнями 2.1. Завдання з обмеженням у вигляді рівностей 2.2. Множники Лагранжа 3. Умови Куна-Таккера 3.1. Умови Куна-Таккера і завдання Куна-Таккера 3.2. Інтерпретація умов Куна-Таккера 3.3. Теореми Куна-Таккера

1.Постановка задачі нелінійного програмування. У задачі нелінійного програмування (НЛП) потрібно знайти значення багатовимірної змінної х = ( ), Мінімізує цільову функцію f (x) за умов, коли на змінну х накладені обмеження типу нерівностей , I = 1,2, ..., m (1) а змінні , Тобто компоненти вектора х, ненегативні: (2) Іноді у формулюванні задачі обмеження (1) мають протилежні знаки нерівностей. Враховуючи, проте, що якщо , То , Завжди можна звести задачу до нерівностей одного знака. Якщо деякі обмеження входять в завдання зі знаком рівності, наприклад , То їх можна представити у вигляді пари нерівностей , , Зберігши тим самим типову формулювання завдання.

2. Критерії оптимальності в задачах з обмеженнями.

Ряд інженерних завдань пов'язаний з оптимізацією за наявності певної кількості обмежень на керовані змінні. Такі обмеження суттєво зменшують розміри області, в якій проводиться пошук оптимуму. На перший погляд може здатися, що зменшення розмірів допустимої області має спростити процедуру пошуку оптимуму. Тим часом, навпаки, процес оптимізації стає більш складним, оскільки встановлені вище критерії оптимальності не можна використовувати за наявності обмежень. При цьому може порушуватися навіть основна умова, відповідно до якого оптимум має досягатися в стаціонарній точці, яка характеризується нульовим градієнтом. Наприклад, безумовний мінімум функції має місце в стаціонарній точці х = 2. Але якщо завдання мінімізації вирішується з урахуванням обмеження , То буде знайдений умовний мінімум, якому відповідає точка x = 4. Ця точка не є стаціонарної точкою функції f, так як (4) = 4. Далі досліджуються необхідні і достатні умови оптимальності рішень завдань з обмеженнями. Виклад починається з розгляду завдань оптимізації, які містять тільки обмеження у вигляді рівностей.

2.1. Завдання з обмеженнями у вигляді рівностей

Розглянемо загальну задачу оптимізації, яка містить кілька обмежень у вигляді рівностей: Мінімізувати при обмеженнях , K = 1, ..., n Це завдання в принципі може бути вирішена як завдання безумовної оптимізації, отримана шляхом виключення з цільової функції k незалежних змінних за допомогою заданих рівностей. Наявність обмежень у вигляді рівностей фактично дозволяє зменшити розмірність вихідної задачі з n до nk .. В якості ілюстрації розглянемо наступний приклад. Приклад 1 Мінімізувати при обмеженні Виключивши змінну , За допомогою рівняння , Отримаємо оптимізаційних задач з двома змінними без обмежень min Метод виключення змінних можна застосовувати лише в тих випадках, коли рівняння, що представляють обмеження, можна дозволити щодо деякого конкретного набору незалежних змінних. При наявності великої кількості обмежень у вигляді рівностей, процес виключення змінних стає дуже трудомісткою процедурою. Крім того, можливі ситуації, коли рівняння не вдається вирішити щодо змінної. Зокрема, якщо в прикладі 1 обмеження задати у вигляді то отримати аналітичний вираз будь-якої з змінних через інші не представляється можливим. Таким чином, при вирішенні завдань, що містять складні обмеження у вигляді рівностей, доцільно використовувати метод множників Лагранжа, опис якого поданий у наступному розділі.