МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» (МАИ)

Институт: Радиоэлектроника, инфокоммуникации и информационная безопасность

Кафедра: 402

Направление подготовки: 11.03.02

Группа: М4О-311Б-19

Квалификация (степень): Бакалавр

Доклад

По курсу: «Теория систем и системный анализ»

На тему: «Динамическое программирование и его задачи»

Выполнил:

Уланов Олег Олегович

Проверил:

Агринский Николай Михайлович

Москва

2021 г.

Содержание

ВВЕДЕНИЕ. 2

ОСНОВНАЯ ЧАСТЬ. 2

1.1 Определение динамического программирования. 2

1.2 Постановка задачи и особенности динамического программирования. 3

1.3 Пример математической задачи, оптимизируемой методом динамического программирования 4

1.4 Достоинства и недостатки динамического программирования. 4

ЗАКЛЮЧЕНИЕ. 5

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ. 6

ВВЕДЕНИЕ

В настоящее время многие организации в своей деятельности сталкиваются с математическими моделями. Математическая модель – это система математических уравнений, неравенств, формул и различных математических выражений, описывающих поведение реального объекта, составляющих его характеристики взаимосвязи между ними.Описание задачи или процесса при помощи математической модели позволяет свести решение, например, экономической задачи к математическому анализу.

В данной работе будет рассматриваться один из подходов к решению такого рода задач – динамическое программирование. Предпосылками к его появлению можно считать следующие факторы:

1. Необходимость поиска оптимального решения задач, в том числе экономических.

2. Для снижения емкости вычислений желательно использование принципа «разделяй и властвуй».

3. Формулировка Ричардом Беллманом принципа оптимальности, который гласит: «Оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения».

ОСНОВНАЯ ЧАСТЬ

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

Динамическое программирование представляет собой математический аппарат, который используется для решения некоторого класса задач путем их разделения на небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование.

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

При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер.

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

1.2 Постановка задачи и особенности динамического программирования

Требуется определить такое управление Х*, переводящее систему из начального состояния S₀ в конечное состояние S_n, при котором целевая функция принимает наибольшее (наименьшее) значение F(S₀, X*) → extr.

1. Задача оптимизации формулируется как конечный многошаговый процесс управления;

2. Целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

F = ∑ F_k (S_k−1, x _k ) → extremum ;

3. Выбор управления х_k на каждом шаге зависит только от состояния системы к этому шагу S_k₋₁, и не влияет на предшествующие шаги (нет обратной связи);

4. Состояние системы S_k после каждого шага управления зависит только от предшествующего состояния системы S_k_-1 и этого управляющего воздействия х_k (отсутствие последействия) и может быть записано в виде уравнения состояния: S_k= f_k (S_k-1, х_k), k = 1, n;

5. На каждом шаге управление х_k зависит от конечного числа управляющих переменных, а состояние системы S_k зависит от конечного числа параметров;

6. Оптимальное управление представляет собой вектор X*, определяемый последовательностью оптимальных пошаговых управлений: X = (х*₁, х*₂, …, х*_k, …, х*_n), число которых и определяет количество шагов задачи.

Динамическое программирование пользуется следующими свойствами задачи:

перекрывающиеся подзадачи;
оптимальная подструктура;
возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

2. Восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

Важным условием динамического программирования является аддитивный характер задачи.

1.3 Пример математической задачи, оптимизируемой методом динамического программирования

Требуется найти значение последовательности чисел Фибоначчи для F{5}, при этом, зная, что F{3}=F{2}+F{1} и F{4}=F{3}+F{2}}, даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F{2} дважды. Если продолжать дальше, то получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал. Чтобы избежать такого хода событий, мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется мемоизацией.

1.4 Достоинства и недостатки динамического программирования

Среди достоинств можно выделить:

1. На каждом этапе решается задача поиска экстремума лишь по части переменных, следовательно, размерность этих задач по сравнению с исходной значительно ниже. Это позволяет упростить поиск оптимальных значений искомых переменных.

2. Решение задач, которые не могут быть решены другими методами.

3. Простая реализация на ЭВМ.

Среди недостатков выделяют:

1. Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач рассматриваемого класса. Алгоритмы ДП объединены лишь общей идеей, и в каждом конкретном случае должны формироваться применительно к специфике прикладной задачи.

2. При большой размерности исходной задачи эти алгоритмы требуют значительных ресурсов ЭВМ.

Условная оптимизация.

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление – х*_n определяется функцией Беллмана: F(S) = max {W_n (S, x_n)}, в соответствии с которой максимум выбирается из всех возможных значений х_n, причем х_n∈Х.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид:

F_n (S) = max {W_n (S, x_n) + F_k₊₁ (S¹(S, x_k))}, x_k∈Х.

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация.

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что начальное состояние S_o, можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x₁, которое этот результат доставляет. После применения этого управления система перейдет в другое состояние S¹(S,х*₁), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге х*₂, и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу).

ЗАКЛЮЧЕНИЕ

Таким образом, динамическое программирование является методом математического решения задач, при помощи которого можно найти оптимальное решение экономических и технических задач. Как и любой вид программирования он имеет свои достоинства и недостатки, а также широко используется при решении различных задач.

Например:

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

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

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

4. Задача о «рюкзаке»

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2001.- 544 с.

2. Ломкова Е. Н., Эпов А. А. Экономико-математические модели управления производством (теоретические аспекты): Учеб. пособие. – Волгоград: ВолгГТУ, 2005. – 67 с.

3. Холод Н. И., Кузнецов А. В., Жихар Я. Н. и др.; под общ. ред. Кузнецова А. В. Экономико-математические методы и модели: Учеб. пособие. –Мн.: БГЭУ, 2000. – 412 с.

4. Шикин Е. В., Чхартищвили А. Г. Математические методы и модели в управлении: Учеб. пособие. – 2-е издание, испр. – М.: Дело, 2002. – 440 с.

5. Wikipedia. Динамическое программирование. URL: https://ru.wikipedia.org/wiki/Динамическое_программирование (Дата обращения: 28.12.2021)

6. Tproger. Динамическое программирование для начинающих. URL: https://tproger.ru/articles/dynprog-starters/ (Дата обращения: 28.12.2021)

7. Labs-org. Динамическое программирование уроки. URL: https://labs-org.ru/dinamicheskoe-programmirovanie/ (Дата обращения: 28.12.2021)