Моделювання оптимального розподілу інвестицій за допомогою динамічного програмування

СОДЕРЖАНИЕ: Теоретичні аспекти математичного моделювання динамічних систем: поняття і принципи, прийняття управлінських рішень з урахуванням фактору часу. Вирішення задач динамічного програмування: побудова і розрахунок моделі; оптимальний розподіл інвестицій.

Українська академія банківської справи

Національного банку України

Кафедра економічної кібернетики

КУРСОВА РОБОТА

з дисципліни «Моделювання економічної динаміки»

«Моделювання оптимального розподілу інвестицій за допомогою динамічного програмування »

Виконала: студентка 5-го курсу

групи ЕК-21

Бабенко Т.М.

Нормоконтроль: канд. фіз.-мат. наук Братушка С.М

Перевірила: ас. Хайлук С.О.

ЗМІСТ

Вступ

1. Теоретичні аспекти математичного моделювання динамічних систем

1.1 Основні поняття теорії моделювання

1.2 Принципи моделювання динамічних систем

1.3 Моделі і методи прийняття управлінських рішень з урахуванням фактору часу

1.4 Моделі динамічного програмування

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

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

2.2 Складання математичної моделі динамічного програмування

2.3 Етапи рішення задачі динамічного програмування

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

Висновки

Список використаної літератури

Додатки

ВСТУП

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

Динамічне програмування – розділ математики, який присвячено теорії і методам розв’язання багатокрокових задач оптимального керування.

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

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

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

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

1. ТЕОРЕТИЧНІ АСПЕКТИ МАТЕМАТИЧНОГО МОДЕЛЮВАННЯ ДИНАМІЧНИХ СИСТЕМ

1.1 Основні поняття теорії моделювання

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

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

б) інформаційні моделі й моделювання, що мають додатки в інформаційних системах;

в) вербальні (тобто словесні, текстові) язикові моделі;

г) інформаційні (комп’ютерні) технології, які треба ділити:

1) на інструментальне використання базових універсальних програмних засобів (текстових редакторів, СУБД, табличних процесорів, телекомунікаційних пакетів);

2) на комп’ютерне моделювання, що представляє собою:

- обчислювальне (імітаційне) моделювання;

- “візуалізацію явищ і процесів” (графічне моделювання);

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

Отже, укрупнена класифікація абстрактних (ідеальних) моделей така:

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

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

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

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

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

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

Шлях математичного моделювання в наш час набагато більш всеосяжний, ніж моделювання натурного. Величезний поштовх розвитку математичного моделювання дало поява ЕОМ, хоча сам метод зародився одночасно з математикою тисячі років тому.

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

Рисунок 1.1 – Загальна схема процесу комп’ютерного математичного моделювання

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

1.2 Принципи моделювання динамічних систем

інвестиція моделювання динамічний програмування

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

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

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

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

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

– Принцип параметризації. У ряді випадків система, що моделюється, має у своєму складі деякі відносно ізольовані підсистеми, що характеризуються певним параметром, у тому числі векторним. Такі підсистеми можна заміняти в моделі відповідними числовими величинами, а не описувати процес їхнього функціонування. При необхідності залежність значень цих величин від ситуації може задаватися у вигляді таблиці, графіка або аналітичного вираження (формули). Принцип параметризації дозволяє скоротити обсяг і тривалість моделювання. Однак треба мати на увазі, що параметризація знижує адекватність моделі [7].

1.3 Моделі і методи прийняття управлінських рішень з урахуванням фактору часу

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

Проблемна ситуація може виникати за умов коли:

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

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

в) система вимагає докорінних змін поставлених цілей.

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

Рисунок 1.2 – Етапи процесу прийняття управлінських рішень з урахуванням фактору часу

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

– Чи є альтернатива реалістичною?

– Чи відповідає альтернатива можливостям організації?

– Чи є прийнятними наслідки реалізації альтернативи?

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

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

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

– задачі в умовах визначеності;

– задачі в умовах імовірнісної визначеності;

– задачі в умовах невизначеності.

Отже, для кожної групи умов в практиці управління використовуються та чи інша методологія.

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

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

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

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

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

Рисунок 1.3 – Схема методів обґрунтувань управлінських рішень

