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

ресурсов между отраслями на п лет

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

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

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

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

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

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

Решая зад_ач1^^Ьное управление: Х*(х'_х, Х\,..., Х'„). схемы по крэд ' ^с^еду_{ет П}о возможности придерживаться этой работает схе|ц_а ^^ Мере в начале изучения темы. Рассмотрим, как ресурсов мех^у примере задачи об оптимальном распределении > 12.2.Планиру_е ^уМя отраслями на п лет.

лет. Начальн^_1е деятельность двух отраслей производства на п начале года, д_а Урсы s_Q. Средства х, вложенные в I отрасль в размере q_x(x)^ ^fi конце года прибыль/](jc) и возвращаются в равна fi(x), а _Во^_в Логично для II отрасли функция прибыли щенные ^сР^еДства з ^а ~" ^q2^ ^2(^x)^<x)- В конце года все возвра-лями, новые _Ср ^аНово перераспределяются между I и II отрас-вкладывается! ^т&а _Не поступают, прибыль в производство не

Требуется _р отраслями пр_0Изв ^Делить имеющиеся средства s₀ между двумя от обеих отра_Сле^ ^ства на п лет так, чтобы суммарная прибыль

Необходим ^{а п} лет оказалась максимальной.

а) построить"

б) решить _3а!^ДеЛьДП для задачи и вычислительную схему;
Л(х) - 0,6х, q^ ^Ну _При у_{СЛ0ВИИ; что Sq} = ЮООО ед., п = 4,

" °>⁷*> fr{x) = 0,5х, д₂(х) = 0,8*.

Глава 12

Модели динамического программирования

Решение, а) Процесс распределения средств между двумя отраслями производства разворачивается во времени, решения принимаются в начале каждого года, следовательно, осуществля­ется деление на шаги: номер шага — номер года. Управляемая система — две отрасли производства, а управление состоит в вы­делении средств каждой отрасли в очередном году. Параметры состояния к началу к-го года — s/c-i (к=1, 2,..., п) — количество средств, подлежащих распределению. Переменных управления на каждом шаге две: х_к — количество средств, выделенных I отрасли, и у/с — II отрасли. Но так как все средства s^-i распределяются, то y/c^=sk-\~^xk, ^и поэтому управление на к-м шаге зависит от одной переменной х_п, т.е. Х_к(х_к, ty-i^-х*).

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

■**=fl(**)⁺0ifot-i-**) (12.13)

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

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

/i(**)+/2fobi-**)- (12.14)

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

и

2 = ^Мх_к)Ш*к-\-х_к)- (12.15)

к=\

Пусть Z_k(sj_c-\) — условная оптимальная прибыль за п—к+1 лет, начиная с к-го года до л-го года включительно, при условии, что имеющиеся на начало к-го года средства s^-i в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за п лет

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

)= max Mx„)+f₂(s„-_l-x„)}, (12.16)

Q<X_k<,S_k_\

Z\Uk-\) = _n ^max \f\(x_k)+f₂{Sk-\-x_k)+Z*_k+l(s_k)}, (12.17)

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

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

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

s_k=0,7x_k+0,8(Sk-\-Xk), или s_k=Q,Ss_k-i-0,\x_k. (12.18)

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

0,6х*+0,5(^_1-х*)=0,1-^+0,5^-1. Целевая функция задачи

Z= 20Ду_л_, + 0Дх_л. (12.19)

к=\

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

Zl(s₃)= max {0,5^3+0,1x4}, (12.20)

0<JC₄<5₃

и^(У= max {0,1^+0,5^1+ ^*₊i fot)b (12.21)Проводим условную оптимизацию.

Д j IV ш а г. Используем уравнение

(12.20). Обозначим через Z₄ функцию,
стоящую в скобках, Zi, — 0,1x4+0,553;
ОДуз^.—■—I функция Z$ — линейная, возрастаю-

щая, так как угловой коэффициент 0,1 больше нуля. Поэтому максимум дос­тигается на конце интервала [0; 5з] *" (рис. 12.5). Следовательно, Zl{s^)=Q,bsi

Рис. 12.5" ^ПР^{И х}\ (Ъ)⁼*з-

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

ZUs₂)= max {0,1х₃+0,55₂+0,б5з}.

Найдем 5з из уравнений состояний (12.18): 5з = 0,852-0,1х₃ и, подставив его выражение в правую часть уравнения, получим

ZUs₂) = max {0,lx₃+0,55₂+0,6(0,85₂-0,lx₃)},

¹ d<x₂<s₂

ZUs₂)= max {0,04x₃+0,985₂}.

0<x₃<j₂

²⁶⁴

--------------------- „___________ .____________________ Глава 12

Как и в предыдущем случае, максимум достигается при x₃=sy т.е. Z] (s₂) = 1,02*2 при х] (s₁)=s₂.

II ш а г. Из уравнения состояния: ^2=0,8*! -0,1*2. Поэтому уравнение (12.20) при к=2 примет вид:

Z'₂(si)= max {1,316*!-0,002x2}.

Линейная относительно х₂ функция
Ц ^Z2 ⁼ 1,316^-0,002x2 убывает на отрезке

—^ ■---------- '---- ► [0; s\], и поэтому ее максимум достигает-

х, сяприх₂=0 (рис. 12.6):

^РиС' ¹²-⁶ А (л)=1,316*, при х* (j,)=0.

I шаг. Ji=0,8jo-0,1x,. Уравнение (12.20) при А=1 имеет ввд: ' Z[{s₀)= max {1,55285b—0,0316xi}.

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

Z\ (s₀) = 1,55285₀ при x,*(j₀)=0. На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получим 2^ = Z,*(10000),

■^пах ⁼ 15528.

^х\ = 0, у\ = s₀ = 10000 (все средства выделяются II отрасли) -»

si =0,8-10000-0,1-0=8000 => х₂ =0, у\ =^,=8000 (все средства выделяются II отрасли) -»

-► *2=0,8-8000-0-,1.0=6400 => х\ =6400, _л*=0-> (все средства выделяются I отрасли) ->

-> ^=0,8-6400-0,1-6400=4480^ х;=4480, ^=0 (все средства выделяются I отрасли).

Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 10000 ед., равна 15528 ед.

Модели динамического программирования

при условии, что I отрасль получает по годам (0; 0; 6400; 4480), а II отрасль — соответственно (10000; 8000; 0; 0)>