Использование метода динамического программирования для решения экономических задач

Решение.

Пусть п = 1. В соответствии с формулой (1.7) в зависимости от начальной суммы c получаем с учетом таблицей 2.17 значения f1(c), помещенные в таблицу 2.18.

Таблица 2.18

Предположим теперь, что средства вкладываются в два предприятия. Тогда в соответствии с формулой (1.9)

f2(с) = (g2(x) + f1(c – x))

Очередная задача – найти значения функции f2(с) для всех допустимых комбинаций c и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.19.

Для каждого значения (20, 40, 60) начальной суммы c распределяемых средств в таблице 2.19 предусмотрена отдельная строка, а для каждого возможного значения x (0, 20, 40, 60) распределяемой суммы – столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям c и x. Такой, например, будет клетка, отвечающая строке c = 20 и столбцу x = 40, ибо при наличии 20 тыс. ден. ед. естественно отпадает вариант, при котором одному из предприятий выделяется 40 тыс. ден. ед.

Таблица 2.19

В каждую клетку таблицы будем вписывать значение суммы g2(x) + f1(c x). Первое слагаемое берем из условий задачи (см. табл. 2.17), второе – из таблицы 2.18. Так, например, при распределении начальной суммы с = 60 тыс. ден. ед. одним из вариантов может быть следующий: второму предприятию выделяется 40 тыс. ден. ед. (х = 40), тогда первому 60 – 40 = 20 тыс. ден. ед. При таком распределении первоначальной суммы на втором предприятий будет обеспечен прирост продукции на сумму в 19 тыс. ден. ед. (см. табл. 2.17), на первом – 9 тыс. ден. ед. (см. табл. 2.18).

Общий прирост составит (19 + 9) тыс. ден. ед., что и записано в соответствующей клетке таблицы 2.19. В двух последних столбцах таблицы проставлены максимальный по строке прирост продукции (в столбце f2(c)) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце x2*(c)). Так, при начальной сумме с = 40 тыс. ден. ед. максимальный прирост выпуска продукции составляет 20 тыс. ден. ед. (11 + 9), и это достигается выделением второму предприятию 20, а первому – 20 – 20 = 0 тыс. ден. ед.

Расчет значений f3(c) приведен в таблице 2.20. Здесь использована формула, получающаяся из (1.9) при п = 3 :

f3(с) = (g3(x) + f2(c – x))

Первое слагаемое в таблице 2.20 взято из табл. 2.17, второе – из табл. 2.19.

Таблица 2.20

Аналогичным образом находятся значения f4(c).

Таблица 2.21

Полученные результаты можно сравнить с теми, которые приведены в сводной таблице (табл. 2.22, см. последние два столбца), составленной на основе расчетных таблиц, начиная с табл. 2.17.

Таблица 2.22

 Скачать реферат