Теория принятия решений принятие оптимальных решений методами динамического программирования

СОДЕРЖАНИЕ

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

ТЕКУЩИЙ КОНТРОЛЬ ЗНАНИЙ

На бихроматическом графе G(X,U), │Х│= 8,│Х₁│=│Х₂│=4, матрица которого приведена

ЧАСТЬ 1

Общие принципы динамического программирования

ОПРЕДЕЛЕНИЕ

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

Принцип оптимальности Беллмана

Оптимальная стратегия обладает тем свойством, что независимо от начального

Часть 2

Принятие решений на моделях, сводимых к задачам дискретной оптимизации с

ПРИМЕР 1: Решение задач с булевыми переменными

Задача о ранце:

1

0

1

0

1

0

1

1

1

0

0

0

0

0

1

1

1

0

S

6,6
0,10

9,0
6,6
3,4
0,10

∞
9,0
10,1
6,6
4,5
0,10

САМОСТОЯТЕЛЬНО

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

ЧАСТЬ 3

Принятие решений на моделях, сводимых к задачам дискретной оптимизации с

ПРИМЕР 2: Решение задачи с небулевыми переменными

Решение задачи вида:
Первые две

ПРИМЕР 2 (ПРОДОЛЖЕНИЕ)

Третья итерация:

Пример 2 (завершение)

Четвертая итерация:

2

2

САМОСТОЯТЕЛЬНО:

Решить задачу с небулевыми и с булевыми переменными вида:

Часть 4

Принятие решений на моделях оптимального упорядочения

ПРИМЕР 3: ЗАДАЧА КОММИВОЯЖЕРА

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

ПРИМЕР 3. ХОД РЕШЕНИЯ

Самостоятельно вывести:

Формулы, определяющие:
1. Число вершин каждого слоя построенной сети.
2. Число