Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Pitannya_EMM.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

38. Теорема Куна-Такера.

Теорема Куна—Таккера дає змогу встановити типи задач, для яких на множині допустимих розв’язків існує лише один глобальний екстремум зумовленого типу. Вона тісно пов’язана з необхідними та достатніми умовами існування сідлової точки.

Розглянемо задачу нелінійного програмування, яку, не зменшуючи загальності, подамо у вигляді:

, (8.22)

, (8.23)

. (8.24)

(Очевидно, що знак нерівності можна змінити на протилежний множенням лівої і правої частин обмеження на (– 1)).

Теорема 8.1. (Теорема Куна—Таккера). Вектор Х* є оптимальним розв’язком задачі (8.22)—(8.24) тоді і тільки тоді, коли існує такий вектор , що при для всіх точка є сідловою точкою функції Лагранжа

,

і функція мети для всіх угнута, а функції — опуклі.

Доведення. Необхідність. Нехай Х* — оптимальний план задачі (8.22)—(8.24), тобто є точкою глобального максимуму задачі. Отже, для всіх інших планів задачі Х з множини допустимих розв’язків виконуватиметься співвідношення:

.

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

З умови (8.21) маємо: , тоді

. (8.25)

Для точки з координатами деякі доданки виду можуть бути відмінними від нуля. Оскільки за умовою задачі , то лише за умови, що , матимемо нерівність:

.

Функція — лінійна відносно , тобто остання нерівність виконується для будь-якого . Отже, точка — точка глобального мінімуму по функції Лагранжа.

Для встановлення нерівності, що відповідає лівій частині умови (8.13), а саме: , скористаємося також рівнянням (8.21), підсумувавши його по і: . За умовою теореми — угнуті функції і , тому виконується таке рівняння:

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

Достатність. Для доведення достатності умов теореми потрібно виходити з того, що , — сідлова точка функції (тобто для виконується нерівність (8.13)), і необхідно довести, що тоді Х* є оптимальним планом задачі опуклого програмування.

Підставимо у нерівність (8.13) вираз функції Лагранжа (8.12) для задачі (8.22)—(8.23):

(8.26)

при всіх значеннях .

Розглянемо праву частину подвійної нерівності (8.26).

.

Остання нерівність має виконуватися для всіх . Крім того, , тобто нерівність справджується лише у разі, коли

.

Тоді з лівої частини нерівності (8.26) маємо:

.

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

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

39. Чого досягається застосовуючи множники Лагранжа в системі нелінійних рівнянь.

*Задача нелінійного програмування ставиться як задача знаходження оптимуму певної цільової функції F(x1,….. xn)при виконанні умов: gj(x1,….. xn)>0,

де xi,i=1,…..,n - параметри, gj,j=1,…,s - обмеження, n - число параметрів, s - число обмежень.

На відміну від задачі лінійного програмування в задачі нелінійного програмування оптимум не обов'язково лежить на границі області, визначеної обмеженнями.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]