3. Экономические задачи, решаемые с помощью методов динамического программирования.

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

Также одним из важнейших классов задач, в которых применение методов динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные ,… должны определяться в строгой временной последовательности и не должны меняться местами. К таким задачам относятся задачи «о найме работников».

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

Пример. Пусть x — количество капитальных вложений, которые необходимо распределить между двумя отраслями. Количество капитальных средств у, вложенное в первую отрасль, за год приносит прибыль g(y) = 0,8y^. Доля капитальных средств x – y вложенных во вторую отрасль, приносит за год доход h(x – y) = 0,5(x - y). К концу года средства, вложенные в первую отрасль, составят a(y) = 0,3y, во вторую – b(x –y) = 0,6(x –y).^. По истечении каждого года оставшиеся капитальные вложения заново распределяются по отраслям. Необходимо установить распределение так, чтобы суммарная прибыль за три года была максимальной.

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

f ₁(x₂) = g(y₂₎ + b(x₂)

или

f ₁(x₂) = 0,8y₂ + 0,5(x₂ – y₂) = 0,5x₂ + 0,3y₂

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

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

где g(y₂₎ + h(x₁ – y₁) — прибыль на предпоследнем этапе при y₁.

f₁ — максимальная прибыль на последнем этапе. Необходимо выбрать y₁ такое, чтобы f₂(x₂) была максимальной.

П о известному f₁ получаем

f₂(x₁) = 0,8y₁ + 0,5(x₁ – y₁) + f₁ =

= 0,5x₁ + 0,3y₁ + 0,8 =

= 0,98x₁ + 0,6y₁

Отсюда f(x₁) _{= 1,04x1; у1 = x1.}

Значит на предпоследнем этапе все капитальные вложения также

должны быть направлены в первую отрасль.

Аналогично для первого этапа

f ₃(x₂) = g(y) + h(x – y) + f₂ =

= 0,8y₁ + 0,5(x – y) + 1,04

= 1,124x – 0,012y

Здесь максимум достигается при у = 0. Следовательно, наибольший суммарный доход на всех этапах f₃(x) = 1,24x. На первом этапе все ресурсы необходимо направить во вторую отрасль: y = 0. Таким образом, получена оптимальная стратегия y = 0; y₁ = x₁; y₂ = x₂.

Первый этап: все ресурсы — во вторую отрасль; прибыль соста­вит h(x) = 0,5x. К концу года останется b(x) = 0,6x капитальных вложений, которые будут направлены в первую отрасль и дадут прибыль g(0,6x) = 0,8 · 0,6x = 0,48x_.Остаток ресурсов при этом _{a(0,6x) = 0,3} . _{0,6x = 0,18x}

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

Контрольные вопросы по теме:

1. Представьте математическую модель задачи динамического программирования.

2. Сформулируйте основной принцип подхода, реализуемого в динамическом программировании.

3. Перечислите основные требования к задачам, выполнение которых позволяет решить их методами динамического программирования.

4. В чем заключается Принцип оптимальности Беллмана?

5. Основные идеи вычислительного метода динамического программирования (алгоритм).

6.Назовите виды экономических задач, решаемых с помощью методов динамического программирования.