Управление и оптимизация / Babenishev - Metodi optimizatsii 2017

31

Решение задачи оптимального управления рассмотрим на примере.

Пример 1. Используя принцип максимума, решить простейшую задачу оптимального быстродействия

0T dt inf,

с заданным уравнением движения, ограничениями на управления и фазовыми ограничениями:

x u, |u(t) | 1, x(0) 1, x(0) 0, x(T ) 0, x(T) 0 .

Решение. Имеем 1 u(t) 1, f0 1. I. 1) Введем фазовые переменные:

x1 x – смещение от 0 по x, x2 x – скорость,

следовательно x0 (1,0) , xT (0,0)

2) Уравнения движения принимают вид:

x1 x2x2 u

таким образом f1 x2 , f2 u .

3) Выпишем гамильтониан системы:

H ( 0 , 1, 2 , x1, x2 ,u) 0 1 x2 2 u .

4) Сопряженная система H принимает вид:

x

			H
	1
			x1
			H
	2		x2

		1	0
		2		1

5) Отсюда, общее решение сопряженной системы имеет вид:

	0						C				C
1					1			C		1	Ct D
		1				2
2										2

II. 1) По принципу максимума Понтрягина

H ( , xˆ,uˆ) maxu U 0 C x2 ( Ct D) u

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

32

1, если - Ct D 0,

u(t) 1, если - Ct D 0.

Таким образом оптимальное управление может принимать два значения ±1, и в силу линейности функции 2 (t) Ct D , имеет не более одной точки переключения. Отметим, что в момент переключения tπ оптимальное управление может принимать любое допустимое значение

– одномоментное воздействие не влияет на поведение системы.

2)Заметим, что управления u(t) 1 и u(t) 1 не могут перевести фазовую точку (1,0) в (0,0) поскольку первое управление монотонно увеличивают, а второе – уменьшает скорость, начиная с нулевой. Управление вида

	1,	0 t t ,
u(t)		t t T ,
1,

не может быть оптимальным, поскольку сначала разгоняет точку вправо, затем тормозит её и начинает разгонять влево.

Таким образом, оптимальное управление, если существует, может иметь только вид:

1,		0 t t ,
u(t)	1,	t t T ,

III. 1) Из первого уравнения движения x2 u получаем:
x2	1, 0 t t ,	x2	t C1, 0 t t ,
	(t)		(t)
	1, t t T ,		t C2 , t t T.

Из условия	x2 (0) 0 , получаем					C1 0 .	Для C2 , в силу непрерывности
x2 (t) , из первого условия системы имеем x2 (t ) t ,								из второго условия
x2 (t ) t C2 . Приравнивая и выделяя C2 , получаем:
		t	t C2			C2 2t .
Итого, x2		t		, 0 t t ,
		(t)				T.
		t 2t , t t
2) Из второго уравнения движения x1 x2 получаем:
t	, 0 t t ,						t2 / 2 C , 0 t t ,
x1(t)					x1(t)		3
							t2 / 2 2t t C , t t T.
t 2t , t t T ,
								4

33

Из условия x1(0) 1, получаем C3 1. В силу непрерывности x1(t) ,

x (t ) t 2		/ 2 1 t2		/ 2 2t t C				C 1 t2		,
1							4	4
Итого x1(t)			1 t2 / 2			, 0 t t ,
			/ 2 2t t 1		t 2	, t	t T.
		t2
3) Из условий xT (0,0)

x2 (T ) 0	T 2t 0	T 2t ,
x (T ) 0 T 2 / 2 2t T 1 t2			2t2	4t2	1 t2	0 t2	1
1
Таким образом, t 1, T 2 .
Из физических соображений следует, что решение задачи существует, по-

этому найденное единственное (за исключением точки переключения) управление является оптимальным.

Ответ: при 0 t 1: u(t) 1, x (t) t,	x (t) 1 t2 /		2	(x 1 x2 / 2) ,
2	1			1
при 1 t 2: u(t) 1, x (t) t 2,	x (t) t2	/ 2	2t 2		(x (t 2)2	/ 2) .
2	1				1

Тема 3. Динамическое программирование

Вопрос 1. Задачи динамического программирования

