Модели динамического программирования
- Динамическое программирования
- - это метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы.
Пусть рассматривается управляемый экономический процесс распределение средств между предприятиями.
Рассмотрим алгоритм решения задачи на конкретном примере.
Планируется деятельность четырёх предприятий на очередной год.
Начальные средства: S 0 ус/ед. Размеры вложений в каждое предприятие кратны 1ус/ед.
Средства Х выделенные предприятию приносят в конце года
прибыль F k (Х). Функции F k (Х) заданы таблично.
Принято считать, что:
- прибыль F k (Х) не зависит от вложения средств в другие предприятия;
- прибыль от каждого предприятия выражается в одних и тех же единицах;
- суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Решение находим с помощью сервиса распределение средств между предприятиями
Введём обозначения:
Х - количество средств, выделенных каждому предприятию.
Суммарная прибыль равна: Z =∑ F k (Х).
Переменные удовлетворяют ограничениям:
∑Х k =5
Х k ≥0
Требуется найти переменные Х1,Х2,Х3,Х4, удовлетворяющие системе уравнений и обращающие в максимум функцию.
Таблица
| Х | F 1(Х) | F 2(Х) | F 3(Х) | F 4(Х) |
| 1 | 8 | 6 | 3 | 4 |
| 2 | 10 | 9 | 4 | 6 |
| 3 | 11 | 11 | 7 | 8 |
| 4 | 12 | 13 | 11 | 13 |
| 5 | 18 | 15 | 18 | 16 |
Используя уравнение Беллмана рассмотрим алгоритм решения задачи.
Если Х1=0, то S 1 =5, то прибыль, полученная от четырёх предприятий при этих условиях, будет равна: Z1 = 0+19=19.
Если Х1=1, то S 2=4, то прибыль при этих условиях равна: Z 1 = 8+16=24.
Если Х1=2, то S 2 =3, то прибыль при этих условиях равна: Z 3 = 10+13=23
Если Х1=3, то S 2 =2, то прибыль при этих условиях равна:
Z 4 = 11+10=2110+13=23
Если Х1=4, то S 2 =1, то прибыль при этих условиях равна: Z 5 = 12+16=28
Если Х1=5, то S 2 =0, то прибыль при этих условиях равна: Z 5 =18+0=18
Сравнивая полученные числа, получим: Z 1 = 24, при Х1=1.
Максимум суммарной прибыли Zmaх = 24 ус/ед. при условии, что:
- первому предприятию выделено 1 ус/ед.;
- второму предприятию 2 ус/ед.;
- третьему предприятию 1 ус/ед.;
- четвёртому предприятию 1 ус/ед.
I этап. Условная оптимизация.
1-ый шаг. k = 4.
| e3 | u4 | e4=e3-u4 | f4(u4) | F*4(e4) | u4(e4) |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 4 | 4 | 1 | |
| 2 | 0 | 2 | 0 | 0 | 0 |
| 1 | 1 | 4 | 0 | 0 | |
| 2 | 0 | 6 | 6 | 2 | |
| 3 | 0 | 3 | 0 | 0 | 0 |
| 1 | 2 | 4 | 0 | 0 | |
| 2 | 1 | 6 | 0 | 0 | |
| 3 | 0 | 8 | 8 | 3 | |
| 4 | 0 | 4 | 0 | 0 | 0 |
| 1 | 3 | 4 | 0 | 0 | |
| 2 | 2 | 6 | 0 | 0 | |
| 3 | 1 | 8 | 0 | 0 | |
| 4 | 0 | 13 | 13 | 4 | |
| 5 | 0 | 5 | 0 | 0 | 0 |
| 1 | 4 | 4 | 0 | 0 | |
| 2 | 3 | 6 | 0 | 0 | |
| 3 | 2 | 8 | 0 | 0 | |
| 4 | 1 | 13 | 0 | 0 | |
| 5 | 0 | 16 | 16 | 5 |
2-ый шаг. k = 3.
| e2 | u3 | e3=e2-u3 | f3(u3) | F*3(e2) | F2(u3,e2) | F*3(e3) | u3(e3) |
| 1 |
0 | 1 | 0 | 4 | 4 | 4 | 0 |
| 1 | 0 | 3 | 0 | 3 | 0 | 0 | |
| 2 | 0 | 2 | 0 | 6 | 6 | 0 | 0 |
| 1 | 1 | 3 | 4 | 7 | 7 | 1 | |
| 2 | 0 | 4 | 0 | 4 | 0 | 0 | |
| 3 | 0 | 3 | 0 | 8 | 8 | 0 | 0 |
| 1 | 2 | 3 | 6 | 9 | 9 | 1 | |
| 2 | 1 | 4 | 4 | 8 | 0 | 0 | |
| 3 | 0 | 7 | 0 | 7 | 0 | 0 | |
| 4 | 0 | 4 | 0 | 13 | 13 | 13 | 0 |
| 1 | 3 | 3 | 8 | 11 | 0 | 0 | |
| 2 | 2 | 4 | 6 | 10 | 0 | 0 | |
| 3 | 1 | 7 | 4 | 11 | 0 | 0 | |
| 4 | 0 | 11 | 0 | 11 | 0 | 0 | |
| 5 | 0 | 5 | 0 | 16 | 16 | 0 | 0 |
| 1 | 4 | 3 | 13 | 16 | 0 | 0 | |
| 2 | 3 | 4 | 8 | 12 | 0 | 0 | |
| 3 | 2 | 7 | 6 | 13 | 0 | 0 | |
| 4 | 1 | 11 | 4 | 15 | 0 | 0 | |
| 5 | 0 | 18 | 0 | 18 | 18 | 5 |
3-ый шаг. k = 2.
| e1 | u2 | e2=e1-u2 | f2(u2) | F*2(e1) | F1(u2,e1) | F*2(e2) | u2(e2) |
| 1 |
0 | 1 | 0 | 4 | 4 | 0 | 0 |
| 1 | 0 | 6 | 0 | 6 | 6 | 1 | |
| 2 | 0 | 2 | 0 | 7 | 7 | 0 | 0 |
| 1 | 1 | 6 | 4 | 10 | 10 | 1 | |
| 2 | 0 | 9 | 0 | 9 | 0 | 0 | |
| 3 | 0 | 3 | 0 | 9 | 9 | 0 | 0 |
| 1 | 2 | 6 | 7 | 13 | 13 | 1 | |
| 2 | 1 | 9 | 4 | 13 | 0 | 0 | |
| 3 | 0 | 11 | 0 | 11 | 0 | 0 | |
| 4 | 0 | 4 | 0 | 13 | 13 | 0 | 0 |
| 1 | 3 | 6 | 9 | 15 | 0 | 0 | |
| 2 | 2 | 9 | 7 | 16 | 16 | 2 | |
| 3 | 1 | 11 | 4 | 15 | 0 | 0 | |
| 4 | 0 | 13 | 0 | 13 | 0 | 0 | |
| 5 | 0 | 5 | 0 | 18 | 18 | 0 | 0 |
| 1 | 4 | 6 | 13 | 19 | 19 | 1 | |
| 2 | 3 | 9 | 9 | 18 | 0 | 0 | |
| 3 | 2 | 11 | 7 | 18 | 0 | 0 | |
| 4 | 1 | 13 | 4 | 17 | 0 | 0 | |
| 5 | 0 | 15 | 0 | 15 | 0 | 0 |
4-ый шаг. k = 1.
| e0 | u1 | e1=e0-u1 | f1(u1) | F*1(e0) | F0(u1,e0) | F*1(e1) | u1(e1) |
| 1 |
0 | 1 | 0 | 6 | 6 | 0 | 0 |
| 1 | 0 | 8 | 0 | 8 | 8 | 1 | |
| 2 | 0 | 2 | 0 | 10 | 10 | 0 | 0 |
| 1 | 1 | 8 | 6 | 14 | 14 | 1 | |
| 2 | 0 | 10 | 0 | 10 | 0 | 0 | |
| 3 | 0 | 3 | 0 | 13 | 13 | 0 | 0 |
| 1 | 2 | 8 | 10 | 18 | 18 | 1 | |
| 2 | 1 | 10 | 6 | 16 | 0 | 0 | |
| 3 | 0 | 11 | 0 | 11 | 0 | 0 | |
| 4 | 0 | 4 | 0 | 16 | 16 | 0 | 0 |
| 1 | 3 | 8 | 13 | 21 | 21 | 1 | |
| 2 | 2 | 10 | 10 | 20 | 0 | 0 | |
| 3 | 1 | 11 | 6 | 17 | 0 | 0 | |
| 4 | 0 | 12 | 0 | 12 | 0 | 0 | |
| 5 | 0 | 5 | 0 | 19 | 19 | 0 | 0 |
| 1 | 4 | 8 | 16 | 24 | 24 | 1 | |
| 2 | 3 | 10 | 13 | 23 | 0 | 0 | |
| 3 | 2 | 11 | 10 | 21 | 0 | 0 | |
| 4 | 1 | 12 | 6 | 18 | 0 | 0 | |
| 5 | 0 | 18 | 0 | 18 | 0 | 0 |
Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*4(e0 = 5) = 24. То есть максимальный доход всей системы при количестве средств e0 = 5 равен 24.
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 5) = 1
При этом остаток средств составит:
e1 = e0 - u1
e1 = 5 - 1 = 4
Из таблицы 2-го шага имеем F*3(e1 = 4) = 16. То есть максимальный доход всей системы при количестве средств e1 = 4 равен 16.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 4) = 2
При этом остаток средств составит:
e2 = e1 - u2
e2 = 4 - 2 = 2
Из таблицы 3-го шага имеем F*2(e2 = 2) = 7. То есть максимальный доход всей системы при количестве средств e2 = 2 равен 7.
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 2) = 1
При этом остаток средств составит:
e3 = e2 - u3
e3 = 2 - 1 = 1
Последнему предприятию достается 1.
Итак, инвестиции в размере 5 необходимо распределить следующим образом:
1-му предприятию выделить 1,
2-му предприятию выделить 2,
3-му предприятию выделить 1,
4-му предприятию выделить 1.
Что обеспечит максимальный доход, равный 24.
