VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

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

Для подготовки к трем зачетам по дисциплинам: теоретическая механика, математика и английский язык студенту предоставлено 4 дня. Зависимость получения баллов на зачете от количества затраченных на подготовку дней представлены в таблице 1. Необходимо определить стратегию подготовки к трем зачетам, так чтобы получить максимальную сумму баллов.

Таблица 1. Зависимость количества баллов от затраченных на подготовку дней

Количество баллов, fk(u)	Выделенные дни на подготовку к зачетам, u
	0	1	2	3	4
f1(u)	0	10	17	21	38
f2(u)	0	25	29	36	40
f3(u)	0	6	12	18	39

Для решения задачи сформулируем многошаговую математическую модель:

f(x,u) - Целевая функция задачи (максимальное количество баллов), где x=x0,x1,x2,x3 -оставшееся количество дней (x^k) после k-го выученного предмета (фазовая траектория), u=u0,u1,u2,u3 – количество дней (u^k) затраченных на k-ый зачет (вектор управлений).

f(x,u)=k=13fkuk→max

xk=xk-1+uk – уравнение состояний, x^k[0;4] и u^k[0;4-x^k-1]

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

Этап 1. (условная оптимизация).

Шаг 1. Найдем B3x2=max f3(u3) - функция Беллмана. Так как Z3x2,u3=f3(u3) есть возрастающая функция аргумента u³ (по таблице 1), то её максимум достигается при максимально допустимом значении u³, т.е. u*3x2=[4-x2].

Отсюда,B3x2=Z3x2,u*3x2=f3([4-x2]). Значения B3x2, найдем с помощью таблицы 1.

Таблица 2. Значения функции B3x2

x2	0	1	2	3	4
B3x2	f34-0=39	18	12	6	0

Шаг 2. Найдем B2x1=max B3x1+u2+f2(u2). Для определения максимума функции Z2x1,u2=B3x1+u2+f2u2 составим таблицу 3, используя таблицу 1 и 2.

Таблица 3. Значения функции Z2x1,u2

x¹

u²

0

1

2

3

4

0

B30+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 0=39

B31+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 1=43

B32+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 2=41

B33+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 3=42

B34+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 4=40

1

B31+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 0=18

37

35

36

-

2

B32+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 0=12

31

29

-

-

3

B33+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 0=6

25

-

-

-

4

B34+f23()ица 3. той функции, используя таблицу 1 и 2.

и английскийбы 0=0

-

-

-

-

В таблице 3 жирным шрифтом выделены максимальные по u² значения функции Z2x1,u2, соответствующие различным x¹. С помощью таблицы 3 находим значения функции B2x1 и u*2x1.

Таблица 4. Значения функции B2x1							Таблица 5. значения функции u*2x1
x1	0	1	2	3	4		x1	0	1	2	3	4
B2x1	43	37	31	25	0		u*2x1	1	1	1	1	0

Шаг 3. Найдем B1x0=maxB2x0+u1+f1(u1), где x⁰=0. Для определения максимума B1x0 составим таблицу 6 значений функции Z20,u1=B2u1+f1u1, которые найдем с помощью таблиц 1 и 4.

Таблица 6. Значений функции Z20,u1

u1	0	1	2	3	4
Z20,u1	B20+f10=43	47	48	46	40

Из таблицы следует, что u^*1(0)=2; B₁(0)=48

Этап 2. (безусловная оптимизация).

Шаг 0. Оптимальное начало фазовой траектории x определяется начальным условием х^*0=0

Шаг 1. С помощью таблицы находим u^*1= u^*1(0)=2; x^*1=x*0+u^*1=0+2=2

Шаг 2. Из таблицы 5 получаем: u^*2= u^*2(2)=1; х^*2=х^*1+u^*2=2+1=3

Шаг 3. u^*3=u^*3(x^*2)=u^*3(3)=1; x^*3=x^*2+u^*3=3+1=4

В результате проведенных расчетов получаем: u*=2,1,1 количество дней затраченных на 1-2-3 зачет соответственно, при этом максимальное суммарное количество баллов составляет B₁(0)=48 баллов.

Литература:

1. Основы методов оптимизации./ Лесин В.В., Лисовец Ю.П. – М. «Издательство МАИ», 1998. – 248-266с.

2. Методы принятия оптимальных решений. Часть I./ Агишева Д.К., Зотова С.А., Матвеева Т.А., Светличная В.Б./ ВПИ (филиал) ВолгГТУ. – Волгоград: ИУНЛ ВолгГТУ, 2011. – 143-153с.

Код для цитирования: Скопировать