вирішення
Дане завдання належить до типу завдань квадратичного програмування. Це окремий випадок задачі нелінійного програмування.
Взагалі, основний недолік методів нелінійного програмування полягає в тому, що з їх допомогою не вдається знайти глобальний екстремум при наявності декількох локальних екстремумів. Тому метод вважається теоретично розробленим, якщо знайдені співвідношення, які є необхідними і достатніми умовами оптимуму, і алгоритми пошуку екстремуму з доказом їх збіжності. Цим вимогам задовольняють тільки методи, що розглядаються в розділі квадратичного програмування, частково методи розв'язання задач з сепарабельного функціями і в значно меншому ступені прямі методи.
Завдання нелінійного програмування.
Розглянемо завдання математичного програмування:
, (1а)
(2а)
(3а)
,, (4а)
тут F (x) - цільова функція, вираз (2) - обмеження рівності, вираз (3) - обмеження нерівності, x - вектор змінних, Dj - деякі множини.
Якщо хоча б одна з функцій F (x),? i (x) - нелінійна, то це модель задачі нелінійного програмування. Рішення подібних завдань можливе тільки для деяких класів функцій F (x),? I (x), і коли Dj - безліч дійсних чисел
Завдання квадратичного програмування=окремий випадок задачі нелінійного програмування, в якій цільова функція=сума лінійної та квадратичної функції, а всі обмеження лінійни:
, (5а)
, (6а)
(7а)
або в матричному вигляді (P, x, B - вектори-стовпці):
, (8а)
, (9а)
(10а)
У виразі (8а) матриця С має бути симетричною і позитивно полуопределенной - це гарантує опуклість цільової функції (5а). Відомо, що для завдання опуклого нелінійного програмування справедлива теорема Куна-Таккера, що виражає необхідні умови того, що точка x0 є рішенням задачі нелінійного програмування:
(11а)
(12а)
де Ф=Ф (x,?) - функція Лагранжа.
Теоретично найбільш широко і детально в нелінійному програмуванні розроблено розділ опуклого програмування, званий квадратичним.
Методи квадратичного програмування можна розділити на три групи:
- Алгоритми, що використовують симплекс-метод;
- Градієнтні методи;
Інші спеціальні методи.
До першої групи можна віднести метод Баранкина і Дорфмана. Для пошуку опорного рішення в нашій задачі ми будемо використовувати саме його, тому що дана цільова функція являє собою суму лінійної та квадратичної функції, а всі обмеження лінійні.
3. Метод Баранкина-Дорфмана
Завдання формулюється наступним чином (у матричному вигляді):
P x + x Cx -> min,? b,
x? 0
Виходячи з теореми Куна-Таккера, позначимо:
У даному випадку умови Куна - Таккера запишуться у вигляді:
Ax + y=b; (1)
Cx - v + A l =-p; (2)
x? 0, Y? 0, V? 0, l? 0; (3) + Y l=0. (4)
Відзначимо, що останнє рівність (4) може виконуватися т...
