рограмування з рішенням х, її цільова функція f (x) і функції обмежень gi (x) - діфференцируєми, нелінійні обмеження у формі нерівностей задовольняють умові регулярності Слейтера, то існує такий вектор u? 0, що (х, u) - сідлова точка функції Лагранжа Ф (х, u). p> Значення теореми Куна-Таккера полягає в тому, що вона дозволяє зв'язати процес вирішення оптимізаційної задачі з пошуком сідлових точок функції Лагранжа, тобто, грубо кажучи, з максимізацією цієї функції з х і мінімізацією по u.
Визначимо F (x) як функцію, яка ставить у відповідність кожному значенню х мінімальне значення функції Ф (х, u) за u:
В
і за аналогією
В
Розглянемо завдання відшукання максимуму функції F (x)
В
і завдання мінімізації G (u)
В
Очевидно, що
В
Звідси випливає, що максимум F (x) знаходиться в допустимої області D і збігається з максимумом цільової функції f (x) задачі (1):
В
Таким чином, задача (2), в певному сенсі, рівносильна (1). Аналогічні висновки можуть бути отримані і для (3). Задачі (2) і (3) утворюють подвійну пару. Як неважко здогадатися, дане відношення є узагальненням відносини подвійності для задач лінійного програмування. Відповідно, за певних умов пара двоїстих задач нелінійного програмування має властивості, аналогічними властивостям двоїстих лінійних завдань. Зокрема, за будь-яких х? Х, u? 0. <В
Умова (4) знаходить широке застосування при побудові оцінок у ітеративних методах вирішення оптимізаційних завдань. Наприклад, якщо є можливість приблизно вирішити пряму і двоїсту завдання і отримати послідовності наближень {х (q)} і {u (q)}, то за допомогою нерівностей виду
В
можна визначити момент зупинки обчислювальної процедури.
На закінчення відзначимо, що можливий варіант виведення виразів для цільових функцій і обмежень пари двоїстих задач лінійного програмування із загального визначення ставлення подвійності для нелінійних задач. Також відзначимо, що в процесі формування нелінійних двоїстих завдань існує велика неоднозначність: їх вигляд можна варіювати, включаючи в безліч Х частину обмежень gi (x)? 0. br/>
1.3 Лінійне програмування. Кутові точки допустимих множин. br/>
Визначення 1. Завдання, в якій потрібно мінімізувати (або максимізувати) лінійну форму
за умови, що,,
або,, і,,
називається задачею лінійного програмування у довільній формі запису.
Визначення 2. Завдання в матричної формі виду
(1)
називається симетричною формою запису задачі лінійного програмування.
Визначення 3. Завдання лінійного програмування виду
(2)
називається канонічної формою запису задачі лінійного програмування.
Будь-яку задачу лінійного програмування можна привести до канонічної формі.
Якщо система обмежень задана у формі,
то можна, ввівши додатко...