Методи математичного програмування. Застосовуються при рішенні умовних екстремальних задач з багатьма змінними.

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

1.4 Моделі динамічного програмування

Модель є образним представленням якогось об’єкту чи процесу і використовується для аналізу або вивчення цього об’єкту чи процесу.

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

Вперше математичні моделі були використані для рішення практичного завдання в 30-х роках у Великобританії при створенні системи протиповітряної оборони. Для розробки даної системи були залучені вчені різних спеціальностей. Система створювалася в умовах невизначеності щодо можливих дій супротивника, тому дослідження проводилися на адекватних математичних моделях. У цей час вперше був застосований термін: “операційне дослідження”, що припускало дослідження воєнної операції. У наступні роки операційні дослідження або дослідження операцій розвиваються як наука, результати якої застосовуються для вибору оптимальних рішень при керуванні реальними процесами й системами.

Можна виділити наступні основні етапи операційного дослідження:

- спостереження явища й збір вихідних даних;

- постановка задачі;

- побудова математичної моделі;

- розрахунок моделі;

- тестування моделі й аналіз вихідних даних. Якщо отримані результати не задовольняють дослідника, то треба або повернутися на етап побудови математичної моделі, тобто запропонувати для рішення задачі іншу математичну модель; або повернутися на етап постановки задачі, тобто поставити задачу більш коректно;

- застосування результатів досліджень.

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

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

Проведення операційного дослідження, побудова й розрахунок математичної моделі динамічного програмування дозволяють проаналізувати ситуацію й вибрати оптимальні рішення по керуванню нею або обґрунтувати запропоновані рішення. Застосування математичних моделей динамічного програмування необхідно в тих випадках, коли проблема складна, залежить від великої кількості факторів, що по-різному впливають на її рішення. У цьому випадку непродумане й науково не обґрунтоване рішення може привести до серйозних наслідків. Прикладів цьому в нашому житті є чимало, зокрема в економіці. Використання математичних моделей динамічного програмування дозволяє здійснити попередній вибір оптимальних або близьких до них варіантів рішень за певними критеріями. Вони науково обґрунтовані, і особа, що приймає рішення, може керуватися ними при виборі остаточного рішення. Варто розуміти, що не існує рішень, оптимальних “взагалі”. Будь-яке рішення, отримане при розрахунку математичної моделі динамічного програмування, оптимально по одному або декількох критеріях, запропонованим постановником завдання й дослідником. До речі, практика показує, що займатися операційними дослідженнями й побудовою математичних моделей динамічного програмування найкраще не “чистим” математикам, що не завжди представляють собі сутність досліджуваної проблеми й приділяють більшу увагу різним математичним особливостям побудови й розрахунку, і не предметникам, які не завжди можуть коректно поставити завдання. Гарні результати одержують фахівці, що знають предметну область і разом з тим володіючи математичними методами дослідження у динамічному програмуванні. У теперішній час математичні моделі динамічного програмування застосовуються для аналізу, прогнозування й вибору оптимальних рішень у різних галузях економіки. Це планування й оперативне керування виробництвом, управління трудовими ресурсами, управління запасами, розподіл ресурсів, планування й розміщення об’єктів, керівництво проектом, розподіл інвестицій і т.п.

Можна виділити наступні основні етапи побудови математичної моделі динамічного програмування.

а) Визначення мети, тобто чого хочуть домогтися, вирішуючи поставлене завдання.

б) Визначення параметрів моделі, тобто заздалегідь відомих фіксованих факторів, на значення яких дослідник не впливає.

в) Формування керуючих змінних, змінюючи значення яких можна наближатися до поставленої мети. Значення керуючих змінних є рішеннями задачі.

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

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

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

Вводяться наступні умовні позначки: – параметри моделі; – керуючі змінні або рішення; – область припустимих рішень; – випадкові або невизначені фактори; – цільова функція або критерій ефективності (критерій оптимальності).

. (1.1)

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

, (1.2)

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

. (1.3)

Таким чином, оптимальне рішення – це рішення, краще перед іншими за певним критерієм ефективності (одному або декільком).

Основні принципи побудови математичної моделі динамічного програмування.

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

