Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
19 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
1.52 MB
Просмотров:
68
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Теория принятия решений
принятие оптимальных решений методами динамического программирования
Лекция 2.8
№2 слайд
Содержание слайда: СОДЕРЖАНИЕ
Текущий контроль знаний
Часть 1. Общие принципы динамического программирования.
Часть 2. Принятие решений на моделях, сводимых к задачам дискретной оптимизации с булевыми переменными.
Часть 3. Принятие решений на моделях, сводимых к задачам дискретной оптимизации с небулевыми переменными.
Часть 4. Принятие решений на моделях оптимального упорядочения.
№3 слайд
Содержание слайда: ТЕКУЩИЙ КОНТРОЛЬ ЗНАНИЙ
На бихроматическом графе G(X,U), │Х│= 8,│Х₁│=│Х₂│=4, матрица которого приведена ниже, определить оптимальное распределение работ при условии, что:
1. Минимизируется время выполнения плана, при условии, что фонд зарплаты равен:
S= 4 ∙max{│k-5│; │k-25│}.
2. Минимизируются затраты на выполнение плана при условии, что время его выполнения не превышает величины Т= max{│k-15│;│k-35│}.
3. Минимизируются затраты на выполнение плана при условии, что время его выполнения не ограничено.
№4 слайд
Содержание слайда: ЧАСТЬ 1
Общие принципы динамического программирования
№5 слайд
Содержание слайда: ОПРЕДЕЛЕНИЕ
Динамическое программирование представляет собой многошаговый процесс принятия решений, направленных на достижение единой цели. При этом на каждом шаге этого процесса решается задача меньшей размерности, чем исходная.
№6 слайд
Содержание слайда: Принцип оптимальности Беллмана
Оптимальная стратегия обладает тем свойством, что независимо от начального состояния и начального решения задачи, последующие решения должны составлять оптимальную стратегию лишь в рассматриваемый момент времени. Иными словами оптимальная стратегия в каждый момент времени определяется лишь состоянием системы, но не ее предысторией.
№7 слайд
Содержание слайда: Часть 2
Принятие решений на моделях, сводимых к задачам дискретной оптимизации с булевыми переменными
№8 слайд
Содержание слайда: ПРИМЕР 1: Решение задач с булевыми переменными
Задача о ранце:
№9 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Пользуясь методом динамического программирования, решить задачу о ранце:
№10 слайд
Содержание слайда: ЧАСТЬ 3
Принятие решений на моделях, сводимых к задачам дискретной оптимизации с небулевыми переменными
№11 слайд
Содержание слайда: ПРИМЕР 2: Решение задачи с небулевыми переменными
Решение задачи вида:
Первые две итерации
№12 слайд
Содержание слайда: ПРИМЕР 2 (ПРОДОЛЖЕНИЕ)
Третья итерация:
№13 слайд
Содержание слайда: Пример 2 (завершение)
Четвертая итерация:
№14 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО:
Решить задачу с небулевыми и с булевыми переменными вида:
№15 слайд
Содержание слайда: Часть 4
Принятие решений на моделях оптимального упорядочения
№16 слайд
Содержание слайда: ПРИМЕР 3: ЗАДАЧА КОММИВОЯЖЕРА
Решить, пользуясь методом динамического программирования, разомкнутую задачу коммивояжера, условия которой отвечают графу G(X, U), изображенному на рисунке ниже.
№17 слайд
Содержание слайда: ПРИМЕР 3. ХОД РЕШЕНИЯ
№18 слайд
Содержание слайда: Самостоятельно вывести:
Формулы, определяющие:
1. Число вершин каждого слоя построенной сети.
2. Число дуг, заходящих в каждую вершину i-го слоя.
3. Число дуг, исходящих из каждой вершины i-го слоя.
№19 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО:
Решить разомкнутую задачу коммивояжера на графе G(X,U), изображенном ниже: