2.2.10 Динамическое программирование. Распределение ресурсов между предприятиями головной фирмы

Метод динамического программирования применяется к непрерывным и дискретным процессам оптимального управления.

Рассматривается многошаговый процесс с последнего шага. Чем кончился предпоследний шаг неизвестно, поэтому делается предположение о состоянии на шаге в различных вариантах, далее идут предположения о шаге и т.д. Т.е. на каждом шаге выделяются условно-оптимальные варианты.

После достижения первого шага делается обратный проход для выбора оптимального варианта из условно–оптимальных.

В основе динамического программирования лежит принцип Беллмана:

«Каково бы ни было состояние системы в результате какого-то числа шагов, необходимо выбирать управление на ближайшем шаге так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах привело бы к максимальному выигрышу».

Функциональное уравнение для решения многоэтажного процесса Беллмана имеет вид

, (2.10.1)

где – целевая функция процесса (доход, прибыль);

– номер этапа процесса;

– переменная состояния системы на -м этапе;

– управляющая переменная, от выбора которой зависит результат на -м этапе;

– величина критерия, полученного на -м этапе при выборе от 0 до ;

– результирующее оптимальное значение критерия, достигаемое после прохождения этапа.

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

Задача 2.2.10.1. Фирме подчиняются 2 предприятия. Головная фирма распределяет ресурс в 150 тыс. денежных единиц для развития производства. Прирост прибыли по предприятиям определяется таблично, дискретность 30 денежных единиц.

Таблица 10.1

Средства	Прирост прибыли по предприятиям
	№1	№2
30	11	14
60	20	26
90	32	30
120	44	60
150	65	70

Решение.

Общее функциональное уравнение Беллмана

.

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

Условно-оптимальный план для первого предприятия:

Таблица 10.2

Средства	Условно-оптимальный план
30	30	11
60	60	20
90	90	32
120	120	44
150	150	65

Для второго предприятия функция Беллмана имеет вид

.

Таблица 10.3

	0	30	60	90	120	150	Условно-оптимальный план
							14	30
30	0+11	14+0
60	0+20	14+11	26+0				26	60
90	0+32	14+20	26+11	30+0			37	60
120	0+44	14+32	26+20	30+11	60+0		60	120
150	0+65	14+44	26+32	30+20	60+11	70+0	71	120

Рассмотрим первую строку =30. В первом столбце =0, , тогда по таблице (10.2). Во втором столбце =30, =30, по таблице (10.1) ; .

Максимальное значение , ему соответствует .

Аналогично вычисляются остальные значения и .

Последнее значение и является оптимальным для второго предприятия, является глобальным значением функции цели.

Оптимальный план 1-го предприятия можно определить:

.

Возможно также найти оптимальный план первого предприятия движением по таблицам от последней к первой. Значение получено от сложения 60+11, число 11 является по таблице (10.2), ему соответствует план .