8.2. Системный анализ и управление развитием группы предприятий методом динамического программирования.

Динамическое программирование представляет собой математический метод оптимизации решений, приспособленный для управления многошаговыми (многоэтапными) процессами.

Пусть решается задача оптимального развития группы предприятий (например, четырех заводов, входящих в производственное объединение). Общая сумма средств, которая может быть использована для этого, составляет не более 5 млн. грн. На основе проектов развития предприятий и ориентировочных расчетов установлено, что в результате развития, в зависимости от затраченных средств, предприятия будут иметь производительность приведенную в табл.8.11. Необходимо определить оптимальное распределение средств между предприятиями, обеспечивающее максимальное увеличение производительности группы предприятий. Таким образом, в этой оптимизационной задаче используется критерий  суммарная производительность предприятий.

Таблица 8.11.

	Средства, вкладываемые в развитие (млн. грн.)
№ предприятия	0	1	2	3	4	5
	Производительность в результате развития (тыс. т.)
1	400	500	550	700	750	1000
2	4000	4200	4300	4500	4600	4700
3	0	100	400	800	850	900
4	600	750	900	950	1100	1200

Пусть х₁, х₂, х₃, х₄  капиталовложения в развитие соответственно первого, второго, третьего и четвертого предприятия, 0 х_i 5, i = 1,4. Обозначим f₁(x), f₂(x), f₃(x), f₄(x)  функции изменения производительности первого, второго, третьего и четвертого предприятия при вложении в их развитие х млн. грн. Этим функциям соответствуют строки 1, 2, 3, 4 в табл.8.12.

Определим максимум функции цели

F (х₁, х₂, х₃, х₄) = f₁(x) + f₂(x) + f₃(x) + f₄(x).

При этом на капиталовложения х₁, х₂, х₃, х₄ наложены ограничения

х₁ + х₂ + х₃ + х₄ = А,

млн. грн.

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

Выделим в нашей задаче 3 шага:

• А млн. грн. вкладываются в первое, второе предприятия одновременно;

• А млн. грн. вкладываются в первое, второе, третье предприятия вместе;

• А млн. грн. вкладываются в четыре предприятия одновременно.

Обозначим: F_1,2 (А), F_1,2,3 (А), F_1,2,3,4 (А)  соответственно оптимальные распределения средств для первого, второго и третьего шагов.

Алгоритм метода динамического программирования состоит из двух этапов. На первом этапе выполняется условная оптимизация, заключающаяся в том, что для каждого из трех шагов находят условный оптимальный выигрыш F_1,2 (А), F_1,2,3 (А), F_1,2,3,4 (А) для . На втором этапе выполняется безусловная оптимизация. Используя результаты первого этапа, находят величины капиталовложений в развитие предприятий х₁, х₂, х₃, х₄, обеспечивающие максимальную производительность группы предприятий.

Первый этап включает следующие шаги:

1) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 1, 2, 3, 4, 5, которые используются только для предприятий 1 и 2. Расчет ведется по формуле

F_1,2 ( А ) = max [ f₁( x ) + f₂ ( A - x ) ];

0  x  5;

0  A  5.

Результаты расчета представлены в табл.8.13.

Таблица 8.13.

		х2 = А - х
х1	f1( x )	0	1	2	3	4	5
		f2( А - x )
		400	4200	4300	4500	4650	4700
0	400	4400	4000	4700	4900	5050	5100
1	500	4500	4700	4800	5000	5150
2	550	4550	4750	4850	5050
3	700	4700	4900	5000
4	750	4750	4950
5	1000	5000

Например, для того, чтобы определить F_1,2 ( 2 ), надо вычислить

f₁( 2 ) + f₂ ( 0 ) = 550 + 4000 = 4550;

f₁( 1 ) + f₂ ( 1 ) = 500 + 4200 = 4700;

f₁( 0 ) + f₂ ( 2 ) = 400 + 4300 = 4700.

Наибольшее из полученных значений будет F_1,2 ( 2 ). Остальные F_1,2 ( х ) получаются как наибольшее значение каждой диагонали в таблице ( эти значения в таблице подчеркнуты:

F₂ ( 0 ) = 4400; F₂ ( 1 ) = max (4600, 4500) = 4600;

F₂ ( 2 ) = max ( 4550, 4700, 4700) = 4700;

F₂ ( 3 ) = max ( 4700, 4750, 4800, 4900) = 4900;

F₂ ( 4 ) = max ( 4750, 4900, 4850, 5000, 5050) =5050;

F₂ ( 5 ) = max ( 5000, 4950, 5000, 5050, 5100, 5100) =5100.

2) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 1, 2, 3, 4, 5, которые используются только для предприятий 1,2 и 3.

Расчет ведется по формуле

F_1,2,3 ( А ) = max [ F_1,2( A ) + f₃ ( A - x ) ];

0  x  5;

0  A  5.

Результаты расчетов занесем в табл.8.14, которая аналогична табл.8.13, только вместо f₁( x ) в ней указаны значения F₂ ( А ), а f₂ ( A - x ) заменена на f₃ ( A - x ).

