ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2020
Просмотров: 1186
Скачиваний: 2
60
1.6.2
Особливості задач динамічного програмування
Управління
– це організація того або іншого процесу, що забезпечує
досягнення певних цілей.
Етапи управління:
1)
збір й обробка інформації з метою оцінки сформованої
ситуації;
2)
ухвалення рішення про доцільні дії;
3)
реалізація схваленого рішення;
4)
(іноді) контроль виконання рішення.
Особливість задач управління: рішення повинне бути прийняте
незалежно від того, може чи ні ОПР точно оцінити результати, до яких
приведе схвалене рішення.
Прийняття рішень здійснюється в умовах невизначеності, тобто коли
інформація про складну ситуацію або недостатня, або перекручена.
Види та критерій якості задач управління
1
Одноетапні (однокрокові) задачі: ідеалізація реального процесу
управління.
2
Багатокрокові задачі: процес управління розбитий на кілька
кроків, причому рішення, прийняте на якому-небудь кроці, залежить від
результатів попереднього кроку, тобто безперервний динамічний процес
управління.
Критерій якості управління
– кількісна оцінка ступеня виконання
вимог, накладених на спосіб управління, з врахуванням обмежень, що
накладаються на процес управління.
Приклад.
Задача залежності між сумою інвестиційних вкладень, що
виділяються, та отриманням прибутку на кожному підприємстві (табл.19).
Таблиця 19 - Вихідні дані
Капітальні вкладення, тис. грн
Прибуток підприємства, тис. грн
А
Б
В
Г
0
0
0
0
0
200
12
14
13
18
400
33
39
38
40
600
40
46
45
44
800
60
64
60
65
1000
70
80
75
85
Розв’язання
. Планована система складається з 4 підприємств.
Початкова точка S
0
відповідає стану системи, коли є капітальні вкладення
x = 1 млн. грн, які необхідно розподілити між даними підприємствами.
Кінцева точка S
k
відповідає стану системи, коли всі капітальні вкладення
витрачені, тобто
x=0
. Рішення завдання розбивається на 4 етапи, кожний з
61
яких відповідає 1 із чотирьох підприємств. Сума капітальних вкладень
0;200;...;1000 тис. грн., отже, і можливі залишки нерозподілених на
початок кожного періоду капітальних вкладень можуть набувати значення,
відповідно, 1000;...;0 тис. грн.
Управління на
i
-му етапі U
1
зводиться до знаходження такого
варіанта розподілу наявної на початок етапу суми капіталовкладень
x
i
k
(k=0;200;…;1000) між
i
-м підприємством і наступним, при якому
загальний прибуток був би максимальним.
А в цілому, завдання зводиться до знаходження шляху від S
0
до S
k
, за
яким забезпечується розподіл капітальних вкладень між підприємствами з
одержанням максимального прибутку.
Застосовуємо наступні функціональні рівняння:
)}
(
{(
)
(
4
4
4
0
4
max
x
f
x
F
x
x
,
)}
(
)
(
{(
)
(
3
4
3
3
0
3
max
3
x
x
F
x
f
x
F
x
x
,
)}
(
)
(
{(
)
(
2
3
2
2
0
2
max
2
x
x
F
x
f
x
F
x
x
,
)}
(
)
(
{(
)
(
1
2
1
1
0
1
max
1
x
x
F
x
f
x
F
x
x
.
0
,
18
0
14
13
0
max
)
200
(
3
3
opt
x
F
;
0
,
40
0
40
13
18
38
0
max
)
400
(
3
3
opt
x
F
;
400
,
56
0
44
13
40
38
18
45
0
max
)
600
(
3
3
opt
x
F
;
400
,
78
0
65
13
44
38
40
45
18
60
0
max
)
800
(
3
3
opt
x
F
;
62
600
,
85
0
85
13
65
38
44
45
40
60
18
75
0
max
)
1000
(
3
3
opt
x
F
.
0
,
18
0
18
14
0
max
)
200
(
2
2
opt
x
F
;
0
,
40
0
40
14
18
39
0
max
)
400
(
2
2
opt
x
F
;
400
,
57
0
56
14
40
39
18
46
0
max
)
600
(
2
2
opt
x
F
;
400
,
79
0
78
14
56
39
40
46
18
64
0
max
)
800
(
2
2
opt
x
F
;
400
,
95
0
88
14
78
39
56
46
40
64
18
80
0
max
)
1000
(
2
2
opt
x
F
.
Таким чином, максимальний прибуток становить 95 тис. грн. При
цьому інвестиції доцільно розподілити таким чином: підприємство Г –
200 тис.грн; підприємство В – 400 тис.грн.; підприємство Б – 400 тис.грн;
підприємство А – 0 тис.грн.
63
1.6.3
Динамічні багатокритеріальні задачі [11]
У багатьох випадках управління
U
u
являється кінцевим чи
нескінченним набором
...
,
,
1
0
u
u
u
деяких дій. Наприклад,
U
u
являє
собою послідовність
...
,
,
1
0
u
u
u
окремих рівнянь, які обираються у
послідовні моменти часу
,...
1
,
0
t
Тоді загальну багатокритеріальну задачу
управління вдасться звести до послідовності більш простих задач,
пов’язаних з окремими управліннями
...
,
,
1
0
u
u
Найбільш важливим являється припущення щодо спеціального виду
структури доходів. Нехай доход наданий у вигляді:
1
Суми кінцевої скінченної кількості складаючих
1
0
0
)
...,
,
(
)
(
),
(
)
(
n
i
i
i
i
i
i
u
u
u
u
a
u
.
(75)
2
Суми нескінченого ряду
0
0
)
...,
,
(
)
(
),
(
)
(
i
i
i
i
i
i
u
u
u
u
a
u
,
(76)
де
...
,
,
1
0
u
u
u
,
i
a
– задані константи, які забезпечують сходження
ряду в (155).
3
Визначеного інтегралу
T
ds
s
u
f
u
0
))
(
(
)
(
,
(77)
де
)
(
t
u
u
на відрізку
T
,
0
.
Суттєво, що у всіх випадках доход
)
(
u
являється сумою доходів,
отриманих від окремих управлінь, а також що відношення
R
інваріантне
відносно
перенесення.
Будемо
називати
динамічними
багатокритеріальними задачами оптимального управління
задачі, де:
1)
управління представимо у вигляді послідовності дій;
2)
доход адитивний відносно окремих рівнянь;
3)
відношення інваріантне відносно перенесення.
Задача з дискретним часом
Нехай
n
x
x
x
...,
,
,
1
0
- стани системи
X
такі, що
)
(
...,
),
(
,
1
0
1
0
n
n
x
T
x
x
T
x
c
x
.
(78)
64
Це визначає, що на множині станів системи
X
діє перетворення
T
; в
початковий момент
0
t
система знаходилася у стані
c
x
x
)
0
(
0
, у момент
1
t
система знаходилася у стані
)
(
0
1
x
T
x
і так далі. Динамічний процес,
який описується перетворенням (78), являється некерованим. Для
керованого процесу необхідно мати можливість на кожному кроці
здійснювати не одиничне перетворення
)
(
k
x
T
, а одне з множини
перетворень
)
(
...,
),
(
1
k
r
k
x
T
x
T
. Зручно вважати, що певний вигляд
перетворення визначається параметром
k
u
, який на
k
-му кроці може
набувати значення з множини значень
k
U
. Параметр
k
u
називається
управлінням, а
k
U
– множина припустимих управлінь на
k
-му кроці. Для
керованого процесу послідовність (78) має вигляд
c
x
x
n
k
U
u
u
x
T
x
k
k
k
k
k
)
0
(
,
1
,
0
,
),
,
(
0
1
. (79)
Доход за один крок залежить від стану процесу на початок кроку та
використаного на цьому кроці управління:
k
k
k
k
k
U
u
u
x
Q
Q
),
,
(
.
(80)
за критерій якості управління приймається повний доход за
n
кроків
процесу:
1
0
0
,
(
)
,
(
n
k
k
k
n
u
x
Q
u
x
J
,
(81)
де
u
– послідовність управлінь,
1
1
0
...,
,
,
n
u
u
u
u
.
Задача оптимального управління з дискретним часом
для
n
-
крокового процесу полягає у знаходженні такої послідовності управлінь
1
1
0
...,
,
,
n
u
u
u
, при якій доход
)
,
(
0
u
x
J
n
буде максимальним. Управління
U
u
u
u
u
n
*
*
*
*
1
1
0
...,
,
,
називається
0
x
– оптимальним, якщо для будь-якого
управління
U
u
)
,
(
)
,
(
*
0
0
u
x
J
u
x
J
n
n
.
(82)
Для знаходження оптимальних управлінь використовується принцип
Беллмана: якими б не були початковий стан
0
x
та початкове управління
0
u
,
наступне управління повинно бути оптимальним відносно стану, який
являється результатом використання початкового управління.
Нехай
*
*
*
*
1
1
0
...,
,
,
n
u
u
u
u
–
0
x
-оптимальне управління. Тоді
управління
*
*
*
*
1
1
0
...,
,
,
~
n
u
u
u
u
за принципом Беллмана
1
x
-оптимальне.
Принцип Беллмана дозволяє спростити знаходження оптимальних
стратегій. Дійсно, нехай
i
i
k
U
(
i
U
– множина управлінь на
i
-му кроці).