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

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

.

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

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

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

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

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

                  Рассмотрим задачу о распределении дополнительных ресурсов между n функциональными подсистемами. Известны F(X, I) – эффективности i-той функциональной подсистемы, если ей выделено
x_i – ресурсов, на которые наложены ограничения:

                                             (1)

      Определить такое распределение ресурсов, чтобы эффективность системы была бы наибольшей.

      Эта задача по своему характеру является комбинаторной. В самом деле, речь идет о том, чтобы перебрать все разбиения b_n  ресурсов на n групп.

      Можно было бы вычислить эффективность, соответствующую каждой комбинации:

(x₁, x₂,…x_n):

(1, 1,…) или (1010…)

(2, 1,…) или (11010…)

      В этом случае пришлось бы просмотреть  вариантов.

      Но если возникнет необходимость знать оптимальное решение в случае, когда общий объем ресурсов не превышает b_n и составляет 0, 1, 2, … b_n, то число вариантов, которые надо было просмотреть, окажется в несколько раз больше:

.

        Для решения такой задачи есть прямой смысл использовать метод динамического программирования.

      Пусть для любого набора (x₁,.x₂, …x_n) существует аддитивный критерий:

      Предположим, что ограничения, наложенные на аргументы x_i, такие, что существует верхняя (sup F_n) или нижняя (inf F_n) граница множества аддитивных критериев, т.е.

                                                             (2)

      Определим набор (x₁,.x₂, …x_n) для соответствующих функций f₁(x₁), f₂(x₂) … F(X, I) такой, чтобы, удовлетворив ограничению (1), получить экстремальное значение (2).

      Предположим, что из совокупности x_i выделена и зафиксирована величина x_n. Если в этой ситуации найти экстремальное значение:

 

то окажется, что значение аддитивного критерия F_n будет зависеть от выбранного значения x_n:

      При любом значении x_n переменные x₁,.x₂, …x_n-1 должны удовлетворять неравенству:

      Введя обозначения:

,

      можно утверждать, что

                                              (3)

      Таким образом, если известна граница аддитивного критерия , первоначальная задача сводится к одномерной задаче оптимизации.

      Имея в виду, что  – верхняя (нижняя) границы множества
F_n-1, нетрудно видеть, что задача отыскания  полностью совпадает с исходной задачей, - различие лишь в числе переменных.

      Следовательно, выделив x_n-1 и повторив все предыдущие рассуждения приходим к выводу:

                                      (4)

        Систематизируя изложенное, получим рекуррентные зависимости: (5), (4), (3):

                                           (5)

т.к. .

        В некоторых задачах целевая функция носит мультипликативный характер:

                                                         (6)

В этом случае такие задачи могут быть сведены к задаче с аддитивным критерием с помощью логарифмирование выражения (6). Однако вся процедура для этого случая может быть построена и непосредственно:

 

Пример:

                                           Пусть n = 3, b_n = 4, a_i = 1, m = 4.

Ф₂(x) – наилучшая эффективность, когда x ресурсов выделяют первой и второй задаче (0 ≤ x ≤ b_n).

(j, i) – способ распределения ресурсов соответствующий Ф₂(х),

i ресурсов выделяют задаче 1,

j ресурсов выделяют задаче 2.

i + j = x.

Ф₃(х) – наивысшая эффективность, когда x ресурсов выделяют трем задачам.

(k, j, i) – способ распределения ресурсов, соответствующий Ф₃(х),
 k + j + i = x, k ресурсов выделяют задаче 3.

 

На первой итерации будем распределять ресурсы только первой и второй задаче:

                           Далее исследования можно продолжать согласно:

,

т.е. необходимо рассматривать не все возможные комбинации, а только те, которые на первом шаге были выделены как перспективные:

 

Задача о кратчайшем маршруте
 в ациклической сети

      Предположим, что известна топология сети (N):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      Каждый узел сети обозначает некоторое состояние исследуемой системы.

      Узел 1 – исток, начальное состояние;

      Узел 10 – сток, конечное состояние;

      С_ij – стоимость перехода из i состояния в j.

      Будем искать кратчайший маршрут из состояния 1 в 10.

 

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

y_j – стоимость, отвечающая стратегии минимальных затрат для пути от узла j до стока;

S_j – решение, позволяющее достичь y_j.

      Поскольку из состояния 10 число оставшихся шагов равно 0, то

 

   .

 

      Очень легко можно вычислить y₉  и  y₈:

 

    ,

    .

 

      Вычислим y₇:

 

 ,   .

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

 

  ,  .

 

      Упорядоченная запись остальных вычислений выглядит так:

 

              ;

 ,         ;

  ,    ;

  ,      ;

  ,              ;

 ,     ;

      Искомый маршрут имеет длину 17 и представляет собой последовательность событий: 1 – 3 – 7 – 9 – 10.

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

 

Таблица 5

 

      Например, маршрут 2 – 10 имеет длину 16 и представляет собой последовательность событий  2 – 6 – 8 – 10.

 

      Пример: Пусть задана топология сети.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      В результате использования алгоритма определения кратчайшего маршрута получим:

,      ;

,        _;

,          ;

,          ;

,         ;

 ,        ;

 ,          ;

,           .

      Кратчайшие маршруты из любого узла в узел-сток можно определить по таблице:

 

Кратчайший маршрут
в сети общего вида

      В ациклической сети можно было пронумеровать узлы сети от 1 до р таким образом, что если сеть содержит дугу (i,j), то i<j. Чтобы добиться этого условия присвоим стоку номер р. Зачеркнем этот узел и все входящие в него дуги и не будем их рассматривать в дальнейшем при присвоении номеров.

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

      В сети общего вида, которая имеет петли, такую нумерацию установить не удается.

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

Вычислить y_p=0, а все остальные y_k=¥.

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

      Краткая математическая запись условий, которым должны удовлетворять все y_i, имеет вид:

      Вычисления можно проводить в различном порядке.

      На самом узле с помощью этого алгоритма отыскиваются кратчайшие маршруты из всех узлов в конечном узле.

 

j

i

1 2 3 4 1 0 2 3 5 2 ¥ 0 1 3 3 ¥ 1 0 1 4 ¥ ¥ ¥ 0

Пример 1:

			C:

 

 

 

 

 

 

 

 

 

 

 

      

     

      

       

       

   

                                       

 

 

      Пример 2:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

j = 1          

  

  

  

   

 

 

 

      j = 2, j =3       

         

 

j = 4          

    

    

 

j = 3 (так как произошла замена y₃)

 

j = 5, j = 1, j = 2, j = 3, j = 4, j = 5 - Останов

 

 

 

Пример 3:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

j = 1          

  

  

  

   

 

j = 2          

              

 

j = 3, j = 4

   

   

  

 

j = 5          

   

        

     

j = 1, j = 2, j = 3   

   

 

j = 4, j = 5, j = 6, j = 7, j = 1, j = 2          

   

 

j = 3, j = 4, j = 5, j = 6, j = 7        

   

 

j = 1, j = 2, j = 3, j = 4, j = 5, j = 6, j = 7 - Останов