Общая схема применения метода ДП. Задача об оптимальном распределении ресурсов между отраслями на n лет

Прежде чем перейти к конкретным задачам, следует усвоить общую схему применения метода ДП.

Предположим, что все требования, предъявляемые к задаче методом ДП, выполнены (требования сформулированы в параграфе 11.1). Построение модели ДП и применение метода ДП для решения сводится к следующим моментам.

• 1. Выбирают способ деления процесса управления на шаги.
• 2. Определяют параметры состояния sk и переменные управления Хк на каждом шаге.
• 3. Записывают уравнения состояний.
• 4. Вводят целевые функции ?-го шага и суммарную целевую функцию.
• 5. Вводят в рассмотрение условные максимумы (минимумы) Zl (?_[) и условное оптимальное управление на ?-м шаге: = n, п-1,…, 2,1.
• 6. Записывают основные для вычислительной схемы ДП уравнения Веллмана для Z'(sn_,) и Z'k (?_,), ?= ?-1,…, 1.
• 7. Решают последовательно уравнения Веллмана (условная оптимизация) и получают две последовательности функций:

• 8. После выполнения условной оптимизации получают оптимальное решение для конкретного начального состояния s0:
  • а) ;
  • б) по цепочке

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

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

11.2. Планируется деятельность двух отраслей производства на п лет. Начальные ресурсы л0. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль /^ (х) и возвращаются в размере q{ (х) < х; аналогично для II отрасли функция прибыли равна /2 (.г), а возврата — q2 (х) {q2 (а:) < х). В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается^[1].

Требуется распределить имеющиеся средства s0 между двумя отраслями производства на п лет так, чтобы суммарная прибыль от обеих отраслей за п лет оказалась максимальной.

Необходимо:

• а) построить модель ДП для задачи и вычислительную схему;
• б) решить задачу при условии, что

Кешенис. а} процесс распределения средств между двумя отраслями производства разворачивается во времени, решения принимаются в начале каждого года, следовательно, осуществляется деление на шаги: номер шага — номер года. Управляемая система — две отрасли производства, а управление состоит в выделении средств каждой отрасли в очередном году. Параметры состояния к началу &-го года — sk ^ (k = 1, 2,…, и) - количество средств, подлежащих распределению. Переменных управления на каждом шаге две: хк - количество средств, выделенных I отрасли, и ук- II отрасли. Но так как все средства sA, распределяются, то У к =sk-1 ~хк > и поэтому управление на ?-м шаге зависит от одной переменной хп, т. е.

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

(11.13).

выражают остаток средств, возвращенных в конце k-ro года.

Показатель эффективности k-ro шага — прибыль, полученная в конце ?-ro года от обеих отраслей:

(11.14).

Суммарный показатель эффективности — целевая функция задачи — прибыль за ? лет:

(11.15).

Пусть  — условная оптимальная прибыль за.

? — к +1 лет, начиная с k-ro года до «-го года включительно при условии, что имеющиеся на начало к-то года средства sk j в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за ? лет

Уравнения Веллмана имеют вид:

(11.16).

(11.17).

б) Используем конкретные данные.

Уравнение состояний (11.13) примет вид.

(11.18).

Целевая функция ?-го шага (11.14).

Целевая функция задачи.

(11.19).

Функциональные уравнения.

(11.20).

(11.21).

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

Рис. 11.5.

IV шаг. Используем уравнение (11.20). Обозначим через Z4 функцию, стоящую в скобках, Z4 = = 0,1;с4 + 0,5s3; функция Z4 — линейная, возрастающая, так как угловой коэффициент 0,1 больше нуля. Поэтому максимум достигается на конце интервала (рис. 11.5).

Следовательно, при

III шаг. Уравнение.

Найдем s3 из уравнений состояний (11.18): s3 =0,8s2- -О, l. r:5 и, подставив его выражение в правую часть уравнения, получим.

Как и в предыдущем случае, максимум достигается при , т. е. при

II шаг. Из уравнения состояния: . Поэтому уравнение (11.20) при k = 2 примет вид.

Линейная относительно х2 функция Z2 = 1,316л'! -0,002×2 убывает на отрезке [О; .у, ] и поэтому ее максимум достигается при х2 = 0 (рис. 11.6):

I шаг. . Уравнение (11.20) при k = 1 имеет вид.

Как и в предыдущем случае, максимум достигается в начале отрезка, т. е.

На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получим: ,.

или ,

Рис. 11.6.

(все средства выделяются II отрасли) >

(все средства выделяются II отрасли) >

(все средства выделяются I отрасли) ->

(все средства выделяются I отрасли).

Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 10 000 ед., равна 15 528 ед. при условии, что I отрасль получает по годам (0; 0; 6400; 4480), а II отрасль — соответственно (10 000; 8000; 0; 0). >

• [1] Последние условия определяют вид уравнений состояний; если поступают новые средства или часть прибыли вкладывается в производство, это можно легко учесть, так как алгоритм метода ДП не изменяется.