Общая схема применения метода динамического программирования

Задача об оптимальном распределении ресурсов на n лет.

Построение модели динамического программирования и применения метода динамического программирования для решения сводится к следующему:

1) выбирается способ деления процесса управления на шаги.

2) Определяют параметры состояния и переменные управления на каждом шаге.

3) Записывают уравнение состояния.

4) Вводят целевые функции k шага и суммарную целевую функцию.

5) Вводят в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k шаге , k=n,n-1,…,1

6) Записывают основные уравнения Беллмана для и , k=n,n-1,…,1

7) Решают уравнение Беллмана и получают 2 последовательности функций.

и

8) Получают оптимальное решение для конкретного начального состояния .

А)

Б) по цепочке оптимальное управление вектор .

Задача: Планируется деятельность 2 отраслей производства на n лет. Начальные ресурсы . Средства х – вложенные в первую отрасль в начале года дают в конце года прибыль и возвращаются в размере . Аналогично для второй отрасли функция прибыли равна , а возврата . В конце года все возвращенные средства заново перераспределяются между 1 и 2 отраслями. Новые средства не поступают. Прибыль в производство не вкладывается. Требуется распределить имеющиеся средства между двумя отраслями на n лет так, чтобы суммарная прибыль от обеих отраслей за n лет оказалась максимальной.

Необходимо: а) построить модель динамического программирования для задачи и вычислить схему.

б) решить задачу при условии =10000 ед., n=4, =0.6x, =0.7x, =0.5x, =0.8x.

Решение:

параметр состояния к началу k года.

-количество средств, выделенных для первой отрасли.

- количество средств, выделенных для второй отрасли.

Уравнение состояния

Прибыль, получаемая в конце года k от двух отраслей

Целевая функция прибыли за n лет имеет вид

- условная оптимальная прибыль за n лет

Уравнение Беллмана имеет вид

Целевая функция k шага

Запишем функциональные уравнения Беллмана

4 шаг.

Проведем условную оптимизацию

Максимум достигается при = на диапазоне [0, ]

3 шаг.

Записываем уравнение Беллмана.

Уравнение состояния

при

1 шаг.

уравнение состояния

при

1 шаг.

Уравнение состояния

Рекуррентное соотношение Беллмана

при

Необходимо еще построить цепь х и найти значение х и у.

Ответ: при начальных средствах 10000 мы можем получить 15528 единиц при условии, что первая отрасль получает по годам