Методы нахождения оптимального управления экономическими системами. Михайлова Э.А - 35 стр.

                                       36

                            Рис. 2.2


      2.2   Использование        сетевых    моделей    в динамическом
      программировании

      Динамические задачи часто решаются с помощью сетевых моделей..
      Сеть (граф) G1=(X,U)
      состоит из множества вершин {X} и множества ребер (дуг) {U}.
      Дуги могут иметь различную длину U = Cij,
      где i - начальная вершина дуги,
          j - конечная вершина дуги.
      Путь в графе G - это последовательность дуг U, в которой конец каждой
предыдущей дуги совпадает с началом следующей.

                        Принцип оптимальности

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



        Для реализации принципа оптимальности удобно использовать следую-
щие обозначения:
        fn(Xs) - стоимость, отвечающая стратегии минимальных затрат для пути
от состояния s, если до конечного состояния остается n шагов.
        jn (Xs ) - решение (управление), позволяющее достичь fn (Xs) (символ j
зависит от шага n, номера вершины s и соответствует некоторому фиксирован-
ному пути), показывает переход от вершины Xs к вершине Xj. Последователь-
ность j соответствует оптимальному уравнению.
        Рекуррентное соотношение имеет вид:
     f n (Xs) = min [ Csj + f n -1 (X j) ]
     S, j (x s, x j) ∈ X
         Упорядоченная запись вычислений выполняется в таблицах.

                                                              Таблица 2.4
                j     Номера вершин, в которые          J l (Xs) f l (Xs)
        S                 совершен переход.
        номера       Csj+f l-1             . . .
        вершин, из
        которых