Динамическое программирование задача распределения капитальных вложений
4.1. Формулировка задачи распределения капитальных вложений
Рассмотрим нелинейную задачу распределения капитальных вложений между предприятиями производственного объединения. Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере хj (тыс. рублей) (прирост прибыли на данном предприятии) выражается функцией fi(xi), i = 1, 2, 3, 4. Функции fi(xi) заданы в исходных данных задачи, где, например, число 37 означает, что прирост прибыли на 1-ом предприятии при инвестировании в него 100 тыс. рублей составит 37 тыс. рублей. На практике определение данных функции – довольно трудоемкая экономическая задача. Приходим к задаче: Требуется найти такое распределение (х1, х2, х3, х4) капитальных вложений между четырьмя предприятиями, которое максимизирует суммарный прирост мощности или прибыли: Z = f1(x1) + f2(x2) + f3(x3) + f4(x4) → max при ограничении по общей сумме капитальных вложений х1 + х2 + х3 + х4 = 700 причем будем считать, что все переменные принимают только целые неотрицательные значения, кратные 100: х1, х2, х3, х4 = 0, или 100 000, или 200 000, или 300 000, или 400 000, или 500 000, или 600 000, или 700 000 где xi – пока еще неизвестный размер инвестиций i-й фирме.
4.2. Решение задачи распределения капитальных вложений методом динамического программирования
Динамическое программирование — это вычислительный метод для решения задач управления определённой структуры, когда задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге (этапе) определяется экстремум функции только от одной переменной. Состояние исследуемой системы на каждом шаге характеризуется некоторой переменной величиной, которая называется параметром состояния. Эффект от принятия параметром состояния того или иного значения на данном этапе вместе с уже рассмотренными шагами характеризуется функцией состояния. Решение конкретной задачи методом динамического программирования сводится к выбору параметра состояния, составления функции состояния и рекуррентных соотношений, связывающих функции состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления. Воспользуемся методом динамического программирования для решения полученной задачи распределения капитальных вложений. Последовательно ищется оптимальное распределение для k = 2, 3 и 4 фирм. Пусть первым двум фирмам выделено тыс. рублей инвестиции ( — параметр состояния, который может изменяться от 0 до 700). Обозначим через F2 () максимальный прирост прибыли на первых двух предприятиях. Если из тыс. рублей 2-ая фирма получит х2 тыс. рублей, то максимальный прирост прибыли на 2-ой фирме можно выразить как f2(x2). На долю 1-ого предприятия останется — х2 тыс. рублей, а максимальный прирост прибыли на 1-ом предприятии составит F1 ( — х2). Тогда максимальный прирост прибыли на двух предприятиях будет равен F2 () = max 2(x2) + F1 ( — х2)> 0 ≤ x2 ≤ 700 Используя исходные данные из задания, строим Таблицу № 1.1. Значения f2(x2) складываем со значениями F1 (-x2) = f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Таблица № 1.1
 -х2 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
| X2 | F1(—x2) f2(x2) | 0 | 37 | 64 | 87 | 105 | 120 | 134 | 145 |
| 0 | 0 | 0     | 37 | 64 | 87 | 105 | 120 | 134 | 145 |
| 100 | 48 | 48* | 85* | 112* | 135 | 153 | 168 | 182 | — |
| 200 | 75 | 7 5 | 112* | 139* | 162* | 180 | 195 | — | — |
| 300 | 98 | 9 8 | 135 | 162* | 185 | 203 | — | — | — |
| 400 | 120 | 120 | 157 | 184 | 207* | — | — | — | — |
| 500 | 132 | 132 | 169 | 196 | — | — | — | — | — |
| 600 | 144 | 144 | 181 | — | — | — | — | — | — |
| 700 | 156 | 156 | — | — | — | — | — | — | — |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2-м предприятиям. В Таблицу № 1.2. в графу F2 () заносим значения максимального прироста прибыли на первых двух предприятиях, а в графе 
указываем соответствующий каждому значениюF2() размер инвестиций 2-ому предприятию. Таблица № 1.2.
| | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
| F2() | 0 | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
 () | 0 | 100 | 100 | 200 | 200 | 300 | 300 | 400 |
| 100 | 200 |
Далее действуем также: находим функции F3 (), F4 (), используя на каждом k-ом шаге основное рекуррентное соотношение: Fk (ξ)=max fk(xk) + Fk-1(ξ — xk)> 0 ≤ xk ≤ 700 для k= 2,3,4 Заполняем Таблицу № 2.1., аналогичным способом определяя максимальный прирост прибыли от распределения капитальных вложений между тремя предприятиями (F3 ()). Таблица № 2.1.
 -х3 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
