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

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

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

План.

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). Розв’язком буде .

Знайдемо

. Маємо