Реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства

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

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

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

       Дадим математическую формулировку принципа оптимальности. Для простоты будем  считать, что начальное x₀ и конечное x_T состояния системы заданы. Обозначим через z₁(х₀, u₁) значение функции цели на первом этапе при начальном состоянии системы x₀ и при управлении u₁, через z₂(х₁,u₂) – соответствующее значение функции цели только на втором этапе, ..., через 
z_i(х_i-1,u_i) – на i-м этапе, ..., через z_N(х_N-1, u_N) —на N-м этапе. Очевидно, что

      Z = =  (1)

       Надо  найти оптимальное управление u*= ( ; ;...; ), такое, что доставляет экстремум целевой функции (1) при ограничениях .

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

определения для подобных задач на последнем  этапе, двух последних и т. д.; 
– область определения исходной задачи. Обозначим через F₁(x_N-1), F₂(x_N-2), …, F_k(x_N-k), …, F_N(x₀) соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах.

       Начинаем  с последнего этапа. Пусть х_N-1 – возможные состояния системы на начало N-го этапа. Находим:

      F₁(x_N-1) = z_N(x_N-1, u_N). (2)

       Для двух последних этапов получаем

      F₂(x_N-2) = (Z_N-1(x_N-2, u_N-1) + F₁(x_N-1)). (3)

       Аналогично:

      F₃(x_N-3) = (Z_N-2(x_N-3, u_N-2) + F₂(x_N-2)). (4)

………………………………………………….

      F_k(x_N-k) = (z_N-k+1(x_N-k, u_N-k+1) + F_k-1(x_N-k+1)). (5)

       …………………………………………………..

      F_N(x₀) = (z₁(x₀, u₁) + F_N-1(x₁)). (6)

       Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

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

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

• Рассматривается система, состояние которой на каждом шаге определяется вектором x_t. Дальнейшее изменение ее состояния зависит только от данного состояния x_t и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
• На каждом шаге выбирается одно решение u_t, под действием которого система переходит из предыдущего состояния x_t-1 в новое х_t. Это новое состояние является функцией состояния на начало интервала x_t-1 и принятого в начале интервала решения u_t, т. е. x_t = x_t(x_t-1,u_t).
• Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
• На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .
• Требуется найти такое допустимое управление u_t для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

       Геометрическая  интерпретация задачи динамического  программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой , начальное и конечное состояния системы – точками х₀, , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X₀ или X_T, которой эти точки принадлежат.

       

       Рисунок 1

Тогда допустимые управления переводят точки  из области Х₀ в X_T. Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х₀ и оканчивающуюся в области Х_T, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

4. Примеры задач динамического программирования.

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

     Задача  перспективного планирования. Задача заключается в следующем: пусть планируется деятельность группы N промышленных предприятий П, (i= ) на период в t (t = ) хозяйственных лет. В начале периода на развитие системы предприятий выделены какие-то средства, обозначим их К, которые должны быть распределены между предприятиями. В процессе деятельности предприятия вложенные в него средства частично амортизируются. Каждое предприятие за год работы приносит доход, который зависит от вложенных в процесс производства средств. Часть этих средств отчисляется в фонд предприятий. В начале каждого хозяйственного года имеющиеся средства перераспределяются между предприятиями. Таким образом, возникает задача определения объема средств в начале каждого года, которые нужно выделить каждому предприятию, чтобы суммарный чистый доход за Т лет был максимальным. Это типичная задача динамического программирования. Здесь процесс принятия решения разбивается на Т шагов. Управление им заключается в начальном распределении и последующих перераспределениях средств  
