1.2. Математическая постановка задачи

Состояние некоторой развивающейся системы в каждый дискрет­ный момент времени t = 0, .... Т характеризуется множеством точек х⁽¹⁾_t, х⁽²⁾_t ,..., х⁽ⁿ⁾_t , совокупность которых—вектор x(t) = (х⁽¹⁾_t, х⁽²⁾_t ,..., х⁽ⁿ⁾_t), называемый вектором состояния системы. Обозначим множе­ство всех состояний системы (вектор состояний) в момент времени t = т через х_m, состояние ее в начальный момент t = 0 считается заданным х (0) = x₀ . Развитие системы состоит в последовательном переходе из одного состояния в другое. На него можно воздействовать в каждый момент времени t определенным управлением и(t), выбран­ным из множества возможных управлений. Таким образом, состояние системы х(t+1) определяется, с одной стороны, вектором х (t) и, с другой - управлением и (t)

х (t + 1) = f {х (t); и (t)}.

Функция f задает правило перехода от состояния х (t) в состояние х (t + 1) в зависимости от управления и (t). Множество управлений, каждое из которых можно выбрать в момент t = т, обозначим через U_m. Развитие системы определяется последовательностью х = {х (0), х(1), ..., х (Т)}, где x(m)  X_m-вектор состояния системы при t = т. Эта последовательность называется стратегией. Стратегия допустимая, если существуют управления, позволяющие делать пере­ход из любого ее состояния в следующее. Каждая стратегия оценива­ется функцией цели F(х). Таким образом, развитие системы описы­вается:

множеством допустимых состояний системы Х_т;

множеством допустимых управлений U_m;

правилами перехода из одного состояния в другое по выбранному управлению х (т +1) = f {х (т), u (m)};

функцией цели F (х).

Необходимо найти допустимую стратегию, обеспечивающую минимум (максимум) функции цели. Последнюю в общем случае задают сум­мой оценочных функций Q_m {х (m), х(т+1)}, получаемых при каж­дом переходе из состояний х (т) в состояние х (т + 1),

Функцию цели можно считать функцией от управления, поскольку любую допустимую стратегию х полностью определяет последова­тельность допустимых управлений и = (и₀, и_1, ..., и_Т-1). Таким образом, задачу динамического программирования можно сформули­ровать так: необходимо определить последовательность управлений

и*=(и₀*,и₁*,и_Т-1*),

минимизирующую функцию цели

при условиях:

x (m+1)=f{x(m), u(m)};

x(m)є X_m; x(0)=x₀;

u(m)є U_m; m=0, 1,…,T-1.

Обозначим через F_k {x(k)} максимальное значение функционала для {x(m)}; {u(m)}; m=k+1,…,T, удовлетворяющих условиям задачи. Тогда, применяя последовательно принцип оптимально­сти к функциям f₁, f₂ и т.д., можно написать систему уравнений:

F_i [x (i)} называются функциями Беллмана. Решение задачи ди­намического программирования сводится к решению данной системы функциональных уравнений, как уже было сказано, начиная с по­следнего уравнения. Задачи динамического программирования, как правило, требуют большого объема вычислений и обычно их решают на ЭВМ. Рассмотрим некоторые конкретные задачи, максимально уп­ростив их для иллюстрации механизма вычислений.

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

Р ис.1 Определение наивыгоднейшего режима ведения поезда по участкам

На участке с восемью элементами профиля (рис.1) движение поезда начи­нается с первого. В зависимости от режима движения по нему кривая скорости может попасть в некоторое число точек на вертикали 1 (на ней фиксируются все возможные значения скорости через какой-либо интервал, например, через 1 км/ч). Рассмотрим только три. Из каждой из этих точек можно попасть в каждую из трех на следующей вертикали с определенными затратами (показаны на линиях, соединяющих точки). Последние подсчитывают заблаговременно для каждого элемента профиля во всех вариантах движения по формуле приведенных затрат в тяговых расчетах.

Решаем задачу с конца поэтапно. На последний элемент поезд может всту­пить с тремя значениями скорости (вертикаль 7). Каждому из них однозначно соответствуют приведенные расходы на передвижение по данному элементу до остановки. Выделяем три условно-оптимальных стратегии (показано жирными линиями): Q’₇ = 50; Q^’’₇= 60; Q^’’’₇ = 70.

На предпоследний элемент поезд может вступить также с тремя значениями скорости (вертикаль 6). Однако из каждой точки можно попасть в конечную точ­ку на вертикали 8 по трем вариантам (трем режимам). Поэтому находим условно-оптимальные стратегии на этом элементе (сравнивая между собой все варианты движения поезда) по минимуму общих расходов на обоих элементах пути

F₆=min (Q₆+Q₇);

F^’₆=min (50+Q^’₇; 60+Q^’’₇; 70+Q^’’’₇)= min (50+50; 60+60; 70+70)=100; Q^’₆=50.

F^’’₆= min (30+Q^’₇; 40+Q^’’₇; 50+Q^’’’₇) = min (30+50; 40+60; 50+70) = 80; Q^’’₆=30.

F^’’’₆=min (40+Q^’₇; 50+Q^’’₇; 60+Q^’’’₇)= min (40+50; 50+60; 60+70)=80; Q^’’’₆=40.

Аналогично определяем условно-оптимальные стратегии на следующем элементе по общему минимуму затрат на трех последних:

F₅=min (Q₅+F₆);

F^’₅=min (50+F^’₆; 60+F^’’₆; 70+F^’’’₆)= min (50+100; 60+80; 70+90)=140; Q^’₅=60.

F^’’₅= min (45+F^’₆; 55+F^’’₆; 60+F^’’’₆) = min (45+110; 55+80; 60+90) = 135; Q^’’₅=55.

F^’’’₅=min (30+F^’₆; 35+F^’’₆; 40+F^’’’₆)= min (30+100; 35+80; 40+90)=115; Q^’’’₅=35 и т.д.

На последнем этапе расчетов:

F₁=min (Q₁+F₂);

F^’₁=min (75+F^’₂; 90+F^’’₂; 110+F^’’’₂)= min (75+275; 90+255; 110+250)=345; Q^’₁=90.

F^’’₁= min (60+F^’₂; 75+F^’’₂; 95+F^’’’₂) = min (60+275; 70+255; 95+250) = 330; Q^’’₁=75.

F^’’’₁=min (55+F^’₂; 70+F^’’₂; 90+F^’’’₂)= min (55+275; 70+255; 90+250)=325; Q^’’’₁=70.

Поскольку начальное состояние системы задано однозначно на последнем этапе, находим лишь одно значение

F = min (100+F^’₁; 110+F^’’₁; 120+F^’’’₁) = min (110+345; 110+330; 120+325) = 440; Q₀=110.

Теперь, начиная с первой точки и проходя последовательно по непрерывной ломаной жирной линии весь процесс до последней точки, определим оптимальную стратегию для всего процесса и на каждом элементе:

F = Q₀+Q^’’₁+Q^’’₂+Q^’₃+Q^’’₄+Q^’’’₅+Q^’’₆+Q^’₇=440.