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

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

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

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

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

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

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

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

6. Записывают основные для вычислительной схемы ДП уравнения Беллмана для и , k=n-l, ..., 1.

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

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

а) Zmax= и

б) по цепочке s0=gt; ?=gt; ? =gt; ...

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

Задача 1. Планируется деятельность двух отраслей производства на п лет. Начальные ресурсы s0. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль f1(x) и возвращаются в размере q1(x)lt;x; аналогично для II отрасли функция прибыли равна f2(x), а возврата – q2(x) (q2(x)lt;x). В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается. (Последние условия определяют вид уравнений состояний; если поступают новые средства или часть прибыли вкладывается в производство, это можно легко учесть, так как алгоритм метода ДП не изменяется).

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

Необходимо:

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

б) решить задачу при условии, что s0=100 ед., п=3, f1(x)=2х, q1(x)=0,8x, f2(x)=5x, q2(x)=0,3x.

¦ а) Процесс распределения средств между двумя отраслями производства разворачивается во времени, решения принимаются в начале каждого года, следовательно, осуществляется деление на шаги: номер шага – номер года. Управляемая система – две отрасли производства, а управление состоит в выделении средств каждой отрасли в очередном году.

sk=q1(хk)+q2(sk-1-xk)                                                   (10)

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

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

f1(xk)+f2(sk-1-xk).                                                         (11)

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

Z=(f1(xk)+f2(sk-1-xk)).                                          (12)

Пусть – условная оптимальная прибыль за n-k+1 лет, начиная с k-го года до п-го года включительно, при условии, что имеющиеся на начало k-го года средства sk-1 в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за п лет Zmax=.

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

=?f1(хп)+f2(sп-1-xп)?,                              (13)

=?f1(хk)+f2(sk-1-xk)+?,                  (14)

(k=n-l, n-2,..., 2).

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

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

sk=0,8хk+0,3(sk-1-xk) или sk=0,3sk-1+0,5хk.                 (15)

Целевая функция k-го шага (11) 2xk+5(sk-1-xk)=-3xk+5sk-1.

Z=(5sk-1-3xk).                                                       (16)

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

=?5s2-3x3)?,                                               (17)

=?-3хk+5sk-1+?.                              (18)

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

	III шаг. Используем уравнение (17). Обозначим через Z3 функцию, стоящую в скобках,Z3=-3х3+5s2; функция Z3 – линейная, убывающая, так как угловой коэффициент -3 меньше нуля. Поэтому максимум достигается в начале интервала [0; s2] (рис. 4). Следовательно, =5s2 при (s2)=0. II шаг. Уравнение:
Рис. 4

=?-3х2+5s1+5s2?.

Найдем s2 из уравнений состояний (15): s2=0,3s1+0,5х2 и, подставив его выражение в правую часть уравнения, получим

=?-3х2+5s1+5(0,3s1+0,5х2)?, =?-0,5х2+6,5s1?.

Как и в предыдущем случае, максимум достигается при х2=0; т.е. =6,5s1 при (s1)=0.

I шаг. Из уравнения состояния: s1=0,3s0+0,5х1. Поэтому уравнение (18) при k=1 примет вид:

	=?-3s0+5х1+6,5s1?=?-3s0+5х1+ +6,5(0,3s0+0,5х1)?=?-1,05s0+8,25х1?. Линейная относительно х2 функция Z1=-1,05s0+8,25х2 возрастает на отрезке [0; s0], и поэтому ее максимум достигается при х1=s0 (рис.
Рис. 5

5): =7,2s0 при (s0)=s0.На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получим Zmax=, Zmax=720.

=s0=100, =0 (все средства выделяются I отрасли) >

=0,3·100+0,5·100=80 =gt; =0, =s1=80 (все средства выделяются II отрасли) >=0,3·80+0,5·0=24 =gt; =0, =24 > (все средства выделяются II отрасли).

Оптимальная прибыль за 3 года, полученная от двух отраслей производства при начальных средствах 100 ед., равна 720 ед. при условии, что I отрасль получает по годам (100; 0; 0), а II отрасль ? соответственно (0; 80; 24).                                                                               ?