Для розробкинелінійних оптимізаційних моделей економічних систем вирішуються задачі нелінійного програмування.
Нелінійне програмування - математичні методи визначення максимуму або мінімуму функції за наявності обмежень у вигляді нерівностей або рівнянь. Максимізувавши або мінімізувавши функція є прийнятим критерієм ефективності вирішення задачі, відповідним поставленій меті. В цьому випадку цей критерій має назву цільової функції.
Цільова функція задач нелінійного програмування полягає в тому, щоб знайти умови, що обертають цільову функцію в мінімум або максимум. Рішення, що задовольняє умові задачі і відповідне наміченій меті, називається оптимальним планом. Нелінійне програмування служить для вибору найкращого плану розподілу обмежених ресурсів в цілях вирішення поставленої задачі. В загальному вигляді постановка задачі нелінійного програмування зводиться до наступного. Умови задачі представляються за допомогою системи нелінійних рівнянь або нерівностей, що виражають обмеження, які накладається на використання наявних ресурсів.
В загальному вигляді математична модель задачі нелінійного програмування формулюється наступним чином:
f =(x1,x2, …,хn) → min (max). (6.1)
При цьому ці змінні повинні задовольняти обмеженням:
g1(x1,x2, …,хn) ≤b1,
…………………………
gm(x1,x2, …,хn) ≤bm,
gm+1(x1,x2, …,хn) ≥bm+1,
…………………………(6.2)
gk(x1,x2, …,хn) ≥bk,
gk+1(x1,x2, …,хn)=bk+1,
………………………
gp(x1,x2, …,хn)=bp.
x1,x2,…,хn ≥0, де одна із функцій f, gi нелінійна.
Для задач нелінійного програмування немає єдиного методу вирішення. Залежно від виду цільової функції і системи обмежень розроблені спеціальні методи вирішення, до яких відносяться метод множників Лагранжа, градієнтні методи, наближені методи вирішення, графічний метод.
Розглянемо деякі з них. Основні ідеї графічного методу: максимум і мінімум досягається в точках дотику лінії рівня з областю допустимих рішень, яка задається системою обмежень. Наприклад, якщо лінії рівня - прямі, то точки дотику можна визначити, використовуючи геометричне значення похідної.
Розглянемо на прикладах вирішення задач нелінійного програмування.
1. Знайти екстремуми функції L(x1,x2)=x1+2x2 при обмеженнях
, .
|
Область допустимого вирішення – це частина кола з радіусом 5, яка розташована в I чверті. Знайдемо лінії рівня функції L: x1+2x2=C. Виразимо x2=. Лініями рівня будуть паралельні прямі з кутовим коефіцієнтом, який дорівнює -. Мінімум функції досягається в точці (0;0), Lmin=0, оскільки градієнт (1,2) спрямовано вверх вправо. Максимум досягається в точці дотику кривої х2=та лінії рівня. Оскільки кутовий коефіцієнт дотику до графіку функції дорівнює -, знайдемо координати точки дотику, використовується геометричне значення похідної.
=-; ()=-;
=-; x0=; x2=2.
Тоді L=+2∙2=5.
Відповідь: Мінімум досягається в точці О(0;0), глобальний максимум, дорівнює 5, в точці А(;2) .
2. Знайти екстремуми функції L=(x1-6)2+(x2-2)2 при обмеженні
x1+x2≤8
3 x1+x2 ≤15
x1+x2 ≥1
.
Вирішення
Область допустимого вирішення – багатокутник ABCDE. Лінії рівня представляють собою окружність (x1-6)2+(x2-2)2=С з центром в точці О1(6;2). Візмимо, наприклад, С=36, бачимо, що максимум досягає в точці А(0;4), яка лежить на окружності найбільшого радіусу, який пересікається з областю допустимого вирішення L(A)=(0-6)2+(4-2)2=40. Мінімум - в точці F, яка знаходиться на перетені прямої 3x1+x2 =15 і перпендикуляру до цієї прямої, виведеного із точки О1. Оскільки кутовий коефіцієнт дорівнює -3, то кутовий коефіцієнт перпендикуляру дорівнює . Із рівняння прямої, яка проходить через точку О1 з кутовим коефіцієнтом , отримаємо (x2-2)= (x1-6). Знайдемо координати точки Е
х1-3х2=0
3 x1+x2 =15.
Вирішивши систему, отримаємо Е(4.5; 1.5).
L (E) = (4.5-6)2+ (1.5-2)2=2.5.
Відповідь: Мінімум дорівнює 2.5 досягається в точці (4.5; 1.5), максимум дорівнює 40 в точці (0;4).
3. Знайти екстремуми функції L=(x1-1)2+(x2-3)2 при обмеженнях , .
Вирішення
Область допустимого вирішення є частина кола з центром на початку координат з радіусом 5, яка розташована в I чверті. Лінії рівня – це окружності з центром в точці О1 і радіусі С, оскільки (x1-1)2+(x2-3)2=С. Точка О1 – це розроблена лінія рівня, яка відповідає мінімальному значенню С=0. глобальний максимум досягається в точці А, яка знаходиться на веретену області допустимого вирішення з лінією рівня найбільшого радіусу. При цьому L(A)=(5-1)2+(0-3)2=25.
Відповідь: Мінімум, дорівнює 0, досягається в точці (1;3), максимум, дорівнює 25, - в точці А(5;0).
4. Підприємець вирішив виділити на розширення своєї справи 150 тис. грн. Відомо, якщо на придбання нового устаткування затрачувати х тис. грн., а на зарплату прийнятих працівників у тис. грн., то приріст обсягу продукції складе Q=0.001x0.6·y0.4. Як необхідно розподілити виділені грошові ресурси, щоб приріст обсягу продукції був максимальним.
Вирішення
Цільова функція має вид 0.001x0.6·y0.4 →max при обмеженнях
x+y≤150,
.
Область допустимого вирішення – трикутник. Лінії рівня будуть мати вид 0.001x0.6·y0.4 =С. Виразивши у, отримуємо у=. Оскільки максимум досягається в точці дотику лінії рівня з областю допустимого вирішення, то умова дотику має вигляд =-1. Знайдемо похідну, отримаємо =-1. Виразивши х, отримаємо х=. у==.
Відповідь: Фактори х і у необхідно розподілити у відношенні 2:3.
Сутність методу Лагранжа складається в побудові функції L(x1,x2, …,хn)= f(x1,x2, …,хn)+gi(x1,x2, …,хn), де невідомі постійні, і знаходженні екстремуму функції L.
Має сенс наступна теорія: якщо точка () є точкою умовного екстремуму функції f(x1,x2, …,хn) за умови g(x1,x2, …,хn)=0, то існують значення такі, що точка () є точкою екстремуму функції L().
Розглянемо метод Лагранжа для функції двох змінних.
L(x1,x2,)= f(x1,x2)+g(x1,x2)
Таким чином, для знаходження умовного екстремуму функції f(x1,x2) за умови g(x1,x2)=0 необхідно знайти вирішення системи
L=f (x1,x2)+g(x1,x2)=0, (6.3)
L=f (x1, x2) +g(x1, x2) =0,
L= g(x1, x2) =0.
Якщо і додаткові умови, при виконанні яких вирішення (x1,x2,) системи (6.3) визначає точку, в якій функція f досягає екстремуму, для цього потрібно розрахувати значення і скласти визначник
=-.
Якщо <0, то функція має в точці () умовний максимум, якщо >0 – то умовний мінімум.
Вирішимо задачу методом множинника Лагранжа.
Загальні витрати виробництва задані функцією Т=0,5х2+0,6ху+0,4у2+ +700х+600у+2000, де х і у відповідно кількість товарів А і В. Загальна кількість виробленої продукції повинна дорівнювати 500 одиниць. Скільки одиниць товару А і В потрібно виробити, щоб витрати на їх виготовлення були мінімальними?
Вирішення
Складемо функцію Лагранжа
L(x, y, ) =0,5х2+0,6ху+0,4у2+ +700х+600у+2000+(х+у-500).
Дорівнюючи до нулю її часні похідні, отримаємо
х+0,6у+700+ =0,
0,6х+0,8у+600+ =0,
х+у-500=0.
Вирішивши систему знайдемо (0, 500, -1000).
Використаємо достатні умови для визначення знайденого значення
L(x0,y0)=1, L(x0,y0)=0.8, L(x0,y0)=0.6. Функція g= х+у-500. g=1, g=1.
=-(0·L·L+ g·L· g+ g·g·L- g·L·g-0·L·L- g· g·L)=0,6>0
Таким чином, в точці (0;500) функція L має умовний мінімум.
Відповідь: Вигідно виробляти тільки 500 одиниці товару В, а товар А не виробляти.