б) Математична модель динамічного програмування повинна відбивати істотні риси досліджуваного явища й при цьому не повинна його сильно спрощувати.

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

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

На рисунку 1.4 зображена класифікація математичних моделей і місце динамічних моделей у загальній структурі [1].

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

По обліку невідомих факторів математичні моделі діляться на детерміновані, стохастичні й моделі з елементами невизначеності.

У стохастичних моделях невідомі фактори – це випадкові величини, для яких відомі функції розподілу й різні статистичні характеристики (математичне очікування, дисперсія, середньоквадратичне відхилення й т.д.). Серед стохастичних можна виділити:

- моделі стохастичного програмування, у яких в цільову функцію (1.2) входять випадкові величини;

- моделі теорії випадкових процесів, призначені для вивчення процесів, стан яких у кожен момент часу є випадковою величиною;

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

Рисунок 1.4 – Класифікація математичних моделей

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

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

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

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

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

Графічні моделі використаються тоді, коли завдання зручно представити у вигляді графічної структури.

2. ТЕОРЕТИЧНІ АСПЕКТИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

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

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

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

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

Нехай – кількість етапів. На будь-якому і-му етапі процес може бути в різних станах {}, кожний з яких характеризується скінченою множиною параметрів. Множину параметрів доцільно розглядати як компоненти деякого вектора , де – кількість параметрів, обраних для характеристики стану. На будь-якому з досліджуваних етапів система може бути в кількох станах.

Перебіг процесу визначається певною послідовністю переходів з одного стану в інший. Якщо процес на і-му етапі перебував у деякому стані , то наступний стан на (і+1)-му кроці визначається не лише попереднім станом, а й вибором певного управління при досягненні (;). У загальному випадку будь-яке управління на будь-якому етапі доцільно розглядати як -мірний вектор . Числові значення компонент вектора управління будуть залежати як від вихідного стану на і-му кроці, так і від наступного стану на (і+1)-му кроці , тобто вектор визначається чотирма індексами і має бути вибраний з певної множини допустимих управлінь.

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

Рисунок 1.5 – Можливі стани системи на кожному етапі

На рисунку 1.5 схематично кругами зображені можливі стани на кожному етапі, лініями – можливі переходи від одного стану до іншого за вибору певного управління. Таким чином, стан процесу на і-му етапі визначається певною функціональною залежністю від стану на попередньому кроці та значеннями параметрів управління на початку чергового кроку, тобто . Процес управління моделюється як вибір за кожного можливого j-го стану на і-му етапі певного k-мірного вектора з деяких допустимих множин векторів {}. Для спрощення він позначається . Множина послідовності управлінь позначається – , які переводять систему зі стану у стан , схематично це представлено на рисунку 1.6.

Рисунок 1.6 – Перехід системи із стану у стан

Будь-яку послідовність , що переводить систему зі стану у стан , називається стратегією, а вектори – її складовими.

Ефективність вибору послідовності управлінь (стратегії) оцінюється за вибраним критерієм певною цільовою функцією :

. (2.1)

Модель динамічного програмування можна використовувати в тих випадках, коли є підстави прийняти такі допущення стосовно досліджуваної системи:

– Стан системи в кінці і-го кроку визначається лише попереднім станом та управлінням на і-му кроці і не залежить від попередніх станів та управлінь. Формула (2.2) – рівняння стану.

, . (2.2)

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

, . (2.3)

Тоді цільова функція (2.1) буде представлена формулою (2.4)

. (2.4)

Метод динамічного програмування також можна використовувати при розв’язанні задач з так званою “мультиплікативною” цільовою функцією, тобто:

. (2.5)

Задача динамічного програмування за названих умов формується так: визначити таку допустиму стратегію управління:

. (2.6)

Дана стратегія переводить систему зі стану у стан і за якої цільова функція (2.4) досягає екстремального значення.

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

, (2.7)

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

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

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

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

Оптимальне управління – це значення управління , при якому значення є максимальним (або мінімальним, якщо потрібно зменшити програш):

,, (2.8)

де – область припустимих управлінь.

Оптимальне управління визначається послідовністю оптимальних крокових управлінь:

. (2.9)

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

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

