Динамическое программирование

      СОДЕРЖАНИЕ

      С.

      Введение                                                                                                            3

      1 Теоретическая часть. Модели динамического  программирования          4

      1.1 Предмет динамического программирования                                           4

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

      1.3 Принцип     оптимальности   и    математическое    описание              динамического процесса управления                                                                      8                                                                  

      1.4 Оптимальное распределение инвестиций                                             10

      1.5 Выбор оптимальной стратегии обновления оборудования                  13

      2 Расчетная часть                                                                                            16

      Заключение                                                                                                      30

      Список  использованных источников                                                            31 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      ВВЕДЕНИЕ 

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

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

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

      1  ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

      1.1 ПРЕДМЕТ ДИНАМИЧЕСКОГО  ПРОГРАММИРОВАНИЯ 

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

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

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

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

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

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

      Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.

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

      1.2 ПОСТАНОВКА ЗАДАЧИ  ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 

      Постановку  задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S₀ в конечное S_n. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных: переменную состояния системы S_k и переменную управления x_k. Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной x_k, которые удовлетворяют определенным ограничениям и называются допустимыми.

      Допустим, X = (x₁, x₂, …, x_k, …, x_n) – управление, переводящее систему из состояния S₀ в состояние S_n, a S_k – есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, изображенного на рис. 1.

                        x₁       x₂        x_k-1          x_k        x_k+1         x_n

                  S₀  → S₁ →   ...  →    S_k-1 →     S_k  →    ...  →  S_n 

      Рисунок 1 – График состояний системы

      Применение  управляющего воздействия x_k на каждом шаге переводит систему в новое состояние S¹(S, x_k) и приносит некоторый результат W_k (S, x_k). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление х*_k, такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k (S) и зависит от номера шага k и состояния системы S.

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

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

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

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

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

                                              k =1

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

      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), число которых и определяет количество шагов задачи.