Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота №15
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
АСУ
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Група:
КН 2
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра “Автоматизовані системи управління”
/
Лабораторна робота № 15
Задачі динамічного програмування
з курсу “ Методи оптимізації дослідження операцій”
Теоретичні відомості
Динамічне програмування — розділ математики, який присвячений теорії і методам розв'язання багатокрокових задач оптимального управління.
У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «прийняття рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.
Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)
1.1 Методика розв’язування динамічних задач
Нехай потрібно оптимізувати деякий керований процес, перебіг якого можна розбити на послідовні етапи (кроки), що задаються. Ефективність усього процесу Z є сумою ефективностей Zj () окремих кроків:
(адитивний критерій)
або
(мультиплікативний критерій).
З кожним кроком задачі пов’язане прийняття певного рішення, так званого покрокового управління хj (), що визначає як ефективність даного стану, так і всієї операції в цілому.
У задачі динамічного програмування знаходять таке управління X = (x1, x2, …, xn) всією операцією, яке максимізує її загальну ефективність:
Оптимальним розв’язком цієї задачі є управління Х* , що складається із сукупності оптимальних покрокових управлінь
і забезпечує максимальну ефективність Z*
Усі типи задач динамічного програмування розв’язують, керуючись основним принципом: яким би не був стан системи S перед черговим кроком, управління на цьому кроці слід вибрати так, щоб ефективність розглядуваного кроку в сумі з оптимальною ефективністю на всіх наступних кроках були максимальними (принцип Беллмана).
Отже, маємо наступний алгоритм розв’язування задач динамічного програмування:
Визначаємо специфіку стану заданої керованої системи та множини параметрів, які описують цей стан. Стан системи обираємо таким чином, щоб забезпечити зв’язок між послідовними етапами перебігу процесу та знайти допустимий розв’язок задачі в цілому як результат оптимізації на кожному кроці зокрема. При цьому оптимальні розв’язки на наступних етапах приймаємо, нехтуючи впливом наступних рішень на прийняті раніше.
Поділяємо динамічний процес на етапи (кроки), що відповідають, як правило, часовим періодам планування чи окремим об’єктам (підприємствам, видам продукції, устаткування тощо), стосовно яких розробляються управлінські рішення.
Формуємо перелік управлінських рішень xj () для кожного кроку та відповідні обмеження щодо них.
Визначаємо ефект, який забезпечується управлінським рішенням xj на j-му кроці, якщо перед тим система була в стані S:
.
Досліджуємо, як змінюється стан S системи під впливом управлінського рішення xj на j-му кроці:
Для розглядуваної задачі будуємо рекурентну залежність, яка визначає умовний оптимальний ефект Zj(s), починаючи з j-го кроку і до останнього, через уже відому функцію Zj+1(s’):
Цьому ефекту відповідає умовне оптимальне управління на j-му кроці (xj(s)). Зауважимо, що за аргумент функції Zj+1(s) беремо не s, а змінений стан системи, тобто .
Виконуємо умовну оптимізацію останнього n-го кроку, розглядаючи множину станів s, що на один крок віддалені від кінцевого стану, і визначаємо умовний оптимальний ефект на n-му кроці:
Далі знаходимо умовне оптимальне управлінське рішення xn(s), завдяки якому цей максимум досягається.
Здійснюємо умовну оптимізацію (n-1)-го, (n-2)-го і т. д., тобто всіх попередніх кроків за рекурентними залежностями згідно п. 6, тобто для кожного кроку знаходимо умовне оптимальне управління:
9. Виконуємо безумовну оптимізацію управління в «зворотному» напрямі – від початкового стану s0 до кінцевого. Для цього з урахуванням визначеного оптимального управління на першому кроці змінюємо стан системи згідно з п. 5. Далі для цього нового стану знаходимо оптимальне управління па другому кроці і діємо таким же чином аж до останнього кроку.
1.2 Приклади розв’язування динамічних задач.
Задача 1. Нехай деякій організації, яка має у своєму розпорядженні 4 млн. грн. інвестиційних коштів, потрібно збільшити виробничі потужності на чотирьох підприємствах. Для кожного з цих підприємств розроблені інвестиційні проекти, що відображають прогнозовані сумарні витрати С та доходи D, які пов’язані з реалізацією певного проекту. Зміст цих проектів проілюстрований в таблиці 1:
Таблиця 1.
Проект
Підприємство
1
2
3
4
С1
D1
С2
D2
С3
D3
С4
D4
1
0
0
0
0
0
0
0
0
2
1
3
1
4
2
4
1
2
3
2
5
2
6
3
9
2
8
4
3
7
3
8
4
12
3
5
Зауважимо, що перший проект передбачає відмову від розширення підприємств, а тому має нульові витрати і доходи.
Отже, потрібно розробити такий план інвестування виділених коштів у зазначені підприємства, щоб одержати максимальний прибуток.
Розв’язування. Найпростішим, але малоефективним способом розв’язування таких задач може бути перебір усіх можливих варіантів. Однак, на практиці їх може бути так багато, що проаналізувати всі і вибрати серед них найефективніший неможливо. Головними недоліками такого способу розв’язування є великий обсяг обчислень, відсутність апріорної інформації про неприпустимі розв’язки, а також неможливість скористатися проміжними результатами аналізу для відкидання неоптимальних комбінацій проектів.
Розв’яжемо цю задачу за алгоритмом (методом) зворотного прогону, а послідовними кроками задачі вважатимемо кожне з чотирьох підприємств, оскільки для кожного з них маємо вибрати оптимальний інвестиційний проект за обмежених грошових ресурсів, причому нединамічний процес розглядатимемо як динамічний, аби скористатися методами динамічного програмування для знаходження оптимального розв’язку. Зв’язок між зазначеними кроками забезпечується обмеженням на загальний обсяг виділених коштів – 4 млн. грн.
Змінні для задачі виберемо так, щоб послідовно керувати процесом розподілу коштів:
х1 – обсяг капіталовкладень, виділених на кроках 1 – 4;
х2 – те саме на кроках 2 – 4;
х3 – те саме на кроках 3 і 4;
х4 – те саме на кроці 4.
kі () – обсяги інвестицій на i-му підприємстві (ki = 0,1,2,3,4).
() – оптимальні обсяги інвестицій на i-му підприємстві.
Рекурентне співвідношення для зворотного прогону від 4-го до 1-го кроку (від четвертого до першого підприємства) можна подати наступним чином:
де – сумарна ефективність інвестицій з і-го кроку до останнього.
Тут оскільки п’ятого підприємства не існує.
У відповідності до цієї моделі виконаємо необхідні поетапні розрахунки, ілюструючи їх одержаним результатами .
Етап 4.
Результати розрахунків подамо таблицею 2:
Таблиця 2.
x4
Дохід
Оптимальний розв’язок
k4=0
k4=1
k4=2
k4=3
k4=4
0
0
0
0
0
1
0
2
2
1
2
0
2
8
8
2
3
0
2
8
5
8
2
4
0
2
8
.5
8
2
Етап 3.
за умов
Результати розрахунків відображає таблиця 3:
Таблиця 3.
x3
Дохід
Оптимальний розв’язок
k3=1
k3=2
k3=3
k3=4
0
0
0
1
2
0
2
8
0
3
9
3
4
12
2 або 4
Розрахунки виконуються так. Нехай потрібно знайти .
Обчислюємо
.
Отже,
Зауважимо, що С3 (k3=1) = 0, оскільки для третього підприємства не існує проекту з інвестиціями в 1 млн. грн. Значення беремо з попередньої таблиці. Далі маємо:
.
Етап 2.
за умов
Результати розрахунків відображає таблиця 4:
Таблиця 4.
x3
Дохід
Оптимальний розв’язок
k3 = 0
k3 = 1
k3 = 2
k3 = 3
k3 = 4
0
0
0
0
1
4
4
4
1
2
8
8
6
8
0
3
9
12
8
8
12
1
4
12
13
14
10
14
2
Етап 1.
за умов
Виконуємо розрахунки лише для х1 = 4, подаючи їх у вигляді таблиці 5:
Таблиця 5.
x3
Дохід
Оптимальний розв’язок
k3=1
k3=2
k3=3
k3=4
4
15
1
Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, який використовує 1 млн. грн. інвестицій з ефективністю 3 млн. грн. Отже, для другого, третього і четвертого підприємств залишається 4 – 1= 3 млн. грн. інвестицій.
Із таблиці другого кроку маємо, що за умов x2 = 3 максимальний ефект настає в разі реалізації для другого підприємства першого проекту (k2 = 1), ефективність становить 4 мли грн. Отже, x3 = 3 – 1 = 2, тобто для третього і четвертого підприємств можна використати тільки 2 млн. грн. інвестицій.
Із таблиці третього кроку за умов х3 = 2 маємо, що k3 = 0. Отже, x4 = 2, а йому відповідають капітальні вкладення k4 = 2, ефективність яких складає 8 млн. грн. Остаточно маємо: ефективність 4 млн. грн. інвестицій складає 3 + 4 + 8 = 15 (млн. грн.).
2. Виконання лабораторної роботи.
2.1 Завдання лабораторної роботи.
Вкладення коштів, тис.грн.
Прибутки підприємств, тис.грн.
f1
f2
f3
f4
0
0
0
0
0
100
50+x
60+x
65+x
45+x
200
150+x
135+x
140+x
100+x
300
215+x
195+x
195+x
225+x
400
275+x
265+x
280+x
270+x
Крайній правий розряд залікової книжки – 1, отже значення x =5.
Вкладення коштів, тис.грн.
Прибутки підприємств, тис.грн.
f1
f2
f3
f4
0
0
0
0
0
100
55
65
70
50
200
155
140
145
105
300
220
200
200
230
400
280
270
285
280
2.2 Аналітичний розв’язок без програмних пакетів.
Крок 1. Виділення коштів для одного підприємства та побудова функції
17.11.2017 17:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора