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

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

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

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

1. Рассматривается система, состояние которой на каждом шаге определяется вектором х_t. Дальнейшее изменение ее состояния зависит только от данного состояния х_t и не зависит от того, каким путем система пришла в него.

2. На каждом шаге выбирается одно решение u_t, под воздействием которого система переходит из предыдущего состояния х_t-1 в новое х_t. Это новое состояние является функцией состояния на начало интервала х_t-1 и принятого в начале интервала решения u_t, ,т.е.

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

4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений u Ω.

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

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

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

Рис.7.1

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

Принципы динамического программирования. Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами u_t и находить экстремум целевой функции одним из существующих методов оптимизации, т.е. искать сразу все элементы решения на всех N шагах. Отметим, что этот путь не всегда приводит к цели, особенно когда функция заданна в виде таблиц или число переменных очень велико. Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. Наоборот, управление на каждом шаге выбирается с учетом всех его последствий. Чаще второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага проще оптимизации всего процесса в целом.

Приведем пример. Пусть проектируется распределителная сеть между пунктами А и В (в условиях существующей городской застройки).

Рис.7.2

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

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

Одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотипных шагов (этапов), каждый из которых планируется отдельно, но с учетом состояния системы на начало этапа и последствий принятого решения. Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без учета последствий. Это последний шаг. Он может быть изучен и спланирован сам по себе наилучшим (в смысле выбранного критерия) образом, поскольку за ним нет больше этапов. Отсюда получаем одну из специфических особенностей динамического программирования: всю вычислительную процедуру программирования целесообразно разворачивать от конца к началу. Раньше всех планируется последний N – й шаг, за ним (N-1)-й и т.д. Но как найти оптимальное управление u_N на N – м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожидаемых исходах предшествующего, но еще не исследованного этапа, т.е. о значениях x_N-1.

