Материал: Економетрія - Навчальний посібник ( Лугінін О.Є.)


3.3. Інші лінійні та нелінійні методи знаходження оптимальних рішень економічних задач

 

3.3.1. Лінійні методи оптимізаційних задач

 

До лінійних оптимізаційних методів, крім розглянутого метода ЛП, можуть бути віднесені такі: цілочисельне програмування; параметричне програмування; дрібно-лінійне програмування; стохастичне програмування; теорія ігор; метод найскорішого спуску та ін.

Цілочисельне програмування, як частковий випадок ЛП, припускає, що значення змінних (наприклад, кількість одиниць обладнання, машин тощо) та цільової функції є дискретними, або цілочисельними. Такі задачі можуть бути вирішені сімплекс-методом. Але при цьому за пропозицією американського математика Р.Гоморі (1956 р.) система обмежень задачі ЛП доповнюється лінійними обмеженнями, які забезпечують цілочисельність рішення. Такі обмеження називають перерізом Гоморі і вони складаються з дрібної частини чисел.

Так, для лінійного обмеження у задачі ЛП

переріз Гоморі записується у вигляді:

(3.20)

(3.21) де ііj=аіj-[аіJ; и=Ьг[Ьі]; [ау], [Ь] найбільша ціла частина коефіцієнтів ау, Ьі; іц, іі невід'ємні дрібні частини коефіцієнтів ау, Ьі.

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

Математична модель задачі має вигляд:

X {pj + tqj )x~j — max;

 

Xajxj — bi{i = 1-m);

(3.22)

 

j=1

Xj > 0 ij = 1...n),

 

де t параметр, який змінюється у інтервалі ta — t — tb; ta, tb деякі дійсні числа; qj коефіцієнти цільової функції (j=1...ri).

Для фіксованих за відповідною програмою значень параметра t=a в заданому інтервалі [ta tb] вирішується задача ЛП із знаходженням такого t, для якого досягається max Zt.

Дрібно-лінійне програмування має значну роль у тих випадках, коли використовуються не абсолютні, а відносні показники, для яких треба знати екстремальне рішення (максимальне або мінімальне).

У такому разі математична модель задачі має вид:

Z c1jxj

 

Z

j=1

■ —> max

jmin);

 

Z c2Jxj

j=1

 

Zajxj -bi j =1...m);

(3.23)

 

j=1

 

x

> 0 {j = 1...n),

 

де c1j, c2j коефіцієнти, які задаються для цільової функції.

Задача вирішується сімплекс-методом.

Стохастичне програмування це один з найперспективніших напрямків у розвитку математичного програмування. У вище розглянутих методах ЛП вхідні дані (коефіцієнти цільової функції та обмежень) і результати розрахунку (змінні, які забезпечують оптимальність рішення) є детермінованими величинами. Вони вибирались та знаходились в умовах визначеності та повної інформації. Але в ряді задач планування і управління доводиться часто зустрічатися з випадками, коли вхідні дані та рішення на їх основі носять випадковий (ймовірний характер). Такі задачі математичного програмування та засновані на них моделі називають стохастичними (ймовірними). Вони відрізняються від детермінованих задач тим, що рішення приймається в умовах ризику та невизначеності інформації. Особливістю задач стохастичного програмування є прийняття довірчих інтервалів вихідних даних та отримання значення цільової функції із певною мірою ймовірності.

Для вирішення задач стохастичного програмування існують методи, з якими можна познайомитись у спеціальній літературі, зазначеній у [22]. В останні роки набувають розвитку нелінійні методи і засновані на них моделі стохастичного програмування.

Теорія ігор була запропонована при розробці моделей економічних систем на початку XX ст. (Дж. фон Нейман) і в наступний час апарат теорії ігор, як і математичного програмування, використовується для знаходження оптимальних рішень.

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

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

І

 

С

--

А

 

 

 

 

Рисунок 3.1 Пошук оптимального рішення МНС

теорії ігор надані у посібнику [22].

Метод найскорішого спуску            (МНС) є

