Лабораторная работа № 35 Динамическое программирование

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния в конечное состояние _n. Предположим, что процесс управления системой можно разбить на n шагов. Пусть ₁, ₂, ...…, _n – состояния сис­те­мы после первого, второго, ...…, n-го шага. В данной лабораторной работе величины ₁, ₂,…..., _n являются скалярными.

Последовательное преобразование системы (по шагам) дости­гается с помощью некоторых мероприятий u₁, u₂, ...…, u_n, которые составляют управление системой

U = (u₁, u₂, …..., u_n),

где u_k – управление на k-м шаге, переводящее систему из сос­тоя­ния _k-1 в состояние _k. Величины u₁, u₂, ..., u_n в данной лабо­ра­торной работе также считаются скалярными.

Будем считать, что состояние системы в конце k – шага зависит только от предшествующего состояния системы _k-1 и управления u_k на данном шаге. Такое свойство получило название отсутствия последействия. Обозначим эту зависимость:

_k = F_k(_k-1, u_k) (k = 1, 2, ...…, n). (31)

Равенства (31) получили название уравнений состояний. Функ­ции F_k(_k-1, u_k) полагаем заданными. Варьируя управление U, получим различную “эффективность” процесса, которую будем оценивать количественно целевой функцией z, зависящей от начального состояния системы ₀ и от выбранного управления U:

z = Ф(₀,U).

Показатель эффективности k-го шага процесса управления, который зависит от состояния _k-1 и управления u_k, обозначим через f_k(_k-1, u_k). В рассматриваемой задаче пошаговой оптимизации целевая функция должна быть аддитивной, т. е.

(32)

Обычно на переменные u_k на каждом шаге накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.

Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений u₁, u₂,…...,u_n пе­реводящих систему из начального состояния ₀ в конечное состояние _n и максимизирующих или минимизирующих показатель эффективности (32).

Не уменьшая общности, в дальнейшем будем рассматривать задачу максимизации. Управление, при котором достигается максимум целевой функции (32), называется оптимальным управлением и обозначается через

Метод динамического программирования (ДП) состоит в том, что оптимальное управление строится постепенно, шаг за шагом. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Это основное правило ДП, сформулированное Р. Беллманом, называется принципом оптимальности.

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

Показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, будем обозначать через z_k, т. е.

Обозначим , которая зависит только от т. е.

где U_k = (u_k, u_k+1,…..., u_n).

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

(33)

которая называется основным функциональным уравнением ДП, или уравнением Беллмана. Это уравнение справедливо для k = 1, 2,…...,n-1. Для k = n уравнение (33) принимает вид

. (34)

Величина U_k , при которой правая часть соотношения (33) или (34) обращается в максимум, обозначается через U_k* и называется условным оптимальным управнением на k-м шаге.

Решение рекуррентных соотношений (33) и (34) начинается с соотношения (34). Затем решается соотношение (33) для k = n—1, n—2,...…,2,1. Величина является максимальным значением показателя эффективности процесса в целом, т. е. . Основная идея метода ДП заключается в том, что задача нахождения максимума функции n переменных сводится к n задачам определения максимума функции одной переменной.

Задача. Планируется распределение начальной суммы средств ₀ между n предприятиями П₁, П₂,...…,П_n. Предполагается, что выделенные предприятию П_k в начале планового периода средства приносят доход f_k(x_k) (k = 1, 2,…..., n). Будем считать, что:

1. доход, полученный от вложения средств в предприятие П_k, не зависит от вложения средств в другие предприятия;

2. доход, полученный от разных предприятий, и вложенные средства выражаются в одинаковых единицах;

3. общий доход равен сумме доходов, полученных от распределения средств по всем предприятиям.

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

Запишем математическую модель задачи. Общий доход выражается целевой функцией:

. (35)

Переменные x_k должны удовлетворять условиям:

, (36)

(37)

Требуется определить переменные x₁, x₂,…...,x_n, которые удовлетворяют ограничениям (36) и (37) и обращают в максимум целевую функцию (35).

Для решения этой задачи применим метод ДП. За номер k-го шага примем номер предприятия, которому выделяются средства x_k. Переменные x_k можно рассматривать как управляющие переменные. Начальное состояние системы характеризуется величиной средств, подлежащих распределению. После выделения x₁ остается средств и т. д. Величины ,, характеризующие остаток средств после распеределения на предшествующих шагах, будем рассматривать как параметры состояния. Уравнениями состояния служат равенства

.

Суммарный доход за n шагов составляет и представляет собой показатель эффективности процесса.

Если к началу k-го шага остаток средств равен , то доход, который можно получить на оставшихся n – k + 1 шагах, составит

Обозначим . Тогда Рассмотрим k-й шаг решения задачи. Величина x_k на этом шаге изменяется в пределах [0, ]. Величину x_k нужно выбирать из условия максимизации суммы

.

Таким образом, получаем уравнение

, (38)

называемое уравнением Беллмана. Уранение (38) решается для

k = n—1, n—2,…...,1. Для k = n оно имеет вид

.

Будем считать, что функция дохода f_k(x_k) (k = 1, 2, ...…, n) моно­тонно возрастающая. Поэтому

. (39)

Таким образом, на n-м шаге условное оптимальное управление

.

Решение задачи начинается с n-го шага. Определяется по формуле (39), причем . Затем решается уравнение (38) для k = n-1, n-2,...…, 2, 1. В результате получим две по­сле­до­ва­тельности функций:

и

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

Теперь приступим ко второму этапу вычислительной схемы – безусловной оптимизации. На этом этапе определяем . Находим , а затем по определяем и и т. д. В результате будет определено оптимальное управление (x₁*, x₂*,...…, x_n*).

