Іі Теорема двоїстості (двоїстий критерій оптимальності)

(звичайний критерій оптимальності: ДБР х – оптим 

)

ДБР х – оптимальний   u = (u₁ , …, u_m):

ua_j = c_j для x_j>0

ua_j <= c_j для x_j = 0

5. a_j – j-ий стовпчик в матриці А

Екзаменаційний білет № 6

6.1. Інтеграл Рiмана на компактi та його застосування (обчислення площин, об'ємiв).

Позначимо , , .

Озн. Верхньою (нижньою) інтегральною сумою Дарбу для функції f:[a,b]R і розбиття Р називається і позначається сума ( ) .

Озн. Верхнім (нижнім) інтегралом Дарбу для функції f на [a,b] називається і позначається вираз: ( ).

Озн. Функція назив-ся інтегровною за Ріманом на [a,b], якщо її = , при цьому спільне значення цих інтегралів називається інтегралом Рімана на [a,b].

До класів інтегровних функцій можна віднести:

1. неперервні ф-ції, інтегровні на [a,b].

2. Ф-ції, що мають злічене (скінчене) число точок розриву 1-го роду.

3. Всі монотонні ф-ції на [a,b].

Властивості кратних інтегралів:

1. Якщо відрізок [a,b] рівний 0, то .

2. .

3. .

4. 

5. 

6. Якщо ф-ції f,g – інтегровні, то добуток цих ф-цій теж інтегровний.

7. 

8. .

Правила інтегрування:

Як правило використовується формула Ньютона-Лейбніца: (Ф – первісна).

Є 2 методи інтегрування:

1. метод інтегрування частинами ;

2. метод підстановки . φ(t) – диференційовна і неперервна, a≤φ(t)≤ b.

Застосування інтегралів Рімана:

1. Обчислення площи криволінійної трапеції.

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

2. Площа криволінійного сектора:

- криволінійний сектор. Площа дорівнює .

3. Параметрично задана крива:

, сама крива не має самоперетинів та розривів при обході за годинниковою стрілкою.

4. Обьєм тіла при обертанні навколо вісі :

, , , - тіло утворене при обертанні.

5. При обертанні навколо так само, лише додаткова умова - монотонна.

6. Довжина параметрично заданої кривої:

, крива задається за 3) плюс ,

6.2. Задача опуклого програмування. Теорема Куна-Такера.

Сформулюємо задачу опуклого програмування. Знайти мінімум опуклої функції z=f⁰(x) при умові xDEⁿ, де D- опукла множина.

Множина D, як правило, задають наступним чином:

,

де (x), ,-опуклі функції. Ця множина опукла в силу такої теореми:

Т. Нехай g(x), xEn -опукла функція. Тоді множина V={x: g(x)<=0}-опукла.

Ясно, що множина D також і замкнена. З наступної теореми випливає, що будь-який локальний мінімум задачі опуклого програмування є і глобальним:

Т. Нехай f(x)- опукла функція, задана на замкнутій опуклій множині XЕn. Тоді б-я відносний мінімум f(x) на X являється абсолютним мінімумом f(x) на X.

Визначимо функцію Лагранжа для задачі опуклого програмування співвідношенням

L(x,)=f ⁰(x)+

x=(x₁,...,x_n) Eⁿ, =(₁,...,_m) E^m,x>=0, >=0.

Говорять, що точка (x*,*)E^n+m являється сідловою точкою функції L(x,), якщо для всіх x0, 0 мають місце нерівності:

L(x*,) <= L(x*,*) <= L(x,*).

Наступне твердження дає узагальнення методу Лагранжа на задачу опуклого програмування.

Т1.(достатні умови оптимальності)

Якщо ф-ція Лагранжа з-чі

, де Х-опукла мн-на, fⁱ(x), i=0,1,…m, опуклі на Х, має сідлову точку (x*,*), то x* є оптимальним р-ком з-чі С, і при цьому виконується правило доповнюючої нежорсткості

Т.(Куна-Такера). Нехай

- задача опуклого програмування, допустима мн-на якої задовольняє умову регулярності Слейтера: якщо існує точка xD_С, в якій fⁱ(x)<0, для будь-яких i=1,m, то говорять, що мн-на D_С задовольняє умову Слейтора. Тоді допустимий р-к x*D_С з-чі С є її оптимальним розв’зком тоді і тільки тоді, коли існує вектор *=(₁*,...,*_m)0 такий, що пара (x*,*) є сідловою точкою функції Лагранжа з-чі С на мн-ні xХ, 0 .

Доведення. Достатність випливає з теореми про достатні умови оптимальності.

Необхідність. Нехай х*- оптимальний р-зок задачі С, тобто для всіх xD_С виконується нерівність f⁰(x*)f⁰(x).Покажемо, що при виконанні умов теореми (опуклість функцій f і g_i і умова Слейтера) існує вектор 0 такий, що пара (х*,*) є сідловою точкою функції Лагранжа

В просторі Е^m+1 визначимо множини Y і Z наступним чином:

Неважко показати, що множина Y і Z- опуклі множини, що не перетинаються. В силу теореми (про відокремленість множин Y і Z) знайдеться вектор с=(с₀,.с₁,...,с_m)0 такий, що (c,z)(c,y) для всіх yY i zZ.За визначенням множин Y і Z із нерівності (c,z)(c,y) випливає, що c0. Нерівність (c,z)(c,y) залишається справедливою, якщо вибрати z належним границі Z. Через це, якщо покладемо y₀=f⁰(x), y_i=fⁱ(x), , z₀=f⁰(x*), z_i=0, , отримаємо для всіх x0 нерівність

або в явному вигляді

(2)

Покажемо, що с₀>0(раніше було с0).Доведемо від супротивного. Нехай с₀=0. Тоді з нерівності (2) маємо

(3)

де не всі с_i( ) дорівнюють 0(с0).Перепишемо (3) у вигляді

Але остання нерівність суперечить умові Слейтера, згідно якої існує таке хD, що fⁱ(x)<0. Нехай тепер *=(₁*,...,_m*),де _m*=с_і/с₀, . Тоді *0 і для будь-яких х0 з співвідношення (3) маємо

.(4)

Поклавши в (4) х=х*, отримаємо

З іншого боку, оскільки ,а , маємо

(5)

Зауважимо, що остання нерівність носить назву умови додаткової нежорсткості і аналогічна співвідношенню

у двоїстому критерії оптимальности ЗЛП. З співвідношеннь (4) та (5) з очевидністю випливає, що і треба було довести.