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

 

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

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

Таблица 8.11.

	Средства, вкладываемые в развитие (млн. грн.)
№ предприятия
	Производительность в результате развития (тыс. т.)
1

Пусть х₁, х₂, х₃, х₄ ¾ капиталовложения в развитие соответственно первого, второго, третьего и четвертого предприятия, 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)
		f2(А - x)
			4000	4700	4900	5050
			4700			5150

Например, для того, чтобы определить 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)
		f3(А - x)
					5250
		4600			5400
					550

Значения 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(А)
		f4(А - x)
		5000
		5200
		5800
		6000	6150

Значения 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.

Список использованной литературы:

 

Акофф Р. Искусство решения проблем: Пер. с англ. ¾ М.:Мир. 1992.¾224 с.

Беллман Р. Динамическое программирование. ¾ М.: Иностранная литература, 1990. ¾ 212 с.

Венцель Е. С. Исследование операций. ¾ М.: Сов. Радио, 1992. ¾ 551с.

Денисов А.А. Колесников Д.Н. Теория больших систем управления:¾Л.: Энергоиздат.1992.¾228 с.

Моисеев А.Н. Математические задачи системного анализа.¾М.: Наука, 1991.¾487 с.

Марюта А.Н., Певзнер О.М. Iнформацiйный системний аналiз виробничо - экономiчних об’ектiв. ¾ Днiпропетровськ.: ДДУ, 1995.¾218 с.

Моисеева Н.К., Карпунин М.Г. Основы теории и практики функционально-стоимостного анализа.¾М.: Высшая школа, 1988.¾189 с.

Половинкин А.И. Основы инженерного творчества.¾М.: Машиностроение,1988.¾167 с.

Первозванский А.А. Математические модели в управлении производством.¾М.: Наука, 1985.¾ 615 с.

Черняк Ю.Н. Системный анализ в управлении экономикой.¾ М.: Экономика, 1995.¾ 191 с.