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

Дополнительно введем следующие условные обозначения: s - состояние процесса; Si; — множество возможных состояний процесса перед i-м шагом;

Wi — выигрыш с i-го шага до конца процесса, i= 1,m.

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

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

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

3. Определение множества шаговых управлений x_f, i =1,m и налагаемых на них ограничений, т.е. области допустимых уп­равлений X.

4. Определение выигрыша,

(1)

который принесет на i-м шаге управление x_l, если система перед этим находилась в состоянии s.

5. Определение состояния s1, в которое переходит система из состояния s под влиянием управления х,i,

(2)

где fi – функция перехода на i -м шаге из состояния S в состояние S1.

6. Составление уравнения, определяющего условный оптималь­ный выигрыш на последнем шаге, для состояния s модели­руемого процесса

Wm(s)=max{ } (3)

7. Составление основного функционального уравнения дина­мического программирования, определяющего условный оп­тимальный выигрыш для данного состояния s с i-го шага и
до конца процесса через уже известный условный оптималь­ный выигрыш с (i+1)- го шага и до конца.

Wi (s)=max {+Wi+1()} (4)

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

Дата добавления: 2014-01-07