Динамическая модель управления запасами
Назначение. Онлайн калькулятор предназначен для решения задачи управления запасами методами динамического программирования.
Инструкция. Выберите период планирования, нажмите Далее.
Рассмотрим предприятие, которое изготовляет партиями некоторые изделия. Оно состоит из производственных цехов и склада для хранения готовой продукции. Предположим, что предприятие получило заказы на продукцию на n месяцев (этапов) вперед. Эти заказы необходимо полностью и своевременно выполнять (дефицит не допускается). Для разных этапов спрос не одинаков, кроме того, на экономические показатели производства влияют размеры изготовляемых партий продукции. Поэтому предприятию иногда бывает выгодно производить в течение месяца продукцию в объеме, превышающем спрос в пределах этого этапа, и хранить запасы «лишней» продукции, используя их для удовлетворения последующего спроса. Продолжительность изготовления партии изделий будем считать пренебрежимо малой (однако это требование может быть изменено в соответствии с особенностями технологического процесса). Цель предприятия – выработать такую программу производства, которая обеспечила бы минимальные затраты на изготовление и хранения продукции.
Введем обозначения:
xt – число изделий, изготовленных в t-м месяце (этапе);
yt – уровень запасов на конец t-го месяца;
dt – спрос на изделие в t-м месяце;
ft(xt, yt) – затраты на производство и хранение изделий в t-м месяце.
Соотношение материального базиса примет вид
yt-1+xt-dt=yt, t=1,..,n (1)
т.е уровень запасов на конец t-го этапа равен сумме уровня запасов на начало t-го и объема производства на t-м этапе за вычетом спроса на t-м этапе.
Данное балансовое соотношение можно записать и в другом виде:
yt-1= yt -xt+dt, t=1,..,n (2)
Наша задача состоит в том, чтобы составить такой план производства
X=(x1, …,xn), или, что тоже самое, найти такой план хранения запасов Y=(y1,…,yn), который обеспечил бы минимальные суммарные затраты предприятия
(3)
за весь плановый период.
Введем ограничения на переменные xt, yt. Будем считать объемы производства и уровни хранения на каждом этапе неотрицательными и целочисленными величинами. Кроме того, предположим, что уровни запасов к началу первого этапа y0 и к концу последнего yn заранее известны.
Решим сформулированную задачу методом динамического программирования. В качестве параметра состояния ζ примем уровень запасов на конец k-го этапа
ζ=yk (4)
Функцию составления Fk(ζ) определим как минимальные затраты за первые k месяцев, т.е.
. (5)
Здесь абсолютный минимум берется по всем значениям x1,…,xk, удовлетворяющим балансовым уравнениям:
yt-1+xt-dt=yt, t=1,..,k (6)
yk-1+xk-dk= ζ , t=k (7)
При k=1 соотношение (7) примет вид
ζ =y0+x1-d1 (8)
или
x1= ζ –y0+d1. (9)
Тогда с учетом (4) и (9) функция состояния
, (10)
причем если не видно никаких ограничений на объем складских помещений и производственную мощность предприятия, то (ζ=y1).
y1≤d2+d3+..+dn+yn
x1≤d1+d2+..+dn+yn-y0, (11)
Это связано с тем обстоятельством, что если иметь на конец 1-го этапа запас изделий в качестве d2+..+dn+yn, то, ничего не изготовляя в течение всего планового периода, а только удовлетворяя спрос, можно выйти на уровень запасов yn в конце n-го месяца. В то же время если уровень запасов на начало 1-го этапа равен y0, то, изготовив в 1-м месяце изделий в количестве d1+d2+..+dn+yn-y0, и не производя ничего на последних этапах, получим тот же запас yn в конце планового периода. Если же на 1-м этапе предприятие может вместить готовой продукции не более М1 изделий, а мощности предприятия не позволяют произвести более N1 изделий, то (ζ=y1)
y1 ≤ min{M1, d2+d3+...+dn+yn},
x1 ≤ min{N1, d1+d2+d3+...+dn+yn-y0}. (12)
Получим рекуррентное соотношение динамического программирования в модели управления запасами при любом k = 2, …,n.
Запишем функцию состояния (5) в виде
. (13)
Здесь, как уже было сказано выше, все переменные связаны балансовыми уравнениями
yt=yt-1+xt-dt, t=1,..,k (14)
В связи с тем что величина запаса yk-1 к концу (k – 1)-го планового этапа с учетом (7) равна ζ–xk+dk, имеем следующее рекуррентное соотношение динамической модели управления запасами:
. (15)
Если внешних ограничений на уровни хранения и объемы производства не существует, то по аналогии с (11) получаем внутренние ограничения модели
,
. (16)
Если складские емкости и производственные мощности предприятия ограничены количеством изделий Mk и Nk соответственно, то аналогично соотношениям (12) имеем
,
. (17)
На самом деле ограничения (16) и (17) имеют более сложную структуру. Однако для решения практических задач этого вполне достаточно. Напомним лишь о том, что переменные xk и yk целочисленны и не отрицательны.
Рассмотрим теперь функцию затрат ft(xt,yt). Введем следующие обозначения:
gt – затраты на производство и доставку заказа на t-м этапе;
ct(xt) – затраты на производство xt единиц продукции на t-м этапе;
ht(yt) – затраты на хранение yt единиц продукции в течение t-го планового этапа.
Для определенности будем считать, что производственные затраты линейны, т.е. ct(xt) = ctxt, и что затраты на хранение пропорциональны объему хранимой продукции в течении месяца. Далее, уровень (объем) хранения в течение этого месяца определяется уровнем хранения на конец этапа. Иными словами, поскольку время изготовления партий изделий пренебрежимо мало, а производить и отправлять заказчикам продукцию предприятию выгодно вначале каждого месяца, то уровень хранимого имущества в течение t-го этапа определяется соотношением баланса yt=yt-1+xt-dt. В итоге получаем ht(yt)=htyt.
Функция затрат с учетом выведенных обозначений примет вид
(18)
Применим теперь метод динамического программирования к решению задачи управления запасами.
Пример №1. Определение оптимальной программы производства.
Рассмотрим плановый период работы предприятия, состоящий из трех месяцев: января, февраля, марта. Исходные данные сведены в таблице 1.
Таблица 1
Этап | k | 1 | 2 | 3 |
Месяц | Январь | Февраль | Март | |
Спрос | dk | 2 | 5 | 2 |
Затраты на оформление заказа | gk | 10 | 5 | 10 |
Затраты на производство одного изделия | ck | 3 | 5 | 3 |
Стоимость хранения одного изделия в течение месяца | hk | 1 | 2 | 1 |
Функция затрат определена формулой (18). Кроме того, будем считать, что предприятие не может производить более четырех изделий, а хранить – более трех, т.е. Mk = 3, Nk = 4, а уровень запасов y0 = y3 = 0.
Необходимо составить оптимальную программу выпуска продукции X=(x1,x2,x3), которая минимизирует суммарные издержки предприятия.
Рассмотрим январский этап (k=1). Поскольку плановый период состоит из одного месяца, у нас практически нет возможности влиять на объем производства изделий. Поэтому все допустимые программы выпуска продукции будут оптимальны, поскольку они единственны.
Функция состояния в соответствии с (10) примет вид
F1(ζ)=f1(x1= ζ-y0+d1, y1= ζ)=f1(x1= ζ+2; y1= ζ)
Прежде чем произвести расчеты F1(ζ) по формуле (18), укажем ограничения на изменения переменных x1 и y1. Поскольку уровни запасов на начало и конец планового периода равны нулю, то в январе мы можем произвести такое количество изделий, чтобы удовлетворять не только январский, но и февральский и мартовский спрос, т.е. произвести d1+d2+d3=7 изделий, однако N1=4, поэтому x1≤min{N1,d1+d2+d3}=4. Возникает естественный вопрос: каков должен быть уровень запасов на конец января (или, что одно и то же, на начало февраля), чтобы, не изготавливая ничего ни в феврале, ни в марте, опять выйти на нулевой уровень запасов в конце марта? Ответ очевиден: объем запасов продукции должен быть равен d2+d3=5. Но поскольку возможности склада ограничены (Mk=3), в итоге получаем:
0≤y1≤ min{M1,d2+d3}=3
Результаты вычислений сведем в табл. 2.
k=1, d1=2, g1=10, c1=3, h1=1
Таблица 2
y1 | x1=y1+2 | F1(ζ)=f1(x1= ζ+2, y1= ζ)=g1+c1x1+h1y1 |
0 1 2 3 | 2 3 4 – | 10 + 3 · 2 + 1 · 0 = 16 10 + 3 · 3 + 1 · 1 = 20 10 + 3 · 4 + 1 · 2 = 24 – |
Рассмотрим k = 2, когда плановый период содержит январь и февраль. У нас появляются дополнительные возможности для изменения объема выпуска изделий на каждом из этапов, с тем чтобы выйти на ненулевой уровень запасов y3=0.
Рекуррентное соотношение (15) примем вид
,
где ξ – оптимальное значение уровня запасов y2 на конец второго этапа, которому соответствует наименьшие суммарные затраты на производство и хранение продукции.
Ограничения на объем производства и уровень хранения очевидны:
0≤x2≤min{N2,d2+d3}=min{4;7}=4
0≤y2≤min{M2,d3}=min{3;2}=2
Отобразим в таблице 3 все необходимые вычисления для февральского этапа (k=2, d2=5, g2=5, c2=5, h2=2).
Таблица 3
x2 y2 | 0 | 1 | 2 | 3 | 4 | x2(ζ=y2) | F2(ζ) |
0 | 5 – | 4 – | 3 – | 2 20 + 0 + 24 = 44 | 1 25 + 0 + 20 = 45 | 3 | 44 |
1 | 6 – | 5 – | 4 – | 3 – | 2 25 + 2 +24 =51 | 4 | 51 |
2 | 7 – | 6 – | 5 – | 4 – | 3 – | – | – |
Поясним содержание этой таблицы. Объем производства и уровень хранения определяются значениями x2 и y2 соответственно. В верхнем правом углу каждой клетки указаны уровни запасов на начало второго этапа, которые с помощью балансового уравнения вычисляются по формуле y1=y2-x2+d2. Сумма внутри каждой клетки содержит три слагаемых. Рассмотрим эти слагаемые для клетки с координатами (x2=3, y2=0). Первое слагаемое – затраты на оформление заказа и производство продукции g2+c2x2=5+5*3=20; второе – затраты на хранение h2y2=2*0=0. Сумма двух первых слагаемых равна f2(x2=3, y2=0). Прежде чем вычислить третье слагаемое, которое в рекуррентном соотношении обозначено как F1(ζ-x2+d2), вспомним, что величина y1= ζ –x2+d2 вычислена, находится в верхнем правом углу клетки и равна 0–3+5=2. Поэтому третье слагаемое F1(y1=2)=24 возьмем из январской таблицы. Аналогично рассчитываются слагаемые в остальных клетках, а в «запрещенных» клетках, для которых не нашлось последнего слагаемого в январской (k = 1) таблице, сделан прочерк. Наименьшие суммарные затраты F2(ζ) для каждого y2 запишем в последнем столбце (они подсчитаны в выделенных рамкой клетках), а значения оптимальных объемов производства изделий в феврале x2(ζ) занесем в предпоследний столбец таблицы.
При k = 3 плановый период уже включает в себя январь, февраль и март. Запишем рекуррентное соотношение
F3(ζ)=min{f3(x3,y3)+F2(ζ-x3+d3)}
где ξ – значения уровня запасов y3 на конец марта, которому соответствуют наименьшие суммарные затраты на хранение и производство продукции.
Новая таблица (табл. 4) содержит лишь одну строку, так как, по условию задачи, y3=0 (k=3, d3=2, g3=10, c3=3, h3=1). Количество столбцов определим в соответствии с неравенством
0≤x2≤min{N3, d3} = min{4;2}=2
Таблица 4
x3 y3 | 0 | 1 | 2 | x3(ζ=y3) | F3(ζ) |
0 | 2 – | 1 13 + 0 +51 = 64 | 0 16 + 0 + 44 =60 | 2 | 60 |
В остальном, содержание таблицы ничем не отличается от предыдущей.
Составим оптимальную программу выпуска продукции на каждом этапе, которая обеспечит минимальные суммарные затраты F3(ζ)=60 в течение всего планового периода. Как видно из мартовской таблицы k=3, x3(ζ)=2, что соответствует оптимальному уровню запасов y2=0, который рассчитан и записан в верхнем правом углу выделенной рамкой клетки. Далее из февральской таблицы (k=2) следует, что x2(ζ=y2=0)=3.
В выделенной рамкой клетке с координатами (x2=3, y2=0) (табл. 3) в верхнем правом углу записан оптимальный уровень запасов y1=2 на конец января. Наконец, из январской таблицы (k=1) получаем, что y1=2 соответствует x1(ζ)=4. Таким образом, построена оптимальная программа выпуска продукции
X=(x1(ζ), x2(ζ), x3(ζ)) = (4;3;2)
которая обеспечивает минимальные суммарные издержки F3(ζ)=60 на производство и хранение продукции.
Управление запасами. Складская задача
Складская задача относится к динамическим детерминированным задачам управления запасами. Следовательно, для решения этой задачи можно применить принцип Беллмана.Пример №2. Рассмотрим задачу.
Планируется деятельность предприятия на три месяца.
ЗАДАНЫ:
- начальный уровень запасов S0 = 20
- остаток запасов S3 = 0
- затраты на пополнение φ(x) = 0.4x
- затраты на хранение ψ(y) = 0.2y + 1 в данном периоде в зависимости от y - среднего уровня хранимых запасов.
Решение.
Используются формулы Уилсона:
Средний уровень хранения yk = dk/2 + Sk
Уравнение состояния Sk = Sk-1 + xk - dk
Третий месяц
| S2 | x3 | y3 | φ(x3) | ψ(y3) | φ + ψ | Z3 |
| 30 | 0 | 15 | 0 | 4 | 4 | 4 |
| 20 | 10 | 15 | 4 | 4 | 8 | 8 |
| 10 | 20 | 15 | 8 | 4 | 12 | 12 |
| 0 | 30 | 15 | 12 | 4 | 16 | 16 |
Второй месяц
| S1 | x2 | S2 | y2 | φ(x2) | ψ(y2) | Z3 | φ + ψ + Z3 | Z2 |
| 50 | 0 | 30 | 40 | 0 | 8 | 4 | 12 | 12 |
| 40 | 0 | 20 | 30 | 0 | 7 | 8 | 15 | 15 |
| 10 | 30 | 40 | 4 | 9 | 4 | 18 | ||
| 30 | 0 | 10 | 20 | 0 | 5 | 12 | 17 | 17 |
| 10 | 20 | 30 | 4 | 7 | 8 | 19 | ||
| 20 | 30 | 40 | 8 | 9 | 4 | 22 | ||
| 20 | 0 | 0 | 10 | 0 | 3 | 16 | 19 | 19 |
| 10 | 10 | 20 | 4 | 5 | 12 | 21 | ||
| 20 | 20 | 30 | 8 | 7 | 8 | 23 | ||
| 30 | 30 | 40 | 12 | 9 | 4 | 25 | ||
| 10 | 10 | 0 | 10 | 4 | 3 | 16 | 23 | 23 |
| 20 | 10 | 20 | 8 | 5 | 12 | 25 | ||
| 30 | 20 | 30 | 12 | 7 | 8 | 27 | ||
| 40 | 30 | 40 | 16 | 9 | 4 | 29 | ||
| 0 | 20 | 0 | 10 | 8 | 3 | 16 | 27 | 27 |
| 30 | 10 | 20 | 12 | 5 | 12 | 29 | ||
| 40 | 20 | 30 | 16 | 7 | 8 | 31 | ||
| 50 | 30 | 40 | 20 | 9 | 4 | 33 |
Первый месяц
| S0 | x1 | S1 | y1 | φ(x1) | ψ(y1) | Z2 | φ + ψ + Z2 | Z1 |
| 20 | 10 | 0 | 15 | 4 | 4 | 27 | 35 | 35 |
| 20 | 10 | 25 | 8 | 6 | 23 | 37 | ||
| 30 | 20 | 35 | 12 | 8 | 19 | 39 | ||
| 40 | 30 | 45 | 16 | 10 | 17 | 43 | ||
| 50 | 40 | 55 | 20 | 12 | 15 | 47 | ||
| 60 | 50 | 65 | 24 | 4 | 12 | 50 |
x1 = 10 S1 = 0 y1 = 15 φ(x1) = 4 ψ(y1) = 4
x2 = 20 S2 = 0 y2 = 10 φ(x2) = 8 ψ(y2) = 3
x3 = 30 S3 = 0 y3 = 15 φ(x3) = 12 ψ(y3) = 4
Выгодно каждый год докупать ровно столько, чтобы хватило на текущий год.
Пример №3. Станкостроительное предприятие производит станки, спрос на которые в каждом из трех месяцев квартала равен Dt единицам. Запас станков на складе на начало квартала равен i0 единицам. Затраты на производство станков равны сумме постоянных затрат k ден. ед. и пропорциональных lxt (l ден. ед. на каждый станок). Затраты на хранение одного станка в течение месяца равны h ден. ед. Складские площади предприятия ограничены, хранить можно не более М станков. Производственные мощности также ограничены, и в каждом месяце можно изготовить не более В станков.
Определите помесячную программу производства станков xt, удовлетворяющую спрос в каждом из месяцев квартала Dt и обеспечивающую минимальные затраты на производство станков и содержание их на складе до отправки потребителям. Запас продукции на складе на конец квартала примите равным нулю.