2. Динамическое программирование.

В динамическом программировании процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).

Для решения задачи о ранце мы будем использовать один из основных методов динамического программирования – метод рекуррентных соотношений. Он основан на использовании принципа оптимальности Беллмана, который состоит в том, что, каковы бы ни были начальное состояние на любом шаге и оптимальное управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придёт система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.

Для решения задачи о ранце введём следующие обозначения:

- эффект от реализации i – го мероприятия;

- финансирование, необходимое для реализации i – го мероприятия.

У нас =320, =360, =125, =90; =80, =120, =50, =60.

Разобьём решение задачи на 4 шага, по количеству мероприятий, которые можно реализовать.

Рекуррентные соотношения будут иметь вид:

Если максимум достигается на , то =1; иначе =0.

Если максимум достигается на , то =0, иначе =1.

Согласно рекуррентным соотношениям:

1 – й шаг.

Запишем результаты вычислений в табл. 1.4 – 1.7.

Таблица 1.4.
R	0 - 79	80 – 310
	0	320
	0	1

2 – й шаг.

Таблица 1.5
R	0 - 79	80 – 119	120 - 199	200 – 310
	0	320	360	680
	0	0	1	1

3 – й шаг.

Таблица 1.6
R	0 – 49	50 – 79	80 - 119	120 – 129	130 - 169	170 - 199	200 - 249	250 - 310
	0	125	320	360	445	485	680	805
	0	1	0	0	1	1	0	1

4 – й шаг.

Таблица 1.7
R	0 – 49	50 – 79	80 – 119	120 – 129	130 – 169	170 – 189	190 – 199	200 – 249	250 – 309	310
	0	125	320	360	445	485	535	680	805	895
	0	0	0	0	0	0	0	0	0	1

Таким образом, на 4 – м шаге мы получили табл. 1.7, аналогичную табл. 1.3, по которой мы уже построили график точной зависимости «затраты - эффект», представленный на рис. 1.3.

Если нам нужно восстановить набор мероприятий, которые следует реализовать, например, при финансировании 150 единиц, то:

1. По табл. 1.7, полученной на 4 – м шаге, получаем: , максимум достигался на ;

2. По табл. 1.6, полученной на 3 – м шаге: , максимум достигался на ;

3. По табл. 1.5, полученной на 2 – м шаге: , максимум достигался на ;

4. По табл. 1.4, полученной на первом шаге: .

Таким образом, при объёме финансирования 150 единиц оптимальным решением является реализация первого и третьего мероприятий.

Имея зависимость «затраты-эффект», можно решать и задачи привлечения дополнительных финансовых ресурсов, в частности, взятия кредита.

Пример. Пусть имеется 170 единиц ресурса, а кредит можно взять по ставке 200% (то есть отдавать придётся 300% от взятой в кредит суммы). Какой величины кредит взять, чтобы получить максимальный финансовый результат?

Из графика на рис. 1.3 видно, что рассмотреть следует 4 варианта – взять кредит в 20, 30, 80 или 140 единиц. При взятии кредита в 20 единиц дополнительный эффект (с учётом возврата суммы кредита) составит 535 - 485 – 20 = 30 единиц, то есть эффективность равна 150%, что ниже, чем процентная ставка кредита. Это значит, что брать кредит нецелесообразно. Если взять кредит в размере 30 единиц, то дополнительный эффект составит 680 - 485 – 30 = 165 единиц, что дает эффективность 550%, что больше ставки кредита. При кредите в 80 единиц дополнительный эффект составит 805 - 485 – 80 = 240 единиц, что дает эффективность 300%, то есть больше, чем ставка кредита. Наконец, при кредите в 140 единиц дополнительный эффект составит 895 - 485 – 140 = 270 единиц, что дает эффективность 192,86%, то есть ниже ставки кредита. Таким образом, остаётся два целесообразных варианта взятия кредита: в 30 и 80 единиц. При этом за вычетом процентов за кредит получим эффект в 165 - 230 = 105 и 240 - 280 = 80 единиц соответственно. Поэтому оптимальная величина кредита равна 30 единицам.

Зависимость «затраты-эффект» характеризует потенциал отрасли по соответствующему критерию. Зная эту зависимость, можно определить минимальный уровень финансирования, достаточный для достижения поставленных целей. И, наоборот, при ограниченных финансах определяется максимальный уровень, который можно достичь по данному критерию. Так, например, если поставлена цель обеспечить по данному критерию эффект в 650 единиц, то при заданном множестве мероприятий для этого потребуется не менее 200 единиц финансовых ресурсов (из графика видно, что эффект составит 680 единиц, но при уменьшении финансирования он сразу падает до 535, то есть поставленная цель не достигается). Если же имеется всего 100 единиц финансовых ресурсов, то максимальный уровень эффекта, который можно достичь, составит 320 единиц (причем достаточно для достижения цели всего 80 единиц ресурса).