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

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

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


План.

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

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

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




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



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

                                                                                       (57)

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

                                                                                       (59)

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

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

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



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

(60)

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

                                                                    (61)

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

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

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

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

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

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

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

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

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

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

                                                                       (62)

при умовах

                                           (63)    (64)        

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



              

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

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

                                                                                        (65)

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

                                                                                       (66)                                  

                                                                                               (67)  

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

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

               , де  .                                (68)

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

                                                                                     (69)

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

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

                  , 

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

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

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

. 

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

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

                                      

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

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

                                          

т.е. .

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

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

                  

                      

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

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


Література.

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

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

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

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

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









5