Інший момент, котрий варто враховувати при виборі управління на даному кроці, – це можливі варіанти закінчення попереднього кроку. Ці варіанти визначають стан процесу. Наприклад, при визначенні кількості коштів, вкладених у підприємство в і-му році, необхідно знати, скільки коштів залишилося в наявності до цього року і який прибуток отриманий у попередньому (і-1)-м році. Таким чином, при виборі крокового управління необхідно враховувати:

– можливі результати попереднього кроку;

– вплив управління на всі кроки, що залишилися, до кінця процесу.

У задачах динамічного програмування перший пункт враховують, роблячи на кожному кроці умовні припущення про можливі варіанти закінчення попереднього кроку й проводячи для кожного з варіантів умовну оптимізацію. Виконання другого пункту забезпечується тим, що в задачах динамічного програмування умовна оптимізація проводиться від кінця процесу до початку. Спершу оптимізується останній m-й крок, на якому не треба враховувати можливі впливи обраного управління на всі наступні кроки, тому що ці кроки просто відсутні. Роблячи припущення про умови закінчення (m-1)-го кроку, для кожного з них проводять умовну оптимізацію m-го кроку й визначають умовне оптимальне управління . Аналогічно діють для (m-l)-го кроку, роблячи припущення про стан закінчення (m-2)-го кроку й визначаючи умовне оптимальне управління на (m-1)-му кроці, що приносить оптимальний виграш на двох останніх кроках – (m-1)-му і m-му. Так само діють на всіх інших кроках до першого. На першому кроці, як правило, не треба робити умовних припущень, тому що стан системи перед першим кроком звичайно відомо.

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

2.2 Складання математичної моделі динамічного програмування

Додатково вводяться наступні умовні позначки:

– стан процесу;

– безліч можливих станів процесу перед і-м кроком;

– виграш із і-го кроку до кінця процесу, .

Можна визначити наступні основні етапи складання математичної моделі задачі динамічного програмування [1].

– Розбивка задачі на кроки (етапи). Крок не повинен бути занадто дрібним, щоб не проводити зайвих розрахунків і не повинен бути занадто великим, ускладнюючий процес крокової оптимізації.

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

– Визначення безлічі крокових управлінь , й накладених на них обмежень, тобто області припустимих управлінь .

– Визначення виграшу:

, (2.10)

який принесе на і-му кроці управління , якщо система перед цим перебувала в стані .

– Визначення стану , у яке переходить система зі стану під впливом керування :

, (2.11)

де – функція переходу на і-му кроці зі стану у стан .

– Складання управління, що визначає умовний оптимальний виграш на останньому кроці, для стану моделюємого процесу:

. (2.12)

– Складання основного функціонального рівняння динамічного програмування, що визначає умовний оптимальний виграш для даного стану з і-го кроку й до кінця процесу через уже відомий умовний оптимальний виграш із (і+1)-го кроку й до кінця:

. (2.13)

У рівнянні (2.13) у вже відому функцію , що характеризує умовний оптимальний виграш із (і+1)-го кроку до кінця процесу, замість стану підставлений новий стан , у яке система переходить на і-му кроці під впливом управління .

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

2.3 Етапи рішення задачі динамічного програмування

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

– Визначення безлічі можливих станів для останнього кроку.

– Проведення умовної оптимізації для кожного на останньому m-му кроці по формулі (2.12) й визначення умовного оптимального управління ,.

– Визначення безлічі можливих станів для і-го кроку, .

– Проведення умовної оптимізації і-го кроку, для кожного стану по формулі (2.13) і визначення умовного оптимального управління , , .

– Визначення початкового стану системи , оптимального виграшу і оптимального управління по формулі (2.13) при . Це є оптимальний виграш для всієї задачі .

– Проведення безумовної оптимізації управління. Для проведення безумовної оптимізації необхідно знайдене на першому кроці оптимальне управління підставити у формулу (2.11) і визначити наступний стан системи . Для зміненого стану знайти оптимальне управління , підставити у формулу (2.11) і так далі. Для і-гo стану , знайти і і т.д. [1].

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

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

Виграшем у даній задачі є прибуток, принесена підприємствами.

Побудова математичної моделі.

