Практики / Практическая работа №4_Моделирование_Гвоздев

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра технической кибернетики

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

Методические указания по выполнению практической работы по

дисциплине

«Моделирование»

Выполнил: ст. гр.

Проверил:

Гвоздев В.Е.

Уфа 2022

Цель работы: ознакомиться с принципами и методами динамического программирования.

Задание: найти оптимальную траекторию для движения из точки А в точку В при заданных условиях.

Вариант 18

12 20 10 15 13 15 12

11 12 10 10 11 12 13 14

8 10 11 13 16 12 10

10 13 11 15 10 10 9 8

8 9 14 10 9 12 14

11 15 12 14 15 10 9 11

10 12 13 10 8 9 10

12 14 11 10 12 11 10 12

14 14 13 12 10 14 13

10 13 12 12 12 11 10 12

10 9 10 8 9 11 10

11 15 12 14 15 10 9 11

14 14 13 12 10 14 13

Ход решения:

Требуется проложить путь, соединяющий два пункта А и В. Допустим, что прокладка пути состоит из ряда шагов и на каждом шаге мы можем двигаться либо строго по Y, либо строго по X. Любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на совершение каждого шага известны.

W = 130 – минимальная стоимость перемещения из A в В.

Контрольные вопросы:

1. Что такое «динамическое программирование»?

Динамическое программирование (иначе динамическое планирование) есть особый метод оптимизации решений, специально приспособленный к так называемыми «многошаговыми» (или многоэтапными) операциями.

2. Что такое «операция» с точки зрения динамического программирования?

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

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

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

4. В чем заключается главный принцип динамического программирования?

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

5. В чем разница между условным оптимальным и оптимальным выигрышем?

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

6. Дайте описание области применимости метода

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

7. Сформулируйте и раскройте содержание практических рекомендаций, полезных при постановке задач динамического программирования.

1) Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом.

2) Расчленить операцию на этапы (шаги).

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

4. Определить, какой выигрыш приносит на м шаге управление , если перед этим система была в состоянии S, то есть записать «функцию выигрыша»:

5. Определить, как изменяется состояние системы S под влиянием управления х_i на м шаге: оно переходит в новое состояние:

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш (начиная с го шага и до конца) через уже известную функцию : (4)

Этому выигрышу соответствует условное оптимальное управление на м шаге (подчеркнем, что в уже известную функцию надо вместо S подставить измененное состояние .

4. Провести условную оптимизацию последнего m-го шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждой из них условный оптимальный выигрыш по формуле:

и находя условное оптимальное управление х_m(S), для которого этот максимум достигается.

4. Провести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (4), полагая в ней =(m-1), (m-2), …, и для каждого из шагов указать условное оптимальное управление х_i(S), при котором этот максимум достигается.

5. Провести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге =х₁(S₀). Изменить состояние системы по формуле (3); для вновь найденного состояния найти оптимальное управление на втором шаге и.д. до конца.