3.Решение задач динамического программирования (методом оптимальности Беллмана)

3.1. Решение задачи о замене оборудования

УСЛОВИЯ ЗАДАЧИ:

Определить оптимальные сроки замены оборудования, чтобы получить максимальную прибыль за 6 лет, если в начале срока установлено новое оборудование. Зависимость стоимости выпускаемой продукции и затрат на ремонти обслуживание от возраста оборудования задана зависимостью:

Возраст оборудования, t (лет)	0	1	2	3	4	5
Выпуск продукции, с (млн.руб )	9	8	7	6	5	5
Затраты на ремонт, r (млн. руб)	1	1	2	2	3	4

Стоимость одного комплекта z= 6 млн руб.

РЕШЕНИЕ:

Для решения задачи будем последовательно находить значения функций для всех возможных на данном этапе состояний S.

смысл функции Fk(s) в задаче таков- это максимальная прибыль, которую можно получить, начиная с момента Так как, если в этот момент возраст оборудования равен S. Поскольку в начальный момент оборудование имеет возраст t=0, то максимально возможный возраст оборудования к моменту к, если замена не производилась ни разу, равен к, а минимально возможный 1, если замена производилась на предыдущем этапе. Поэтому возможные состояния Ski системы на каждом из этапов Тk (кроме этапа Т0, на котором имеется одно состояние - начальное) характеризуются числами t= 1, ... ,к, то есть для этапа Тk (k=1, ... ,5) число возможных состояний равно к.

Найдем значения функций Fk(s).

После пятого этапа эксплуатация оборудования не предусматривается, поэтому F6 (s)= f * (s) =0

F5(1) = max { f5 (1, u ); f5(1, u )}= max{ 8-1; 9-1-6} = 7

u*5(1)=u;

F5(2) = max { f5(2, u ) ; f5(2, u )}= max{ 7-2; 9-1-6} = 5

u*5(2)=u;

F5(3) = max { f5(3, u ); f5(3, u )}= max{ 6-2; 9-1-6} = 5

u*5(3)=u;

F5(4) = max { f5(4, u ); f5(4, u )}= max{5-3; 9-1-6} = 2

u*5(4)=u, u*5(4)=u;

F5(5) = max { f5(5, u ); f5(5, u )}= max{5-4; 9-1-6} = 2

