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

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙИСКОЙ ФЕДЕРАЦИИ»

(Финансовый университет)

 

Факультет

прикладной математики и информационных технологий

Кафедра «Прикладная математика»

 

 

ДОМАШНЕЕ ТВОРЧЕСКОЕ ЗАДАНИЕ

 

по дисциплине:

«Математические методы поддержки принятия решений»

 

на тему «Модель управления запасами методом динамического программирования»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	Выполнила: Студентка группы ПИ1-1м
	Терентьева Екатерина Сергеевна Подпись ______________________
	Преподаватель:
	К.ф-м.н., доцент Набатова Д.С. Подпись_______________________

 

Москва, 2014

 

Управление запасами

Цель предприятия – разработать такую программу, при которой общая сумма затрат на производство и содержание запасов минимизируется при условии полного и своевременного удовлетворения спроса на продукцию. Для обеспечения непрерывного и эффективного функционирования практически любой организации необходимо создание запасов, например, в производственном процессе, торговле, медицинском обслуживании и т.д. В зависимости от ситуации под запасами могут подразумеваться: готовая продукция, сырье, полуфабрикаты, станки, инструмент, транспортные средства, наличные деньги и др. Неверный расчет необходимых запасов может привести как к незначительному ущербу (потеря части дохода от дефицита товара), так и к катастрофическим последствиям (при ошибочной оценке запасов топлива на самолете). К экономическому ущербу приводит как чрезмерное наличие запасов, так и их недостаточность. Так, если некоторая компания имеет товарные запасы, то капитал, овеществленный в этих товарах, замораживается. Этот капитал, который нельзя использовать, представляет для компании потерянную стоимость в форме невыплаченных процентов или неиспользуемых возможностей инвестирования. Кроме того, запасы, особенно скоропортящиеся продукты, требуют создания специальных условий для хранения. Для этого необходимо выделить определенные площади, нанять персонал, застраховать запасы. Все это влечет определенные издержки. С другой стороны, чем меньше уровень запаса, тем больше вероятность возникновения дефицита, что может принести убытки вследствие потери клиентов, остановки производственного процесса и т.д. Кроме того, при малом уровне запасов приходится часто поставлять новые партии товара, что приводит к большим затратам на доставку заказов. Отсюда следует важность разработки и использования математических моделей, позволяющих найти оптимальный уровень запасов, минимизирующих сумму всех описанных видов издержек.

В данной работе будет рассмотрена и решена задача управления запасами на наглядном примере.

Экономическая постановка задачи.

Существует предприятие, которое может производить ежемесячно до 4-х единиц некоторой продукции. Затраты на производство xj единиц продукции в месяце j указаны в таблице 1. Каждый месяц предприятие должно отгрузить 2 единицы продукции своим потребителям. Продукцию можно хранить на складах. Затраты на хранение 1 единицы продукции составляют 1 тысячу рублей. Оплата за хранение производится в конце месяца j. Склады могут вместить до 4 единиц продукции. Учитывая, что в начале на складах было 2 единицы продукции, определить оптимальный план производства на 4 месяца.

Таблица 1.- Затраты на производство xj единиц продукции.

xj	0	1	2	3	4	штук продукции.
C(xj)	0	7	9	11	13	млн.руб.

Составим математическую модель задачи. Введем следующие обозначения:

N – число календарных  этапов из которых состоит плановый период;

При этом каждый j-й этап (j=1,N) характеризуется параметрами:

yj-1 – запас, оставшийся после окончания j-1-го этапа;

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

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

xmax – максимальный объем производства на одном этапе;

ymax – максимальный объем запасов на одном этапе;

Сj(xj,yj-1) – затраты на j-м этапе функционирования, связанные с выпуском хj и хранением yj-1 запасов.

Математическая модель задачи выглядит следующим образом.

Тогда критерий оптимизации имеет вид:

F=  ® min

при ограничениях:

1) Ограничение на удовлетворение  спроса на каждом этапе:

dj £ yj-1 + xj , j=1,N

2) Установление объема  запаса в конце j-го периода:

yj = yj-1 + xj – dj , j=1,N , xj = 0,xmax , yj = 0,ymax

запасы yj в конце текущего j-го месяца равны запасам в предыдущем месяце плюс xj произведенных в текущем месяце j изделийи минус dj проданных изделий.

Обозначение основных компонентов:

1. Этап - календарный период  деятельности предприятия, j=1,N;

2. Состояние – объем  запасов yj в конце n периода;

3. Управление – планируемый объем производства xj на j-м периоде;

4. Локальный доход – затраты на j-м этапе, связанные с хранением запасов и производством новой продукции Сj(xj,yj-1);

5. Оператор перехода –  устанавливает связь между объемом  запасов в конце j– 1-го и j-го этапов: yj = yj-1 + xj – dj .

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

fj(yj) = min∑ Сj(xj,yj-1).

Функциональное уравнение Беллмана для такой задачи:

