Динамическое и линейное программирование (стр. 9 из 13)

Таблица 8.
		0	100	200	300	400	500	600	700
		0	42	72	94	113	129	144	158
0	0	158
100	50	194
200	68	197*
300	82	195
400	92	186
500	100	172
600	107	149
700	112	112

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

денежных единиц

причем четвертому предприятию должно быть выделено:

денежных единиц

Тогда третьему предприятию должно быть выделено (см. табл. 7.):

денежных единиц

второму предприятию должно быть выделено (см. табл. 5.):

денежных единиц

на долю первого предприятия остается:

денежных единиц

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

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

денежных единиц

6. Динамическая задача управления запасами

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

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

Примем следующие обозначения:

	Номер месяца (j=1,2,…,n)
	Число изделий, производимых в j-ом месяце
	Величина запаса к началу j-го месяца
	Число изделий, которые должны быть отгружены в j-ом месяце
	Затраты на хранение и производство изделий в j-ом месяце

Тогда, задача состоит в том, чтобы найти план производства

компоненты которого удовлетворяют условиям материального баланса:

, где

и минимизируют суммарные затраты за весь планируемый период:

причем по смыслу задачи

, , при

Т.к. объем произведенной продукции

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

Полученную задачу можно решить методом динамического программирования, для чего необходимо определить параметр состояния

и функцию состояния :

	Наличный запас продукции в конце k-го месяца ( )
	Минимальные затраты за первые месяцев:

Тогда, минимальные затраты за один первый месяц (

):

Следовательно, минимальные затраты при

:

, где

Если при этом функция затрат на хранение и производство изделий в j-ом месяце имеет вид:

, где

, при и , при
	Затраты на оформление заказа (переналадку оборудования) в j-ом месяце
	Затраты на хранение единицы продукции, переходящей из j‑го месяца в месяц j+1
	Затраты на производство (закупку) единиц продукции в j‑ом месяце

то минимальные затраты за один первый месяц (

):