Класичні методи розв’язання задач нелінійного програмування. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Класичні методи розв’язання задач нелінійного програмування.



Загальна задача нелінійного програмування полягає у знаходженні максимального(мінімального) значення функції

Z=f(x1, x2,….. xn) →max/ min (8)

за умов

gi(x1, x2,….. xn) { ≤=≥}bi, i=1,2…..m (9)

де всі функції (або їх частина) нелінійні.

Функція f з (8) – цільова функція, а умови gi з (9) - умовами обмеження.

Сукупність змінних, що задовольняють обмеженням (9) задачі називається допустимим розв’язком або планом. Кожному допустимому розв язкувідповідає певне значення цільової функції.

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

Лише для небагатьох типів задач НП розроблені обчислювальні методи їх розв’язання.

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

Як згадувалось вище, найбільш вивченими є задачі з нелінійною цільовою функцією і лінійними обмеженнями, які можна класифікувати таким чином:

- Задачі дробово-лінійного програмування

Z=(∑cixi)/(∑dixi) →max/ min

за умов

∑aijxj =bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

- Сеперабельна задача НП

f(x1, x2,….. xn) =∑fi(xi) →max/ min

за умов

∑aijxj{ ≤=≥}bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

- Квадратична задача НП

f(x1, x2,….. xn) =∑cjxj +∑∑djixixj →max/ min

за умов

∑aijxj{ ≤=≥}bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

- Задача опуклого програмування

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

Розглянемо задачу (8), якщо на змінні не накладаються умови обмежень.

Така задача вирішується класичними методами дифереціального числення.

Нехай Z=f(x1, x2,….. xn) неприривно – диференційована функція в своїй області визначення. Необхідною умовою екстремуму в точці Х0 функції Z=f(x1, x2,….. xn) є рівність нулю градієнта функції Z(X0)=0.Для функції Z=f(x1, x2,….. xn) запишемо матрицю Гессе:

Н=

яка складається з частинних похідних другого порядку.

Головні мінори матриці Гессе позначимо:

M1= ‌‌ , M2= , ………….,Mn=H,

де fij= – значення частинної похідної другого порядку функції Z в точці X0.

Якщо всі головні мінори M1, M2, M3, …… Mn>0, то Х0 – точка локального мінімуму. Якщо головні мінори почергово міняють знак, починаючи з мінуса, то точка Х0 – точка локального максимуму. Проаналізувавши всю область допустимих розв’язків, можна виділити серед локальних екстремумів найбільший і найменший, які і будуть глобальними.

Метод множників Лагранжа.

Розглянемо задачу НП з обмеженнями – рівностями:

Z=f(x1, x2,….. xn) →max/ min (10)

за умов

gi(x1, x2,….. xn)=bi, i=1,2…..m (11)

в якій f і gi двічі неперервно диференційовані функції.

Для визначення оптимальних точок цієї задачі, введемо набір змінних λi (i=1,2,….m), які називаються множниками Лагранжа, і побудуємо функцію Лагранжа

L(x1, x2,….. xn, λ1,, λ2,...., λm)= f(x1, x2,….. xn) + ∑ λi(bi - gi(x1, x2,….. xn)) (12)

Відшукання умовного екстремуму задачі зводиться до знаходження безумовного екстремуму функції Лагранжа (12). Характер оптимальності з’ясовується аналогічно, як і у випадку безумовного екстремуму.

5. Задачі опуклого програмування.

Означення 1. Функція f(x1, x2,….. xn), що задана на опуклій множені Х, називається опуклою, якщо для будь – яких двох крапок Х12 є Х і довільного µє[0;1] виконується співвідношення:

f(µX1+(1-µ) X2) ≤ µ f(X1) +(1-µ) f(X2)

Означення 2. Функція f(x1, x2,….. xn), що задана на опуклій множині Х, називається вгнутою, якщо для будь яких двох крапок Х12 є Х і довільного µє[0;1] виконується співвідношення

f(µX1+(1-µ) X2) ≥ µ f(X1) +(1-µ) f(X2).

Якщо f(x1, x2,….. xn) – опукла, то - f(x1, x2,….. xn) – вгнута.

Загальна постановка задачі опуклого програмування:

Z=f(x1, x2,….. xn) →max (13)

за умов

gi(x1, x2,….. xn) ≤bi, i=1,2…..m (14)

xj ≥0 j=1,2,…..n (15)

де f – вгнута і gi - опуклі функції

Надалі припустимо, що ОДР задачі (13) – (15) не порожня й обмежена.

Теорема 3. Довільний локальний максимум (мінімум) задачі опуклого програмування є глобальним максимумом (мінімумом).

Означення 3. Говорять, що множина ОДР задовольняє умову регулярності, якщо існує хоча б одна крапка

Означення 4. Говорять, що множина допустимих планів (13) – (15) задовольняє умові регулярності, якщо існує хоча б одна крапка х i з області допустимих розв’язків така, що gi(xi)<bi (i=1,2,….m).

Означення 5. Крапка (Х**) називається сідловою крапкою функції Лагранжа, якщо L(Х,Λ*) ≤L(Х**)≤L(Х*,Λ) для всіх xj ≥0 (j=1,2,…n) і λi≥0 (i=1,2,….m).

Теорема 4. (Куна-Такера). Нехай для ОДР задачі опуклого програмування (13) – (15) виконується умова регулярності. План Х*буде оптимальним планом цієї задачі тоді і тільки тоді, коли існує такий вектор Λ*, λi≥0 (i=1,2,….m), що пара (Х**) – сідлова крапка функції Лагранжа.

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



Поделиться:


Последнее изменение этой страницы: 2017-02-05; просмотров: 389; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.197.195.36 (0.011 с.)