обчислювальним інструментом у вирішенні оптимізаційних задач і виступає альтернативою до методу ЛП. Тут потрібно більше обчислень для кожної ітерації (знаходження цільової функції та змінних в однієї з вершин многогранника допустимих рішень) порівняно з симплекс-методом, однак оптимальне рішення може бути знайдено за меншу кількість ітерацій. Ідея МНС ілюструється на рис. 3.1.

Згідно з МНС пошук оптимального рішення починається з деякої точки А усередині області допустимих рішень О. Пошук

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

області О. Подальший рух за напрямом вектора-градієнта г обгрунтовується тим, що в цьому напрямку збільшення цільової функції відбувається у найбільшій мірі (ХІ>ХІ-1). Нарешті досягається точка X, де має місце Хтах.

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

3.3.2. Нелінійні методи оптимізації

 

До нелінійних методів знаходження оптимізаційних рішень, які використовуються в економічній практиці, відносяться такі методи нелінійного програмування: випукле програмування; динамічне програмування; стохастичне програмування та ін. У нелінійних задачах широко застосовується МНС.

Нелінійне програмування (НП) це сукупність ряду спеціальних методів, у яких цільова функція і обмеження є нелінійними функціями відносно змінних.

У загальному вигляді задача НП може бути надана у такому вигляді:

 

 

 

дех2, хп), gi(xl, х2, хп) нелінійні залежності цільової функції та обмежень.

Окремі методи нелінійного програмування надані нижче.

Випукле програмування може бути розглянуте як спрощений метод загальної задачі НП.

У методі мінімізується випукла цільова функція і область допустимих  рішень   представляється   випуклою множиною.

 

у

Випукла цільова функція має важливу властивість: любий мінімум у області допустимих рішень є глобальним і відсутні локальні мінімуми. Для приклада у функції з одною незалежною змінною у=/(х) її випуклість означає, що графік функції завжди знаходиться по один бік від відрізка прямої АВ, який з'єднує точки А та В (рис. 3.2): /(а)>/(у)</ф).

 

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

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

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

(3.25)

де х об'єм ресурсів у розпорядженні об'єднання; у - кількість ресурсів, виділених для одного підприємства; /(у), g(x-y) відомі функції, що виражають прибуток підприємств після одного періоду планування; а, Ь параметри, які відповідають витратам виробництва на випуск і реалізацію продукції та зменшенню ресурсів     до     начала     другого     періоду планування

(0 < а < 1;0 < Ь < І).

Рішення задачі полягає у послідовному знаходженню функцій Бі(х), Б2(х), ...Бп(х).

Запитання для самоконтролю

Які методи існують при вирішенні задач ЛП?

Пояснити суть графічного методу. Коли він може бути використаний?

Пояснити принципову суть сімплекс-методу.

Яка задача ЛП називається двійчастою?

Як із прямої задачі ЛП можна получити запис двійчастої задачі?

3.2.6.   Навести приклад економічної інтерпретації двійчастої задачі ЛП.

Пояснити суть транспортної задачі.

Яка модель транспортної задачі називається закритою? відкритою?

Які випадки мають місце для відкритих моделей? Як це позначається на обмеженнях задачі?

 

Пояснити суть цілочисельного програмування.

Які обмеження називаються "перерізом Гоморі"? Яка їх структура?

 

В яких випадках використовується на практиці параметричне програмування?

В яких випадках використовується дрібно-лінійне програмування?

 

Пояснити суть стохастичного програмування.

В яких випадках може бути використаний апарат теорії ігор?

Пояснити суть методу найскорішого спуску.

3.2.17. В яких випадках використовується нелінійні методи знаходження оптимізаційних рішень?

3.2.18. Сформулювати задачу випуклого (квадратичного) програмування.

3.2.19. Яка функція називається випуклою?

3.2.20. В яких випадках використовується динамічне програмування?

3.2.21. Пояснити суть динамічного програмування на прикладі задачі про оптимальний розподіл капіталовкладень.