- Преподавателю
- Математика
- Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов
Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов
Раздел | Математика |
Класс | - |
Тип | Конспекты |
Автор | Евдокимова М.Д. |
Дата | 23.09.2015 |
Формат | doc |
Изображения | Есть |
План урока
Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ
Тема урока Решение различных практических задач ДП с применением математических методов.
Цели урока
-
Развить навык решения задач динамического программирования.
-
Развитие качества ума, внимания, умений учебного труда студентов.
-
Воспитание дисциплинированности, целеустремленности студентов.
Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».
Ход урока:
-
Организационный момент:
проверка отсутствующих, заполнение журнала.
-
Актуализация опорных знаний: ответы на контрольные вопросы
-
Какие задачи называются многошаговыми?
-
При помощи какого математического аппарата решаются многошаговые задачи?
-
Что такое оптимальное управление u*?
-
Каков алгоритм метода последовательных приближений в два круга?
-
Приведите примеры задач оптимального распределения ресурсов.
-
Изучение нового материала:
Классические задачи динамического программирования
-
Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
-
Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
-
Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
-
Задача о вычислении чисел Фибоначчи
-
Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.
-
Задача о выборе траектории
-
Задача последовательного принятия решения
-
Задача об использовании рабочей силы
-
Задача управления запасами
-
Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
-
Алгоритм Флойда - Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
-
Алгоритм Беллмана - Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
-
Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.
Пример: Оптимальное распределение ресурсов
Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)
u
Прибыль от внедрения
f4(u)
f3(u)
f2(u)
f1(u)
8
55
39
35
32
16
58
53
76
68
24
90
80
120
115
32
100
120
135
134
40
140
145
158
147
Решение:
Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) - ищем оптимальное решение задачи.
1 этап.
Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L(i), i=8,16,24,32,40.
1 шаг: Денежные средства вкладываются в четвертый проект.
L(8)=55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
2 шаг: Денежные средства вкладываются в четвертый и третий проекты.
u
Прибыль от внедрения
1 шаг
f3(u)
8
55
39
16
58
53
24
90
80
32
100
120
40
140
145
3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.
u
Прибыль от внедрения
2 шаг
f2(u)
8
55
35
16
94
76
24
108
120
32
135
135
40
175
158
4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.
u
Прибыль от внедрения
3 шаг
f1(u)
8
55
32
16
94
68
24
131
115
32
175
134
40
214
147
2 этап:
На четвертом шаге выбираем максимальное из полученных значений прибыли L(40)=214.
И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.
Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:
1 проект - 0 млн. руб.
2 проект - 24 млн. руб.
3 проект - 8 млн. руб.
4 проект - 8 млн. руб.
-
Закрепление нового материала:
5. Подведение итогов урока: выводы, оценки, домашнее задание:
(2) п.5.1
Ср12: формирование и усвоение содержания теоретического материала
Подпись преподавателя