ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Краткие теоретические сведения

города 6 груз доставляется в конечный город 7 (место назначения). Таким образом, мы определили оптимальный маршрут х* = (1–2–6–7), затраты на перевозку груза по которому составляют f3(1) = 4 + 4 + 3 = 11.

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

Порядоквыполненияработы

1.Изучить основные принципы динамического программирования.

2.Изучить порядок эксплуатации программных средств.

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

4.Ввести данные в ЭВМ и получить решение задачи.

5.Оформить отчет, в который включить: краткую формулировку цели

исодержания работы, основные положения теории динамического программирования, вариант задания, результаты расчета на ЭВМ, анализ результатов

ивыводы.

Задание

Найти кротчайший путь из первой вершины в последнюю по счету в заданном графе:

	Номер	Граф	Номер	Граф
	варианта		варианта

1

2

Моделирование процессов и объектов в металлургии. Лаб. практикум

-63-

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Задание

	Номер	Граф	Номер	Граф
	варианта		варианта

3

4

5

6

7

8

9

10

11

12

Моделирование процессов и объектов в металлургии. Лаб. практикум

-64-

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Задание

	Номер	Граф	Номер	Граф
	варианта		варианта

13

14

15

16

17

18

19

20

Контрольныевопросыизадания

1.Для каких оптимизационных задач применяется метод динамического программирования?

2.В чем заключается суть метода динамического программирования?

3.Сформулируйте принцип оптимальности Беллмана.

4.Что является целевой функцией в задаче о кратчайшем маршруте?

5.Какой параметр определяет состояние системы на каждом шаге?

Моделирование процессов и объектов в металлургии. Лаб. практикум

-65-