Реферат Визначення капітальних вкладень

op>

134

122

250

158

165

152

160

148

300

195

20

180

185

190

3. Метод динамічного програмування

Ідея методу динамічного програмування полягає в тому, що виділена сума Х розподіляється не між усіма М підприємствами (інакше виходить повний перебір), а між двома "підприємствами": останнім підприємством (що має номер М ) і групою з ( М -1) - го попереднього підприємства, для якого оптимальний розподіл між ними будь часткової суми вже відомо. Це відповідає рішенню основного функціонального рівняння динамічного програмування М -го, останнього кроку

(3)

Тут f M ( X) - максимальний сумарний приріст продукції, одержуваний від М підприємств при оптимальному розподілі суми Х між M -тим і групою з ( М -1) - го перших підприємств, за умови, що виділяється їм часткова сума ( Х-Х М ) розподіляється оптимально;

f M -1 ( X-Х М ) - максимальний сумарний приріст продукції, одержуваний від ( М -1) - го перших підприємств при оптимальному розподіл між ними часткової суми ( Х-Х М ), залишилася, від М-го підприємства.

Вирішити рівняння (3) неможливо, оскільки функція f M -1 ( X-Х М ) невідома. Однак її можна виразити за допомогою основного функціонального рівняння для (М-1) - го кроку через функцію максимального сумарного приросту продукції, одержуваного при оптимальному розподілі часткових сум у групі з (М-2) - х перших підприємств

(4)

Знову невідома функція f M -2 ( nh-Х М-1 ) однак, використовуючи основне f M -3 ( nh-Х М-2 ) функціональне рівняння , її можна визначити аналогічно через функцію і т.д. Ця процедура рекурентних підстановок невідомих функцій максимального сумарного приросту продукції закінчується точно через М кроків. Дійсно, на останньому кроці підстановок (його номер m = 1) отримуємо основне функціональне рівняння динамічного програмування у вигляді

(5)

Функція f 0 ( nh-Х 1 ) формально є максимальний приріст продукції при оптимальному розподілі часткової суми ( nh-Х 1 ) в групі, що з "0" підприємств. Природно, такий групі, в якій немає жодного підприємства, ніяких коштів не виділяється тому

f 0 (nh-Х 1 ) = 0 (6)

Звідси випливає, що на першому кроці основне функціональне рівняння має наступне рішення:

(7)

Це означає, що на першому кроці, коли розглядається тільки одне перше підприємство, будь-яка часткова сума nh виділяється йому цілком, так як її нікому, крім нього, розподіляти. Таким чином, оптимальне управління на першій кроці

X 1 * (nh) = nh (8)

Уявімо знайдене рішення основного функціонального рівняння на першому кроці у вигляді табл.2.

Таблиця 2 - Визначення оптимальних управлінь і максимальних приріс продукції на першому кроці

Часткова розподіляється сума

Сума, що виділяється першому підприємству

Оптимальне управління

Максимальний приріст продукції

0

50

100

150

200

250

300

0

0

0

0

50

30

50