Застосування динамічного програмування в економічних дослідженнях

2. Застосування динамічного програмування в економічних дослідженнях

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

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

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

В 60-і роки нашого сторіччя розгорнулася дискусія про математичні методи в економіці. Наприклад, академік Немчинов виділяв п'ять базових методів дослідження при плануванні:

1) балансовий метод;

2) метод математичного моделювання;

3) векторно-матричний метод;

4) метод економіко-математичних множників (оптимальних суспільних оцінок);

5) метод послідовного наближення.

У той же час академік Канторович виділяв математичні методи в чотири групи:

– макроекономічні моделі, куди відносив балансовий метод і моделі попиту;

– моделі взаємодії економічних підрозділів (на основі теорії ігор);

– лінійне моделювання, включаючи ряд завдань, що небагато відрізняються від класичного лінійного програмування;

– моделі оптимізації, що виходять за межі лінійного моделювання (динамічне, нелінійне, ціле і стохастичне програмування).

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

Із крапки ж зору ролі математичних методів варто говорити лише про широту застосування різних методів у реальних процесах планування.

Із цього погляду безсумнівним лідером є метод лінійної оптимізації, що був розроблений академіком Канторовичем в 30-і роки ХХ-го століття. Найчастіше завдання лінійного програмування застосовується при моделюванні організації виробництва. От як по Канторовичу виглядає математична модель організації виробництва:

У виробництві беруть участь M різних виробничих факторів (інгредієнтів) – робоча сила, сировина, матеріали, устаткування, кінцеві й проміжні продукти й ін. Виробництво використає S технологічних способів виробництва, причому для кожного з них задані обсяги вироблених інгредієнтів, розраховані на реалізацію цього способу з одиничною ефективністю, тобто заданий вектор a_k = (a_1k, a_2k,…, a_mk), k = 1,2…, S, у якому кожна з компонентів a_іk указує обсяг виробництва, що відповідає (і-го) інгредієнта, якщо вона позитивна; і обсяг його витрати, якщо вона негативна (у способі k).

Вибір плану означає вказівка інтенсивності використання різних технологічних способів, тобто план визначається вектором x = (x1, x2,…, x) з невід’ємними компонентами.

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

S a _ikx_k > b_i; i=1,2,…, m. (2.1)

Якщо і > 0, то нерівність означає, що з потреба в інгредієнті в розмірі й, якщо і < 0, то нерівність означає, що є ресурс даного інгредієнтів розмірі – і =| і |. Далі передбачається, що використання кожного способу, пов'язаного з витратами одного з перерахованих інгредієнтів або особливо виділеного інгредієнта в кількості Ck при одиничній інтенсивності способу k. Як цільова функція приймається сумарна витрата цього інгредієнта в плані.

f(x) = S c_kx_k. (2.2)

Тепер загальне завдання лінійного програмування може бути представлена в математичній формі.

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

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

S a_ij x_j < b_i (i Î I) (2.3)

Аналогічно й з ресурсами, в обмеженні беруть участь не всі ресурси відразу, а якась їхня підмножина (і Î І).

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

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

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

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

Тепер можна поставити завдання в математичній формі. Знайти

max y₁(x₁)+ y₂(x₂)+ … + y_n(x_n) (2.4)

(загальний доход від використання ресурсів всіма способами) при умовах:

– виділювані кількості ресурсів ненегативні;

[1] x1 > 0,…, x > 0

– загальна кількість ресурсів дорівнює x.

[2] x1 + x2 +… + x = x

Для цього загального завдання можуть бути побудовані рекуррентные

співвідношення

¦₁(x) = max {j₁(x₁)}, (2.5)

0 <=X₁<= X

¦_k(x) = max {j_k(x_k)+ ¦_k-1(x – x_k)}. (2.6)

к = 2,3,…, N,

за допомогою яких перебуває її рішення.

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

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

Крім цих двох, досить детально розроблених методів, в економічних дослідженнях останнім часом стали застосовуватися безліч інших методів.

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

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

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

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

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

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

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