logo
Опорний конспект ОММ 4 Ф

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

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

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

Означення 2. Функція f(x1, x2,….. xn), що задана на опуклій множині Х, називається вгнутою, якщо для будь яких двох крапок Х1,Х2 є Х і довільного µє[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 (6)

за умов

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

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

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

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

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

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

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

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

      1.