Термин «динамическое программирование» (ДП) ввёл американский математик Ричард Беллман в 1940-х гг. «Программирование» в этом сочетании значит «оптимизация», также как в выражениях «математическое программирование», «линейное программирование», «выпуклое» и «целочисленное программирование». В этом значении термин «программирование» связан с организационным планированием, как, например, в высказывании «Программа переоснащения вооруженных сил».

Динамическое программирование также называлась «системный анализ и инжиниринг» и с самого начала имела практическую направленность.

Динамическое программирование – способ решения задач оптимизации путем разбиения их на более простые подзадачи, схожие по структуре с исходной, с последующим использованием полученных решений для построения решения исходной задачи.

ДП применимо к задачам, имеющем оптимальную подструктуру, то есть таким, в которых оптимальные решения перекрывающихся подзадач могу быть использованы для синтеза оптимального решения исходной задачи.

34

Смысл введенных понятий проиллюстрируем на примерах.

Пример 1. Найти кратчайший путь во взвешенном ориентированном графе между двумя заданным вершинами A и B (А и В – пункты выезда и назначения, v2 , ,v14 – перекрестки, двигаться можно только вправо или вниз). Граф может представлять условную схему проезда по городу в час пик с указанием затрат времени при проезде вдоль участков дорог (рис. 1).

Рис. 1.

В общем случае граф может быть какого угодно вида, например, граф дорожной сети города непрямоугольной планировки, с многоуровневыми развязками, переулками, дворовыми проездами и т.п. Помимо затрат времени, веса на таком графе могут означать: расстояния, расход топлива на прохождение участка, затраты на строительство, риски и так далее. Решение этой задачи используется в навигационных программах, логистических расчетах, компьютерных играх и т.п.

Математическое понятие графа подходит для описания всех этих и многих других ситуаций и поэтому является базовым для соответствующего вида задач динамического программирования.

Пример 2. Задача о загрузке транспортного средства («задача о за-

грузке корабля», «задача о рюкзаке» или «задача линейного раскроя»).

В общей постановке задача формулируется следующим образом: пусть имеется транспортное средство грузоподъёмности W, которое может быть загружено предметами n типов. Если обозначить через wk и ck вес и ценность предмета k-го типа (от английских “weight” – вес и “cost” – цена), через xk – количество таких предметов, то можно поставить задачу загрузки транспортного средства грузом максимальной ценности.

Алгоритмы решения этой задачи используются в логистике, при планировании эффективного раскроя материалов и т.п.

35

Пример 3. Пример задачи о распределении ресурсов.

Городское управление получило N пожарных автоцистерн, которые следует распределить между K пожарными частями. Каждая из пожарных частей Fi , i 1, , K , при поступлении в неё n автоцистерн повышает уровень технической готовности машинного парка до какого-то значения, зависящего от n, т.е. представляющего собой функцию fi (n) . Все функции

fi (n), i 1, , K, n 0, , N ,

заданы. Как следует распределить закупленную технику, чтобы в сумме это давало максимальное значение технической готовности по управлению?

Алгоритмы решения этой задачи используется при организационном и производственном планировании.

Изучение методов динамического программирования начнем с формулировки общей схемы решения.

Общая 3-шаговая схема решения задач с оптимальной подструктурой

1.Разбиение задачи на подзадачи меньшего размера.

2.Рекурсивное нахождение оптимальных решений подзадач, применяя эту же схему.

3.Синтез общего решения из полученных оптимальных решений подзадач.

Выводы. И так, метод динамического программирования опирается на следующие свойства задач:

1)наличие перекрывающихся схожих подзадач;

2)наличие оптимальной подструктуры;

3)возможность запоминания решений часто встречающихся подзадач.

Понимание этих свойств позволяет определить какие задачи можно решать с помощью ДП и какие вычислительные средства ресурсы нужны для этого.

Вопрос 2. Принцип поэтапного построения оптимального уравнения.

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

Общая постановка задачи Дискретное время: t 0,1, ,n (шаги исполнения).

В качестве шагов исполнения могут выступать, например, количество пройденных кварталов, видов загруженных товаров, уже укомплектованных пожарных частей.

36

Обозначим:

xt – состояние системы, наступившее на t-ом шаге (положение на карте,

оставшаяся грузоподъемность, количество нераспределенных автомобилей на текущем шаге);

