Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример решения задачи методом динамического программирования.
|
|
Задание. Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.
Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль p; (x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным:
| Инвестирование средств (тыс. ден. ед.) | Прибыль (тыс. ден. ед.) | ||
| x | pi(x) | p2 (x) | p3(x) |
| 3, 22 | 3, 33 | 4, 27 | |
| 3, 57 | 4, 87 | 7, 64 | |
| 4, 12 | 5, 26 | 10, 25 | |
| 7, 34 | 15, 93 | ||
| 4, 85 | 9, 49 | 16, 12 |
Решение. Составим математическую модель задачи.
1.Число шагов равно 3.
2.Пусть s - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.
3. Управление на i-ом шаге (i=1, 2, 3) выберем xi - количество средств, инвестируемых в i- ое предприятие.
4. Выигрыш pi(xi) на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p1(x1)+ p2(x2)+ p3(x3).
5. Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: fi(s, x) = s-x.
6.На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x3(s)=s, W3(s)=p3(s).
7.Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид
W2 (s) = max{ p 2 (x) + W3(s - x)}
x< s
Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.
| s | i=3 | i=2 | i=1 | |||
| x3(s) | W3(s) | x2(s) | W2(s) | xi(s) | Wi(s) | |
| 4, 27 | 4, 27 | |||||
| 7, 64 | 7, 64 | |||||
| 10, 25 | 10, 97 | |||||
| 15, 93 | 15, 93 | |||||
| 16, 12 | 19, 26 | 19, 26 |
В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид x3(s)=s, W3(s)=p3(s), то две колонки таблицы, соответствующие i=3, заполняются автоматически по таблице исходных данных.
На шаге i=2 основное функциональное уравнение имеет вид
W2 (s) = max{p2 (x) + W3(s - x)}
x≤ s
Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.
| s | x | s-x | p2(x) | W3(s-x) | p2(x)+W3(s-x) | W2(s) |
| 4, 27 | 4, 27 | 4, 27 | ||||
| 3, 33 | 3, 33 | |||||
| 7, 64 | 7, 64 | 7, 64 | ||||
| 3, 33 | 4, 27 | 7, 6 | ||||
| 4, 87 | 4, 87 | |||||
| 10, 25 | 10, 25 | 10, 97 | ||||
| 3, 33 | 7, 64 | 10, 97 | ||||
| 4, 87 | 4, 27 | 9, 14 | ||||
| 5, 26 | 5, 26 | |||||
| 15, 93 | 15, 93 | 15, 93 | ||||
| 3, 33 | 10, 25 | 13, 58 | ||||
| 4, 87 | 7, 64 | 12, 51 | ||||
| 5, 26 | 4, 27 | 9, 53 | ||||
| 7, 34 | 7, 34 | |||||
| 16, 12 | 16, 12 | 19, 26 | ||||
| 3, 33 | 15, 93 | 19, 26 | ||||
| 4, 87 | 10, 25 | 15, 12 | ||||
| 5, 26 | 7, 64 | 12, 9 | ||||
| 7, 34 | 4, 27 | 11, 61 | ||||
| 9, 49 | 9, 49 |
На шаге i=1 основное функциональное уравнение имеет вид
Wx(s) = max{ px(x) + W2(s - x)}
x ≤ s
а состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.
| s | x | s-x | pi(x) | W2(s-x) | pi(x)+W2(s-x) | Wi(s) |
| 19, 26 | 19, 26 | 19, 26 | ||||
| 3, 22 | 15, 93 | 19, 15 | ||||
| 3, 57 | 10, 97 | 14, 54 | ||||
| 4, 12 | 7, 64 | 11, 76 | ||||
| 4, 27 | 8, 27 | |||||
| 4, 85 | 4, 85 |
Видно, что наибольшее значение выигрыша составляет 19, 26. При этом оптимальное управление на первом шаге составляет x1(s1)=0 (s1=5), на втором шаге x2(s2) =1 (s2=s1-x1=5) и на третьем шаге x3(s3) =4 (s3=s2-x2=4).
Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.
Таким образом, для получения наибольшей общей прибыли в размере 19, 26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие.[4]
|
|