Пример. Решим рассмотренную задачу для следующих данных: ₀ = 400, n = 3, x = 100. Функции дохода указаны в табл. 7.

Таблица 7

x	f(x)
	f1(x)	f2(x)	f3(x)
100 200 300 400	3 10 12 16	4 7 15 17	6 8 13 14

Решение. Задача является дискретной, причем x = 100. Здесь имеются три управляющие переменные x₁, x₂, x₃ и четыре параметра состояния ₀, ₁, ₂, ₃. Уравнения состояния имеют вид

.

Данный процесс является трехшаговым. Поэтому и уравнение Беллмана на последнем шаге имеет вид

Для первого и второго шага уравнение Беллмана запишется в форме

Обозначим z_k(_k-1, x_k) = f_k(x_k) + z*_k+1(_k). Тогда уравнение Беллмана для двух первых шагов запишется в виде

При решении задачи результаты расчетов поместим в две таблицы. В первую, основную, поместим результаты условной оптимизации (табл. 8), во вторую, вспомогательную, ­ значения z_k(_k-1, x_k) и другие промежуточные результаты, полученные при выполнении условной оптимизации.

Условную оптимизацию начнем с выполнения 3-го шага. Так как f₃(x) — монотонно возрастающая функция, то x₃(₂) = ₂. При этом получим

z₃^*(₂) = f₃(₂) , где 0  ₂  400.

Этот результат условной оптимизации 3-го шага помещен непосредственно во второй и третий столбцы табл. 8, переписав необходимые данные из последнего столбца табл. 6.

Результаты условий оптимизации 2-го и 1-го шагов запишем в табл. 9. Во второй столбец записаны значения x_k, которые изменяются от 0 до _k-1 с шагом x =100, в третий столбец ­ значения _k = _k-1 - x_k, в четвертый столбец ­ значения функции f₂(x₂), взятые из табл. 7, в пятый столбец – значения функции z₃^*(₂), взятые из табл. 8. В шестой столбец записаны значения Затем для данных из шестого столбца для каждого возможного значения ₁ определяется величина

.

Если максимальных значений не одно, то задача имеет несколько решений. В этом случае нужно взять одно из них. Они подчеркнуты в шестом столбце. Эти значения, а также соответствующие им значения x₂ переносим в табл. 8.

Вычисления на первом шаге производятся аналогичным способом. Результаты записаны в табл. 8 и 9. Дальнейшие (безусловные) оптимальные управления определяем по данным из табл. 8. Имеем

x₁^*= 0; ₁^*= 400;

x₂^*= 30; ₂^*= 100;

x₃^*= 100; ₃^*= 0.

Таблица 8

	3-й шаг		2-й шаг		1-й шаг
	z3^*(2)	x3^*(2)	z2^*(1)	x2^*(1)	z1^*(0)	x1^*(0)
100	6	100	6	0	6	0
200	8	200	10	100	10	0
300	13	300	15	300	16	200
400	14	400	21	300	21	0

Таблица 9

k = 2, 1			2-й шаг			1-й шаг
k-1	xk	k	f2(x2)	z3^*(2)	z2(1,x2)	f1(x1)	z2^*(1)	z1(0,x1)
100	0 100	100 0	0 4	6 0	6 4	0 3	6 0	6 3
200	0 100 200	200 100 0	0 4 7	8 6 0	8 10 7	0 3 10	10 6 0	10 9 10
300	0 100 200 300	300 200 100 0	0 4 7 15	13 8 6 0	13 12 13 15	0 3 10 12	15 10 6 0	15 13 16 12
400	0 100 200 300 400	400 300 200 100 0	0 4 7 15 17	14 13 8 6 0	14 17 15 21 17	0 3 10 12 16	21 15 10 6 0	21 18 20 18 16

Максимальный доход равен 21. Он получится, если первому предприятию не выделить средств, второму – 300, третьему – 100 де­нежных едениц. В табл. 8 подчеркнуты значения x₂^* и x₁^*.

Задание. Решить рассмотренную задачу для следующих данных:

1.  задано ₀, указанное в табл. 10;

2.  n = 4;

3. средства выделяются только в размерах, кратных x = 0,2₀,

4. функции дохода приведены в табл. 10.

Таблица 10

0 = 150	Варианты 1 – 6
x	f(x)
	f1(1)	f2(x)	f3(x)	f4(x)
30 60 90 120 150	5 6+k 13 17 20	4 7 8+k 16 19	6 9 11 12+k 20	4 6 14 17 19+k

Продолжение табл. 10

0 = 200	Варианты 7 – 12
x	f(x)
	f1(1)	f2(x)	f3(x)	f4(x)
40 80 120 160 200	4 k 14 18 20	3 7 k+2 17 22	4 8 12 7+k 20	5 7 15 18 12+k

Продолжение табл. 10

0 = 250	Варианты 13 – 18
x	f(x)
	f1(1)	f2(x)	f3(x)	f4(x)
50 100 150 200 250	5 k-6 15 17 19	4 6 k-5 18 20	7 8 10 k 22	5 7 12 16 k+5

Продолжение табл. 10

0 = 300	Варианты 19 – 24
x	f(x)
	f1(1)	f2(x)	f3(x)	f4(x)
60 140 180 240 300	5 k-13 14 18 22	3 5 k-12 19 21	5 7 12 k-3 22	4 8 16 18 k

Окончание табл. 10

0 = 350	Варианты 25 – 30
x	f(x)
	f1(1)	f2(x)	f3(x)	f4(x)
70 140 210 280 350	3 k-20 12 16 19	4 7 k-15 17 18	4 6 15 18 k-6	4 9 12 16 k-7

Ответы