ЛСО) = 2(0) + /з(0) = о + о = о, xliO) = о, Л(1) = тах{2(0) + /з(1),20) + /з(0)} = гпах{2,1} = 2,
Л (2) = max (0) + f, (2), (1) + /з (1), 2(2) + /з (0)} = max {4,3,3} = 4,
х;(2) = 0,
Л (3) = max (0) + /з (3), <Р2 (1) + /з (2), (2) + /з (1), <Р2 (3) + /з (1)} = = max{5,5,5,6} - 6,
х;(3) = 3,
/2 (4) = max
2(0) + /з(4),2(1) + /з(3),2(2) + [+/з (2), <р, (3) + /з (1),(4) + /з (0) J
х;(4) = 3,
= max{6,6,7,8,7} = 8,
/2(5) = max <
2 (0) +/3 (5), 2 0) +/3 (4), 2 (2) + +/з(3),2(3) + /з(2),«2(4) + /з(1),«2(5) + /з(0) J = max{8,7,8,10,9,8} = 10,
x;{5) = 3.
Далее вычислим значения функции /(й?) и соответствующие значения x*(u?) исходя из соотношения
f(d) = max{<p(x,) + f(d-x,)}. 0<x, <d
/,(0) = ,(0) = 0, х;(0) = 0,
/,(1) = тах{,(0) + M\),<PiO) + /2(0)} = max{2,3} = 3, хЛ\) = 1
yj(4) = max
= max{8,9,8,7,7} = 9.
/,(2) = max{,(0) + Л(2),,(1) + Л(1),«?,(2) + Л(0)} = max{3,5,4} = 4,
xl(2) = \,
f, (3) = max (0) + Л (3), (p, (1) + (2), «о, (2) + Л (1), , (3) + Л (0)} = = max{6,7,6,5} = 7,
,*(3) = 1,
>,(0) + Л(4),«»,(1) + Л(3),,(2) + +/2(2),«,,(3) + Л(1),,(4) + /2(0)
x;(4) = l,
>,(0) + /2(5),,(1) + Л(4),,(2) + Л(3),,(3) + Л(2),,(4) + Л(1),,(5) + /(0)] = max{lO,l 1,10,9,9,8} = 11, х\{5) = \.
Результаты приведенных вычислений собраны в табл. 7.2.
Таблица 7.2
/(5) = max
Как отмечалось, максимальная эффективность может быть вычислена из соотношения
max = max {0,3,5,7,9,11} = 11. 0<х<5
Далее воспользуемся общими соотношениями (7.3) для нахождения оптимального распределения
х[=х\{5) = \.
xl =Хз(5-х* -Х2) = ХзЧ5-1-3) = Хз(1) = 1.
Ответ, Оптимальным распределением кредитных денег между предприятиями является распределение: 1-е предприятие 1 млн. руб.; 2-е предприятие 3 млн. руб.; 3-е предприятие 1 млн. руб. Ожидаемая при этом прибыль составит 11 млн. руб.
К задачам рассматриваемого типа относится и такая классическая задача линейного программирования, как задача о рюкзаке, которая в переменных О и 1 имеет следующий вид:
max z = qx, -i- С2Х2 +... + с„х„ aiXi+a2X2+... + a„x„<fe, x,g{0; 1}, / = 1, 2,...,«.
В общем виде этот тип задач может быть описан следующим образом. Имеется п позиций, каждую из которых можно либо выбрать (х, = 1),
либо нет (х, = 0). Выбор /-й позиции требует затрат ресурса в количестве . Общее количество имеющегося в распоряжении ресурса равно Ь. Эффект от выбора i-и позиции есть q . Следует осуществить выбор среди позиций, допустимый в смысле затрат ресурсов и имеющий максимальный суммарный эффект.
7.3. Метод динамического программирования в недетерминированном случае
В рассмотренных задачах текущее состояние системы и решение на текущем шаге однозначно определяли состояние системы в последующем периоде. Такие задачи относятся к детерминированным задачам динамического программирования. Однако во многих случаях последующее состояние может зависеть от некоторых случайных величин (например, уровень рыночного спроса на определенный вид товара и так далее). Рассмотрим модификацию метода динамического программирования в этом случае на примере задачи о воспроизводстве форели в озере, приведенной ранее в детерминированном случае.
Пример. Владелец озера должен решить, сколько форели вылавливать и продавать каждый год. Если он продает х форелей в течение года