Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов

План урока

Учебная дисциплина    МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ

Тема урока        Решение различных практических задач ДП с применением математических методов.

Цели урока  

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

2.      Развитие качества ума, внимания, умений учебного труда студентов.

3.      Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока  конспект лекций,  В.П.Агальцов «Математические методы в программировании».

Ход урока:

1.      Организационный момент: 

проверка отсутствующих, заполнение журнала.

2. Актуализация опорных знаний:  ответы на контрольные вопросы

1.      Какие задачи называются многошаговыми?

2.      При помощи какого математического аппарата решаются многошаговые задачи?

3.      Что такое оптимальное управление u*?

4.      Каков алгоритм метода последовательных приближений в два круга?

5.      Приведите примеры задач оптимального распределения ресурсов.

3.      Изучение нового материала:

Классические задачи динамического программирования

·        Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

·        Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

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

·        Задача о вычислении чисел Фибоначчи

·        Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.

·        Задача о выборе траектории

·        Задача последовательного принятия решения

·        Задача об использовании рабочей силы

·        Задача управления запасами

·        Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

·        Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

·        Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

·        Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Пример: Оптимальное распределение ресурсов

Капитал 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 млн. руб.

4.      Закрепление нового материала:

5. Подведение итогов урока: выводы, оценки, домашнее задание:

(2) п.5.1

Ср12: формирование и усвоение содержания теоретического материала

Подпись преподавателя