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

 

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

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

 

 (2.1)

причем

 .

 

Поскольку  для неотрицательных целых чисел, удовлетворяющих условию, зависит от , то обозначим

 .

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

Очевидно, что

 

 .

 

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

Покажем, как вычислить .

Обозначим

 

при условии

 .

Повторив вышеприведенные выкладки, получим

 , (2.2)

где

 ,

причем максимум в уравнении отыскивается при условии

 .

 

Аналогичным образом вычисляем и т.д. В конце концов на -м шаге мы используем 'основное рекуррентное соотношение (ОРС) динамического программирования'

 

 (2.3)

при условии, что

 .

 

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

 

 (2.4)

 

для всех возможных значений =0, 1, . , b. Оптимальное решение первого шага обозначим через . Составляем таблицу динамического программирования первого шага (табл. 7.1) и заполняем ее результатами вычислений.

На втором шаге ( =2) находим  в соответствии с соотношением

 

 , (2.5)

 

причем значения  берем из табл. 1.1.

Вычисляем последовательно  для всех значений = 0,1,., , используя результаты табл. 1.1. Одновременно находим  и . Результаты вычислений заносим в таблицу второго шага (табл. 1.2).

 

Таблица 1.1				Таблица 1.2
0				0
1				1

 

Дале, пользуясь соотношением, последовательно вычисляем  для всех значений  = 0, 1, 2, ., .

В конце концов, на последнем шаге при  находим

 

 , (2.6)

 

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

 

 .(2.7)

 

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

Сравним метод динамического программирования по числу необходимых операций с простым перебором вариантов. Для упрощения расчетов примем .

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

 

 . (2.8)

 

Например, при  = 5,  = 20, = 10626.

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

Для вычисления  при фиксированном  необходимо выполнить ( +1) вычислений функции  при . Следовательно, чтобы заполнить одну таблицу (при =0,1, ., ) необходимо  операций.

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

С учетом вычислений функции  общее число операций составляет

 

 .(2.9)

 

Это значительно меньше, чем , то есть имеем существенное сокращение объема вычислений сравнительно с простым перебором.

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

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

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

Задача должна допускать интерпретацию как -шаговый процесс принятия решений.

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

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

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

Выбор решения (стратегии управления) на -м шаге не должен влиять на предыдущие решения, кроме необходимого пересчета переменных.

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

Пусть X_k - вектор переменных управления (стратегия), который необходимо определить на -м шаге.

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

 

 , (3)

 

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

Сформулируем принцип оптимальности Беллмана, который обосновывает это соотношения.

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

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

 

2.2 Общая постановка и алгоритм решения задач методом динамического программирования

 

Будем считать, что состояние рассматриваемой системы S на k-м шаге (k = 1, 2, ..., п) определяется совокупностью чисел

 

(3.1)

 

которые получены в результате реализации управления обеспечивающего переход системы S из состояния в состояние

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояние в которое перешла система S, зависит от исходного состояния и выбранного управления и не зависит от того, каким образом система S перешла в состояние

2. Условие аддитивности. Если в результате реализации k-го шага обеспечен определенный доход также зависящий от исходного состояния системы и выбранного управления то общий доход за п шагов составит

 

(3.2)

где

 

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений в результате реализации которых система S за п шагов переходит из начального состояния в конечное и при этом функция дохода G(m) принимает наибольшее значение. Принцип оптимальности Беллмана. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы доход на данном шаге плюс оптимальный доход на всех последующих шагах был максимальный. Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление обеспечивающее максимальное значение функции дохода Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага. Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначив через максимальный доход, получаемый за п шагов при переходе системы S из начального состояния в конечное состояние при реализации оптимальной стратегии управления , а через -- максимальный доход, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления на оставшихся (n - k) шагах. Тогда

 

(3.3)

 

В можно считать известным. Используя теперь уравнение и рассматривая всевозможные допустимые состояния системы S на (n - 1)-м шаге находим условные оптимальные решения

 

(3.4)

и соответствующие значения функции:

(3.5)

 

Таким образом, на n-м шаге находим условно оптимальное управление при любом допустимом состоянии системы после (n - 1)-го шага, т. е. в каком бы состоянии система не оказалась после (n - 1)-го шага, нам уже известно, какое следует принять решение на n-м шаге.

Перейдем теперь к рассмотрению функционального уравнения при k = n - 2:

 

(3.6)

Решая функциональное уравнение при различных состояниях на (n - 2)-м шаге, получим условно оптимальные управления Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах. Последовательно осуществляя описанный выше итерационный процесс, дойдем до первого шага. На этом шаге известно, в каком состоянии может находиться система. Поэтому уже не требуется делать предположений о допустимых состояниях системы, а остается лишь только выбрать управление, которое является наилучшим с учетом условно оптимальных управлений, уже принятых на всех последующих шагах. Чтобы найти оптимальную стратегию управления, т. е. определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. На первом шаге в качестве оптимального управления возьмем найденное условно оптимальное управление . На втором шаге найдем состояние в которое переводит систему управление Это состояние определяет найденное условно оптимальное управление которое теперь будем считать оптимальным. Зная находим значит, определяем и т. д. В результате этого находим решение задачи, т. е. максимально возможный доход и оптимальную стратегию управления, включающую оптимальные управления на отдельных шагах.