Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

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

Динамические задачи управления запасами. Одной из наиболее известных сфер приложения методов динамического программирования является такая область математической экономики, как теория управления запасами. Ее предметом является разработка и исследование математических моделей систем, занимающих промежуточное положение между источниками (производителями) тех или иных ресурсов и их потребителями. При математической формализации процессов управления запасами очень часто приходится использовать скачкообразные, недифференцируемые и кусочно-непрерывные функции. Как правило, это обусловливается необходимостью учета эффектов концентрации, фиксированных затрат и платы за заказ. В связи с этим получаемые задачи с трудом поддаются аналитическому решению классическими методами, однако могут быть успешно решены с помощью аппарата динамического программирования. Рассмотрим достаточно типичную задачу, возникающую в процессе планирования деятельности системы снабжения, — так называемую динамическую задачу управления запасами.

Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения:

yk — остаток запаса после (k-1)-го периода;

dk — заранее известный суммарный спрос в k-м периоде;

хk — заказ (поставка от производителя) в k-м периоде;

сk (хk) —затраты на выполнение заказа объема xk в k-м периоде;

skk) — затраты на хранение запаса объема ξk в k-м периоде.

После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξk = yk + хk - dk . Учитывая смысл параметра yk , можно записать соотношение:

Расходы на получение и хранение товара в период k описываются функцией

Планом задачи можно считать вектор х = (х1, х2, ..., хn), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:

Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x*k и связанных с ними оптимальных состояний (запасов) ξ*k , которые обращают в минимум (5.25). В качестве начального условия используем требование о сохранении после завершения управления заданного количества товара yn+1 , а именно

При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы Λk(ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k-й период имеется запас ξ . Тогда можно записать основное рекуррентное соотношение

поскольку

Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений 1(ξ), 2(ξ), …, n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*n = n (yn+1). Остальные значения оптимальных управлений x*k определяются по формуле:

Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса сk(хk) являются вогнутыми по хk , а функции затрат на хранение skk) являются линейными относительно объема хранимого запаса, т. е. skk) = skξk . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.

Обозначим функцию затрат в течение k-ro периода через

или, что то же самое,

В силу сделанных предположений все функции затрат fk (xk , yk+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk , yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:

при условиях

Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функций fk(xk , yk+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:

где

С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что при оптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение

где ξ = уk+1= хk + уk - dk .

Учитывая (5.34)-(5.35) и вогнутость fk (xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk поэтому

тогда для предыдущего периода функция состояния может быть выражена как

на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения

При дальнейших конкретизирующих предположениях о виде функций fk (xk , уk+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов.