МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Часто возникают ситуации, когда решение можно принять только в несколько приемов — шаг за шагом. В этом случае необходимо привлекать аппарат динамического программирования.

Одна из таких типичных задач — распределение капитальных вложений, когда на каждом этапе (например, ежегодно) решается задача распределения. Требуется установить такое распределение капитальных ресурсов на каждом этапе, при котором суммарная прибыль за все этапы будет максимальной.

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

Первыми к появлению динамического программирования привели динамические задачи управления запасами (ЗУЗ). Они составляют один из наиболее многочисленных классов экономических задач. Правильное и своевременное определение оптимальной стратегии управления запасами, а также их нормативного уровня позволяет высвободить значительные оборотные средства, замороженные

75

в виде запасов, что в конечном итоге повышает эффективность используемых ресурсов.

Пример 1. Пусть X — количество капитальных вложений, которые необходимо распределить между двумя отраслями. Количество капитальных средств у, вложенное в первую отрасль, за год приносит прибыль д(у) = 0,8у. Доля капитальных средств х^у, вложенных во вторую отрасль, приносит за год доход h(x — y) = 0, Ъ(х — у). К концу года средства, вложенные в первую отрасль, составят а(у) = 0, Зу, во вторую — Ь(х — у) = 0,6(ж — у). По истечении каждого года оставшиеся капитальные вложения заново распределяются по отраслям. Необходимо установить распределение так, чтобы суммарная прибыль за три года была максимальной.

Итак, сначала ищем величину у2 — количество средств, вложенных в течение третьего года, затем у\ и уо (соответственно второго и первого годов). В соответствии с принципом оптимальности, зная зависимость от величин у\ и уо, а также ж2 — количество ресурсов, полученных к началу третьего года, необходимо наилучшим образом использовать доступное количество ресурсов, т. е. решить задачу

/1(2*2) =   max {д(у2) + b(x2 у2)}

0<у2<Х2

ИЛИ

/1(2*2)=   тах {0,8у2 + 0,5(ж2 — у2)} =   max {0,5ж2 + 0,3у2}.

0<у2<Х2 0<у2<Х2

Очевидно, максимум возможен при х2 = у2.

Следовательно, все ресурсы на последнем этапе нужно направить в первую отрасль. При этом будет получена прибыль /і(ж2) = 0,8ж2. Теперь найдем у\. Рассмотрим двухшаговый процесс — последний и предпоследний этапы. Необходимо наилучшим образом использовать ресурсы Х\, не интересуясь предыдущим решением. Максимальный суммарный доход на последних двух этапах

/2(2*1) =   max {g(y1) + h{x1 yi) + /і[a(j/i) + Ь(хг -уі)]},

0<уі<хі

где д(уі) + h(xi — уі) — прибыль на предпоследнем этапе при у\\ /i[a(t/i) + Ь(х\ — yi)] — максимальная прибыль на последнем этапе.

Необходимо выбрать ід Є [0,Жі] такое, чтобы /2(жі) была максимальной.

76

По известному /і получаем /2(жі) =   max {0,8yi + 0,5(жі yi) +/і[0,3уі + 0,6(жі yi)]} =

0<уі<хі

=   max {0,5жі + 0,3t/i + 0,8[0,6жі — 0,3j/i]} =

0<Vi<xi

=   max {0,98жі + 0,06t/i}.

0<уі<хі

Отсюда /(жі) = 1,04жі; у\ = х\.

Значит, на предпоследнем этапе все капитальные вложения также должны быть направлены в первую отрасль. Аналогично для первого этапа

/з(ж) = max {д(у) + h(x у) + f2[a(y) + b(x у)]} =

0<у<х

= max {0,8у + 0,5(ж у) + 1,04[0, Зу + 0,6(ж у)}} =

0<у<х

= max {1,124ж-0,012у}.

0<у<х

Здесь максимум достигается при у = 0. Следовательно, наибольший суммарный доход на всех этапах /з(ж) = 1,124ж. На первом этапе все ресурсы необходимо направить во вторую отрасль: у = 0.

Таким образом, получена оптимальная стратегия у = 0; у± = х±; У 2 = х2Первый этап: все ресурсы — во вторую отрасль; прибыль составит h(x) = 0,5х. К концу года останется Ь(х) = 0,6ж капитальных вложений, которые будут направлены в первую отрасль и дадут прибыль д(0,6ж) = 0,8 • 0,6ж = 0,48х. Остаток ресурсов при этом а(0,6ж) = 0,3 • 0,6ж = 0,18ж.

Прибыль на третьем этапе д(0,18х) = 0,8 • 0,18ж = 0,144ж; тогда суммарная прибыль составит 0,5х + 0,48х + 0,144ж = 1,124ж.

Формально задача динамического программирования имеет такой вид: найти

п

max z = J2fj(xj)

Xl,...,X„ •г—'

i=i

при условиях

OjXj < Ь,      aj > 0,   Xj > 0,   j = 1,2,..., те.

Целевая функция задачи является суммой функций от одной переменной. Такая функция называется сепарабельной, или аддитивной.

77

 

 ...  8



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх