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

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

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

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

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

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S₀ В конечное S_n. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния системы S_k переменную управления x_k . Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим. = (x₁ , x₂ , ..., x_k , ..., x_n ) - управление, переводящее систему на состояния S₀ в состояние S_n , a S_k - есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного ниже:

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

Применение управляющего воздействия x_k на каждом шаге переводит систему в новое состояние S¹ (S, x_k) и приносит некоторый результат W_k (S, x_k). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x*_k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния S₀ в конечное состояние S_n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S₀ , ) => extr.

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

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

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

F = ∑ F_k (S_k−1, x _k ) → extremum ;

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

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

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

6. оптимальное управление представляет собой вектор , определяемый последовательностью оптимальных пошаговых управлений: (х*₁, х*₂, …, х*_k, …, х*), число которых и определяет количество шагов задачи.

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

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

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

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

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

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

Пусть имеем m предприятий A₁, A₂,..., A_m, производящих один и тот же продукт в количествах соответственно a₁, a₂,..., a_m.

Пусть, далее, имеется n потребителей (складов) B₁, B₂,..., B_n с потребностями (вместимостями) соответственно b₁, b₂,..., b_n.

Пусть весь произведенный продукт может быть размещен на складах B₁, B₂,..., B_n при полном их заполнении.

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

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

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

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

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

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

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

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

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

	(1)
	(2)
	(3)

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

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

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

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

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

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

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

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

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

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

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