Программные продукты и системы

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

Пусть имеется некоторая система снабжения (склад, оптовая база и т.п.), планирующая свою работу на n периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю этого продукта. Спрос конечных потребителей в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться. Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью и временем между заказом и его выполнением можно пренебречь. Введем обозначения: yk – остаток запаса после (k–1)-го периода; dk – заранее известный суммарный спрос в k-м периоде; xk – заказ (поставка от производителя) в k-м периоде; ck(xk) – затраты на выполнение заказа объема xk в k-м периоде; sk(xk) – затраты на хранение запаса объема xk в k-м периоде. После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит . Учитывая смысл параметра yk, можно записать соотношение:

.                            (1)

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

.                                           (2)

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

.                                                               (3)

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

   (4)

поскольку yk=x -xk+dk>0 , и

.                        (5)

Система рекуррентных соотношений (4)–(5) позволяет найти последовательность функций состояния ,,…,  и условных оптимальных управлений , ,…, . На n-м шаге с помощью начального условия (3) можно определить . Остальные значения оп­тимальных управлений  определяются по формуле:

.                           (6)

Особый интерес представляет частный случай задачи (1)–(2), при котором предполагается, что функции затрат на пополнение запаса ck(xk) являются вогнутыми по xk, a функции затрат на хранение sk(xk) являются линейными относительно объема хранимого запаса, то есть . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.

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

,                                (7)

или .                          (8)

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

                     (9)

при условиях

.                            (10)

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

,                                               (11)

где                                                (12)

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

,  (13)

где .

Учитывая (11)–(12) и вогнутость fk(xk,x), заключаем, что минимум (13) достигается в одной из крайних точек xk = 0 или xk=x + dk, поэтому

,           (14)

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

         (15)

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

                            (16)

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