4.11. Применение метода динамического программирования для решения задачи управления запасами

Постановка задачи. Рассматривается функционирование предприятия в течение календарных этапов планирования. Каждый-й этап, характеризуется следующими параметрами:

- величина запаса, оставшаяся на предприятии после окончания предыдущего -го этапа;

- объем производства предприятия на -м этапе;

- величина спроса на продукцию предприятия на -м этапе.

Известна функция затрат , на-мэтапе функционирования предприятия. Эта функция завесит от объема производства и величины запасовкоторые должны храниться на складе в течение-го периода. Необходимо определить объем производства для каждого этапа планирования, при котором суммарные затраты, связанные с производством продукции и ее хранением, были бы минимальны, и в каждом периоде выполнялось ограничение на спрос продукции со стороны потребителей.

Критерий представляется как:

Ограничения имеют следующий вид:

удовлетворение спроса потребителей на продукцию в -м периоде

установление объема запаса в конце -го периода

.

Для решения этой задачи методом динамического программирования необходимо определить основные компоненты:

этапы - календарные периоды деятельности предприятия,;

состояния - объем запасов в конце-го периода;

управление - планируемый объем производствах на-м периоде;

локальный доход - затраты на -м этапе, связанные с хранением запасов и производством новой продукции:;

оператор перехода - устанавливает связь между объемом запасов в конце я - -го и-го этапов:.

Введем функцию

.

Тогда функциональное уравнение Беллмана имеет следующий вид:

Решение функционального уравнения Беллмана производится, начиная с первого этапа, та переменная последовательно полагается равной единице, двум, трем, ....

Рассмотрим решение уравнения Беллмана для случая, когда

где - затраты на производство продукции на-м этапе в объеме;-затраты на хранение продукции на-м этап, h - коэффициент;- начальный запас продукции;- затраты на производство начального запаса а объеме ;- затраты на хранение начального запаса в объеме.

Шаг 1. Соответствует первому этапу принятия решения, т.е. :

.

В полученном уравнении все величины являются известными. Для решения этого уравнения формируется табл. 4.27.

Алгоритм заполнения таблицы включает выполнение следующих действий:

столбцы таблицы соответствуют величине начального запаса, строки -объему производства на первом этапе . Каждая клетка таблицы делится на две части: в нижней части записываются значения состояния в конце первого этапа, т.е. значения для переменной:. В том случае, еслипринимает отрицательное значение, то такие состояния являются недопустимыми и исклю­чаются из рассмотрения путем вычеркивания, В частности, для положительного спросаклетка дляиявляется отрицательной и недопустимой. Очевидно. что первым допустимым состоянием является значение;

в верхней части каждой из клеток записывается значение функции

Таблица 4.28 Результаты выполнения первого шага

Объем производства на первом этапе	Величина начального запаса
			... …
			... ...
	…. ….	…. ….	… …		…. ….
		…. ….	… …	… …

Среди допустимых клеток находятся клеши с одинаковыми значениями состояний, и о качестве оптимальной выбирается клетка, для которой при­нимает оптимальное значение. Такие оптимальные значения находятся для всех состояний, т.е.. Для каждого состояния фиксируется опти­мальный объем производства. Результаты представляются в окончательной табл. 4.28 для первого шага: в первом столбце приводится перечень состояний, во втором — оптимальный объем производства для каждого из состояний; и третьем - оптимальные затраты на производство и хранение запаса для перво­го календарного периода. Максимальное значение состояния первого этапа ограничиваетсят.е.а минимальное -.

Таблица 4.28 Окончательная таблица первого шага

Величина запаса	Оптимальный объем производства	Оптимальная функция затрат
… …	… …	… …

Шаг 2. Соответствует второму этапу принятия решений, т.е. =2. Функциональное уравнение Беллмана имеет следующий вид:

где - оптимальное значение функции затрат для предыдущего этапа;-исходные данные. Результаты выполнения второго шага представлены а табл. 4.29.

Таблица 4,29. Результаты выполнения второго шага

Объем производства на первом этапе	Величина начального запаса
			... …
			... ...
	…. ….	…. ….	… …		…. ….
		…. ….	… …	… …

Аналогично предыдущему шагу каждая клетка разбивается на дне части, определяются клетки, соответствующие недопустимым состояниям, и они уда­ляются путем вычеркивания. Для допустимых клеток вычисляются значения состояний , которые записываются в нижней части каждой из клеток. В верхней части клетки указывается значение функции затрат:. Затем находятся одинаковые состояния, и для них вычисляется условно оптимальное значение функции затрат. Таким образом, после окончания второго этапа для каждого из допустимых состоянийдолжна быть определена функция затрат, а также значение объема производстваи запаса. Эти результаты представляються в окончательной таблице для второго этапа в табл. 4.30.

Таблица 4.30.

Величина запаса	Оптимальный объем производства	Оптимальная функция затрат
… …	… …	… …

Аналогичные действия выполняются для всех этапов, пока .

Пример. Методом динамического программирования определять оптимальный план производства предприятия для следующих исходных данных: количество интервалов планирова­ния ; величина спроса на продукцию постоянна для всех этапов планирования:; затраты на производство и хранение продукции; затраты на формиро­вание начального запаса; ограничение на производственные мощности; огра­ничение на предельный уровень запасок.

Шаг 1. Решение уравнения Беллмана производится в соответствии с алгоритмом прямой прогонки:

Для выполнения шага 1 формируется промежуточная табл. 4.3. Клетки таблицы, соответствующие недопустимым состоянием, отмечаются символом * . В качестве примера приведено вычисление ряда функций :

На основе промежуточном табл. 4.31 формируется окончательная табл. 4.32 для шага 1

Таблица 4.31 промежуточная таблица для шага 1

Объем производства
	*	*	*	*	40
	*	*	*	49	59
	*	*	46	56	66
	*	43	53	63	73
	40	50	60	70	80
	47	57	67	77	*
	54	64	74	*	*

Таблица 4.32 Окончательная таблица для шага 1

Объем запаса	Объем производства	Функция затрат

Шаг 2. Рассматривается второй интервал функционирования предприятия, - 2. Уравнение Беллмана будет иметь вид:

Для решения уравнения формируются промежуточная и окончательная (табл. 4.33 и табл. 4.34.)

Таблица 4.33. Промежуточная тавблица для шага 2

Объем производства
	*	*	*	*	78
	*	*	*	86	97
	*	*	82	93	104
	*	81	99	100	111
	80	88	96	107	118
	87	95	103	114	*
	94	102	110	*	*

Таблица 4.34. Окончательная таблица для шага 3

Объем запаса	Объем производства	Функция затрат

Д

Л

Для нахождения оптимальных объемов производства и оптимальных уровней запаса, производиться решение задачи в обратном порядке: