§3. Нелінійне програмування
Розв’язуючи задачі оптимального управління (планування), доводиться враховувати нелінійний характер взаємозв’язків між економічними показниками. У загальному вигляді нелінійна економіко-математична модель має вигляд:
Z =f(x1, x2, …, xn) →max (min)
За умов:
qi (x1, x2, …, xn) {≤, =, ≥} bi
де: f(x1, x2, …, xn), qi (x1, x2, …, xn) – нелінійні функції.
Для розв’язування задач нелінійного програмування не існує універсального методу, тому доводиться застосовувати набір методів і обчислювальних алгоритмів, які грунтуються на теорії диференційного числення, і вибір їх залежить від конкрнтної постановки задачі та форми економіко-математичної моделі.
Методи нелінійного програмування бувають прямі і непрямі. Прямими методами оптимальні розв’язки відшукують у напрямку найшвидшого збільшення (зменшення) цільової функції. Типовими, для цієї групи методів є градієнтні. Непрямі методи полягають у зведені задачі до такої, знаходження оптимуму якої можна спростити. До них належать найбільш розроблені методи квадратичного і сепарабельного програмування.
Оптимізаційні задачі, на змінні яких не накладаються обмеження, розв’язуються методами класичної математики. Оптимізацію з обмеженнями-рівностями виконують методами зведеного градієнта, такими як метод Якобі та метод множників Лагранжа. У задачає оптимізації з бмеженнями-нерівностями досліджують необхідні і достатні умови існування екстремуму Куна-Таккера.
Розглянемо метод множників Лагранжа на прикладі такої нелінійної задачі:
Z =f(x1, x2, …, xn) → max (min) (3.1)
qi (x1, x2, …, xn) = bi (3.2)
( i = 1:m)
Де функції qi (x1, x2, …, xn) і f(x1, x2, …, xn) - диференційовані.
Ідея методу множників Лагранжа полягає у заміні даної задачі простішою: на знаходження екстремуму скаднішої функції, але без обмежень. Ця функція називається функцією Лагранжа і подається у вигляді:
L(x1, x2, …, xn λ1, λ2, …, λm) =
=
f(x1,
x2,
…, xn)
+
(3.3)
Де λі – не визначені поки що величини, множники Лагранжа.
Знайшовши частинні похідні функції L за усіма змінними і прирівнявши їх до нуля:
(3.4)
Запишемо систему, що є, як правило, нелінійною:
(3.5)
Розв’язавши цю систему, знайдемо Х* = (x1, x2, …, xn) і λ*= (λ1, λ2, …, λm) – стаціонарні точки. Оскільки їх визначено із необхідної умови екстремуму, то в них можливий максимум або мінімум. Іноді стаціонарні точки є точками перегину (сідлова точка). Для визначення достатніх умов екстремуму існують спеціальні методи.
Приклад. Ррозв’язати задачу методом Лагранжа.
Попит на продукцію, що виготовляється на двох видах обладнання, становить 120 одиниць. Собівартість виробництва продукції на обладнанні кожної групи залежить від обсягу виробництва – відповідно х1, х2 – та подається у вигляді для першої групи: 3х1 +4х12; для другої групи :5х22. знайти оптимальний план виробництва продукції на кожній групі обладнання, який за умови задоволення попиту потребує найменших витрат, пов’язаних із собівартісттю продукції.
Розв’язок.
Математична модель задачі:
Z =3х1 +4х12 +5х22 → min
Функція Лагранжа:
L(x1, x2 , λ) =3х1 +4х12 +5х22 + λ(120- x1 - x2)
Прирівнявши до нуля частинні похідні цієї функції за невідомими параметрами x1, x2 , λ отримаємо систему рівнянь:
Розв’язавши цю систему маємо:
х1 = 66,5, х2 = 53,5; λ = 535
Отже, на першій групі обладнання необхідно випускати 66,5, а на другій 53,5 одиниць продукції. При цьому мінімальні витрати становитимуть:
Z =3·66,6 +4·(66,5)2 + 5·(53,5)2 = 32199,75 (грошових одиниць).