– Визначення числа кроків. Число кроків дорівнює числу підприємств, в котрі здійснюється інвестування.

– Визначення станів системи. Стан системи на кожному кроці характеризується кількістю коштів , наявних перед даним кроком, .

– Вибір крокових управлінь. Управлінням на і-му кроці , є кількість коштів, котрі інвестуються і-те підприємство.

– Функція виграшу на і-му кроці:

. (3.1)

– це прибуток, котрий приносить і-те підприємство при інвестуванні в нього коштів .

. (3.2)

Отже, дана задача може бути вирішена методом динамічного програмування.

– Визначення функції переходу в новий стан:

. (3.3)

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

– Складанні функціонального рівняння для .

. (3.4)

А також:

. (3.5)

На останньому кроці, тобто перед інвестування коштів в останнє підприємство, умовне оптимальне управління відповідає кількості коштів, що маються в наявності; тобто скільки коштів залишилось, стільки й необхідно вкласти в останнє підприємство. Умовний оптимальний виграш дорівнює прибутку, котрий приноситься останнім підприємством.

– Складання основного функціонального рівняння.

Підставивши у формулу (2.13) вираження (3.1) і (3.3), отримуємо наступне функціональне рівняння:

. (3.6)

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

Проведення автоматизації розподілу інвестицій між підприємствами здійснюється із застосуванням ЕОМ, оснащеної спеціальним програмним засобом MS EXCEL. До розгляду береться, що =5000, =3.

Таблиця 3.1 – Прибуток підприємств , від інвестування в них коштів

, тис. у.о.	, тис. у.о.	, тис. у.о.	, тис. у.о.
1	1,5	2	1,7
2	2	2,1	2,4
3	2,5	2,3	2,7
4	3	3,5	3,2
5	3,6	4	3,5

Для , .

Вхідні умови зображені на рисунку А.1 (Додаток А). Для простоти у задачі зроблено припущення, що вкладаються тільки тисячі умовних одиниць. Проводиться умовна оптимізація. По її результатам заповнюється таблиця 3.2.

Таблиця 3.2 – Результати умовної оптимізації

s
1	1	1,7	0	2
2	2	2,4	1	3,7
3	3	2,7	1	4,4
4	4	3,2	1	4,7
5	5	3,5	1/4	5,2	2	6,4

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

Детальний розгляд результатів умовної оптимізації.

а) Проведення умовної оптимізації для останнього кроку . Функціональне рівняння на останньому кроці має вигляд:

, . (3.7)

На рисунку 3.1 ілюстраційно зображено результати проведення умовної оптимізації для останнього кроку.

Виходячи з цього, два стовпця таблиці 3.2, котрі відповідають , заповнюються автоматично по таблиці вихідних даних.

Рисунок 3.1 – Результати умовної оптимізації для останнього кроку

б) Умовна оптимізація для .

Функціональне рівняння має вигляд:

. (3.8)

Для проведення умовної оптимізації заповнюються допоміжні таблиці 3.3–3.7, котрі відповідають різним значенням , тобто різним закінченням попереднього кроку, результати практичного дослідження відображені на рисунках А.2–А.4 (Додаток А).

Таблиця 3.3 – Наявність коштів у розмірі умовних одиниць після закінченням попереднього кроку

0	1	0	1,7	1,7
1	0	2	0	2

, звідси:

– ;

– .

Таблиця 3.4 – Наявність коштів у розмірі умовних одиниць після закінченням попереднього кроку

0	2	0	2,4	2,4
1	1	2	1,7	3,7
2	0	2,1	0	2,1

, звідси:

– ;

– .

Таблиця 3.5 – Наявність коштів у розмірі умовних одиниць після закінченням попереднього кроку

0	3	0	2,7	2,7
1	2	2	2,4	4,4
2	1	2,1	1,7	3,8
3	0	2,3	0	2,3

, звідси:

– ;

– .

Таблиця 3.6 – Наявність коштів у розмірі умовних одиниць після закінченням попереднього кроку

0	4	0	3,2	3,2
1	3	2	2,7	4,7
2	2	2,1	2,4	4,5
3	1	2,3	1,7	4
4	0	3,5	0	3,5

, звідси: ; – .