| Х3 | F2(—x3) f3(x3) | 0 | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
| 0 | 0 | 0      | 48 | 85 | 112 | 139 | 162 | 185 | 207 |
| 100 | 85 | 85* | 133* | 170* | 197* | 224* | 247* | 270* | — |
| 200 | 100 | 100 | 148 | 185 | 212 | 239 | 262 | — | — |
| 300 | 111 | 111 | 159 | 196 | 223 | 250 | — | — | — |
| 400 | 118 | 118 | 166 | 203 | 230 | — | — | — | — |
| 500 | 124 | 124 | 172 | 209 | — | — | — | — | — |
| 600 | 129 | 129 | 177 | — | — | — | — | — | — |
| 700 | 132 | 1 32 | — | — | — | — | — | — | — |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3-м предприятиям. В Таблицу № 2.2. в графу F3 () заносим значения максимального прироста прибыли на трех предприятиях, а в графе 
указываем соответствующий функцииF3() размер инвестиций 3-ему предприятию. Таблица № 2.2.
| | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
| F3() | 0 | 85 | 133 | 170 | 197 | 224 | 247 | 270 |
 () | 0 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
В Таблице № 3.1., определяющей максимальный прирост прибыли от распределения капитальных вложений между четырьмя предприятиями F4(), заполняем только одну диагональ для значения = 700, поскольку данный этап является завершающим, предприятий всего четыре и между ними необходимо распределить именно 700 тыс. рублей. Таблица № 3.1.
 -х4 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | |
| Х4 | F(—x4) f2(x4) | 0 | 85 | 133 | 170 | 197 | 224 | 247 | 270 |
| 0 | 0 | 270 | |||||||
| 100 | 47 | 294* | — | ||||||
| 200 | 70 | 294* | — | — | |||||
| 300 | 80 | 277 | — | — | — | ||||
| 400 | 86 | 256 | — | — | — | — | |||
| 500 | 91 | 224 | — | — | — | — | — | ||
| 600 | 94 | 179 | — | — | — | — | — | — | |
| 700 | 98 | 98 | — | — | — | — | — | — | — |
Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций в размере 700 тыс. рублей 4-м предприятиям. Z max = 294 тыс. рублей, причем 4-ому предприятию должно быть выделено х4* = х4 (700) = 200 тыс. рублей ЛИБО х4** = х4 (700) = 100 тыс. рублей. На долю остальных трех предприятий остается в 1-ом случае (х4* = 200) 500 тыс. рублей, во 2-ом случае (х4** = 100) 600 тыс. рублей. Из Таблицы № 2.2. видно, что 3-ему предприятию должно быть выделено в 1-ом случае (х4* = 200): х3* = х3 (700 – х4*) = х3 (500) = 100 тыс. рублей во 2-ом случае (х4** = 100): х3** = х3 (700 – х4**) = х3 (600) = 100 тыс. рублей. Таким образом, х3* = 100 тыс. рублей. Продолжая обратный процесс, находим: в 1-ом случае (х4* = 200): х2* = х2 (700 – х4* — х3*) = х2 (400) = 200 тыс. рублей во 2-ом случае (х4** = 100): х2** = х2 (700 – х4** — х3*) = х2 (500) = 300 тыс. рублей ЛИБО х2*** = х2 (500) = 200 тыс. рублей = х2*. На долю 1-ого предприятия останется: х1* = 700 – х4* — х3* — х2* = 200 тыс. рублей х1** = 700 – х4** — х3** — х2*** = 300 тыс. рублей х1*** = 700 – х4** — х3** — х2** = 200 тыс. рублей = х1* Таким образом, одинаково оптимальными будут являться 3 варианта распределения капитальных вложений. 1-ый вариант
| х1* = 200; | Z max = 294 |
| х2* = 200; | |
| х3* = 100; | |
| х4* = 200 |
2-ой вариант
| х1* = 200; | Z max = 294 |
| х2** = 300; | |
| х3* = 100; | |
| х4** = 100 |
3-ий вариант
| х1** = 300; | Z max = 294 |
| х2* = 200; | |
| х3* = 100; | |
| х4** = 100 |
В качестве проверки правильности решения задачи можно использовать равенство: Z max = f1(x1) + f2(x2) + f3(x3) + f4(x4) 1-ый вариант: 64 + 75 + 85 + 70 = 294 тыс. рублей 2-ой вариант: 64 + 98 + 85 + 47 = 294 тыс. рублей 3-ий вариант: 87 + 75 + 85 + 47 = 294 тыс. рублей Следовательно, полученные решения верны.
Задача оптимального распределения инвестиций
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор.
Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.
| f1 | f2 | f3 | xi |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
I этап. Условная оптимизация.
1-ый шаг. k = 3.
| e 2 | u 3 | e 3 = e 2 — u 3 | f3(u 3 ) | F*3(e 3 ) | u3(e 3 ) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
2-ый шаг. k = 2.
| e 1 | u 2 | e 2 = e 1 — u 2 | f2(u 2 ) | F*2(e 1 ) | F1(u 2 ,e 1 ) | F*2(e 2 ) | u2(e 2 ) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
3-ый шаг. k = 1.
| e 0 | u 1 | e 1 = e 0 — u 1 | f1(u 1 ) | F*1(e 0 ) | F0(u 1 ,e 0 ) | F*1(e 1 ) | u1(e 1 ) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Примечание: Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 3-го шага имеем F*1(e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u*1(e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 — u 1 , e 1 = 4 — 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F*2(e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u*2(e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 — u 2 , e 2 = 4 — 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.
Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
