Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Конспекты / Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Математика

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

библиотека
материалов

План урока

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

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

Цели урока

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

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

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

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

Ход урока:

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

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



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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Капитал 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


hello_html_m2ebe228c.gif

3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.

u

Прибыль от внедрения

2 шаг

f2(u)

8

55

35

16

94

76

24

108

120

32

135

135

40

175

158


hello_html_14d8f1b0.gif

4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.

u

Прибыль от внедрения

3 шаг

f1(u)

8

55

32

16

94

68

24

131

115

32

175

134

40

214

147


hello_html_4463fa9c.gif

2 этап:

На четвертом шаге выбираем максимальное из полученных значений прибыли L(40)=214.

И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.

Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.





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

hello_html_99de4c2.png

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

(2) п.5.1

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



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

Автор
Дата добавления 30.10.2015
Раздел Математика
Подраздел Конспекты
Просмотров614
Номер материала ДВ-109812
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх