16.5.2. Задача об оптимальном распределении денежных средств между предприятиями.

Задача 4. Группе из п предприятий П1, П2, .... ,Пп выделяются дополнительные средства на реконструкцию и модернизацию производства. Известна матрица f, в которой на позиции (i, k) находится величина fik, fik?0, равная приросту выпуска продукции на предприятии Пk, при выделении ему дополнительных средств в размере i ден.

¦ Данную систему также представим как двухпараметрическую: текущее состояние системы определим двумя параметрами i и k, которые показывают, что между первыми k предприятиями П1, П2, .... ,Пk уже распределена сумма в i ден. ед. Поэтому состояния данной системы будем обозначать через sik. Множество ?(sik) состоит из локальных управлений «выделить r ден. ед. предприятию Пk+1» r=0, 1, ..., m-i. Этим управлениям соответствуют приросты выпуска продукции fr,k+1, r=0, 1, ..., m-i. Кроме того, управление «выделить r ден.ед. предприятию Пk+1» переводит систему из состояния sik в состояние si+r,k+1. Множество конечных состояний есть s0n, s1n, …, sтn.

Рассмотрим данную задачу при следующих исходных данных:

                                                 П1  П2  П3

f=, п=3, т=2.

Используя вышеописанную графовую интерпретацию обшей задачи динамического программирования, построим орграф G, изображенный па рис. 8, чей путь максимальной длины, соединяющий вершину s00 с одной из конечных вершин, будет определять оптимальное распределение денежных средств между тремя предприятиями.

Определим теперь путь максимальной длины из s00 в одну из конечных вершин, используя прин-цип оптимальности Беллмана (при этом для каждой вершины sik «запоминается» ближайшая вершина potik, указывающая направление оптимального пути из sik): Z23=Z13=Z03=0, Z22=3, pot22=s23, Z12=mах{14+Z23, 3+Z13}=14, pot12=s23, Z02=mах{29+Z23,14+Z13, 3+Z03}=29, pot02=s23,
	Рис. 8

Z21=2, pot21=s22,

Z11=mах{12+Z22,2+Z12}=mах{12+3, 2+14}=15, pot11=s12,

Z01=mах{35+Z22,12+Z12, 2+Z02}=mах{35+3,12+14,2+29}=38, pot01=s22,

Z00=mах{18+Z21,10+Z11, 1+Z01}=mах{18+2,10+15,1+38}=39, pot00=s01.

Итак, оптимальный путь проходит через вершины s00, pot00=s01, pot01=s22, pot22=s23. Найденный оптимальный путь определяет оптимальное распределение денежных средств между тремя предприятиями: второму предприятию необходимо выделить всю сумму в 2 ден. ед., остальным – ничего. При этом будет достигнут максимальный прирост выпуска продукции, равный 39.                                                             ?