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

Основная идея и особенности вычислительного метода динамического программирования

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

максимизировать (2).

при условиях.

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

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

(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).

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

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

(2.6).

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

.(2.7).

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

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

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

. (2.8).

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

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

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

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

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

.(2.9).

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

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

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

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

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

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

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

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

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

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

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

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

(3).

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

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

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

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