Решение задач методом динамического программирования

 

Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.

Решение:

I этап. Условная оптимизация.

Обозначим через X_k количество средств, выделенных k-му предприятию. Тогда суммарная прибыль равна:

 

Переменные  x удовлетворяют ограничениям:

 

 

Процесс распределения средств рассматривается как 4-шаговый, номер шага совпадает с номером предприятия. Уравнение состояний в данной задаче имеют вид:

 

где -параметр состояния – количество средств, оставшихся после k-го шага, т.е. средства, которые остается распределить между оставшимися предприятиями.

Ведем в  рассмотрение функцию  – условную оптимальную прибыль, полученную от k-го, (k+1)-го, …, 4-го предприяти1, если между ними распределились оптимальным образом средства .

Допустимые  управления на k-ом шаге удовлетворяют условию: (либо k-му предприятию ничего не выделяем, либо не больше того, что имеем к k-му шагу,).

 

Уравнения Беллмана имеют вид:

 

,

,

 

 

Последовательно решаем записанные уравнения, проводя  условную оптимизацию каждого шага.

 

 

 

 

1-й шаг. 

k = 4.

Sk-1	Xk	Sk	F3(x3) + Z4(S3)	Z3(S2)	X3(S2)
0	0	0	0	0	0
50	0 50	50 0	0 13	13	50
100	0 50 100	100 50 0	0 13 31	31	100
150	0 50 100 150	150 100 50 0	0 13 31 37	37	150
200	0 50 100 150 200	200 150 100 50 0	0 13 31 37 44	44	200
250	0 50 100 150 200 250	250 200 150 100 50 0	0 13 31 37 44 63	63	250

 

 

 

 

 

2-й шаг.

k = 3.

 

Sk-1	Xk	Sk	F3(x3) + Z4(S3)	Z3(S2)	X3(S2)
0	0	0	0	0	0
50	0 50	50 0	0+13=13 17+0=17	17	50
100	0 50 100	100 50 0	0+31=31 17+13=30 33+3=33	33	100
150	0 50 100 150	150 100 50 0	0+37=37 17+13=48 33+13=46 40+0=40	48	50
200	0 50 100 150 200	200 150 100 50 0	0+44=44 17+37=54 33+31=64 40+13=53 47+0=47	64	100
250	0 50 100 150 200 250	250 200 150 100 50 0	0+63=63 17+44=61 33+37=70 40+31=71 47+13=60 60+0=60	71	150

 

 

 

 

3-й шаг.

k = 2.

Sk-1	Xk	Sk	F3(x3) + Z4(S3)	Z3(S2)	X3(S2)
0	0	0	0	0	0
50	0 50	50 0	0+17=17 12+0=12	17	0
100	0 50 100	100 50 0	0+33=33 12+17=29 30+0=30	33	0
150	0 50 100 150	150 100 50 0	0+48=48 12+33=45 30+17=47 38+8=38	48	0
200	0 50 100 150 200	200 150 100 50 0	0+64=64 12+48=60 30+33=63 38+17=55 45+0=45	64	0
250	0 50 100 150 200 250	250 200 150 100 50 0	0+71=71 12+64=76 30+48=78 38+33=71 45+17=62 54+0=54	78	100

 

 

 

 

 

4-й шаг.

k = 1.

Sk-1	Xk	Sk	F3(x3) + Z4(S3)	Z3(S2)	X3(S2)
0	0	0	0	0	0
50	0 50	50 0	0+17=17 15+0=15	17	0
100	0 50 100	100 50 0	0+33=33 15+12=27 32+0=32	33	0
150	0 50 100 150	150 100 50 0	0+48=48 15+33=48 32+17=49 39+0=39	49	100
200	0 50 100 150 200	200 150 100 50 0	0+64=64 15+48=63 32+33=65 39+17=56 46+0=46	65	100
250	0 50 100 150 200 250	250 200 150 100 50 0	0+78=78 15+64=79 32+48=80 39+33=72 46+17=63 52+0=52	80	100

 