Таблиця 3.7 – Наявність коштів у розмірі умовних одиниць після закінченням попереднього кроку

0	5	0	3,5	3,5
1	4	2	3,2	5,2
2	3	2,1	2,7	4,8
3	2	2,3	2,4	4,7
4	1	3,5	1,7	5,2
5	0	4	0	4

.

Для , можливі два умовних оптимальних рівняння:

– ;

– .

Рисунок 3.2 – Результати умовної оптимізації для другого підприємства

в) Умовна оптимізація для .

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

Таблиця 3.8 – Наявність коштів у розмірі умовних одиниць перед першим кроком

0	5	0	5,2	5,2
1	4	1,5	4,7	6,2
2	3	2	4,4	6,4
3	2	2,5	3,7	6,2
4	1	3	2	5
5	0	3,6	0	3,6

, звідси:

– ;

– .

Вираз (3.9) відображає оптимальний прибуток, що дають три підприємства при інвестуванні в них коштів у розмірі 5 тисяч умовних одиниць, дорівнює 6,4 тисяч умовних одиниць.

. (3.9)

Рисунок 3.3 – Результати умовної оптимізації для першого підприємства

Проведення безумовної оптимізації. Її результати ілюстраційно відображено на рисунку Б.1 додатку Б.

– , , ; .

– по формулі (3.3) . ; .

– , . ; .

Отриманий результат – .

Таблиця 3.9 – Результати проведення безумовної оптимізації

Таким чином, для отримання максимального прибутку у розмірі 6400 умовних одиниць, необхідно по 2000 умовні одиниці вкласти в перше і третє підприємства і 1000 умовну одиницю – у друге підприємство. Графічно це відображено на графіку В.1 у додатку В.

ВИСНОВКИ

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

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

Практичний аналіз динамічного програмування розглядався на прикладі оптимального розподілу інвестицій між підприємствами, мета розподілу полягала у максимізації загального прибутку від інвестування. У результаті практичної реалізації було встановлено, що для отримання максимального прибутку у розмірі 6400 умовних одиниць, необхідно по 2000 умовні одиниці вкласти в перше і третє підприємства і 1000 умовну одиницю – у друге підприємство. Необхідно зазначити, що отримане рішення є лише деяким наближенням до оптимального рішення. Його можна покращити, тобто приблизити до оптимального, взявши менший крок оптимізації, наприклад вкладати у підприємства кошти, кратні 500 умовним одиницям, а отже існує широкий простір для подальшої і більш глибокої роботи.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Хазанова И.Э. Математическое моделирование в экономике: Учебное пособие. –М.: Издательство БЕК, 1998. – 132 с.

2. Сіднєв С.П., Шарапов О.Д. Математичні методи підвищення якості управлінських рішень: Підручник.-К.: ІЗМН, 1997. – 258 с.

3. Основи комп’ютерних алгоритмів. Динамічне програмування. – http://moodle.ukma.kiev.ua.

4. Вікіпедія. Вільна енциклопедія. Стаття про динамічне програмування. – http://uk.wikipedia.org.

5. Мажукин В.И., Королева О.Н. Математическое моделирование в экономике: Учебное пособие. – М.: Издательство “Флинта” МГУ, 2004. – 232с.

6. Самарский А.А., Михайлов Ф.П. Математическое моделирование. М.: Наука. 1997. – 212 с.

7. Клебанова Т.С., Дубровина Н.А., Полякова О.Ю., Раевнева Е.В., Моделирование экономической динамики: Учебное пособие. – Х.: Издательский дом “ИНЖЭК”, 2005. – 244 с.

Додаток А

Лист “Вхідна форма”

Проведення умовної оптимізації для другого підприємства за умови вкладання 1000 і 2000 умовних одиниць

Проведення умовної оптимізації для другого підприємства за умови вкладання 3000 і 4000 умовних одиниць

Проведення умовної оптимізації для другого підприємства за умови вкладання 5000 умовних одиниць

Проведення умовної оптимізації для першого підприємства за умови вкладання 5000 умовних одиниць

Додаток Б

Результати проведення безумовної оптимізації

Додаток В

Оптимальний розподіл інвестицій

Скачать архив с текстом документа