Сущность метода динамического программирования

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

Примеры таких операций:

- передача информационного пакета по сети;

- вычисление кратчайших путей между узлами сети;

- последовательность тестов при контроле аппаратуры.

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

В общем виде постановка задачи ДП сводится к следующему. Имеется некоторая управляемая операция распадающаяся (естественно или искусственно) на m шагов (этапов). На каждом шаге осуществляется распределение и перераспределение сил и средств, участвующих в операции, с целью улучшения ее результата в целом. Эти распределения в динамическом программировании называются управлениями операций. Будем обозначать их буквой u. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления - W (u). При этом эффективность управления W (u) зависит от всей совокупности управлений на каждом шаге операции

W = W (u) = W (u 1, u 2,..., um).

(4.5)

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

u ^* = (u ^*1, u *2,..., u * m)

(4.6)

Задача ДП - определить оптимальное управление на каждом шаге u_i, i = 1, m и тем самым оптимальное управление всей операцией в целом. Сформулированную задачу, на первый взгляд можно решить непосредственно, объединив все этапы. Действительно, W можно рассматривать как функцию многих переменных - элементов управления на каждом шаге:

W = f (u ₁, u ₂,..., u_m).

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

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

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

Достоинства ДП:

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

Однако, ДП имеет и свои недостатки.

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

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

(4.7)

где w _i - эффективность операции на i -шаге. В случае опти­мального управления очевидно, что

(4.8)

Выше мы выяснили, что искать оптимальное решение сразу на всех m шагах как правило невозможно.

Попробуем строить оптимальное управление шаг за шагом, на каждом этапе оптимизируя только один шаг. С первого взгляда может показаться, что задача очень проста.

Пусть каждый шаг будет маленькой операцией, оптимизировать которую нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальной. И сделав так мы совершили ошибку!

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

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

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

Т.е. мы не знаем условий, в которых мы приступаем к последнему шагу?

Нужно сделать разные предположения о том, чем закончился предпоследний(m -1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на m -м шаге.

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

Теперь мы можем оптимизировать управление на предпоследнем (m -1)-м шаге. Снова сделаем все возможные предположения о том, чем закончился(m -2)-й шаг и для каждого из этих предположений найдем такое управление на(m -1)-м шаге, при котором выигрыш за последние два шага (из которых m -й уже оптимизирован) максимален. Так мы найдем для каждого исхода(m -2)-го шага условное оптимальное управление на(m -1)-м шаге и условную эффективность на двух последних шагах.

Далее, «пятясь назад», оптимизируем управление на(m -2)-м шаге и т.д., пока не дойдем до первого. Предположим, что все условные оптимальные управления и условная эффективность на всех шагах, начиная от данного и до конца нам известны. А это значит: мы знаем, что надо сделать, как управлять на данном шаге и какая в результате будет эффективность всей операции, в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно оптимальное, а просто оптимальное управление u ^* и найти не условную эффективность, а просто эффективность многошаговой операции W (u^*).

В самом деле, пусть мы знаем, в каком состоянии S ₀ была управляемая система в начале первого шага. Тогда мы можем выбрать оптимальное управление u ₁^* на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S ₁^*; в этом состоянии мы подошли ко второму шагу.

Тогда нам тоже известно условное оптимальное управление u ₀^*, которое к концу второго шага приводит систему в состояние S ₂^* и т.д. Что касается оптимального выигрыша за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс находится дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условная эффективность операции с любого шага; второй раз - от начала к концу, когда нам остается только использовать уже готовые рекомендации и найти безусловное оптимальное управление u ^*, состоящее из оптимальных шаговых управлений u ₁^*, u ₂^*,..., u_m ^*.

Первый этап - условной оптимизации - несравненно сложнее и длиннее второго. Второй этап почти не требует дополнительных вычислений.