1. Задача управления запасами как пример задачи динамического программирования
2) Предполагается, что на конец последнего отрезка времени N уровень запасов равен 0.
3) Условие полного и своевременного удовлетворения спроса в пределах каждого отрезка времени обеспечивается двумя следующими ограничениями:
Первое — балансовое: уровень запасов на конец отрезка t, равен уровню запасов на начало отрезка t плюс выпуск продукции в течение отрезка t и минус спрос на продукцию в течение отрезка времени t:
Второе – целочисленность уровня запасов:
Таким образом, модель адекватна поставленной задаче.
Заметим, что на практике функция затрат Ct (xt , it) чаще всего бывает нелинейна. Так, при выпуске партии изделий могут потребоваться дорогостоящие затраты, например затраты на пуск и наладку оборудования, поэтому затраты на производство первой единицы партии могут превышать затраты на производство остальных единиц партии. Например, если объем производства превышает мощность производственного участка, то дополнительные затраты на единицу изделия увеличиваются за счет использования сверхурочных работ.
1.2. Задача управления запасами в динамической форме
Рассмотрим N – количество отрезков времени. N = 6, Плановый период —это: Январь, Февраль,… Июнь. В этой постановке конечное состояние – это начало последнего отрезка планового периода, для нас 1 июня. Исходное состояние – начало первого отрезка ( когда впереди N шагов).
Будем использовать систему индексов, при которой подстрочный индекс «1» соответствует конечному состоянию, а подстрочный индекс «N» соответствует начальному состоянию.
Обозначим «dn» — спрос на продукцию на отрезке времени, отстоящем от конца планового периода на n шагов, включая рассматриваемый:
Обозначим Cn(х, i) – затраты на отрезке времени, отстоящем от конца на n шагов, связанные с выпуском х единиц продукции и затратами на хранение запасов, уровень которых на конец отрезка равен i единиц. Так, С3 (10, 15) – затраты на производство в апреле 10 единиц продукции и хранение запасов, уровень которых на 30 апреля составит 15 единиц.
В этой системе обозначений
d1 = DN, dN = D1,
C1(х, i) = CN(х, i)
Например, N =4 тогда, если рассматриваем программу с начала год, то
d4 = D1 – январский спрос;
d1 = D4 – апрельский спрос.
Состояние системы в начале любого отрезка, определяется уровнем запаса на начало отрезка. Для принятия решения об объеме выпуска в текущем отрезке времени не требуется знать, каким образом достигнут уровень запасов на начало отрезка. Учитывая это, введем обозначения:
— минимальные затраты на n оставшихся отрезков, при начальном уровне запасов i.
Например, f2 (10) – минимальные затраты на май и июнь, при условии, что на 1 мая у нас 10 единиц запасов.
— выпуск продукции, обеспечивающий достижение .
Согласно условию (3) уровень запасов на конец планового периода равен нулю. Поэтому
f0 (0) = 0 (6) (здесь n = 0)
Рассмотрим случай n = 1 – это начало последнего отрезка времени. Начальный уровень запасов здесь i , может быть любым неотрицательным целым числом не большим чем d1 (спрос на этом отрезке), чтобы запас на конец отрезка был равен нулю.
Запишем условие (4) для этого отрезка:
(т.е. 0 = i1 + x1 − d1)
Независимо от значения i спрос в последнем отрезке времени полностью удовлетворяется при объеме выпуска равным .
(i = 0,1,2…d1)
Перейдем к n = 2. Если начальный уровень запасов равен i (для 1 мая) n = 2, то общие затраты для двух последних месяцев (с 1 мая по 30 июня) составят:
— оптимальные затраты на июнь
— уровень запасов на конец предпоследнего или начало последнего периода.
Величина запаса i для n = 2 (запас на 1 мая) может принимать любые неотрицательные целые значения не превосходящие d1 + d2, чтобы на конец планового периода уровень i был равен 0.
При заданном i величина х должна быть не меньше чем (d2 – i), что обеспечивает полное удовлетворение спроса на предпоследнем отрезке . В то же время величина х не должна быть больше чем , т.к. конечный запас равен нулю.
Для нахождения минимума перебираются все неотрицательные целые значения х в интервале .
Аналогично вычисляется — если известно и в конце концов мы вычислим , где i0 – уровень запасов на начало всего планового периода i0 в рассматриваемом примере – на 1 января.
Рекуррентное соотношение для вычисления оптимальной стоимости затрат можно записать так:
где n = 1, 2, 3 ,…, N;
х – неотрицательная целочисленная величина, лежащая в пределах
Замечание: Так как начальный уровень запасов i рассматривается как переменная величина, полностью характеризующая состояние системы, то единственной независимой управляющей переменной в рекуррентном соотношении (8) является х, так как уровень запасов на конец отрезка равен (i = x — dn).
Схема всего алгоритма решения задачи управления запасами такова:
Далее определяется, какой объем выпуска позволяет достичь это оптимальное значение , то есть определяем оптимальный объем выпуска продукции, когда начальный запас равен i0 в первом периоде (для нашего примера в январе) и, далее находим и т.д.
В этом случае уровень запасов на начало второго отрезка равен
Далее находим объем выпуска для второго отрезка и т.д.
Таким образом можно сделать следующие выводы:
1. Процесс принятия решений в задаче управления запасами рассматривается как многошаговый.
2. N обозначает число шагов (число отрезков планового периода)
Если N = 4, то n = 1 – это апрель
3. Уровень запасов на начало отрезка времени является характеристикой системы за n шагов до конца планового периода.
4. Если известно состояние запасов на начало отрезка, то легко найти оптимальный объем выпуска для этого периода. При этом уже найден оптимальный выпуск на предыдущем шаге.
1. Задача управления запасами как пример задачи динамического программирования
2) Предполагается, что на конец последнего отрезка времени N уровень запасов равен 0.
3) Условие полного и своевременного удовлетворения спроса в пределах каждого отрезка времени обеспечивается двумя следующими ограничениями:
Первое — балансовое: уровень запасов на конец отрезка t, равен уровню запасов на начало отрезка t плюс выпуск продукции в течение отрезка t и минус спрос на продукцию в течение отрезка времени t:
Второе – целочисленность уровня запасов:
Таким образом, модель адекватна поставленной задаче.
Заметим, что на практике функция затрат Ct (xt , it) чаще всего бывает нелинейна. Так, при выпуске партии изделий могут потребоваться дорогостоящие затраты, например затраты на пуск и наладку оборудования, поэтому затраты на производство первой единицы партии могут превышать затраты на производство остальных единиц партии. Например, если объем производства превышает мощность производственного участка, то дополнительные затраты на единицу изделия увеличиваются за счет использования сверхурочных работ.
1.2. Задача управления запасами в динамической форме
Рассмотрим N – количество отрезков времени. N = 6, Плановый период —это: Январь, Февраль,… Июнь. В этой постановке конечное состояние – это начало последнего отрезка планового периода, для нас 1 июня. Исходное состояние – начало первого отрезка ( когда впереди N шагов).
Будем использовать систему индексов, при которой подстрочный индекс «1» соответствует конечному состоянию, а подстрочный индекс «N» соответствует начальному состоянию.
Обозначим «dn» — спрос на продукцию на отрезке времени, отстоящем от конца планового периода на n шагов, включая рассматриваемый:
Обозначим Cn(х, i) – затраты на отрезке времени, отстоящем от конца на n шагов, связанные с выпуском х единиц продукции и затратами на хранение запасов, уровень которых на конец отрезка равен i единиц. Так, С3 (10, 15) – затраты на производство в апреле 10 единиц продукции и хранение запасов, уровень которых на 30 апреля составит 15 единиц.
В этой системе обозначений
d1 = DN, dN = D1,
C1(х, i) = CN(х, i)
Например, N =4 тогда, если рассматриваем программу с начала год, то
d4 = D1 – январский спрос;
d1 = D4 – апрельский спрос.
Состояние системы в начале любого отрезка, определяется уровнем запаса на начало отрезка. Для принятия решения об объеме выпуска в текущем отрезке времени не требуется знать, каким образом достигнут уровень запасов на начало отрезка. Учитывая это, введем обозначения:
— минимальные затраты на n оставшихся отрезков, при начальном уровне запасов i.
Например, f2 (10) – минимальные затраты на май и июнь, при условии, что на 1 мая у нас 10 единиц запасов.
— выпуск продукции, обеспечивающий достижение .
Согласно условию (3) уровень запасов на конец планового периода равен нулю. Поэтому
f0 (0) = 0 (6) (здесь n = 0)
Рассмотрим случай n = 1 – это начало последнего отрезка времени. Начальный уровень запасов здесь i , может быть любым неотрицательным целым числом не большим чем d1 (спрос на этом отрезке), чтобы запас на конец отрезка был равен нулю.
Запишем условие (4) для этого отрезка:
(т.е. 0 = i1 + x1 − d1)
Независимо от значения i спрос в последнем отрезке времени полностью удовлетворяется при объеме выпуска равным .
(i = 0,1,2…d1)
Перейдем к n = 2. Если начальный уровень запасов равен i (для 1 мая) n = 2, то общие затраты для двух последних месяцев (с 1 мая по 30 июня) составят:
— оптимальные затраты на июнь
— уровень запасов на конец предпоследнего или начало последнего периода.
Величина запаса i для n = 2 (запас на 1 мая) может принимать любые неотрицательные целые значения не превосходящие d1 + d2, чтобы на конец планового периода уровень i был равен 0.
При заданном i величина х должна быть не меньше чем (d2 – i), что обеспечивает полное удовлетворение спроса на предпоследнем отрезке . В то же время величина х не должна быть больше чем , т.к. конечный запас равен нулю.
Для нахождения минимума перебираются все неотрицательные целые значения х в интервале .
Аналогично вычисляется — если известно и в конце концов мы вычислим , где i0 – уровень запасов на начало всего планового периода i0 в рассматриваемом примере – на 1 января.
Рекуррентное соотношение для вычисления оптимальной стоимости затрат можно записать так:
где n = 1, 2, 3 ,…, N;
х – неотрицательная целочисленная величина, лежащая в пределах
Замечание: Так как начальный уровень запасов i рассматривается как переменная величина, полностью характеризующая состояние системы, то единственной независимой управляющей переменной в рекуррентном соотношении (8) является х, так как уровень запасов на конец отрезка равен (i = x — dn).
Схема всего алгоритма решения задачи управления запасами такова:
Далее определяется, какой объем выпуска позволяет достичь это оптимальное значение , то есть определяем оптимальный объем выпуска продукции, когда начальный запас равен i0 в первом периоде (для нашего примера в январе) и, далее находим и т.д.
В этом случае уровень запасов на начало второго отрезка равен
Далее находим объем выпуска для второго отрезка и т.д.
Таким образом можно сделать следующие выводы:
1. Процесс принятия решений в задаче управления запасами рассматривается как многошаговый.
2. N обозначает число шагов (число отрезков планового периода)
Если N = 4, то n = 1 – это апрель
3. Уровень запасов на начало отрезка времени является характеристикой системы за n шагов до конца планового периода.
4. Если известно состояние запасов на начало отрезка, то легко найти оптимальный объем выпуска для этого периода. При этом уже найден оптимальный выпуск на предыдущем шаге.