ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2020
Просмотров: 1200
Скачиваний: 2
65
Тоді
1
0
n
i
i
U
U
та пошук оптимальних стратегій повним перебиранням
вимагає перегляду
1
0
n
i
i
k
k
управлінь. Використовуючи принцип
Беллмана, маємо:
l
y
y
...,
,
1
– всі стани, з яких можливий перехід за один
крок до кінцевого стану
n
x
. Позначимо через
l
u
u
...,
,
1
оптимальні
управління, які переводять
0
x
за
1
n
крок у
l
y
y
...,
,
1
відповідно, а через
)
,
(
...,
),
,
(
0
1
1
0
1
l
n
n
u
x
J
u
x
J
– отримані доходи. Тоді оптимальне управління, які
переводять початковий стан
0
x
до кінцевого стану
n
x
, має вигляд
*
1
*
,
n
d
u
u
u
, де
d
u
знаходиться з умови
)
,
(
max
)
,
(
max
1
0
1
...,
,
1
u
y
Q
u
x
J
Arg
d
s
U
u
s
n
l
s
S
n
,
(83)
де
)
,
1
(
1
l
s
U
s
n
– множина управлінь, які переводять
s
y
у
n
x
;
*
1
n
u
визначається з умови
)
,
(
max
1
*
1
u
y
Q
Arg
u
d
d
n
U
n
.
(84)
Таким чином, задача знаходження оптимальної стратегії за
n
кроків
зводиться до
l
аналогічних
)
1
(
n
-кроковим задачам. Кількість варіантів
перебору управлінь при цьому зменшується, так як управління на
останньому кроці обирається у відповідності з (84), а інші управління з
d
n
U
1
вже не розглядаються.
Задача незалежного вибору
Нехай існує послідовність множин
n
...,
,
1
, кожна з яких міститься
у
m
E
. Альтернативою являється послідовність
;
...
...,
,
1
1
n
n
x
x
;
n
i
x
i
i
,
1
,
. Нехай
R
– бінарне відношення, яке задане на
m
E
. Будемо
вважати
x
всіх
для
E
x
x
n
i
m
i
1
)
(
.
(85)
Бінарне відношення
R
на
має вигляд
y
x
y
R
x
y
R
x
,
),
(
)
(
.
Задача полягає в тому, щоб знайти
R
, тобто недоміновані на
у
відношенні до
R
послідовності
n
x
x
...,
,
1
. Сформульована задача є
задачею незалежного вибору
, так як альтернатива в задачі являє собою
послідовність елементів, кожний з яких належить одній множині
i
, а
66
включення одного чи іншого елемента до послідовності не залежить від
наявних елементів.
Відповідно до багатокритеріальної задачі оптимального управління
маємо: множиною управлінь
U
являється множина
; окремому
управлінню відповідає точка з
i
. Послідовність
n
x
x
...,
,
1
точок,
обраних з кожного
i
, являє собою управління за
n
кроків. Відображення
множини управлінь
U
у просторі
m
E
визначається формулою (164).
Відношенню
R
в загальній задачі відповідає бінарне відношення, яке
задане на просторі доходів
m
E
.
Таким чином, задача незалежного вибору являє собою окремий
випадок загальної багатокритеріальної задачі оптимального управління
R
U
,
,
з визначеними вище параметрами. Для опису даної задачі
достатньо використовувати запис
R
,
. Параметр
виключений, так як
він також визначається за формулою (85).
Важливо. 1
-згорткою задачі
R
,
являється однокритеріальна
задача
,
~
, де
n
i
i
1
~
~
та
i
~
–
образ
i
при лінійному відображенні
g
:
1
E
E
m
, яке задається формулою
m
j
j
j
x
x
g
1
)
(
.
(86)
Послідовність точок
n
z
z
...,
,
1
на прямій являється її рішенням тоді,
коли
i
z
– максимальне число в
)
,
1
(
~
n
i
i
, що дозволяє знайти всі розв’язки
однокритеріальної задачі.
2
Якщо відношення
R
може бути відділено у вигляді
, то будь-яке
рішення
-згортки вихідної задачі при будь-якому
, що міститься у
дійсному конусі
KR
відношення
R
, являється розв’язком вихідної задачі.
У випадку кінцевої множини
для існування рішення задачі
R
,
достатньо відокремленості відношення
R
.
У випадку опуклого
та відношення
R
такого, що
R
R
K
, будь-яке
рішення задачі
R
,
при деякому
*
K
.
3
Якщо
n
i
i
x
1
(
i
x
– конус нормалей до всіх опорних
гіперплощин до
i
, які проходять через точку
i
i
x
), то послідовність
n
x
x
x
...,
,
1
парето-оптимальна.
4
Нехай
i
опуклі. Послідовність
n
x
x
x
...,
,
1
парето-оптимальна
тоді, коли
n
i
i
x
1
.
(87)
67
Багатокритеріальна задача з неперервним часом
Розглянемо систему
)
,
1
(
)
,
,
(
)
(
n
m
m
i
t
u
x
f
t
x
i
i
,
)
,
1
(
)
0
(
0
n
m
m
i
x
x
i
i
.
(88)
Введемо
m
критеріїв:
T
i
i
m
i
dt
t
t
u
t
x
f
u
x
0
)
,
1
(
)
),
(
),
(
(
)
,
(
.
(89)
На просторі
m
E
задана бінарна множина
R
, за яким порівнюються
різні управління.
Управлінням
U
u
загальної задачі відповідають всі кусочно-
неперервні вектор-функції, визначені на відрізку
T
,
0
, та набувають
значення у заданій області
U
простору
r
E
.
Відображення
:
m
E
U
визначається формулою (89), яка кожному
управлінню
U
u
зіставляє
m
-мірний вектор
)
(
...,
),
(
)
(
1
u
u
u
m
. Вектор
)
(
t
x
за
)
(
t
u
з (88). Тобто, відображення
в даному випадку залежить від
функцій
i
f
у (88) та початкових умов
0
x
. Відношенню
R
в загальній задачі
відповідає бінарне відношення, яке задане на
m
E
.
Багатокритеріальна задача оптимального управління з неперервним
часом
має вигляд:
).
,
0
(
)
(
),
,
1
(
0
)
0
(
),
,
1
(
)
0
(
),
,
1
(
)
,
,
(
)
(
),
,
,
,
(
)
(
0
0
T
t
U
t
u
m
i
x
n
m
m
i
x
x
n
m
i
t
u
x
f
t
x
R
x
f
U
t
u
i
i
i
i
i
(90)
де
)
,
,
,
(
0
R
x
f
U
– загальний розв’язок задачі.
Окремим розв’язком являється будь-яке управління
*
u
, що
задовольняє (90). Для рішення задачі використовується
-згортка.
Важливо 2
.
-згорткою задачі (90) являється однокритеріальна
задача
68
.
)
(
),
,
1
(
0
)
0
(
),
,
1
(
)
0
(
),
,
1
(
)
,
,
(
)
(
,
max
)
(
0
1
U
t
u
m
i
x
n
m
m
i
x
x
n
m
i
t
u
x
f
t
x
T
x
i
i
i
i
i
m
i
i
i
(91)
Розв’язок задачі (91) знаходиться за допомогою принципу
максимуму, який для задачі (91) набуває вигляду: нехай
)
(
~
),
(
~
t
x
t
u
-
оптимальне управління та відповідна траєкторія у задачі (91). Тоді існує
вектор-функція
)
(
~
...,
),
(
~
)
(
~
1
t
t
t
n
m
, яка задовольняє системі рівнянь
)
,
1
(
)
,
~
,
~
(
)
(
)
(
1
n
m
i
x
t
u
x
f
t
t
m
n
j
i
j
j
i
(92)
з кінцевими умовами
),
,
1
(
0
)
(
),
,
1
(
)
(
m
n
m
i
T
m
i
T
i
i
i
(93)
така, що при майже всіх
T
t
,
0
)
),
(
~
,
),
(
~
(
max
)
(
~
t
t
u
t
x
H
Arg
t
u
U
,
(94)
де
n
m
i
i
i
t
u
x
f
t
u
x
H
1
)
,
,
(
)
,
,
,
(
.
(95)
Множина
U
n
m
T
x
T
x
D
)
(
...,
),
(
1
(96)
кінців траєкторії при всіх припустимих управліннях
U
u
називається
множиною досягнення у задачі (91).
Важливо 3
. Нехай множина досягнення
D
опукла та
R
R
K
. Тоді для
будь-якого
)
,
,
,
(
0
*
R
x
f
U
u
існує
*
K
такий, що
*
u
являється
оптимальним розв’язком задачі (91) при
.
69
1.7
Моделі і методи стохастичного програмування [7-9]
1.7.1
Загальні
положення
методу
стохастичного
програмування
Наявність стохастичної невизначеності вносить у планування та
прийняття економічних рішень елемент ризику.
Для підприємств, які працюють за ринкових умов, встановлення
внутрішнього плану (програми), як правило, супроводжується
укладанням контрактів з оптовими споживачами, причому порушення
контракту призводить не тільки до явних економічних неприємностей
для підприємства (корпорації) у вигляді штрафів, але і до непрямих
наслідків, що йменуються «втрата інтересу і пріоритетності
споживачів». Завжди мають місце дві тенденції, що вступають у
протиріччя: з одного боку, прагнення до збільшення обсягу
зобов'язань, тобто у кінцевому результаті до збільшення валового
обсягу запрограмованої продукції чи прибутку, з іншого боку,
прагнення до зменшення ризику невиконання зобов'язання через
несприятливі зовнішні та внутрішні обставини протягом планового
періоду. Стохастичним програмуванням називають розділ математичного
програмування, що вивчає теорію, моделі й методи розв'язування
умовних екстремальних задач за неповної інформації щодо параметрів
умов задачі.
Предметом стохастичного програмування
є умовні екстремальні
задачі, де параметри умов чи складові розв'язку, або усі вони разом, є
випадковими величинами.
Постановка задач стохастичного програмування суттєво залежить
від цільових засад та інформаційної структури задачі.
Одна з постановок задачі управління і, зокрема, планування за
умов невизначеності та ризику полягає у наступному.
Припустимо, що вектор
х
позначає можливі рішення (альтернативи) з
деякої апріорно допустимої множини
X.
Раціональний вибір рішень
здійснюється з наслідків, до яких призводять ці рішення. Але наслідки
рішення залежать не лише від обраного вектора
х
є
X,
але й від випадкових
чинників (параметрів), котрі позначають через
. Значення
заздалегідь
невідомі. Вважають, що відома множина
, до якої належить вектор
.
Відносно розподілу
на множині
можуть бути різні гіпотези. У кращому
разі відомий точний закон розподілу
, у гіршому — лише те, що
.
Зв'язок між рішенням х та наслідками записують у виді функціональної
залежності
)
,
(
x
f
, яка називається моделлю.
Моделями можуть бути алгебраїчні співвідношення з випадковими
параметрами, стохастичні диференційні рівняння, марковські процеси та
інші.