Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата

Распределение капитальных вложений

Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с 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 тыс. руб.

Таблица I

[pic]

Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями
F1(( - x2) = f1((- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение [pic]. Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3((), [pic](() и т.д. В табл.
6 заполняем только одну диагональ для значения (= 700. Наибольшее число на этой диагонали:

Zmax = 155 тыс. руб., причем четвертому предприятию должно быть выделено х*4 = [pic]4 (700) = 300 тыс. руб.
На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено x*3 = [pic]3 (700-x*4) = [pic]3 (400) = 200 тыс. руб.
Продолжая обратный процесс, находим x*2 = [pic]2 (700 - x*4 - x*3) = [pic]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) | 0 20 34 46 53 55 |
| |f2(x2) |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 |
|([pic](() | 0 0 100 100 300 400 500|
| |500 |

Таблица 4
| |( - x3 | 0 100 200 300 400 500 600 |
| | |700 |
|x3 |F2(( - x3) | 0 20 38 52 65 82 |
| |f3(x3) |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 |
| | |. |

Рекомендуем скачать другие рефераты по теме: гигиена реферат, информация реферат.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата