Динамическое программирование
Метод динамического программирования - широко известный и мощный математический метод современной теории управления.
Рассмотрим управляемую систему, состояние которой в каждый момент времени характеризуется n-мерным вектором x с компонентами x1 , …, xn . Предполагаем, что время t изменяется дискретно и принимает целочисленные значения 0, 1, …. Так, для процессов в экономике и экологии дискретным значениям времени могут отвечать дни, месяцы или годы, а для процессов в электронных устройствах интервалы между соседними дискретными моментами времени равны времени срабатывания устройства. Предполагаем, что на каждом шаге на систему оказывается управляющее воздействие при помощи m-мерного вектора управления u с компонентами u1 , …, um . Таким образом, в каждый момент времени t состояние системы характеризуется вектором x(t), а управляющее воздействие - вектором u(t). На выбор управления обычно бывают наложены ограничения, которые в достаточно общей форме можно представить в виде
u(t) k U, t = 0, 1, …
Здесь U - заданное множество в n-мерном пространстве.
Под влиянием выбранного в момент t управления (принятого решения) система переходит в следующий момент времени в новое состояние. Этот переход можно описать соотношением
x(t + 1) = f (x(t), u(t)), t = 0, 1, …
Здесь f (x, u) - n-мерная функция от n-мерного вектора x и m-мерного вектора u, характеризующая динамику рассматриваемой системы. Эта функция предполагается известной (заданной) и отвечает принятой математической модели рассматриваемого управляемого процесса.
Зададим еще начальное состояние системы
x(0) = x0,
где x0 - заданный n-мерный вектор. Таким образом, многошаговый процесс управления описывается соотношениями (1)-(3). Процедура расчета конкретного процесса сводится к следующему. Пусть в некоторый момент t состояние системы x(t) известно. Тогда для определения состояния x(t + 1) необходимо выполнить две операции:
выбрать допустимое управление u(t), удовлетворяющее условию (1);
определить состояние x(t + 1) в следующий момент времени согласно (2). Так как начальное состояние системы задано, то описанную процедуру можно последовательно выполнить для всех t = 0, 1, … Последовательность состояний x(0), x(1), … часто называется траекторией системы.
Заметим, что выбор управления на каждом шаге содержит значительный произвол. Этот произвол исчезает, если задать цель управления в виде требования минимизации (или максимизации) некоторого критерия оптимальности. Таким образом мы приходим к постановке задачи оптимального управления.
Задача оптимального управления
Пусть задан некоторый критерий качества процесса управления (критерий оптимальности) вида
Здесь R(x, u) и F (x) - заданные скалярные функции своих аргументов, N - момент окончания процесса, N > 0. При этом функция R может отражать расход средств или энергии на каждом шаге процесса, а функция F - характеризовать оценку конечного состояния системы или точность приведения в заданное состояние.
Задача оптимального управления формулируется как задача определения допустимых управлений u(0), u(1), …, u(N - 1), удовлетворяющих ограничениям (1), и соответствующей траектории, то есть последовательности x(0), x(1), …, x(N ), которые в совокупности доставляют минимальное значение критерию (4) для процесса (2), (3).
Минимизация критерия (4) обычно отвечает выбору управления, обеспечивающего наименьшие затраты средств, ресурсов, энергии, наименьшее отклонение от заданной цели или заданной траектории процесса. Наряду с этим часто ставится также задача о максимизации критерия вида (4), например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (- J ). Поэтому простая замена знака у функций R и F в (4) приводит задачу о максимизации критерия к задаче о его минимизации. Далее всюду для определенности рассматриваем задачу о минимизации критерия (4).
Листинг программы
type
ElType = string[3];
TVector = array of ElType;
const FORBIDDEN:ElType = 'x';
var
Form1: TForm1;
D: Array of TVector; // Матрица весов переходов
P: Array of TVector; // Матрица узлов
implementation
{$R *.dfm}
procedure TForm1.Button2Click(Sender: TObject);
var
i, j: integer;
_Width, _Height: Integer;
Weight1, Weight2: integer;
X, Y: Integer;
S: string;
begin
_Width := 5;
_Height := 4;
SetLength(D, _Width);
for i := Low(D) to High(D) do
SetLength(D[i], 2 * _Height - 1);
D[0,0] := '4'; D[1,0] := '5'; D[2,0] := '3';
D[0,1] := '5'; D[1,1] := '4'; D[2,1] := '6';
D[0,2] := '4'; D[1,2] := '5'; D[2,2] := '5';
D[0,3] := '4'; D[1,3] := '5'; D[2,3] := '6';
D[0,4] := '6'; D[1,4] := '5'; D[2,4] := '5';
D[0,5] := '7'; D[1,5] := '5'; D[2,5] := '7';
D[0,6] := '6'; D[1,6] := '8'; D[2,6] := '7';
D[3,0] := '5'; D[4,0] := FORBIDDEN;
D[3,1] := '6'; D[4,1] := '7';
D[3,2] := '5'; D[4,2] := FORBIDDEN;
D[3,3] := '6'; D[4,3] := '8';
D[3,4] := '7'; D[4,4] := FORBIDDEN;
D[3,5] := '8'; D[4,5] := '9';
D[3,6] := '7'; D[4,6] := FORBIDDEN;
SetLength(P, _Width);
for i := Low(P) to High(P) do
SetLength(P[i], _Height);
for i := Low(P) to High(P) do
for j := Low(P[i]) to High(P[i]) do begin
if (i=0) and (j=0) then begin
P[i,j] := '0';
Continue;
end;
if (i=0) then begin
P[i,j] := IntToStr(StrToInt(P[i,j-1]) + StrToInt(D[i,2*j-1]));
Continue;
end;
if (j=0) then begin
P[i,j] := IntToStr(StrToInt(P[i-1,j]) + StrToInt(D[i-1,2*j]));
Continue;
end;
Weight1 := StrToInt(P[i,j-1]) + StrToInt(D[i,2*j-1]);
Weight2 := StrToInt(P[i-1,j]) + StrToInt(D[i-1,2*j]);
if Weight1<Weight2 then begin
P[i,j] := IntToStr(Weight1);
D[i-1,2*j] := FORBIDDEN;
end
else
begin
P[i,j] := IntToStr(Weight2);
D[i,2*j-1] := FORBIDDEN;
end;
end;
for i := Low(P) to High(P) do begin
S := '';
for j := Low(P[i]) to High(P[i]) do
S := S + P[i,j] + #9;
Memo1.Lines.Add(S);
end;
X := _Width;
Y := _Height;
S := '(' + IntToStr(X) + ';' + IntToStr(Y) + ')';
while (X<>1) and (Y<>1) do begin
if D[X-1-1,2*Y-1-1]<>FORBIDDEN then X := X - 1
else Y := Y - 1;
S := '(' + IntToStr(X) + ';' + IntToStr(Y) + ') -> ' + S;
end;
S := '(1;1) -> ' + S;
ShowMessage(S);
end;
end.