183950 (629983), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Інший момент, котрий варто враховувати при виборі управління на даному кроці, – це можливі варіанти закінчення попереднього кроку. Ці варіанти визначають стан процесу. Наприклад, при визначенні кількості коштів, вкладених у підприємство в і-му році, необхідно знати, скільки коштів залишилося в наявності до цього року і який прибуток отриманий у попередньому (і-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 (Додаток А). Для простоти у задачі зроблено припущення, що вкладаються тільки тисячі умовних одиниць. Проводиться умовна оптимізація. По її результатам заповнюється таблиця 3.2.

Характеристики

Список файлов курсовой работы