at – действие (управление, решение) предпринятое на t-ом шаге (дви-

гаться вниз или вправо, и т.д.).

Для состояния xt обозначим:

(xt ) – множество управляющих действий допустимых в состоянии xt ; V (xt ) – оптимальный выигрыш, который может быть получен, начиная

с состояния xt .

Если на шаге t в состоянии xt предпринято действие at , то обозначим: T (xt , at ) – результирующее состояние системы xt 1 ,

f (xt , at ) – полученный в результате выигрыш.

Тогда (абсолютный) оптимальный выигрыш V (x0 ) для всей задачи может записан как

n

V (x0 ) max f (xt , at ) ,

a t 0

где a (a0 , , an ) – обозначает последовательность управлений, если выполнены условия

at (xt ) , xt 1 T (xt , at ) .

Замечание. Простейший, так называемый «наивный», способ решения этой задачи состоит в переборе всех возможных векторов управлений a , сначала проверяя их на допустимость, затем вычисляя выигрыш; в конце выбираются управления с наибольшим выигрышем.

Вопрос 3. Уравнение Беллмана

Решение задачи ДП простым перебором является чрезвычайно трудоемким, поскольку экспоненциально зависит от числа шагов (|{a}| | (xt ) |n ). Кардинально сократить трудоемкость позволяет использование принципа оптимальности.

Принцип оптимальности Беллмана для дискретных систем. Опти-

мальное управление имеет свойство, что каковы бы ни были первоначальное

37

состояние и управление, последующие действия должны составлять оптимальное управление относительно состояния, наступившего после первого действия.

Согласно принципу оптимальности, можно отделить первый шаг от последующих:

	n		at (xt )
V (x0 ) max f (x0	, a0 ) max f (xt	, at ) ,
a0	a1 , ,an t 1

откуда видно, что второе слагаемое представляет собой оптимальный выигрыш V (x1) , который можно получить, начиная с состояния x1 , таким образом:

V (x0 ) max f (x0 ,a0 ) V (x1)

a0

Окончательно, после итерирования, приходим к уравнению Беллмана.

Уравнение Беллмана:

V (x) max f (x,a) V (T (x,a)) .

a ( x)

Значения V (xt ), t 1, , n называются условными оптимальным выигрышами, в отличии от абсолютного оптимального выигрыша V (x0 ) – реше-

ния задачи, поскольку они дают оптимальное значение, как будто бы задача начиналась с состояния xt (то есть при дополнительном условии).

Замечание. При использовании уравнения Беллмана на каждом шаге t тоже проводится перебор: для каждого выбора a (xt ) высчитывается сумма f (xt ,a) V (T (xt ,a)) (предполагается, что V (T (xt , a)) уже известны), после чего берется максимум результатов по a.

Рассмотрим реализацию принципов динамического программирования на примере простой модельной задачи.

Пример. Пусть требуется пройти по заданной доске из верхнего левого угла в нижний правый угол так, чтобы сумма встреченных чисел была максимальной (рис. 2). Двигаться можно только вправо или вниз.

1 2 3

a

b

c

0

1

2

2		2	1
		3		4
Рис. 2.

38

Решение. Дискретное время принимает значения: t 0,1,2,3,4 .

Множество состояний xt		состоит из элементов
	{(a,1),(a,2),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)},
которые для краткости обозначим a1,a2,b1 и так далее. Причем
x0 a1,	x1 {a2,b1},	x2 {a3,b2},		x3 {b3,c2},		x4 c3.
Допустимые управления (п – право, в – вниз):
	(a1) (a2) (b2) {п, в},				(c3)
	(b1) (c2) {п},		(a3) (b3) {в}.

Функция перехода между состояниями задается очевидным соотношениями:

T (a1,п) а2, T (b2,в) c2 и так далее.

Замечание. При решении примеров, можно не расписывать формально t, xt , (xt ) и T (xt , at ) , необходимо только уяснить для себя содержание этих понятий в конкретной задаче. Однако такой анализ является абсолютно необходимым при написании компьютерной программы для соответствующего алгоритма.

Приведем восходящую схему решения данной задачи ДП:

t 3: V (c2) V (b3) 4;

