Прийняття управлінських рішень - Петруня Ю.Є. - Розділ 6. Використання нелінійного та динамічного програмування в розробці управлінських рішень

6.1. Нелінійне програмування

Економічні моделі та процеси переважно нелінійні. Для ефективного управління окремими об'єктами господарювання, галузями та національною економікою в цілому необхідне застосування нелінійних економіко-математичних моделей і методів.

Розглянемо ситуацію, коли для деякої виробничої системи необхідно визначити план виробництва продукції за умови якнайкращого використання наявних ресурсів. Для системи, яка досліджується, відомі запаси ресурсів, необхідні для виготовлення продукції, норми витрат кожного ресурсу на одиницю продукції, ціна реалізації одиниці продукції. За критерій оптимальності найчастіше беруть максимізацію прибутку від реалізації продукції, який подається лінійною залежністю. В умовах ринкової конкуренції питання збуту продукції стає складним, оскільки обсяг реалізації визначається переважно її ціною. Таким чином, критерій оптимальності розглядається як максимізація лише реалізованої продукції. Отже, потрібно визначити ціну одиниці продукції, яка забезпечить максимальний збут. У задачу таке значення ціни вводиться як невідоме, при цьому обмеження задачі мають ураховувати зв'язки між такими показниками, як ціна товару, витрати на рекламу та обсяги збуту продукції. Тобто, маємо ситуацію, коли цільова функція містить добуток двох невідомих величин, а це означає, що цільова функція стає нелінійною.

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

Нехай вектор X = |х1,х]Ч} визначає структуру портфеля цінних паперів; Я - випадкова величина норми прибутку цінних паперів 7-го

N

виду, і = 1, N детермінована величина тп = £ хіші - очікувана но-

¡=1

рма прибутку портфеля пінних паперів, де mi = M (Ri) - очікувана норма прибутку цінних паперів i-ro виду; о - оцінка ступеня ризику портфеля цінних паперів.

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

Математична модель задачі:

NN

min оя = min ^Hxixj°у,

x1,...,xn x1,...,xni=1 j=l

N

£ xi = 1, xi > 0, i = 1, N,

де oj = M((Rt -mi)(Rj - mj)J - коваріація випадкових величин R та Rj.

Задача одержання бажаного (фіксованого) прибутку полягає у виборі такої структури портфеля цінних паперів, за якої його очікувана норма прибутку буде не меншою заданого рівня - mc (mc = const), а ступінь ризику при цьому буде мінімальним.

Математична модель задачі:

2 NN

min о я = min Y^HXiXj а у ,

X1,...,xn X1,...,xni=1 j=1

NN

mn = Zximi > mC , 2xi = 1, xi > 0, i = 1, N.

Задача забезпечення приросту капіталу полягає у виборі такої структури портфеля цінних паперів, щоб ступінь його ризику не перевищував заданого рівня оL (оL = const) і при цьому досягалася б максимальна величина сподіваної норми прибутку.

Математична модель задачі:

max mn = max £ximi,

x1,...,xn x!,...,xni=1

2 NN 2 N

° и = HHxixj Qj < о2, 2 xi = 1, xi > 0, i = 1, N.

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

У загальному вигляді задача нелінійного програмування формулюється так: знайти значення змінних х1, х2, хп, щоб цільова функція

г = /(х1, х2,хп) набувала екстремального (максимального чи мінімального) значення

г = /(х1, х2,хп) -" шах(шіп);

за умов

[<

&і(х1, хп)їЬі, і = 1,т;

х] ^ 0, ; = 1, п,

де gi( х1, х2,..., хп) - відомі функції; Ьі - задані константи, і = 1, т.

Задачі нелінійного програмування, можна класифікувати за характером функцій та обмежень, якими вони описуються.

1. Класичні задачі оптимізації, де треба знайти умовний екстремум функції, тобто екстремум деякої функції за умови, що на змінні такої функції накладаються додаткові обмеження

г = /(х1, х2,хп) -" шах(шіп);

[ gi (х1, х2,..., хп ) = Ьі , і = 1, т; їх; > 0, і = 1,п,

Характерною особливістю цих задач є те, що її обмеження задані системою рівнянь. Якщо т = 0, то маємо класичну задачу відшукання безумовного екстремуму функції г = /(х1, х2, хп). Для класичних задач оптимізації суттєва вимога гладкості (існування і неперервність у

функцій_Дхь х2, хп) та gi(x1, х2, хп) (і = 1, т) частинних похідних

принаймні до 2-го порядку включно).

2. Задачі з нелінійною цільовою функцією і лінійними обмеженнями. Вони мають вигляд

г = _Дхь х2, хп) шіп; gi (х1, хп) = 2 сі^х; - Ь < 0, і = 1, т;

х; > 0, і = 1, п.

Характерна ознака таких задач полягає в тому, що їх допустима множина багатогранна.

Зауважимо, що задача максимізації функції f(x1, x2, xn) еквівалентна задачі мінімізації функції f(x1, x2, xn), обмеження gi(x1, x2, xn) > 0 еквівалентне обмеженню gi(x1, x2, xn) < 0. Тому при формулюванні й розв'язанні задач можна обмежитись лише одним з цих випадків.

3. Задачі опуклого програмування. Опукле програмування розглядає методи розв'язання задач нелінійного програмування, математичні моделі яких містять опуклі функції.

Функція fix) називається опуклою, якщо для довільних значень її аргументу x1 та x2 виконується нерівність

f (1x1 + (1 + VX2) ^ У(X1) + (1 - (X2), 0 < І < 1. Загальний вигляд задачі опуклого програмування такий:

z = f(x1, X2, Xn) -> min; gi(X1, X2,..., Xn) < 0, i = 1,m; |Xj > 0, j = 1, n,

дєf X1, X2, Xn), gi(X1, X2, Xn) -опуклі функції.

4. Задачі квадратичного програмування. У цих задачах потрібно мінімізувати квадратичну функцію

n n n

z = f (X1, X2,Xn) = ZCjXj + 2 ZdjXiXj min; при лінійних обмеженнях

gi (X1, X2,Xn ) = Z ajXj - bi < 0, i = 1, m;

Xj ^ 0, j = 1, n,

за умови, що f(X1, x2, Xn) є опуклою функцією.

Задачі квадратичного програмування можна зарахувати як до задач з нелінійною цільовою функцією і лінійними обмеженнями, так і до класу задач опуклого програмування. Але їх виділяють в окремий клас через специфіку цільової функції.

5. Задачі сепарабельного програмування. Для цих задач характерно те, що цільова функція і функції умов адитивні, тобто їх можна подати у вигляді

п 7=1

7=1

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