fj(yj-1) = min(fj(yj-1) + Сj(xj,yj-1)).

Если Сj(xj,yj-1) = cj(xj) + h*yj-1 ,

Где cj(xj) – затраты на производство продукции на j-ом этапе в xj объеме;

h*yj-1 – затраты на хранение продукции на j-ом этапе в объеме y0.

Известно c0(x0) - затраты на формирование начального запаса.

 

уравнение Беллмана примет вид:

Итак, начало решения задачи о запасах будет осуществляться с последнего месяца – апреля.

Этап 4: апрель.

f4 (y3) = {C(x4) + 1 · (y3 + x4 − 2)}

x4 0:4

Таблица 1. Управление запасами, этап 4

y3	Оптимальное решение
	f4(3)
0	9	2
1	7	1
2	0	0

 

В конце апреля запасы на складе должны быть равны нулю y3 +x4 − 2 = y4;    y4 = 0, отсюда y3 + x4 = 2 и все возможные значения y3 и x4 в таблице 3.2 перечислены. Таких пар всего три. Для каждого возможного значения (y3 , x4) вычислена целевая функция C(x4).

Этап 3: март, апрель.

f3 (y2 ) = min {C(x3 ) + 1 · (y2 + x3 − 2) + f4 (y2 + x3 − 2)}

x3 ∈0:4

Таблица 2. Управление запасами, этап 3

y2	C(x3) + 1 · (y2 + x3 − 2) + f4 (y2 + x3 − 2)					Оптим. решение
	x3=0	x3=1	x3=2	x3=3	x3=4	f3(y2)	х3*
0	_	_	9+0+9=18	11+1+7=19	13+2+0=15	15	4
1	_	7+0+9=16	9+1+7=17	11+2+0=13	_	13	3
2	0+0+9=9	7+1+7=15	9+2+0=11	_	_	9	0
3	0+1+7=8	7+2+0=9	_	_	_	8	0
4	0+2+0=2	_	_	_	_	2	0

 

Этап 2: февраль, март, апрель.

f2 (y1) = min {C(x2) + 1 · (y1 + x2 − 2) + f3 (y1 + x2 − 2)}.

x2 ∈0:4

Таблица 3. Управление запасами, этап 2

y1	C(x2) + 1 · (y1 + x2 − 2) + f3 (y1 + x2 − 2)					Оптим. решение
	x2=0	x2=1	x2=2	x2=3	x2=4	f2(y1)	х2*
0	_	_	9+0+15=24	11+1+13=25	13+2+9=24	24	2,4
1	_	7+0+15=22	9+1+13=23	11+2+9=22	13+3+8=24	22	1,3
2	0+0+15=15	7+1+13=21	9+2+9=20	11+3+8=22	13+4+2=19	15	0
3	0+1+13=14	7+2+9=18	9+3+8=20	11+4+2=17	_	14	0
4	0+2+9=11	7+3+8=18	9+4+2=15	_	_	11	0

 

Этап 1: январь, февраль, март, апрель.

f1 (y0) = min {C(x1) + 1 · (y0 + x1 − 2) + f2 (y0 + x1 − 2)}.

x1 ∈0:4

Таблица 4. Управление запасами, этап 1

y0	C(x1) + 1 · (y0 + x1 − 2) + f2 (y0 + x1 − 2)					Оптим. решение
	x1=0	x1=1	x1=2	x1=3	x1=4	f1(y0)	х1*
0	_	_	9+0+24=33	11+1+22=34	13+2+15=30	30	4
1	_	7+0+24=31	9+1+22=32	11+2+15=28	13+3+14=30	28	3
2	0+0+24=24	7+1+22=30	9+2+15=26	11+3+14=28	13+4+11=28	24	0
3	0+1+22=23	7+2+15=24	9+3+14=26	11+4+11=26	_	23	0
4	0+2+15=17	7+3+14=24	9+4+11=24	_	_	17	0

 

Находим оптимальное решение, начиная с последнего этапа 1. y0 = 2 из условий задачи, поэтому из таблицы 4 следует, что x1* = 0, y1 = y0 + x1 * − 2 = 0. В таблице этапа 2 в строке y1 = 0 видим два оптимальных решения. Рассмотрим сначала решение x2*= 4. Это решение подчеркнуто. Из уравнения y2 = y1 + x2∗− 2 находим y2 = 0 + 4 − 2 = 2. Переходим к таблице этапа 3 к строчке y2 = 2. Понятно, что соответствующая компонента решения x3∗= 0 и в таблице этапа 4 надо смотреть на строку y3 = y2+0−2 = 0. Эта строка y2 = 0 дает последнюю компоненту решения x4∗= 2.

Из этого следует окончательный ответ.

х*= (0, 4, 0, 2), f1 (2) = 24.

Итак, из проведенных расчетов известно, что в феврале надо произвести 4 единицы продукции и в апреле 2 единицы, при этом за четыре месяца будет затрачено 24 миллиона рублей. С меньшими затратами нельзя выполнить намеченную программу.