Моделювання оптимальної стратегії заміни обладнання за допомогою динамічного програмування (стр. 3 из 5)
Отже, зі знаходження рішення завдання динамічного програмування видно, що цей процес є досить громіздким. Тому більше складні завдання вирішують за допомогою ЕОМ.
Динамічне завдання по заміні встаткування можливо також вирішити й графічним методом. На осі Х відкладають номер кроку (к). на осі В – вік устаткування (t). Крапка (до-1; t) на площині відповідає початку К-ого кроку по експлуатації встаткування у віці t років.
Будь-яка траєкторія переводящая крапку S (k-1; t) зі стану S0 S. Складається з відрізків, тобто із кроків відповідним рокам експлуатації. Потрібно вибрати таку траєкторію при якій витрати на експлуатацію будуть мінімальні. Якщо відомі залежність продуктивності встановленого на підприємстві встаткування від часу його використання R(t) і залежність витрат на ремонт устаткування при різному часі його використання S(t) і витрати пов'язані із придбанням нового обладнання, то показником ефективності в цьому випадку є прибуток яка максимізується.2. Застосування динамічного програмування в економічних дослідженнях
програмування економічний дослідження динамічний
В економічних дослідженнях здавна застосовувалися найпростіші математичні методи. У господарському житті широко використаються геометричні формули. Так, площа ділянки поля визначається шляхом перемножування довжини на ширину або обсяг силосної траншеї – перемножуванням довжини на середню ширину й глибину. Існує цілий ряд формул і таблиць, що полегшують господарським працівникам визначення тих або інших величин.
Застосування арифметики, алгебри в економічних дослідженнях, є вже питанням про культуру дослідження, кожен поважаючий себе економіст володіє такими навичками. Особняком тут стоять так звані методи оптимізації, частіше називаються як економіко-математичні методи.
В 60-і роки нашого сторіччя розгорнулася дискусія про математичні методи в економіці. Наприклад, академік Немчинов виділяв п'ять базових методів дослідження при плануванні:
1) балансовий метод;
2) метод математичного моделювання;
3) векторно-матричний метод;
4) метод економіко-математичних множників (оптимальних суспільних оцінок);
5) метод послідовного наближення.
У той же час академік Канторович виділяв математичні методи в чотири групи:
– макроекономічні моделі, куди відносив балансовий метод і моделі попиту;
– моделі взаємодії економічних підрозділів (на основі теорії ігор);
– лінійне моделювання, включаючи ряд завдань, що небагато відрізняються від класичного лінійного програмування;
– моделі оптимізації, що виходять за межі лінійного моделювання (динамічне, нелінійне, ціле і стохастичне програмування).
І з тієї, і з іншою класифікацією можна сперечатися, оскільки, наприклад моделі попиту можна по ряду особливостей віднести до нелінійного програмування, а стохастичне моделювання йде коріннями в теорію ігор. Але все це проблеми класифікації, які мають певне методологічне значення, але в цьому випадку не настільки важливі.
Із крапки ж зору ролі математичних методів варто говорити лише про широту застосування різних методів у реальних процесах планування.
Із цього погляду безсумнівним лідером є метод лінійної оптимізації, що був розроблений академіком Канторовичем в 30-і роки ХХ-го століття. Найчастіше завдання лінійного програмування застосовується при моделюванні організації виробництва. От як по Канторовичу виглядає математична модель організації виробництва:
У виробництві беруть участь M різних виробничих факторів (інгредієнтів) – робоча сила, сировина, матеріали, устаткування, кінцеві й проміжні продукти й ін. Виробництво використає S технологічних способів виробництва, причому для кожного з них задані обсяги вироблених інгредієнтів, розраховані на реалізацію цього способу з одиничною ефективністю, тобто заданий вектор ak = (a1k, a2k,…, amk), k = 1,2…, S, у якому кожна з компонентів aіk указує обсяг виробництва, що відповідає (і-го) інгредієнта, якщо вона позитивна; і обсяг його витрати, якщо вона негативна (у способі k).
Вибір плану означає вказівка інтенсивності використання різних технологічних способів, тобто план визначається вектором x = (x1, x2,…, x) з невід’ємними компонентами.
Звичайно на кількості що випускають і затрачуваних інгредієнтів накладаються обмеження: зробити потрібно не менш, ніж потрібно, а затрачати не більше, ніж є. Такі обмеження записуються у вигляді
S a ikxk > bi; i=1,2,…, m. (2.1)
Якщо і > 0, то нерівність означає, що з потреба в інгредієнті в розмірі й, якщо і < 0, то нерівність означає, що є ресурс даного інгредієнтів розмірі – і =| і |. Далі передбачається, що використання кожного способу, пов'язаного з витратами одного з перерахованих інгредієнтів або особливо виділеного інгредієнта в кількості Ck при одиничній інтенсивності способу k. Як цільова функція приймається сумарна витрата цього інгредієнта в плані.
f(x) = S ckxk. (2.2)
Тепер загальне завдання лінійного програмування може бути представлена в математичній формі.
На основі об'єктивно обумовлених оцінок американським математиком Дж. Данцигом – був розроблений симплекс-метод рішення завдань оптимального програмування. Цей метод досить широко застосовується. Алгоритм його досить детально пророблений, і навіть розроблені прикладні пакети програм, які застосовуються в багатьох галузях планування.
Метод лінійної оптимізації з того моменту, як він був розроблений Канторовичем, не залишався без змін, він розвивався й продовжує розвиватися. Наприклад, формула (2.2) у сучасній інтерпретації виглядає в такий спосіб.
S aij xj < bi (i Î I) (2.3)
Аналогічно й з ресурсами, в обмеженні беруть участь не всі ресурси відразу, а якась їхня підмножина (і Î І).
Введенням підмножин не обмежилося вдосконалювання методу лінійної оптимізації. Потреби практики змусили розробити ще цілий ряд прийомів і методів для різних випадків опису реалій господарської практики у вигляді обмежень. Це такі прийоми, як запис обмежень по використанню виробничих ресурсів, запис обмежень по гарантованому обсязі робіт або виробництва продукції, прийоми моделювання при невідомих значеннях показників і багато хто інші, на яких тут не варто зупинятися.
Ціль всіх цих прийомів – дати більше розгорнуту модель якого-небудь явища з господарської практики, заощадивши при цьому на кількості змінних й обмежень.
Незважаючи на широту застосування методу лінійного програмування, він ураховує лише три особливості економічних завдань – велика кількість змінних, обмеженість ресурсів і необхідність цільової функції. Звичайно, багато завдань із іншими особливостями можна звести до лінійної оптимізації, але це не дає нам права випустити з уваги інший добре розроблений метод математичного моделювання – динамічне програмування. По суті, завдання динамічного програмування є описом багатокрокових дій із прийняття рішень. Завдання динамічного програмування можна сформулювати в такий спосіб:
є деяка кількість ресурсу х, яких можна використати N різними способами. Якщо позначити через хі кількість ресурсу, використовувана й-m способом, то кожному способу зіставляється функція корисності (хі), що виражає доход від цього способу. Передбачається, що всі доходи виміряються в однакових одиницях і загальному доході дорівнює сумі доходів, отриманих від використання кожного способу.
Тепер можна поставити завдання в математичній формі. Знайти
max y1(x1)+ y2(x2)+ … + yn(xn) (2.4)
(загальний доход від використання ресурсів всіма способами) при умовах:
– виділювані кількості ресурсів ненегативні;
[1] x1 > 0,…, x > 0
– загальна кількість ресурсів дорівнює x.
[2] x1 + x2 +… + x = x
Для цього загального завдання можуть бути побудовані рекуррентные
співвідношення
¦1(x) = max {j1(x1)}, (2.5)
0 <=X1<= X
¦k(x) = max {jk(xk)+ ¦k-1(x – xk)}. (2.6)
к = 2,3,…, N,
за допомогою яких перебуває її рішення.
При висновку цих рекурентних співвідношень, по суті, використався наступний принцип, оптимальна стратегія володіє тим властивістю, що стосовно будь-якого первісного стану після деякого етапу рішення сукупність наступних рішень повинна становити оптимальну стратегію. Цей принцип оптимальності лежить в основі всієї концепції динамічного програмування. Саме завдяки йому вдається при наступних переходах випробовувати не всі можливі варіанти, а лише оптимальні виходи. Рекурентні співвідношення дозволяють замінити надзвичайно трудомісткі обчислення максимуму по N змінним у вихідному завданні рішенням N завдань, у кожній з яких максимум перебуває лише по однієї змінній.
Таким чином, метод динамічного програмування дозволяє врахувати таку важливу особливість економічних завдань, як детермінованість більше пізніх рішень від більше ранніх.
Крім цих двох, досить детально розроблених методів, в економічних дослідженнях останнім часом стали застосовуватися безліч інших методів.
Одним з підходів до рішення економічних завдань є підхід, заснований на застосуванні нової математичної дисципліни – теорії ігор.
Суть цієї теорії полягає в тім, що гравець (учасник економічних взаємовідношень) повинен вибрати оптимальну стратегію залежно від того, якими він представляє дії супротивників (конкурентів, факторів зовнішнього середовища й т.д.). У залежності від того, наскільки гравець обізнаний про можливі дії супротивників, гри (а під грою тут розуміється сукупність правил, тоді сам процес гри це партія) бувають відкриті й закриті. При відкритій грі оптимальною стратегією буде вибір максимального мінімуму виграшу (у термінах Моргерштерна – «максі-міна») із всієї сукупності рішень, представлених у матричній формі. Відповідно супротивник буде прагне програти лише мінімальний максимум («міні – макс») який у випадку ігор з нульовою сумою буде дорівнює «максі-міну». В економіці ж частіше зустрічаються ігри з ненульовою сумою, коли виграють обоє гравця.