Реферат: Задачі нелінійного програмування. Деякі основні методи їх розвязування та аналізу

Реферат на тему:

Задачі нелінійного програмування. Деякі основні методи їх розв’язування та аналізу.

План.

1. Метод Франка-Вулфа.

2. Приклади розв’язування задач.

3. Література

Деякі з основних методів розв’язування задач НЛП.

1. Метод Франка –Вулфа. Нехай потрібно найти максимальне значення вогнутой функції

(57)

при умовах: (58)

(59)

Характерною особливістю цієї задачі являється то, що її система обмеження вміщує тільки лінійні нерівності. Ця особливість являє основний для заміни в межах досліджуваної точки нелінійної цільової функції лінійною, завдяки чому розв’язок даної задачі зводиться до послідовного розв’язку задач лінійного програмування.

Процес найдення розв’язку задачі начинають з оприділення точки, принадлежавшої області допустимих розв’язків задачі.

Нехай ця точка , тоді в цій точці вираховують градієнт функції (57)

і будують лінійну функцію

(60)

Потім знаходять максимальне значення цієї функції при обмеженнях (58) і (59). Нехай рішення даної задачі визначається точкою . Тоді за новий допустимий розв’язок даної задачі приймають координати точки

(61)

де — деяке число, називають кроком вирахуваним і закінченням між нулем і одиницею . Це число беруть довільно чи визначають таким способом, щоб значення функції в точці

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

Отже, процес находження розв’язків задачі (57) – (59) методом Франка – Вулфа включає наступні етапи :

1. Визначають даний допустимий розв’язок задачі.

2. Находять градієнт функції (57) в точці допустимого розв’язку.

3. Будують функцію (60) і находять її максимальне значення при умовах (58) і (59) .

4. Визначають крок обчислень .

5. По формулам (61) находять компоненти нового допустимого розв’язку.

6. Провіряють необхідність переходу до наступного допустимого розв’язку. У випадку необхідності переходять до етапу 2, в поганому випадку найдене прийняте розв’язок даної задачі.

3.27. Методом Франка – Вулфа найти розв’язок задачі 3.22., забезпеченої в певному максимальному значенні функції

(62)

при умовах

(63) (64)

Розв’язок. Найдем градієнт функції

і в якості даного допустимого розв’язку задачі візьмемо точку а в якості критерія оцінки якості одержимо розв’язок – нерівності де .

1. Ітерація. В точці градієнт .Знаходимо максимальне значення функції

(65)

при умовах (63) і (64)

(66)

(67)

Задача (65)—(67) має оптимальний план .

Найдемо новий допустимий розв’язок даної задачі по формулі (61):

, де . (68)

Підставимо замість і їх значення, отримаємо

(69)

Знайдемо тепер число . Підкладемо в рівність (62) замість і

із значення у відповідності з відношенням (69)

,

знайдемо подібну цій функції по і прирівняємо її нулю:

.Розв’язуючи цю рівність, отримаємо .

Оскільки найдене значення заключне між 0 і 1, приймаючи його за величину кроку.Таким образом,

.

2. Ітерація. Градієнт цільової функції даної задачі в точці є . Находимо максимальне значення функції при умовах (63) і (64). Рішення являється .

Оприділяєм тепер .Останню рівність перепишемо наступним образом:

Підкладемо тепер в функцію (62) замість і їх значення у відношенні з відношенням (70), отримаємо

звідки . Прирівняємо нулю і розв’язуючи отримаємо рівність, знаходимо . Таким образом,

т.е..

3. Ітерація. Градієнт функції f в точці є . Находимо максимальне значення функції при умовах (63) і (64). Розв’язком буде .

Знайдемо . Маємо

Розв’язуючи рівність , находимо . Слідуючи, ,, .

Таким образом, являється задовільним розв’язком даної задачі. Дана точка находиться достатньо близько до точки максимального значення цільової функції , найденої при розв’язку цієї задачі в п. 3.3. Задав меншу величину , можна було, зробивши доповнюючи приближення, ще ближче підійти до точки максимального значення цільової функції.

Література.

1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.: КНЕУ, 2003.- 452 с.

2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут післядипломної освіти) “Інтелект — Захід”, 2004. – 448 с.

3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. – Вища школа, 1985-319с., ст.270-274.

4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.

5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., — Чернівці: „Рута”, 1998.-168 с.