Пример: имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S0 =100 д.ед. Функции дохода предприятий даны в матрице прибылей по каждому предприятию.
| Х | 1 предприятие f (х1) | 2 предприятие f (х2) | 3 предприятие f (х3) | 4 предприятие f (х4) |
Решение:
Схема решения:
4 предприятия Условная оптимизация
денег всего S0=80
So____Iпр____S1____IIпр_____S2____IIIпр____S3____IVпр________S4
1шаг 2 шаг 3 шаг 4 шаг
х1 х2 х3 х4
f(x1) f(x2) f(x3) f(x4)
F4=max{f(x4)}
Безусловная F3=max{ f(x3)+F4}
Оптимизация F2=max{ f(x2)+F3}
F1=max{ f(x1)+F2}
Используется принцип Беллмана:
Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце каждого шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
математическая модель прямой задачи:
Экономический смысл переменных:
xi – количество денег, вкладываемых в i предприятие.
Si – количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге);
F(xi) – прибыль от вложенной суммы денег;
S0 – начальный капитал.
Рассмотрим 4-й шаг:
На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед.Тогда прибыль от вложения денег можно получить следующую.
| S3 | Х4 | f (x4) | F4 |
Рассмотрим 3-й шаг:
На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 д.ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 д.ед.можно поделить так (0;40), (20;20);
60 д.ед. – (0;60), (20;40), (40;20), (60;0).
Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага
Прибыль на 3-м шаге берется максимальной по каждому вложению.
| Вклад | Проект | Остаток | Прибыль из матрицы | Прибыль за шаг | Прибыль на шаге | |
| S2 | Х3 | S3 | f (x3) | F4 | f+F | F3 |
Рассмотрим 2-й шаг.
| Вклад | Проект | Остаток | Прибыль из матрицы | Прибыль за шаг | Прибыль на шаге | |
| S1 | Х2 | S2 | f (x2) | F3 | f+F | F2 |
Рассмотрим 1-й шаг.
| Вклад | Проект | Остаток | Прибыль из матрицы | Прибыль за шаг | Прибыль на шаге | |
| S1 | Х2 | S2 | f (x2) | F3 | f+F | F2 |
Анализ результатов:
Максимальная прибыль равна 15 д.ед. Расположить денежные средства между проектами можно несколькими способами:
1) 1 проект – 0 д.ед., 2 проект – 0 д.ед., 3 проект – 60 д.ед., 4 проект – 40 д.ед.
2) 1 проект – 0 д.ед., 2 проект – 100 д.ед., 3 проект – 0 д.ед., 4 проект – 0 д.ед.
3) 1 проект – 20 д.ед., 2 проект – 0 д.ед., 3 проект – 60 д.ед., 4 проект – 20 д.ед.
4) 1 проект – 60 д.ед., 2 проект – 0 д.ед., 3 проект – 20 д.ед., 4 проект – 20 д.ед.
5) 1 проект – 60 д.ед., 2 проект – 0 д.ед., 3 проект – 0 д.ед., 4 проект – 40 д.ед.
6.4. Задача распределения средств на два года
Найти оптимальный способ распределения средств S0 = 100 тыс.руб между двумя предприятиями на два года, если вложенные средства в первое предприятие дают доход f1(x) = 0.9x и возвращаются в размере j1(x) = 0.5x. Аналогично, для второго предприятия f2(x) = 0.8x и j2(x) = 0.7x.
| 1 предприятие | 2 предприятие | Всего | |
| Средства в начале года 1 года | х1 | 100-х1 | |
| Прибыль на первом году | 0,9х1 | 0,8(100-х1) | (0,9-0,8)х1+80 |
| Возврат денег | 0,5х1 | 0,7(100-х1) | (0,5-0,7)х1+70 =70-0,2х1 |
| Средства в начале 2 года | х2 | 70-0,2х1- х2 | 70-0,2х1 |
| Прибыль во втором году | 0,9х2 | 0,8(70-0,2х1- х2) | 56-0,16х1+0,1х2 |
| Прибыль за два года | 0,1х1+80+56-0,16х1+0,1х2=136-0,6х1+0,1х2 |
Отсюда можно сделать вывод о том, что х1=0, х2=70, максимальная прибыль за два года составит 143 ден. ед.
Контрольные вопросы:
1.Какие задачи решаются методом динамического программирования?
2.Что означает понятие «шаговое управление»?
3.Как определяются шаги при решении задачи ДП?
4.В чем суть принципа оптимальности Беллмана?
5.Каким образом проводится условная и безусловная оптимизация?
6.Как решить задачу распределения средств на 1 год?
7. Как решить задачу распределения средств на 2 года?
8.Анализ результатов решения задачи распределения средств на 1год и на 2 года?