t 2 : V (a3) f (a3,в) V (b3) 1 4 5

V (b2) max{ f (b2,п) V (с2), f (b2,в) V (с2)}

a {п,в}

max{1 4,3 4} max{5,7} 7

t 1: V (a2) max{ f (a2,п) V (a3), f (a2,в) V (b2)}

a {п,в}

max{2 5, 2 7} max{7,9} 9 V (b1) f (b1,п) V (b2) 2 7 9

t 0 : V (a1) max{ f (a1,п) V (a2), f (a1,в) V (b1)}

a {п,в}

max{1 9, 2 9} max{10,11} 11

Ответ. Таким образом максимум V (x0 ) 11 достигается при следующей последовательности действий: впвп.

39

Вопросы для самоконтроля:

1.К задачам какого вида применим метод динамического программиро-

вания?

2.Чем характеризуется задачи с оптимальной подструктурой?

3.В чем заключается детерминированность рассмотренной постановки задачи ДП?

4.Чем нисходящая схема решения задачи ДП отличается от восходящей? Приведите примеры.

5.Сформулируйте принцип оптимальности для дискретных систем.

6.Запишите уравнение Беллмана.

Рассмотрим применение динамического программирования для решения задач, поставленных в примерах 1-3.

Алгоритм поиска кратчайшего пути

Общее описание. В процессе выполнения этого алгоритма вершинам ν графа приписываются временные пометки l(ν), каждая из которых даёт верхнюю границы для длины пути из s в эту вершину. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге ровно одна пометка становится постоянной, что значит, что найдена длина минимального пути из s в эту вершину. Алгоритм останавливается, когда постоянной становится пометка терминальной вершины.

Алгоритм.

1.а) Положить l(s) = 0 и считать эту пометку постоянной.

б) Для каждого xi ≠ s, полагаем l(xi) = ∞ и считаем эту пометку времен-

ной.

в) Положить текущую вершину p = s.

2. Для всех x достижимых из p, пометки которых временные, положить: l(x) : min{l(x), l( p) w( p, x)}.

3. а) Среди всех вершин с временными пометками найти вершину x , пометка которой минимальна.

б) Считать пометку этой вершины постоянной и положить p = x .

в) Если p = t, то l(p) является длиной кратчайшего пути, иначе перейти к пункту 2 алгоритма.

40

Пример 1. Найти кратчайший путь из вершины A в вершину B, при условии, что переход от вершины к вершине возможен только слева-направо и сверху-вниз (табл. 1):

Таблица 1

A- 5 - v2 - 6 - v3 - 5 - v4 - 6 - v5
|
	|	|	|	|
6	1	9	5	4
|	|	|	|	|

v6 - 4 - v7 - 4 - v8 - 3 - v9 - 7 - v10

|	|	|	|	|
5	7	4	8	6
|	|	|	|	|

v11 - 7 - v12 - 1 - v13 - 4 - v14 - 3 -B

Решение. Решение будем искать согласно алгоритму нахождения кратчайшего пути. Ход решения будем записывать в следующую вспомогательную таблицу 2, которая получена из таблицы 1 условия, заменой обозначений вершин пробелами:

Таблица 2

- 5		-	-	6	-	-	5	-	-	6	-
|		|				|			|		|
6		1				9			5		4
|		|				|			|		|
- 4		-	-	4	-	-	3	-	-	7	-
|		|				|			|		|
5		7				4			8		6
|		|				|			|		|
-	7	-	-	1	-	-	4	-	-	3	-

Чтобы узнать номер вершины, стоящей в заданной позиции таблицы 2, нужно обратиться к исходной таблице 1. Хотя для записи решения задачи достаточно наличия только одного экземпляра таблицы 2, в целях наглядности будут приведены несколько частично заполненных вариантов Таблицы 2 для последовательных шагов алгоритма.

Будем использовать следующие соглашения и обозначения:

а) значения временных пометок вершин будут записываться числами на месте соответствующих вершин, постоянные пометки будут выделяться жирным шрифтом;

б) веса дуг графа (длины соответствующих путей) записываем наклонным шрифтом;

в) вместо бесконечностей оставляем пустые места;

г) положение текущей вершины p обозначаем подчеркиванием соответствующей пометки.