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

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

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

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

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S0 В конечное Sn. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния системы Sk переменную управления xk . Переменная Sk определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим. Динамическое программирование - student2.ru = (x1 , x2 , ..., xk , ..., xn ) - управление, переводящее систему на состояния S0 в состояние Sn , a Sk - есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного ниже:

x1 x2 xk-1 xk xk+1 xn
S0 → S1 → ... → Sk-1 → Sk → ... → Sn

Применение управляющего воздействия xk на каждом шаге переводит систему в новое состояние S1 (S, xk) и приносит некоторый результат Wk (S, xk). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x*k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление Динамическое программирование - student2.ru , переводящее систему из начального состояния S0 в конечное состояние Sn , при котором целевая функция принимает наибольшее (наименьшее) значение F(S0 , Динамическое программирование - student2.ru ) => extr.

Рассмотрим более подробно особенности математической модели динамического программирования:

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

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

F = ∑ Fk (Sk−1, x k ) → extremum ;

3. выбор управления xk на каждом шаге зависит только от состояния системы k этому шагу Sk-1, и не влияет на предшествующие шаги (нет обратной связи);

4. состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия xh (отсутствие последействия) и может быть записано в виде уравнения состояния: Sk = fk(Sk-1 , xk), k = 1, n;

5. на каждом шаге управление xk зависит от конечного числа управляющих переменных, а состояние системы зависит Sk – от конечного числа параметров;

6. Динамическое программирование - student2.ru оптимальное управление представляет собой вектор Динамическое программирование - student2.ru , определяемый последовательностью оптимальных пошаговых управлений: Динамическое программирование - student2.ru (х*1, х*2, …, х*k, …, х*), число которых и определяет количество шагов задачи.

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

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление - х*n определяется функцией Беллмана: F(S) = max {Wn (S, xn )}, в соответствии с которой максимум выбирается из всех возможных значений xn , причем xn ? X.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид Fn(S) = max {Wn (S, xn ) + Fk+1(Sn(S, xk )} xk ? X.
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Транспортная задача

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

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A1, A2,..., Am, производящих один и тот же продукт в количествах соответственно a1, a2,..., am.

Пусть, далее, имеется n потребителей (складов) B1, B2,..., Bn с потребностями (вместимостями) соответственно b1, b2,..., bn.

Пусть весь произведенный продукт может быть размещен на складах B1, B2,..., Bn при полном их заполнении.

Пусть, наконец, перевозка единицы продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).

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

Строим математическую модель.

Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Из постановки задачи очевидно, что каждый склад вмещает:

Динамическое программирование - student2.ru

А так как производится столько продукции, сколько ее потребляется (складируется), то:

Динамическое программирование - student2.ru

(продукт с предприятия вывозится полностью).

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

Динамическое программирование - student2.ru

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

Динамическое программирование - student2.ru

Таким образом, имеем следующую математическую постановку задачи. Найти такие xij, которые доставляют минимум линейной форме L, т.е. и удовлетворяют условиям:

Динамическое программирование - student2.ru (1)
Динамическое программирование - student2.ru (2)
Динамическое программирование - student2.ru (3)

Из (1) и (2) следует, что

Динамическое программирование - student2.ru

закрытая транспортная задача

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

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

1. Правило "северо-западного угла"

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х11 приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина сij). Более совершенным правилом является правило "минимального элемента".

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

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

Практическая часть

Наши рекомендации