Для каждого возможного исхода x_N-1 на (N-1)-м этапе находим оптимальное управление на N–м этапе. Такой набор оптимальных управлений, зависящих от возможных исходов предыдущего этапа, называется условно-оптимальным решением . Завершив анализ конечного этапа, требуя, чтобы функция цели достигала экстремального значения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе , т.е. делаются всевозможные предположения о том, чем кончился предыдущий (N-2)-й шаг, и для каждого из предположений находится такое управление на (N-1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N-2)-го шага условно-оптимальное управление на (N-1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к началу, найдем последовательность условно-оптимальных управлений , …, , .

Условно-оптимальные управления дают возможность найти не условное, а просто оптимальное управление на каждом шаге. В самом деле , пусть начальное состояние x₀ известно. Тогда, проделав процедуру движения от конца к началу, находим . Так как начальное состояние х₀определяется однозначно, это оптимальное управление для первого шага. Вместе с тем находим экстремальное значение целевой функции относительно всего процесса. Зная оптимальное действие (с точки зрения всего процесса) для первого шага, выявим, к какому состоянию перейдет система в результате этого действия, т.е. найдем оптимальное состояний системы на начало второго этапа. Но для всех возможных состояний на начало второго этапа выявлены оптимальные управления. Таким образом, зная , установим оптимальное управление для второго этапа и т.д. Проделав обратное движение от начала к концу, найдем оптимальные управления для всех этапов.

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

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

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

Приведем математическую формулировку принципа оптимальности для задач с аддитивным критерием оптимальности (сепарабельная функция цели). Для простоты будем считать, что начальное и конечное состояния системы заданы. Обозначим через значение функции цели на первом этапе при начальном состоянии системы и при управлении , через - соответствующее значение функции цели только на втором этапе,…, через - на i - м этапе, …, через - на N -м этапе. Очевидно, что

Z = (7.1)

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

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

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

.(7.2)

u_N Ω

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

. (7.3)

u_N-1 Ω

Аналогично:

(7.4)

u_N-2 Ω

…………………………………………………………………………

, (7.5)

u_N-k+1 Ω

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

. (7.6)

u₁ Ω

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

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

1.Решим с помощью метода динамического программирования задачу определения оптимальной степени участия синхронных двигателей в компенсации реактивной мощности Q_∑ = 1,8 Мвар, если каждый из двигателей может выдать реактивную мощность соответственно: Q_Д1 = 0,6 Мвар; Q_Д2 = 0,5 Мвар и Q_Д3 = 1,2 Мвар. Потери мощности ΔР, возникающие в синхронном двигателе, зависят от реактивной мощности Q_Д, генерируемой двигателем. ΔР_i представляются нелинейными зависимостями от Q_ДI.

Величина потерь мощности, возникающих в первом двигателе составит ΔР₁ = 0,00749 Q₁ + 0.01104 ,

во втором двигателе - ΔР₂ = 0,01294 Q₂ + 0.02244

и в третьем – ΔР₃ = 0,00973 Q₃ + 0.00797 .

Задача состоит в том, чтобы отыскать такие мощности Q _i, i = 1,2,3, которые обеспечили бы минимум суммарных потерь ΔР_∑ = ΔР₁ + ΔР₂ + +ΔР₃ при соблюдении ограничений по величинам Q_{Д i}, i =1,2,3, а также по суммарной реактивной мощности Q_∑ = 1,8 Мвар, которую должны скомпенсировать синхронные двигатели.

В математическом плане задача сводится к минимизации целевой функции F(x) = ∑ f_i(x_i) → min; (7.7)

f₁(x₁) = 0,00749 x₁ + 0,01104 ,

f₂(x₂) = 0,01294 x₂ + 0,02244 ,

f₃(x₃) = 0,00973 x₃ + 0,00797 .

при соблюдении ограничений: х₁ + х₂ + х₃ = 1,8;

х₁ ≤ 0,6;

х₂ ≤ 0,5;

х₃ ≤ 1,2;

х_i ≥ 0, i = 1,2,3.

При использовании метода динамического программирования производим дискретизацию переменных Δx = 0,1. т.е. строим сетку X = 0,0; 1,8 с шагом Δх.

Формирование рекуррентных соотношений начинается с к = 1. Поскольку здесь не требуется распределения ресурса между переменными, то рекуррентное соотношение примет вид F₁(X) = f₁(X); поэтому

F₁(0) = f₁(0) = 0,00749·0 + 0,01104 0² = 0;

F₁(0,1) = f₁(0,1) = 0,00749·0,1 + 0,01104 0,1² = 0,00086;

……………………………………………………………

F₁(0,6) = f₁(0,6) = 0,00749·0,6 + 0,01104 0,6² = 0,00847.

Расчеты F₁(X) прекращаются для Х = 0,6, поскольку имеются ограничения х₁ ≤ 0,6.

На втором шаге рекуррентное соотношение имеет вид

F₂(X) = min [F₁(X-x₂) + f₂(x₂)], в силу чего будем иметь:

для Х = 0 F₂(0) = 0 + 0,01294 0 +0,02244 0² = 0;

для Х = 0,1 F₂(0,1) = 0,00086 + 0,01294 0 +0,02244 0² = 0,00086 (х₂=0)

F₂(0,1) = 0 + 0,01294 0,1 +0,02244 0,1² = 0,00152 (х₂ = 0,1)

т.е. минимальным F₂(0,1) = 0,00086 (отмечаем это значение);

для Х =0,2 F₂(0,2) = 0,00194 + 0,01294 0 +0,02244 0² = 0,00194 (х₂=0,0);

F₂(0,2)=0,00086+0,01294 0,1+0,02244 0,1²=0,00238 (х₂=0,1);

F₂(0,2)=0 + 0,01294 0,2 + 0,02244 0,2² = 0,00349 (х₂ = 0,2)

Подобные расчеты продолжаем до Х – 1,1, чем обеспечиваеися одновременное соблюдение ограничений х₁ ≤ 0,6 и х₂ ≤ 0,5. При этом для Х = 1,1 вычисляется F₂(1,1) лишь для одного допустимого значения х₂=0,5:

F₂(1,1) = 0,00847 + 0,01294 0,5 + 0,02244 0,5² = 0,02055.

На третьем шаге по рекуррентному соотношению F₃(X) = min [F₂(X-x₃) + f₃(x₃)] вычисляется серия значений F₃(1,8) для х₃=0,7;0,8;0,9;1,0;1,1;1,2. Для х₃ ≤ 0,7 расчеты не проводятся, поскольку в этом случае никакие сочетания х₁ и х₂ не обеспечат выполнения ограничения х₁ + х₂ + х₃ = 1,8.

Ход решения задачи методом динамического программирования при Δx = 0,1 Мвар представлен в табл. 7.1

Таблица 7.1

Заполнением строки Х = 1,8 завершается «прямой ход» метода динамического программирования. Из табл. 7.1 видно, что минимальное значение целевой функции F₃(1,8) = 0,02958. Ему соответствует = 0.9. Тогда х₁ + х₂ = 1,8 – 0,9 = 0,9. Из табл 7.1 видно, что F₂(0,9) = 0, 1437. Ему соответствует = 0,3. Наконец, = 1,8 - - = 0,6. Таким образом, получено решение = 0,6; = 0,3; = 0.9, а ΔР_∑ = ΔР₁ + ΔР₂ + ΔР₃ = F(x) = ∑ f_i(x_i) → min =0,02958 МВт.

ЛИТЕРАТУРА

1. Электрические системы. Математические задачи электроэнергетики / В. А. Веников [и др.]. – Москва : Высш. шк., 1981. – 288 с.

2. Математическая статистика/В.М.Иванова, В.Н. Калинина [и др.] – Москва : Высш. шк., 1981. – 371 с.

3. Вентцель, Е. С. Теория вероятностей / Е. С. Вентцель. – Москва: Наука, 1969. – 576 с.

4. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование – Минск: Вышэйшая школа, 2001. – 351 с.

5. Зайчинка Ю.П. Исследования операций. – Киев,: Вища школа, 1979. – 392 с.

6. Колесникова И.Н., Круглякова Д.В. Статистика – Минск: Вышэйшая школа, 2011. – 285с.

7. Шундалов Б.М. Статистика. Общая теория. – Минск: ИВЦ Минфина, 2006. – 288с.