При k = 1 соотношение (4.7) примет вид
(4.8)или
. (4.9)Тогда с учетом (4.4) и (4.9) функция состояния
, (4.10)причем если не видно никаких ограничений на объем складских помещений и производственную мощность предприятия, то
, . (4.11)Это связано с тем обстоятельством, что если иметь на конец 1-го этапа запас изделий в качестве
, то, ничего не изготовляя в течение всего планового периода, а только удовлетворяя спрос, можно выйти на уровень запасов yn в конце n-го месяца. В то же время если уровень запасов на начало 1-го этапа равен y0, то, изготовив в 1-м месяце изделий в количестве и не производя ничего на последних этапах, получим тот же запас yn в конце планового периода. Если же на 1-м этапе предприятие может вместить готовой продукции не более М1 изделий, а мощности предприятия не позволяют произвести более N1 изделий, то , . (4.12)Получим рекуррентное соотношение динамического программирования в модели управления запасами при любом k = 2, …,n.
Запишем функцию состояния (4.5) в виде
. (4.13)Здесь, как уже было сказано выше, все переменные связаны балансовыми уравнениями
. (4.14)В связи с тем что величина запаса yk-1 к концу (k – 1)-го планового этапа с учетом (4.7) равна
, имеем следующее рекуррентное соотношение динамической модели управления запасами:Если внешних ограничений на уровни хранения и объемы производства не существует, то по аналогии с (4.11) получаем внутренние ограничения модели
, . (4.16)Если складские емкости и производственные мощности предприятия ограничены количеством изделий Mk и Nk соответственно, то аналогично соотношениям (4.12) имеем
, . (4.17)На самом деле ограничения (4.16) и (4.17) имеют более сложную структуру. Однако для решения практических задач этого вполне достаточно. Напомним лишь о том, что переменные xk и yk целочисленны и не отрицательны.
Рассмотрим теперь функцию затрат
. Введем следующие обозначения:gt – затраты на производство и доставку заказа на t-м этапе;
ct(xt) – затраты на производство xt единиц продукции на t-м этапе;
ht(yt) – затраты на хранение yt единиц продукции в течение t-го планового этапа.
Для определенности будем считать, что производственные затраты линейны, т.е. ct(xt) = ctxt, и что затраты на хранение пропорциональны объему хранимой продукции в течении месяца. Далее, уровень (объем) хранения в течение этого месяца определяется уровнем хранения на конец этапа. Иными словами, поскольку время изготовления партий изделий пренебрежимо мало, а производить и отправлять заказчикам продукцию предприятию выгодно вначале каждого месяца, то уровень хранимого имущества в течение t-го этапа определяется соотношением баланса
. В итоге получаем .Функция затрат с учетом выведенных обозначений примет вид
(4.18)Применим теперь метод динамического программирования к решению задачи управления запасами.
o Пример 6. Определение оптимальной программы производства
Рассмотрим плановый период работы предприятия, состоящий из трех месяцев: января, февраля, марта. Исходные данные сведены в таблице 1.
Таблица 1
Этап | k | 1 | 2 | 3 |
Месяц | Январь | Февраль | Март | |
Спрос | dk | 2 | 5 | 2 |
Затраты на оформление заказа | gk | 10 | 5 | 10 |
Затраты на производство одного изделия | ck | 3 | 5 | 3 |
Стоимость хранения одного изделия в течение месяца | hk | 2 | 2 | 1 |
Функция затрат определена формулой (4.18). Кроме того, будем считать, что предприятие не может производить более четырех изделий, а хранить – более трех, т.е. Mk = 3, Nk = 4, а уровень запасов y0 = y3 = 0.
Необходимо составить оптимальную программу выпуска продукции
, которая минимизирует суммарные издержки предприятия.Рассмотрим январский этап (k=1). Поскольку плановый период состоит из одного месяца, у нас практически нет возможности влиять на объем производства изделий. Поэтому все допустимые программы выпуска продукции будут оптимальны, поскольку они единственны.
Функция состояния в соответствии с (4.10) примет вид
.Прежде чем произвести расчеты
по формуле (4.18), укажем ограничения на изменения переменных x1 и y1. Поскольку уровни запасов на начало и конец планового периода равны нулю, то в январе мы можем произвести такое количество изделий, чтобы удовлетворять не только январский, но и февральский и мартовский спрос, т.е. произвести изделий, однако N1 = 4, поэтому . Возникает естественный вопрос: каков должен быть уровень запасов на конец января (или, что одно и то же, на начало февраля), чтобы, не изготавливая ничего ни в феврале, ни в марте, опять выйти на нулевой уровень запасов в конце марта? Ответ очевиден: объем запасов продукции должен быть равен . Но поскольку возможности склада ограничены , в итоге получаем: .Результаты вычислений сведем в табл. 2.
.Таблица 2
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.
Рекуррентное соотношение (4.15) примем вид
,где ξ – оптимальное значение уровня запасов y2 на конец второго этапа, которому соответствует наименьшие суммарные затраты на производство и хранение продукции.
Ограничения на объем производства и уровень хранения очевидны:
, .Отобразим в таблице 3 все необходимые вычисления для февральского этапа
.Таблица 3
x2 y2 | 0 | 1 | 2 | 3 | 4 | ||
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 соответственно. В верхнем правом углу каждой клетки указаны уровни запасов на начало второго этапа, которые с помощью балансового уравнения вычисляются по формуле
. Сумма внутри каждой клетки содержит три слагаемых. Рассмотрим эти слагаемые для клетки с координатами . Первое слагаемое – затраты на оформление заказа и производство продукции ; второе – затраты на хранение . Сумма двух первых слагаемых равна . Прежде чем вычислить третье слагаемое, которое в рекуррентном соотношении обозначено как , вспомним, что величина вычислена, находится в верхнем правом углу клетки и равна 0 – 3 + 5 = 2. Поэтому третье слагаемое возьмем из январской таблицы. Аналогично рассчитываются слагаемые в остальных клетках, а в «запрещенных» клетках, для которых не нашлось последнего слагаемого в январской (k = 1) таблице, сделан прочерк. Наименьшие суммарные затраты для каждого y2 запишем в последнем столбце (они подсчитаны в выделенных рамкой клетках), а значения оптимальных объемов производства изделий в феврале занесем в предпоследний столбец таблицы.