u^t ={ }, где — объем средств, выделенных i-му предприятию в начале t-го года. Для описания динамики системы вводится вектор состояния х^t={ }, где — состояние i-го предприятия на начало t-го года. В свою очередь состояние каждого предприятия является вектором, координатами которого служат трудовые ресурсы, основные фонды, финансовое положение и т. д., т. е. =( ). Очевидно, что вектор управления — это функция состояния системы на начало соответствующего года: u^t=u^t(x^t-1), при этом начальное состояние системы x⁰ может быть заданным. Целевой функцией будет суммарная прибыль объединения за Т лет, тогда, если z^t — прибыль за t-й год, то получим задачу

      max Z = , ,

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

     Задача  об оптимальном управлении поставками. В различных областях народного хозяйства возникает задача определения момента подачи партии поставки и ее объема. С размещением заказов связаны некоторые фиксированные затраты К, не зависящие от величины заказываемой партии, а зависящие только от факта заказа. С содержанием материальных ресурсов связаны затраты, пропорциональные остатку нереализованной продукции на конец интервала планирования. Пусть Т - промежуток планирования. Обозначим через v_t интенсивность потребления ресурса в t-м интервале. Состояние системы будем описывать величиной остатка нереализованной продукции на конец интервала х_t, при этом начальное х₀ и конечное х_t состояния системы можно считать заданными. Для обеспечения непрерывности потребления поставками нужно управлять. Обозначим через u = {u_t} вектор управления, координаты которого величина поставок в начале соответствующих интервалов планирования. Очевидно, что вектор управления есть функция состояния на начало интервала. Из множества возможных управлений требуется выбрать такое, при котором достигается минимум издержек на заказ и содержание материальных ресурсов. Если S_t — издержки содержания единицы продукции в t-м интервале, то функция цели примет вид:

           min Z = ,

     где

     Состояние системы опишется соотношением х_t = x_t-1 + u_t – v_t (t = ). На состояние системы может быть наложено ограничение, связанное с надежностью снабжения: х_t ≥ , где - величина некоторого страхового запаса, защищающего с заданной надежностью от сбоев в системе. Объединение ограничений, налагаемых на состояние системы и вектор управления, обозначим через .

     Получим задачу:

           min Z = , . 

2. ЗАДАЧА  РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
1. Общая постановка задачи.

     Пусть на реконструкцию и модернизацию основного производства объединению выделяется некоторый объем материальных ресурсов X₀. Имеется N предприятий, между которыми нужно распределить данный ресурс. Обозначим через z_i(х_i) прибыль, которую приносит народному хозяйству выделение i-му предприятию х_i (i= ) единиц ресурса. Предполагается, что размер прибыли зависит как от выделенного количества ресурса, так и от предприятия. Причем констатируется, что прибыль, получаемая каждым предприятием, измеряется в одних и тех же единицах и прибыль, получаемая любым из предприятий, не зависит от того, какое количество этого ресурса выделено другим предприятиям, общая прибыль объединения состоит из прибылей отдельных предприятий.

      Решение.

      Сформулированные  выше предположения приводят к функции  цели:

      max Z = z₁(x₁) + … + z_N(x_N). (7)

      Задача  оптимального распределения возникает оттого, что имеется ограниченный объем ресурса X₀, т. е.

      x₁ + … + x_N = X₀, x_i ≥ 0 (i = ). (8)

     Чтобы решить задачу распределения ограниченных ресурсов, применим аппарат функциональных уравнений Р. Беллмана. Погружаем  ее в семейство подобных задач распределения. Вместо решения одной задачи с заданным объемом ресурса Х₀ и фиксированным числом предприятий N рассмотрим их семейства, в которых объем выделенного ресурса х может меняться от нуля до Х₀ и число предприятий – от 1 до N. Введем последовательность функций F₁(x), F₂(x), …, F_N(x), где F₁(x) – это максимальная прибыль, если бы ресурс 0 ≤ x ≤ X₀ был выделен только одному первому предприятию, F₂(x)–максимальная прибыль, полученная при условии, что ресурс 0 ≤ x ≤ X₀ был распределен двум предприятиям, и т. д. Пусть, наконец, F_N(x) – максимальная прибыль, получаемая от распределения ресурса 0 ≤ x ≤ X₀ между N предприятиями. Очевидно, что F_N(X₀) = max Z.

      В двух случаях элементы последовательности F(х) имеют особенно простой вид:

      F₁(0) = 0 (i = ), F₁(х) = z₁(х), 0 ≤ x ≤ X₀.

      Пусть ресурс 0 ≤ x ≤ X₀ распределяется между двумя предприятиями. Если x₂ – объем ресурса, выделенного второму предприятию, то его прибыль составит z₂(x₂). Оставшийся ресурс x – x₂ распределяется наилучшим образом.

      Общая прибыль для двух предприятий  составит

      F₂(x) = (z₂(x₂) + F₁(x-x₂)).

Аналогично  найдем рекуррентное соотношение, которое связывает F_k(x) и 
F_k-1(xx_k) (k = ) для произвольных значений 0 ≤ x ≤ X₀. Тогда, оставшийся ресурс х – x_k распределится между остальными k – 1 предприятиями наилучшим образом. Так как F_k-1(x – x_k) известно, то