u*5(5)=u; F5(4

Просчитав все значения F5(S), переходим к вычислениюF4(S), S=1,2,3,4.

F4(1) = max { f4(1, u )+ F5(2); f4(1, u ) +F5(1); }

= max{8-1+5; 9-1-1+7} = 12

u*4(1)=u;

F4(2) = max { f4(2, u )+ F5(3); f4(2, u ) +F5(1); }

= max{7-2+4; 9-1-6+7} = 9

u*4(2)=u , u*4(2)=u

F4(3) = max { f 4 (3, u )+ F5(4); f4(3, u ) +F5(1); }

= max{6-2+2; 9-1-6+7} = 9

u*4(3)=u

F4(4) = max { f 4 (4, u )+ F5(5); f4(4, u ) +F5(1); }

= max{5-3+2; 9-1-6+7} = 9

u*4(4)=u

Далее аналогично вычисляем F 3(s), S=1,2,3

F 3(1) = max{8-1+9; 9-1-6+12} = 16

u*3(1)=u

F 3(2) = max{7-2+9; 9-1-6+12} = 14

u*3(2)=u = u

F 3(3) = max{6-2+9; 9-1-6+12} = 14

u*3(1)=u

Находим F 2(s), S=1,2

F 2(1) = max{8-1+14;9-1-6+16} = 21

u* 2(1)=u

F 2(2) = max{7-2+14; 9-1-6+16} =19

u* 2(2)=u

Находим F 1(1), S=1.

F 1(1) = max{8-1+19; 9-1-6+21} =26

u* 1(1)=u

Находим F 0(0)- значение соответствующее заданному начальному состоянию процесса: в начальный момент времени оборудование новое , т.е. его возраст равен 0. Единственно возможное управление u = u*0(0),

так что F 0(0) = 9+1+26=34.

Число F 0(0) =34 - это наибольшая прибыль , которую можно получить в изученном процессе. Для того, чтобы достигнуть такой прибыли мы должны определить последовательность локально оптимальных управлений и промежуточных состояний, к которым ведут эти управления. Итак:

S*1 = R 0 (0; u ) = 1 (так как u* 0(0) =u );

S*1 = R 1 (1; u ) = 2 (так как u* 1(1) =u );

S*3 = R 2 (2; u ) = 3 (так как u* 2(2) =u );

S*4 = R 3 (3; u ) = 1 (так как u* 3(3) =u );

S*5 = R 4 (2; u ) = 2 (так как u* 4(1) =u );

S*6 = R 5(1; u ) = 3 (так как u* 5(2) =u );

Следовательно, оптимальное управление в течении всего процесса таково:

u*=( u* 0(0) u* 1(1) u* 3(3) u* 4(1) u* 5(2))

ВЫВОД

Оборудование нужно заменить один раз, по истечении трех лет эксплуатации. При этом будет получена максимально возможная прибыль равная 34.

3.2.Решение задачи об оптимальном распределении инвестиций

УСЛОВИЯ ЗАДАЧИ

Найти оптимальное распределение инвестиций в объеме 5 млн. руб. между четырьмя предприятиями, чтобы сумма дополнительной прибыли была максимальна. Зависимость дополнительной прибыли каждого предприятия от размера инвестиций указана в таблице:

Инвестиции	Дополнительная прибыль
	Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4
0 1 2 3 4 5	0 1 4 5 7 8	0 1 3 4 5 6	0 1 3 5 6 7	0 3 5 6 9 11

РЕШЕНИЕ

Пусть Т1, Т2, Т3, Т4 этапы процесса распределения инвестиций. На этапе Так как выделяются средства к-му предприятию. Состояние процесса на каждом из эпапов характеризуется суммой s средств, которые оста лось распределить между предприятиями Рк, ... , Р4. Возможные значения s-это числа о 0 до 5 млн. руб.

Функция f * (s)=Fk(s) имеет следующий смысл: это максимально возможная прибыль, которую можно получить от предприятий если между ними распределить средства в сумме 5 млн. рублей. Управление - это число, равное сумме, выделяемой на этапе Так как предприятию Рк.

Так ка предприятий всего 4, то значения F4(s) совпадают с числами в в последнем столбце таблицы, потому что все средства , оставшиеся к этапу 4 идут предприятию Р4 .

F4(0)=0; F4(1)=3; F4(2)=5; F4(3)=6; F4(4)=9; F4(5)=11.

Условно оптимальное управление на четвертом этапе-это отдать все средства s предприятию Р4:

u*4(s)=s, s=0,1,2,3,4,5.

Вычисляем F3 (s).

Если s=0, то единственно возможное управление состоит в том , чтобы ничего не выделять предприятию Р3 (u=0), тогда на долю. Р4 тоже достанется 0, и дополнительная прибыль равна 0:

F3 (0)= f3(0)+ F4(0)=0.

Если s=1, то имеются два возможных управления:

u=0, если Р3 ничего не получает; тогда Р4 достается сумма равная 1. Дополнительная прибыль равна f3(0)+ F4(1)=0+3=3.

u=1, т.е. предприятие Р3 получает сумму 1, дополнительная прибыль от Р3 равна 1, F4(0)=0. Значит дополнительна я прибыль от Р3 и Р4 будет равна f3(1)+ F4(1)=1.

Найдем F3(1) и условно оптимальное управление u*3(1):

F3(1) = max{ f3(0) +F4(1); f3(1) +F4(0)}= max{3,1}=3

Максимум достигается при управлении г=0, значит u*3(1)=0

Аналогично действуем и дальше , при s= 2,3,4,5:

f3(2) = max { f3 (0) + F4(2); f3 (1) + F4(1); f3 (2) + F4(0)}=

max{5;4;3}= 5,

u*3(2)= 0

f3(3) = max { f3 (0) + F4(3); f3 (1) + F4(2); f3 (2) + F4(1); f3 (3) + F4(0)}=

max{6;6;6;5}= 5,

u*3(3)= 0 u*3(3)= 1 u*3(3)=2

f3(4) = max { f3 (0) + F4(4); f3 (1) + F4(3); f3 (2) + F4(2); f3 (3) + F4(1); f3 (4) + F4(0)}=

max{9;7; 8;8; 6}=9,

u*3(4)= 0

f3(5) = max { f3 (0) + F4(5); f3 (1) + F4(4); f3 (2) + F4(3); f3 (3) + F4(2); f3 (4) + F4(1); f3 (5) + F4(0)}=

max{11; 10; 9; 10; 9; 7}=11,

u*3(5)= 0 .

Находим значения F2(S), S = 1,2,3,4,5.

F2(0) = f2 (0) + F3(0)=0

F2(1) = max { f2 (0) + F3(1); f2 (1) + F3(0)}= max{3; 1}=3,

u*2(1)= 0 .

F2(2) = max { f2 (0) + F3(2); f2 (1) + F3(1); f2 (2) + F3(0)}=

max{5; 4; 3}=5

u*2(2)= 0 .

F2(3) = max { f2 (0) + F3(3); f2 (1) + F3(2); f2 (2) + F3(1); f2 (3) + F3(0)}=

max{6; 6; 6; 4}=6

u*2(3)= 0 , 1, 2.

F2(4) = max{9; 7; 8; 7; 5}=9

u*2(4)= 0.

F2(5) = max{11; 10; 9; 9; 8; 6}=11

u*2(5)= 0.

Для функций F1(s) ненужно вычислять значения при s= 0,1,2,3,4 , так как на первом этапе между предприятиями предстоит распределить всю сумму.

F1(5)= max{11; 10; 10; 10; 10; 8}=11

u*1(5)= 0.

Следовательно максимально возможная прибыль от инвестиций равна 11. Чтобы найти способ ее получения, т.е. размеры вложений в каждое предприятие, составим последовательность состояний в предположении, что эти состояния действуют условно оптимальными управлениями:

s* 1 =5; s* 2 = R1 ( s* 1; u*1 (s* 1)) = 5-0 =5;

s* 3 = R2 ( s* 2; u*2 (s* 2)) = 5-0 =5;

s* 4 = R3 ( s* 3; u*3 (s* 3)) = 5-0 =5.

При расчете показателей необходимо учитывать тот факт, что если на k-ом этапе распределению подлежит сумма s и предпринято управление u, то на долю предприятия остается сумма s-u.

Таким образом, оптимальное управление таково:

u* = ( u*1 ; u*2 ; u*3; u*4 )=(0; 0; 0; 5).

ВЫВОД

Всю сумму выгоднее отдать предприятию Р4. В этом случае полу-чится дополнительная прибыль f max = 11. При всех других способах распределения инвестиций дополнительная прибыль окажется меньше.

3.3.Решение задачи о строительстве и оснащении

Итак, точка должна переместиться из положения А в положение Z , набирая в итоге значение координаты i в соответствии с разрешенными направлениями движения: вправо (r), вверх(t), или по диагонали вправо вверх(d). Поставим задачу следующим образом:

С помощью теории графов задача о строительстве и оснащении формулируется следующим образом: в нагруженном графе изображенном на рисунке , требуется найти путь минимальной длины, соединяющий вершину А с вершиной Z и следующий по ребрам графа вдоль направлений r, t или d.

S=3 ---------------------------------------------

| | | | | | |

3 9 9 6 9 1 3 8 6 3 7 9 1

| | | | | | |

S=2 ---------------------------------------------

| | | | | | |

3 4 9 9 9 3 6 5 2 7 6 8 3

| | | | | | |

S=1 ----------------------------------------------

| | | | | | |

8 5 1 4 2 9 4 8 7 8 2 1 1

| | | | | | |

S=0 --2--------6-------1-----6------6------8---

T0 T1 T2 T3 T4 T5 T6

Этапом Тк решения задачи считается номер вертикали k, а состояние на k-ом этапе - номер горизонтали s, на которых находится текущая вершина графа. Пары чисел (k; s) задают координаты всех вершин графа. Начиная с последней вертикали, в которой расположена точка Z, будем находить для каждой вершины кратчайшее расстояние до Z, а также направление, в котором нужно двигаться из текущей вершины, чтобы получить для нее это кратчайшее расстояние. Значения кратчайших расстояний до Z будут равны Fk (s) = f * (S), а условно оптимальными управлениями - выбранные направления r или d либо последовательность нескольких выбранных направлений t, за которой следует выбранное направление r F6 (s) или d. Тем самым все сводится к выбору каждого локального состояния оптимального управления (r, d или t).

Для вертикали Т6 и s= 0,1,2 локально оптимальные управления - это управление t, а значения F6 (s) равны:

F6 (3) = 0 (расстояние от до равно 0);

F6 (2) =1(длина вертикального отрезка);

F6 (1) = 3+ F6 (2) = 3+1 =4;

F6 (0) = 1+ F6 (1) = 1+4 =5.

Отметим локально оптимальные управления t на вертикали Т6 стрелками вверх, а рядом с вершинами напишем соответствующие значения F6 (s). рис.

Переходим на вертикаль Т5 и начинаем определять локально оптимальные управления и значения

Значения кратчайших расстояний до Z будут равны Fk (s) = f * (S), а условно оптимальными управлениями - выбранные направления r или d либо последовательность нескольких выбранных направлений t, за которой следует выбранное направление r F6 (s) или d. Тем самым все сводится к выбору каждого локального состояния оптимального управления (r, d или t).

Для вертикали Т6 и s= 0,1,2 локально оптимальные управления - это управление t, а значения F6 (s) равны:

F6 (3) = 0 (расстояние от до равно 0);

F6 (2) =1(длина вертикального отрезка);

F6 (1) = 3+ F6 (2) = 3+1 =4;

F6 (0) = 1+ F6 (1) = 1+4 =5.

Отметим локально оптимальные управления t на вертикали Т6 стрелками вверх, а рядом с вершинами напишем соответствующие значения F6 (s).

Переходим на вертикаль Т5 и начинаем определять локально оптимальные управления и значения F5 (s), двигаясь сверху вниз.

Для верхней точки s=3 единственно возможное управление - по горизонтали (r). Отметим его стрелками вправо на рис .

F5 (3) = 9; поставив метку 9 у вершины (5;3).

Для s=2 имеются три локальных управления:

-t(тогда длина пути до Z составит 7+ F5 (3)= 16);

-d (тогда длина пути до Z составит 9+ F6(3)= 9);

-r (тогда длина пути до Z составит 6+ F6(2)= 7);

Из полученных чисел выбираем наименьшее: F5 (2) = min {16; 9; 7}=7. Это значение соответствует локальному управлению r, значит r для точки (5;2) - локально оптимальное управление. Отметим его стрелкой вправо из точки (5;2) на рис.

Z

S=3 ---------------------------------------------

| 43 | 42 | 33 | 24 | 16 | 9 | 0

3 9 9 6 9 1 3 8 6 3 7 9 1

| | | | | | |

S=2 ---------------------------------------------

| 33 | 25 | 21 | 16 | 12 | 7 | 1

3 4 9 9 9 3 6 5 2 7 6 8 3

| | | | | | |

S=1 ----------------------------------------------

| 29 | 27 | 19 | 17 | 10 | 7 | 4

8 5 1 4 2 9 4 8 7 8 2 1 1

| | | | | | |

S=0 --2--------6-------1-----6------6------8---

A 25 23 18 17 11 5 5

T0 T1 T2 T3 T4 T5 T6

Для точки (5;1) ( состояние s=1 на этапе T5) также выбираем из трех локальных управлений, чтобы получить наименьшую сумму.

-t(тогда длина пути до Z составит 6+ F5 (2)= 13);

-d (тогда длина пути до Z составит 8+ F6(2)= 9);

-r (тогда длина пути до Z составит 3+ F6(1)= 7);

Из полученных чисел выбираем наименьшее 7 . Это значение соответствует локальному управлению r, значит r для точки (5;1) - локально оптимальное управление. Отметим его стрелкой вправо из вершины (5;1) и записываем метку 7.

Для точки (5;0) ( состояние s=0 на этапе T5) также выбираем из трех локальных управлений, чтобы получить наименьшую сумму.

-t(тогда длина пути до Z составит 9);

-d (тогда длина пути до Z составит 5);

-r (тогда длина пути до Z составит 13);

Из полученных чисел выбираем наименьшее 5 . Это значение соответствует локальному управлению d, значит d для точки (5;0) - локально оптимальное управление. Отметим его стрелкой по д из вершины (5;0) и записываем метку 5.

Аналогично разбираем ситуацию в вершинах (4;3), (4;2), (4;1), (4;0) вертикали Т4, далее вертикалей Т3, Т2, Т1, Т0.

Значения функций Fk (S) таковы:

F6 (3)=0 F6 (2)=1 F6 (1)=4 F6 (0)=5

F5 (3)=9 F5 (2)=7 F5 (1)=7 F5 (0)=5

F4 (3)=16 F4 (2)=12 F4 (1)=10 F4 (0)=11

F3 (3)=24 F3 (2)=16 F3 (1)=17 F3 (0)=18

F2 (3)=33 F2 (2)=21 F2 (1)=19 F2 (0)=18

F1 (3)=42 F1 (2)=25 F1 (1)=27 F1 (0)=23

F0 (3)=43 F0 (2)=33 F0 (1)=29 F0 (0)=25

Локально оптимальные управления определены для каждого состояния на каждом этапе и изображены на рисунке стрелками, выходящими из каждой вершины.

Метка 25 , стоящая у вершины А(0;0), дает нам длину кратчайшего пути из А в Z. Графически длину кратчайшего пути из А в Z можно найти, следуя из исходной вершины вдоль стрелок. Путь по стрелкам ведет через вершины B, C, D, E, F. Последовательность условно оптимальных управлений задачи задает оптимальное управление:

u* = (r, d, d, r, d, r ).

ВЫВОД

Наименьшая стоимость осуществления строительства равна 25 найдено оптимальное управление при котором достигается данный минимум.

ВЫВОД:

(общее заключение по разделу "Динамическое программирование ")

Итак, в заключительном разделе данной работы дана оценка значимости динамических моделей, их вклад в решении управленческих вопросов.

Итак, в отличие от методов линейного и нелинейного программирования, в основе динамического метода лежит разбиение задачи оптимизации на последовательность шагов, на каждом из которых решается задача меньшей размерности.

Таким образом, можно выделить следующие особенности задач динамического программирования :

1. Управляемые переменные и соответствующие ограничения группируются по шагам, и многошаговый процесс принятия решений исследуется в определенной последовательности.

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

3. Рассматриваемое решение, принимаемое при заданном текущем состоянии системы, оказывает прогнозирующее влияние на состояние системы на следующем шаге.

4.Оптимальность решения оценивается в терминах прогнозируемого экономического эффекта для рассматриваемого шага и всех последующих шагов.

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