konspect_2010

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 підприємств. Початкова точка S0 відповідає стану системи, коли є капітальні вкладення x = 1 млн. грн, які необхідно розподілити між даними підприємствами. Кінцева точка Sk відповідає стану системи, коли всі капітальні вкладення витрачені, тобто x=0. Рішення завдання розбивається на 4 етапи, кожний з

60

яких відповідає 1 із чотирьох підприємств. Сума капітальних вкладень 0;200;...;1000 тис. грн., отже, і можливі залишки нерозподілених на початок кожного періоду капітальних вкладень можуть набувати значення, відповідно, 1000;...;0 тис. грн.

Управління на i -му етапі U1 зводиться до знаходження такого варіанта розподілу наявної на початок етапу суми капіталовкладень xik (k=0;200;…;1000) між i -м підприємством і наступним, при якому загальний прибуток був би максимальним.

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

Застосовуємо наступні функціональні рівняння:

F4 (x) max{( f4 (x4 )},

0 x4 x

F3 (x) max{( f3 (x3 ) F4 (x x3 )},

0 x3 x

F2 (x) max{( f2 (x2 ) F3 (x x2 )},

0 x2 x

F1 (x) max{( f1 (x1 ) F2 (x x1 )}.

0 x1 x

F (200) max 0 13 18,				xopt 0 ;
3				3
	14 0
	0 38			xopt 0 ;
F (400) max		40,
3	18	13		3
	40	0
	0 45
				x	opt	400	;
F (600) max 18		38 56,
3					3
	40 13
		0
	44
	0 60
	18 45
F3					opt	400	;
	(800) max		78,	x3
	40	38
	44 13
	65	0

61

	0 75
	18 60
F (1000) max 40 45 85,			xopt 600 .
3			3
	44 38
	65 13
	85 0

F (200) max 0 14 18,
2
	18 0
F2	0 39
	(400) max		40,
	18	14
		0
	40
	0 46
F (600) max 18		39 57,
2
	40 14
	56 0
	0 64
	18 46
F2
	(800) max		79,
	40	39
	56 14
	78	0

0 8018 64

F (1000) max 40 46 95,

2 56 39

78 1488 0

x2opt 0 ;

x2opt 0 ;

x2opt 400 ;

x2opt 400 ;

x2opt 400 .

Таким чином, максимальний прибуток становить 95 тис. грн. При цьому інвестиції доцільно розподілити таким чином: підприємство Г – 200 тис.грн; підприємство В – 400 тис.грн.; підприємство Б – 400 тис.грн; підприємство А – 0 тис.грн.

62

1.6.3 Динамічні багатокритеріальні задачі [11]
У багатьох випадках управління u U		являється	кінцевим	чи
нескінченним набором u u0 , u1 ,...	деяких дій.	Наприклад, u U являє
собою послідовність u u0 , u1 ,...	окремих рівнянь, які		обираються	у

послідовні моменти часу t 0,1,... Тоді загальну багатокритеріальну задачу управління вдасться звести до послідовності більш простих задач, пов’язаних з окремими управліннями u0 , u1 ,...

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

1 Суми кінцевої скінченної кількості складаючих

	n 1
	(u) ai i (u), i		(u) i (u0 ,..., ui ) .	(75)
	i 0
2	Суми нескінченого ряду
	(u) ai i (u), i		(u) i (u0 ,..., ui ) ,	(76)
	i 0
де u u0 , u1 ,... , ai – задані константи, які забезпечують сходження
ряду в (155).
3	Визначеного інтегралу
	T
	(u) f (u(s))ds ,			(77)
	0
де u u(t) на відрізку 0,T .
Суттєво, що у всіх випадках доход			(u) являється сумою доходів,
отриманих від окремих управлінь, а також що відношення				R інваріантне
відносно	перенесення.	Будемо	називати	динамічними

багатокритеріальними задачами оптимального управління задачі, де:

1)управління представимо у вигляді послідовності дій;

2)доход адитивний відносно окремих рівнянь;

3)відношення інваріантне відносно перенесення.

Задача з дискретним часом
Нехай x0 , x1 ,..., xn - стани системи X такі, що
x0 c, x1 T (x0 ),..., xn T (xn 1 ) .	(78)

63

Це визначає, що на множині станів системи X діє перетворення T ; в початковий момент t 0 система знаходилася у стані x0 x(0) c , у момент

t 1 система знаходилася у стані x1 T (x0 ) і так далі. Динамічний процес,

який описується перетворенням (78), являється некерованим. Для керованого процесу необхідно мати можливість на кожному кроці здійснювати не одиничне перетворення T (xk ) , а одне з множини

перетворень T1 (xk ),...,Tr (xk ) . Зручно вважати, що певний вигляд перетворення визначається параметром uk , який на k -му кроці може набувати значення з множини значень U k . Параметр uk називається управлінням, а U k – множина припустимих управлінь на k -му кроці. Для керованого процесу послідовність (78) має вигляд

xk 1 T (xk , uk ), uk U k , k 0, n 1, x0 x(0) c .			(79)
Доход за один крок залежить від стану процесу на початок кроку та
використаного на цьому кроці управління:
Qk Q(xk , uk ), uk U k .			(80)
за критерій якості управління приймається повний доход за n кроків
процесу:
	n 1
J n (x0 , u) Q(xk , uk ,			(81)

k 0

де u – послідовність управлінь, u u0 , u1 ,..., un 1 .

Задача оптимального управління з дискретним часом для n -

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

u0 , u1 ,..., un 1 , при		якій доход J n (x0 , u) буде максимальним.	Управління
u* u* , u* ,..., u*		U називається x0 – оптимальним, якщо для будь-якого
0 1	n 1
управління u U
		J n (x0 , u) J n (x0 , u* ) .	(82)

Для знаходження оптимальних управлінь використовується принцип Беллмана: якими б не були початковий стан x0 та початкове управління u0 ,

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

Нехай	u* u* , u* ,..., u*								–	x0 -оптимальне управління. Тоді
управління u	u		0 1					n 1
			, u		,..., u			за принципом Беллмана x1 -оптимальне.
~*		*		*			*
		0		1			n 1
Принцип Беллмана дозволяє спростити знаходження оптимальних
стратегій. Дійсно,			нехай					ki	(U i	– множина управлінь на i -му кроці).
						U i

64

n 1

Тоді

U

U i

та пошук оптимальних стратегій повним перебиранням

i 0

n 1

вимагає

перегляду

k ki

управлінь.

Використовуючи

принцип

i 0

Беллмана,

маємо: y1 ,..., yl –

всі стани,

з яких можливий перехід за один

крок

до

кінцевого

стану

x

n

.

Позначимо

через u1 ,..., u l

оптимальні

управління,

які переводять

x0

за

n 1

крок у

y1 ,..., yl відповідно,

а через

J

n 1

(x

, u1 ),..., J

n 1

(x

, u l

) – отримані доходи. Тоді оптимальне управління, які

0

0

переводять

початковий стан

x0

до

кінцевого стану

xn ,

має

вигляд

u* u d , u*

, де u d знаходиться з умови

n 1

d Arg max

J

n 1

(x

0

, u s ) max Q( y

s

, u)

,

(83)

s 1, ...,l

S

u U n 1

де U s

u *

(s 1, l)

– множина управлінь, які переводять

y

s

у

x

n

;

n 1

n 1

визначається з умови

un* 1 Arg max Q( y d , u) .

(84)

Ud n 1

Таким чином, задача знаходження оптимальної стратегії за n кроків зводиться до l аналогічних (n 1) -кроковим задачам. Кількість варіантів перебору управлінь при цьому зменшується, так як управління на останньому кроці обирається у відповідності з (84), а інші управління з

U d		вже не розглядаються.
n 1
						Задача незалежного вибору
		Нехай існує послідовність множин 1 ,..., n , кожна з яких міститься
у E	m	. Альтернативою являється послідовність					x1 ,..., xn ...		n	; ;
							1
xi i , i 1, n . Нехай						R – бінарне відношення,	яке задане на Em . Будемо
вважати
						n
						(x) xi Em для всіх x .		(85)
						i 1
		Бінарне відношення R на має вигляд
						xRy (x)R ( y), x, y .
		Задача полягає в тому, щоб знайти R ,					тобто недоміновані на у
відношенні до						послідовності x1 ,..., x n .	Сформульована	задача є
					R

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

65

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

Відповідно до багатокритеріальної задачі оптимального управління

маємо: множиною управлінь		U	являється	множина ; окремому
управлінню відповідає точка		з	i . Послідовність		x1 ,..., x n точок,
обраних з кожного i ,	являє собою управління за n кроків. Відображення
множини управлінь	U у просторі Em визначається формулою (164).
Відношенню R в загальній задачі відповідає				бінарне відношення, яке
задане на просторі доходів Em .

Таким чином, задача незалежного вибору являє собою окремий випадок загальної багатокритеріальної задачі оптимального управлінняU , , R з визначеними вище параметрами. Для опису даної задачі достатньо використовувати запис , R . Параметр виключений, так як він також визначається за формулою (85).

Важливо. 1 -згорткою задачі , R являється однокритеріальна

	~	~	n ~	~	образ i при лінійному відображенні g :
задача	, , де i та			i –
			i 1
Em E1 , яке задається формулою
						m
				g(x) j x j .				(86)
						j 1
Послідовність точок z1 ,..., zn на прямій являється її рішенням тоді,
коли zi				~
	– максимальне число в i				(i 1, n) , що дозволяє знайти всі розв’язки
однокритеріальної задачі.
2	Якщо відношення R може бути відділено у вигляді , то будь-яке
рішення		-згортки	вихідної	задачі при будь-якому				, що міститься у

дійсному конусі KR відношення R , являється розв’язком вихідної задачі.

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

Увипадку опуклого та відношення R такого, що RK R , будь-яке

рішення задачі , R при деякому K * .

		n
3	Якщо	ix	( ix –	конус нормалей	до всіх опорних
		i 1
гіперплощин до		i , які проходять через точку xi i			), то послідовність
x x1 ,..., xn парето-оптимальна.
4	Нехай i опуклі.		Послідовність x x1 ,..., xn парето-оптимальна
тоді, коли
			n
			ix	.	(87)

i 1

66

Багатокритеріальна задача з неперервним часом

Розглянемо систему

xi (t) fi (x, u, t) (i m 1, m n) ,

	xi (0) xi0 (i m 1, m n) .							(88)
Введемо m критеріїв:
		T
	i	(x, u) fi (x(t), u(t), t)dt (i			1, m	) .		(89)
		0
На просторі	Em задана бінарна множина R , за яким порівнюються
різні управління.
Управлінням	u U	загальної задачі відповідають					всі	кусочно-
неперервні вектор-функції, визначені на відрізку 0,T ,							та	набувають

значення у заданій області U простору Er .

Відображення : U Em визначається формулою (89), яка кожному управлінню u U зіставляє m -мірний вектор (u) 1 (u),..., m (u) . Вектор x(t) за u(t) з (88). Тобто, відображення в даному випадку залежить від функцій f i у (88) та початкових умов x 0 . Відношенню R в загальній задачі відповідає бінарне відношення, яке задане на Em .

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

u(t) (U , f , x 0 , R),

xi (t) fi (x, u, t) (i 1, m n),

x

i

(0)

x

0

(i m 1, m n),

i

(90)

xi (0)

0

(i 1, m),

u(t) U (t 0,T ).

де (U , f , x0 , R) – загальний розв’язок задачі.

Окремим розв’язком являється будь-яке управління u * , що задовольняє (90). Для рішення задачі використовується -згортка.

Важливо 2. -згорткою задачі (90) являється однокритеріальна задача

67

m

i xi (T ) max,

i 1

xi (t) f i (x, u, t) (i 1, m n),

x

i

(0) x

0 (i m 1, m n),

(91)

i

xi (0) 0

(i 1, m),

u(t) U .

Розв’язок

задачі (91)

знаходиться

за допомогою

принципу

максимуму, який

для задачі

(91) набуває

вигляду: нехай

~

~

u (t), x (t) -

оптимальне управління та відповідна траєкторія у задачі (91). Тоді існує

~ ~ ~

вектор-функція (t) 1 (t),..., m n (t) , яка задовольняє системі рівнянь

n m

i (t) j (t)

j 1

з кінцевими умовами

f j	~ ~
	(x, u , t)				(92)
		(i 1, m n)
	xi

i (T ) i	(i 1, m),

i (T ) 0 (i m 1, n m),

така, що при майже всіх t 0,T

~ ~ ~

u (t) Arg max H (x (t), u, (t), t) ,

U

де

m n

H (x, u, , t) i fi (x, u, t) .

i 1

(93)

(94)

(95)

Множина

D x1 (T ),..., xm n (T )	(96)
U

кінців траєкторії при всіх припустимих управліннях u U називається множиною досягнення у задачі (91).

Важливо 3. Нехай множина досягнення D опукла та RK R . Тоді для

будь-якого u* (U , f , x0 , R)		такий, що u *	являється
	існує K *

оптимальним розв’язком задачі (91) при .

68

f (x, )

1.7Моделі і методи стохастичного програмування [7-9]

1.7.1 Загальні	положення	методу	стохастичного
програмування

Наявність стохастичної невизначеності вносить у планування та прийняття економічних рішень елемент ризику.

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

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

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

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

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

Зв'язок між рішенням х та наслідками записують у виді функціональної залежності , яка називається моделлю.

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

69