Лекция №15
4.3. Применение метода динамического программирования к здп 2
{z = fj(x[j])};
a[1,j]x[j] £ b[1]; a[2,j]x[j] £ b[2],
Для решения дискретной ЗДП II вводится функция Беллмана следующего вида:
(4.23)
Она представляет собой максимальное значение первых k=1,2,…,n компонент целевой функции при выделении на реализацию первых k управлений первого ресурса величиной x1=0,1,2…,b[1], а второго - величиной x2=0,1,2,…,b[2].
Определение значений Lk(x1, x2) представляет собой задачу, аналогичную по своей структуре исходной, только, в общем случае, меньшего размера и по количеству компонент управлений и по величинам распределяемых ресурсов.
В соответствии с этим определением можно утверждать, что
Lо(x1,x2)º 0 для всех возможных значений x1и x2, а
=Ln(b[1],b[2]).
Рекуррентное соотношение для определения Lk(x1, x2) приведем здесь без вывода, который по своей идее ничем не отличается от того, как это было сделано для ЗДП I:
Lj(x1,x2)=
{fj(x[j])+Lj-1(x1-a[1,j]x[j],x2-a[2,j]x[j])}, (4.24)
где d(x1,x2)=min{[x1/a[1,j]],[x2/a[2,j]]}
определяет наибольшее возможное значение x[j], не приводящее к нарушению ограничений в определении функции Беллмана (4.23).
Условно оптимальное управление, соответствующее Lj(x1,x2), обозначим как х[x1,x2,j].
Необходимо заметить, что в ЗДП 2 для хранения значений функции Беллмана и условно оптимальных управлений необходимо использовать трехмерные массивы в отличие от двумерных массивов в ЗДП 1.
Процесс решения ЗДП 2 осуществляется так же в два этапа:
Этап
1. Состоит
в определении функции состояния Lj(x1,x2)
и условных управлений
[x1,x2,j]
в следующем порядке:
1.1) для j = 1,2,…,(n-1), по x1 = 0,1,2,…,b[1], по x2 =0,1,2,…,b[2];
1.2) для j=n, x1=b[1], x2=b[2].
В результате последнего шага получаем оптимальное значение целевой функции исходной задачи z0=Ln(b[1],b[2]) и первое найденное безусловно оптимальное управление по n-ой компоненте x*[n]= х[b[1],b[2],n].
Этап 2. Состоит в определении остальных безусловно оптимальных управлений обратным ходом по массиву условно оптимальных управлений следующим образом:
по значению x*[n] вычисляются оптимальные значения первого и второго ресурсов, оставшихся в оптимальном плане на первые n-1 управлений:
x*1,n-1=b[1]-a[1,n]x*[n]; x*2,n-1=b[2]-a[2,n]x*[n];
из массива условно оптимальных управлений определяется
x*[n-1]=x[x*1,n-1,x*2,n-1,n-1];
общие соотношения для всех остальных шагов j=n-2,…,1 имеют следующий вид:
x*1,j=x*1,j+1 - a[1,j+1]x*[j+1], x*2,j=x*2,j+1 - a[2,j+1]x*[j+1],
x*[j]=х[x*1,j , x*2,j , j]. (4.25)
4.4. Применение метода динамического программирования к здп 3
fj(x[j],y[j]);
a[1,j]x[j] £ b[1]; a[2,j]y[j] £ b[2], Материал этого раздела во многом аналогичен предыдущему. Поэтому обратим внимание лишь на отличия.
Для решения дискретной ЗДП 3 вводится функция Беллмана следующего вида:
(4.26)
Она представляет собой максимальное значение первых k=1,2,…,n компонент целевой функции при выделении на реализацию первых k управлений первого типа первого ресурса величиной x1=0,1,2…,b[1], а на реализацию первых k управлений второго типа - второго ресурса величиной x2=0,1,2,…,b[2].
В соответствии с этим определением можно утверждать, что Lо(x1,x2)º 0 для всех возможных значений x1и x2, а =Ln(b[1],b[2]).
Рекуррентное соотношение для определения Lk(x1, x2) приводится здесь также без вывода:
Lj(x1,x2)=
{fj(x[j],y[j])+Lj-1(x1-a[1,j]x[j],x2-a[2,j]y[j])}. (4.27)
Необходимо отметить, что в отличие от ЗДП 1 и ЗДП 2 максимизация в этом соотношении ведется перебором на двумерной целочисленной решетке. Это приводит к существенному увеличению вычислительной сложности процесса оптимизации.
Условно оптимальные управления, соответствующие Lj(x1,x2), обозначим как х[x1,x2,j] и y[x1,x2,j].
Таким образом, увеличился и объем памяти ЭВМ, требуемой для хранения результатов вычислений.
Процесс решения ЗДП 3 осуществляется в два этапа:
Этап 1. Состоит в определении функции состояния Lj(x1,x2) и условных управлений х[x1,x2,j] и у[x1,x2,j] в следующем порядке:
1.1) для j = 1,2,…,(n-1), по x1 = 0,1,2,…,b[1], по x2 =0,1,2,…,b[2];
1.2) для j=n, x1=b[1], x2=b[2].
В результате последнего шага получаем оптимальное значение целевой функции исходной задачи z0=Ln(b[1],b[2]) и первые найденные безусловно оптимальные управления обоих типов по n-ой компоненте x*[n]= х[b[1],b[2],n], у*[n]= у[b[1],b[2],n].
Этап 2. Состоит в определении остальных безусловно оптимальных управлений обратным ходом по массиву условно оптимальных управлений следующим образом:
по значениям x*[n] и у*[n] вычисляются значения первого и второго ресурсов, оставшихся в оптимальном плане на первые n-1 компоненты управлений соответствующих типов:
x*1,n-1=b[1]-a[1,n]x*[n]; x*2,n-1=b[2]-a[2,n]у*[n];
из массивов условно оптимальных управлений определяются
x*[n-1]= х[x*1,n-1,x*2,n-1,n-1] и у*[n-1]=у[x*1,n-1,x*2,n-1,n-1]
общие соотношения для всех остальных шагов j=n-2,…,1 имеют следующий вид:
x*1,j=x*1,j+1 - a[1,j+1]x*[j+1], x*2,j=x*2,j+1 - a[2,j+1]у*[j+1],
x*[j]= х[x*1,j , x*2,j , j], у*[j]= у[x*1,j , x*2,j , j]. (4.28)