Решение. 1. Номер шага совпадает с номером предприятия.

1. Номер шага совпадает с номером предприятия.

2. Введём обозначения: − остаток средств после -ого шага, конечное состояние системы , так как все наличные средства должны быть распределены; − количество средств, выделяемых -ому предприятию (, , ).

3. Уравнения состояний имеют вид: .

4. Функция прибыли -ого шага: , суммарная функция прибыли задачи имеет вид: .

5. Уравнения Беллмана.

· Для последнего 4-ого шага: ;

· для 3-его шага: ;

· для 2-ого шага: ;

· для 1-ого шага: .

6. Последовательно решим уравнения Беллмана. Решение проведем в таблице 2.

7. Рассмотрим 4-й шаг. В таблице 1 прибыль монотонно возрастает, поэтому все средства, оставшиеся к 4-ому шагу, вкладываем в 4-ое предприятие. При этом для возможных средств получим:

и

3-й шаг. Делаются предположения для всех возможных остатков средств на начало 3-его шага. Для каждого варианта перебираются , находятся и сравниваются при фиксированном и разных значения сумм . Для каждого наибольшее из этих значений есть − условная оптимальная прибыль. Оптимизация дана в таблице 2 при . Для каждого значения и помещены в графах 8 и 9 соответственно.

2-й шаг. Делаются предположения для всех возможных значений значения и помещены в графах 11и 12 соответственно. Первые слагаемые в столбце 10 − значения , взяты из таблицы 1, а вторые из столбца 8 таблицы 2 при .

1-й шаг. Делаются предположения для всех возможных значения и помещены в графах 14 и 15 соответственно. Первые слагаемые в столбце 13 − значения , взяты из таблицы 1, а вторые из столбца 11 таблицы 2 при .

В столбце 14 выберем максимальное значение : получим достигается при (см. соответствующее значение в столбце 15).

Далее найдем остаток средств после вложений в первое предприятие: По таблице 2, на пересечении столбца 12 и строки =4 находим оптимальное управление для на втором шаге − это или .

Далее найдем остаток средств после вложений во второе предприятие:

Для первого варианта

По таблице 2, на пересечении столбца 12 и строки находим оптимальное управление для (на третьем шаге − это ). Переходим к четвертому шагу

По таблице 2, на пересечении столбца 6 и строки находим оптимальное управление для на последнем шаге − это .

Таким образом, оптимальное управление имеет вид

.

Для второго варианта По таблице 2, на пересечении столбца 12 и строки находим оптимальное управление для на третьем шаге − это . Переходим к четвертому шагу По таблице 2, на пересечении столбца 6 и строки находим оптимальное управление для на последнем шаге − это .

Оптимальное управление .

Ответ: Максимум суммарной прибыли равен усл. ед. средств, при условии, что средства вкладываются в предприятия в соответствии с одним из следующих вариантов: первый вариант − во второе предприятие вложено 1 усл. ед., в четвертое предприятие − 3 усл. ед., в первое и четвертое предприятия средства не вкладываются; второй вариант − во второе предприятие вложено 3 усл. ед., в четвертое предприятие − 1 усл. ед., в первое и четвертое предприятия средства не вкладываются.

Замечание. 1. Альтернативой методу ДП для подобной дискретной задачи является метод перебора. Метод ДП предпочтительнее, так как на этапе условной оптимизации отбрасываются заведомо невыгодные варианты.

Замечание. 2. Достоинством метода является возможность анализа решения на чувствительность к изменению начального состояния и числа шагов . Если произошло уменьшение начальных средств, то достаточно из таблицы убрать соответствующие строки, и снова выписать оптимальное управление, и, наоборот, если начальные средства увеличились, а функции прибыли остались прежними, то достаточно добавить в таблицу раздел для . Наконец, если увеличилось число предприятий (число шагов), то таблицу можно дополнить, присоединяя шаги .

Таблица 2

0+6=6 4+0=4

0+6=6 6+0=6

0+6=6 4+0=4

0+10=10 4+6=10 7+0=7

0+10=10 6+6=12 8+0=8

0+12=12 4+6=10 6+0=6

0+16=16 4+10=14 7+6=13 10+0=10

0+16=16 6+10=16 8+6 =14 16+0=14

0+16=16 4+12=16 6+6=12 12+0=12

0+20=20 4+16=20 7+10=17 10+6=16 16+0=16

0+20=20 6+16=22 8+10=18 16+6=22 20+0=20

0+22=22 4+16=20 6+12=18 12+6=18 18+0=18