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

Нехай xi=(xi1,…,xin)єEn, i=1,…,r, r2. Опуклою лінійною оболонкою точок x1,...,xr називається сукупність точок виду

, де , i=1,...,r, — будь-якi числа, що задовольняють умовам

Будь-яка точка опуклої лінійної оболонки називається опуклою лінійною комбінацією точок x1,...,xr.

При r = 2 опукла лінійна оболонка називається відрізком, що з'єднує точки x1, x2, i позначається [x1, x2], тобто

[x1,x2] ={x: x=бx1 + (1-б)x2, 0?б? 1}.

Множина W називається опуклою, якщо для довільних x1,x2єW виконується [x1, x2] W.

Нагадаємо також, що множина

називається пiвпростором у En, а множина (1)

гiперплощиною в En.

Перетином двох множин називається множина тих i тільки тих точок, що належать обом множинам.

Л1 Перетин опуклих множин є опуклою множиною.

Доведення. Нехай A та B опуклі множини, A?B — їх перетин. Розглянемо довільні точки x1 ,x2 є A?B. За означенням перетину множин x1 ,x2єA, x1 ,x2єB. Оскільки A та B — опуклі множини, то [x1,x2]A, [x1,x2]B. Звiдси за означенням перетину [x1,x2] A? B.

Л2 Пiвпростiр є опуклою множиною.

Доведення. Розглянемо, наприклад, пiвпростiр

і нехай x1,x2 єP. Це означає, що

(2), де x1k ,...,xnk — координати точки xk. Розглянемо деяку довільну точку x відрізка

[x1,x2] i покажемо, що вона також належить Р. Нехай

х=ах1 + (1-а)х2, 0<а<1. Маємо з врахуванням (2)

Це означає, що довільна точка x відрізка [x1,x2] належить P. Отже пiвпростiр є опуклою множиною.

Л3. Гiперплощина є опуклою множиною. Доведення. Гiперплощина (1.4) є перетин пiвпросторiв та

що є опуклими множинами згідно леми 2, отже, гiперплощина є опуклою множиною згідно леми 1.1.

Озн. Многогранною множиною називається перетин скiнченного числа пiвпросторiв. Обмежена многогранна множина називається многогранником.

Зрозумiло, що допустима множина D ЗЛП є многогранною множиною (якщо вона не порожня). Iнколи область D називають многогранником, додаючи слова "обмежений" або "необмежений".

Безпосереднiм наслідком цих означень та доведених тверджень є така теорема.

Т1 Допустима множина D ЗЛП є опуклою многогранною множиною.

Отже, ЗЛП полягає у знаходженні мінімуму (максимуму) лінійної функції L(x) на опуклій многограннiй множині D.

Озн. Точка x опуклої мн-ни X називається кутовою (крайньою), якщо її не можна представити у вигляді x=бx1 + (1-б)x2, деx1,x2 єX, x1 ?x2, 0<б<1.

З геометричної точки зору точка x є крайньою точкою множини X, якщо її не можна розташувати усередині відрізка, кінці якого належать X.

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

Критерiй оптимальності.

Ознака необмеженості цільової функції

Наведені у попередньому параграфі міркування складають основу симплекс-методу розв'язування ЗЛП.

Перш, ніж сформулювати алгоритм цього методу, доведемо декілька необхідних для його обгрунтування тверджень.

Т2 (критерій оптимальності базисного розв'язку ЗЛП). Якщо для деякого базисного розв'язку x* справджуються нерівності ?j?0, j=1,...,n, то x* — оптимальний розв'язок ЗЛП.

Доведення. Нехай для базисного розв'язку x*=(в1,...,вm,0,...,0), що визначається канонічною формою обмежень ЗЛП

бх=в, х0, в0, виконується умова теореми, тобто

Ми повинні довести, що для будь-якого допустимого розв'язку y=(y1,...,yn)

(бy=в, y?0) виконується нерівність L(y)L(x*), а це і буде означати, що x* — оптимальний розв'язок ЗЛП.

Дійсно, з умови теореми та з допустимості розв'язку y маємо

що і доводить теорему.

3. Постановка скінченновимірної гладкої задачі з обмеженнями типу рівностей і нерівностей.

Нехай ф-ція : , і=1,...,m. - мають певні властивості гладкості.

Озн. Гладкою скінченно- вимірною зад. з обмеженнями типу рівностей і нерівностей наз. таку задачу: extr, , =1,..., . Розглянемо зад. на min. Точка =(), для якої викон. ум.:; наз. т. locmin, якщо окіл такий, що : ; ; .

2. Необхідні і достатні умови extr. а) принцип Лагранжа. Теорема 1.

Нехай точка , ф-ції є неперервно диференційованими в околі т. ,тоді існує ненульовй вектор множників Лагранжа такий , що для ф-ції Лагранжа викон. умови: а) стаціонарності : , . б) доп. нежорсткості : ,

в) умова невід’ємності : , Зауваження: Якщо розглядається задача на max, то в умові в) . В задачі (Р) обмеження типу рівностей завжди можна записати у вигляді : , , . Для такого випадку принцип Лагранжа також справджується і дає ті самі критичні точки , тобто ті точки , що задовольняють умову а)–в).

б) Необхідні і достатні умови extr другого порядку .

Теорема 2. (Необхідна умова). Нехай точка , ф-ції , двічі неперервно диференційовані в околі точки і вектори є лінійно незалежними (умова регулярності) тоді існує вектор множників Лагранжа такий , що запишеться і викон. умови а)-в) і ,, де . Конус допустимих варіацій в задачі Р.

Теорема 3 . Достатня умова extr. Нехай ф-ції є двічі неперервно диференційованими в околі т. , вектори - лін. незалежні і існує вектор множників Лагранжа такий , що для ф-ції задачі Лагранжа викон. умова а) і умова , де - додатні стала .Тоді , K, L ті самі , що в теоремі 2. Формулювання теореми (2),(3) для випадку задачі на max відр. тим , що , а ф-ція .

Алгоритм отримання розв’язку.

Для розв’язання зад. потрібно: 1) виписати ф-цію Лагранжа ; 2) виписати необх. ум. екстремуму 2-го порядку, тобто ум. стаціонарності, доповнюючої нежорсткості і невід’ємності (в зад. на максимум ). В ум. доповнюючої нежорст. для кожного треба розглядати випадки і . 3) перевірити виконання достатніх і необхідних ум. екстрем. 2-го пор. Але дуже часто перевірка цих ум. є громіздкою, тому варто користуватися безпосередньою перевіркою, порівнюючи значення ф-ції в критичних точках і в допустимих т. з їх околу.

4. Задача