§8. Динамическое программирование. Распределение капитальных вложений
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Знакомство с методом динамического программирования проще всего начать с рассмотрения нелинейной задачи распределения ресурсов между предприятиями одного производственного объединения или отрасли. Для определенности можно считать, что речь идет о распределении капитальных вложений.
Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2, ... , xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли z = f1(x1) + f2(х2) + ... + fn(xn) при ограничении по общей сумме капитальных вложений x1 + x2 + ... + xn = b причем будем считать, что все переменные xj принимают только целые неотрицательные значения xj = 0, или 1, или 2, или 3, ... Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых k предприятиях, если они вместе получают рублей. Параметр может изменяться от 0 до b. Если из рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные - xk рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль Fk-1( - xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1( - xk). Надо выбрать такое значение xk между 0 и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению Fk()=max{fk(xk) + Fk-1(-xk)} 0 xk
для k = 2, 3, 4, ... , n . Если же k=1, то F1() = f1() .
Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.
Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 700. Наибольшее число на этой диагонали: Zmax = 155 тыс. руб.,
причем четвертому предприятию должно быть выделено х*4 = 4 (700) = 300 тыс. руб.
На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено x*3 = 3 (700-x*4) = 3 (400) = 200 тыс. руб.
Продолжая обратный процесс, находим x*2 = 2 (700 - x*4 - x*3) = 2 (200) = 100 тыс. руб.
На долю первого предприятия остается x*1 = 700 - x*4 - x*3 - x*2 = 100 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
x*1 =100; x*2 =100; x*3 = 200; x*4 = 300.
Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 155 тыс. руб.
Студенту рекомендуется проверить выполнение равенства f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max
Таблица 2
| - x2 | 0 100 200 300 400 500 600 700 |
x2 | F1( - x2) f2(x2) | 0 20 34 46 53 55 60 60 |
0 | 0 | 0 20* 34 46 53 55 60 60 |
100 | 18 | 18 38* 52* 64 71 73 78 |
200 | 29 | 29 49 63 75 82 84 |
300 | 45 | 45 65* 79 91 98 |
400 | 62 | 62 82* 96 108 |
500 | 78 | 78 98* 112* |
600 | 90 | 90 110 |
700 | 98 | 98 . |
Таблица 3
| 0 100 200 300 400 500 600 700 |
F2() | 0 20 38 52 65 82 98 112 |
() | 0 0 100 100 300 400 500 500 |
Таблица 4
| - x3 | 0 100 200 300 400 500 600 700 |
x3 | F2( - x3) f3(x3) | 0 20 38 52 65 82 98 112 |
0 | 0 | 0 20 38 52 65 82 98 112 |
100 | 25 | 25* 45* 63* 77 90 107 123 |
200 | 41 | 41 61 79* 93 106 123 |
300 | 52 | 52 72 94* 112 126 |
400 | 74 | 74 94* 112* 126* |
500 | 82 | 82 102 120 |
600 | 88 | 88 106 |
700 | 90 | 90 . |
Таблица 5
| 0 100 200 300 400 500 600 700 |
F3() | 0 25 45 63 79 94 112 126 |
() | 0 100 100 100 200 400 400 400 |
Таблица 6
- x4 | 0 100 200 300 400 500 600 700 | |
x4 | F3( - x4) f4(x4) | 0 25 45 63 79 94 112 126 |
0 | 0 | 126 |
100 | 30 | 142 |
200 | 52 | 146 |
300 | 76 | 155* |
400 | 90 | 153 |
500 | 104 | 149 |
600 | 116 | 141 |
700 | 125 | 125 . |
- §1. Цели и задачи курсового проекта
- §2. Задание на курсовОй ПрОект
- §3. Организация выполнения курсовоГо ПрОекта
- §4. Линейная производственная задача
- §5. Двойственная задача
- §6. Задача о "расшивке узких мест производства"
- §7. Транспортная задача линейного программирования
- §8. Динамическое программирование. Распределение капитальных вложений
- §9. Динамическая задача управления производством и 24запасами
- §10. Матричная модель производственной программы предприятия.
- §11. Матричная игра как модель конкуренции и сотрудничества.
- §12. Анализ доходности и риска финансовых операций.
- §13. Задача формирования оптимального портфеля ценных бумаг.
- §14. Принятие решений в условиях неопределенности.
- §15. Математико-статистический анализ данных