Экономико-математические модели управления производством (теоретические аспекты). Ломкова Е.Н - 47 стр.

UptoLike

ВУЗ: 

КТИ ВолгГТУ | Камышин

Составители: 

Рубрика: 

47
6.2. Постановка задачи динамического программирования
Постановку задачи динамического программирования рассмотрим
на примере инвестирования, связанного с распределением средств между
предприятиями. В результате управления инвестициями система после-
довательно переводится из начального состояния S
0
в конечное S
n
. Пред-
положим, что управление можно разбить на n шагов и решение принима-
ется последовательно на каждом шаге, а управление представляет собой
совокупность n пошаговых управлений. На каждом шаге необходимо оп-
ределить два типа переменных: переменную состояния системы S
k
и пе-
ременную управления х
k
. Переменная S
k
определяет, в каких состояниях
может оказаться система на рассматриваемом k-м шаге. В зависимости от
состояния S на этом шаге можно применить некоторые управления, ко-
торые характеризуются переменной х
k
, которые удовлетворяют опреде-
ленным ограничениям и называются допустимыми.
Допустим, X = (x
1
, x
2
, …, x
k
, …, x
n
) – управление, переводящее сис-
тему из состояния S
0
в состояние S
n
, a S
k
– есть состояние системы на k-м
шаге управления. Тогда последовательность состояний системы можно
представить в виде графа, изображенного на рис. 6.1.
S
0
S
1
...
S
k-1
S
k
...
S
n
x
1
x
2
x
k-1
x
k
x
k+1
x
n
Рис. 6.1. Граф состояний системы
Применение управляющего воздействия х
k
на каждом шаге перево-
дит систему в новое состояние S
1
(S, х
k
) и приносит некоторый результат
W
k
(S, х
k
). Для каждого возможного состояния на каждом шаге среди всех
возможных управлений выбирается оптимальное управление х
*
k
, такое,
чтобы результат, который достигается за шаги с k-го по последний n-й,
оказался бы оптимальным. Числовая характеристика этого результата на-
зывается функцией Беллмана F
k
(S) и зависит от номера шага k и состоя-
ния системы S.
Задача динамического программирования формулируется следую-
щим образом: требуется определить такое управление Х*, переводящее
систему из начального состояния S
0
в конечное состояние S
n
, при кото-
ром целевая функция принимает наибольшее (наименьшее) значение
F(S
0
, X*) → extr.
Особенности математической модели динамического программиро-
вания заключаются в следующем:
1) задача оптимизации формулируется как конечный многошаго-
вый процесс управления;
2) целевая функция (выигрыш) является аддитивной и равна сумме 
      6.2. Постановка задачи динамического программирования
     Постановку задачи динамического программирования рассмотрим
на примере инвестирования, связанного с распределением средств между
предприятиями. В результате управления инвестициями система после-
довательно переводится из начального состояния S0 в конечное Sn. Пред-
положим, что управление можно разбить на n шагов и решение принима-
ется последовательно на каждом шаге, а управление представляет собой
совокупность n пошаговых управлений. На каждом шаге необходимо оп-
ределить два типа переменных: переменную состояния системы Sk и пе-
ременную управления хk. Переменная Sk определяет, в каких состояниях
может оказаться система на рассматриваемом k-м шаге. В зависимости от
состояния S на этом шаге можно применить некоторые управления, ко-
торые характеризуются переменной хk, которые удовлетворяют опреде-
ленным ограничениям и называются допустимыми.
     Допустим, X = (x1, x2, …, xk, …, xn) – управление, переводящее сис-
тему из состояния S0 в состояние Sn, a Sk – есть состояние системы на k-м
шаге управления. Тогда последовательность состояний системы можно
представить в виде графа, изображенного на рис. 6.1.
                 x1        x2         xk-1          xk        xk+1         xn
            S0        S1        ...          Sk-1        Sk          ...        Sn


                           Рис. 6.1. Граф состояний системы
     Применение управляющего воздействия хk на каждом шаге перево-
дит систему в новое состояние S1(S, хk) и приносит некоторый результат
Wk(S, хk). Для каждого возможного состояния на каждом шаге среди всех
возможных управлений выбирается оптимальное управление х*k, такое,
чтобы результат, который достигается за шаги с k-го по последний n-й,
оказался бы оптимальным. Числовая характеристика этого результата на-
зывается функцией Беллмана Fk(S) и зависит от номера шага k и состоя-
ния системы S.
     Задача динамического программирования формулируется следую-
щим образом: требуется определить такое управление Х*, переводящее
систему из начального состояния S0 в конечное состояние Sn, при кото-
ром целевая функция принимает наибольшее (наименьшее) значение
F(S0, X*) → extr.
     Особенности математической модели динамического программиро-
вания заключаются в следующем:
    1) задача оптимизации формулируется как конечный многошаго-
вый процесс управления;
    2) целевая функция (выигрыш) является аддитивной и равна сумме

                                              47

Страницы