Из таблицы  4-го шага имеем F*₄(e⁰ = 250) = 80. То есть максимальный доход всей системы при количестве средств e⁰ = 250 равен 80.

Из этой же таблицы получаем, что 1-му предприятию  следует выделить u*₁(e⁰ = 250) = 100

 

При этом остаток  средств составит:

e¹ = e⁰ - u¹

e¹ = 250 - 100 = 150

Из таблицы 3-го шага имеем F*₃(e¹ = 150) = 48. То есть максимальный доход всей системы при количестве средств e¹ = 150 равен 48

Из этой же таблицы получаем, что 2-му предприятию  следует выделить u*₂(e¹ = 150) = 0

При этом остаток  средств составит:

e² = e¹ - u²

e² = 150 - 0 = 150

Из таблицы 2-го шага имеем F*₂(e² = 150) = 48. То есть максимальный доход всей системы при количестве средств e² = 150 равен 48

Из этой же таблицы получаем, что 3-му предприятию  следует выделить u*₃(e² = 150) = 50

При этом остаток  средств составит:

e³ = e² - u³

e³ = 150 - 50 = 100

Последнему  предприятию достается 100

Ответ: инвестиции в размере 250 млн.руб. необходимо распределить следующим образом:

1-му предприятию  выделить 100 млн.руб.

2-му предприятию  выделить 0

3-му предприятию  выделить 50 млн.руб.

4-му предприятию  выделить 100 млн.руб.

Что обеспечит  максимальный доход, равный 80 млн.руб.

 

 

 

 

ЗАКЛЮЧЕНИЕ.

 

Одним из условий применимости метода динамического  программирования является возможность  разбиения процесса оптимизации  решения на ряд однотипных шагов (этапов), каждый из которых планируется  отдельно, но с учетом состояния  системы на начало этапа и последствий  принятого решения. Однако из этого  правила есть исключение. Среди всех шагов существует один, который может  планироваться без оглядки на будущее. Это последний шаг. Он может  быть изучен и спланирован сам  по себе наилучшим образом, поскольку  за ним нет больше этапов. Отсюда получаем одну из специфических особенностей динамического программирования: всю  вычислительную процедуру программирования целесообразно разворачивать от конца к началу.

В процессе оптимизации управления методом  динамического программирования многошаговый процесс проходится дважды. Первый раз – от конца к началу, в  результате чего находятся условно-оптимальные  управления и условно-оптимальное  значение функции цели для каждого  шага, в том числе оптимальное  управление для первого шага и  оптимальное значение функции цели для всего процесса. Второй раз  – от начала к концу, в результате чего находятся уже оптимальные  управления на каждом шаге с точки  зрения всего процесса. Первый этап сложнее и длительнее второго, на втором остается лишь отобрать рекомендации, полученные на первом. Следует отметить, что понятия «конец» и «начало» можно поменять местами и разворачивать  процесс оптимизации в другом направлении. С какого конца начать – диктуется удобством выбора этапов и возможных состояний  на их начало.

Из качественного  анализа идеи поэтапной оптимизации  используют принципы, лежащие в основе динамического программирования: принцип  оптимальности и принцип погружения.

 

СПИСОК  ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ.

 

1. А.Т.Надеев, О.С.Данилова, Е.С.Прохорова Разработка управленческих решений – Нижний Новгород, 2007
2. Кузнецов, А. В. Высшая математика. Математическое программирование А. В. Кузнецов, В. А. Сакович, Н.И. Холод. – Минск: Вышэйшая школа, 1994. – 237 с.
3. Габасов Р.Л. Методы оптимизации / Р. Л. Габанов, М.И Кирилова. – Минск: Наука, 1981. – 129 с.
4. Кузнецов А.В. Руководство к решению задач по математическому программированию / А. В. Кузнецов, Н.И. Холод, Л.С. Костевич. – Минск: Вышэйшая школа, 2001. – 240 с.
5. Карманов В.Г. Математическое программирование / В. Г. Карманов. – Минск: Наука, 1986. – 74 с.
6. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22.-368 с.
7. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. — 2-е изд. — М.: «Вильямс», 2006.-1296 с.