Таблица 8.14.

		х3 = А - х
A	F1,2(A)	0	1	2	3	4	5
		f3( А - x )
		0	100	400	400	850	900
0	4400	4400	4500	4800	5250	5250	5300
1	4600	4600	4700	5000	5400	5450
2	4700	4700	4800	5100	550
3	4900	4900	5000	5300
4	5050	5050	5250
5	5150	5150

Значения F_1,2,3 ( A ) будут следующими:

F_1,2,3 ( 0 ) = 4400; F_1,2,3 ( 1 ) = 4600; F_1,2,3 ( 2 ) = 4800;

F_1,2,3 ( 3 ) = 5200; F_1,2,3 ( 4 ) = 5400; F_1,2,3 ( 5 ) = 5500.

3) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 1, 2, 3, 4, 5, которые используются для всех предприятий.

Расчет ведется по формуле

F_1,2,3,4 ( А ) = max [ F_1,2,3( A ) + f₄ ( A - x ) ];

0  x  5;

0  A  5.

Результаты расчетов заносим в табл.8.15.

Таблица 8.15.

		х4 = А – х
A	F1,2,3(А)	0	1	2	3	4	5
		f4( А - x )
		600	750	900	950	1100	1200
0	4400	5000	5150	5300	5350	5500	5600
1	4600	5200	5350	5500	5550	5700
2	4800	5400	5550	5700	5750
3	5200	5800	5950	6100
4	5400	6000	6150
5	5500	6100

Значения F_1,2,3,4 ( А ) в результате расчета будут следующими:

F_1,2,3,4 ( 0 ) = 5000; F_1,2,3,4 ( 1 ) = 5200;

F_1,2,3,4 ( 2 ) = 5400; F_1,2,3,4 ( 3 ) = 5800;

F_1,2,3,4 ( 4 ) = 6000; F_1,2,3,4 ( 5 ) = 6150.

На этом первый этап решения задачи динамического программирования заканчивается.

Перейдем ко второму этапу решения задачи динамического программирования  безусловной оптимизации. На этом этапе используются табл.8.15, 8.14, 8.13. Определим оптимальные капиталовложения в развитие предприятий для А = 0, 1, 2, 3, 4, 5. Для этого выполним следующие расчеты.

1. Пусть объем капиталовложений, выделенный на развитие предприятий, составляет А = 5 млн. грн.

Определим объем капиталовложений на развитие четвертого предприятия. Для этого используем табл.10.4. Выберем на ней диагональ, соответствующую А = 5  это значения 6100, 6150, 6100, 5750, 5700, 5600. Из этих чисел возьмем максимальное F_1,2,3,4 ( 5 ) = 6150 тыс. т. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем капиталовложений в четвертое предприятие х₄ = 1.

На развитие первого, второго и третьего предприятий остается

А = 5 - х₄ = 4 млн. грн.

2. Определим объем капиталовложений, выделенный на развитие третьего предприятия.

Для этого используем табл.8.14. Выберем в этой таблице диагональ, соответствующую А = 4  это значения 5050, 5000, 5100, 5400, 5200. Отмечаем столбец, в котором стоит максимальная (подчеркнутая) величина производительности F_1,2,3 ( 4 ) = 5400 тыс. т. Определяем значение х₄ = 3 млн. грн. в отмеченном столбце.

3. На развитие первого и второго предприятия остается сумма

А = 5 - х₄ - х₃ =1 млн. грн.

Определим объем капиталовложений на развитие второго предприятия. Используем для этого табл.8.13. Выберем в таблице диагональ, соответствующую А = 1  это значения 4500, 4600. Отмечаем столбец с максимальной величиной производительности F_1,2 ( 1 ) = 4600 тыс. т. Тогда в этом столбце х₂ =1 млн. грн.

4. Определим объем капиталовложений на развитие первого предприятия. Так как выделенные капиталовложения исчерпаны х₂ + х₃ + 1+ х₄ = 5, то на развитие первого предприятия средства не выделяются.

Таким образом, для капиталовложений объемом А = 5 млн. грн. оптимальным является вложение в развитие второго предприятия 1 млн. грн, третьего  3 млн. грн., четвертого  1 млн. грн., в развитие первого предприятия средства не выделяются. При этом суммарная производительность четырех предприятий составит 6150 тыс. т.

Повторив расчеты второго этапа решения для А = 4, 3, 2, 1, 0, определим оптимальные капиталовложения в развитие предприятий. Результаты будут следующими:

F_1,2,3,4 ( 4 ) =6000; х₁ =0; х₂ =1; х₃ =3; х₄ =0;F_1,2,3,4 ( 3 ) =5800; х₁ =0; х₂ =0; х₃ =3; х₄ =0;

F_1,2,3,4 ( 2 ) =5400; х₁ =0; х₂ =0; х₃ =2; х₄ =0;F_1,2,3,4 ( 1 ) =5200; х₁ =0; х₂ =1; х₃ =0; х₄ =0;

F_1,2,3,4 ( 0 ) =5000; х₁ =0; х₂ =0; х₃ =3; х₄ =0.