Дискретная модель управления запасами при заданном расходе. Метод динамического программирования

Управление запасами при заданном расходе

Процесс управления рассматривается как многошаговый разделенный на n – промежутков времени (дни, декады, месяцы и т.д.). В каждом из промежутков задан расход d k k = 1, n. Известны начальный и конечный уровень запасов, а также зависимость суммарных затрат на хранение от среднего уровня хранимых запасов и затрат на пополнение от величины их пополнения. Суммарные затраты складываются из затрат на хранение и пополнение. Требуется определить размеры пополнения запасов на каждом промежутке времени. Для обеспечения заданного расхода d k при минимальных суммарных затратах за весь планируемый период.

Обозначим размер пополнения запасов на каждом шаге x k, а уровень запасов в конце k-го шага x k, уровень запасов в начале каждого шага x k-1 тогда средний уровень запаса определяется: x _k‾ = x _k-1 + x _k/2

Основное балансовое уравнение: x _k = x _k-1 + x _k – d _k

Суммарные затраты на пополнение и хранение:

При этом должны быть минимизированы суммарные затраты на приобретение (покупку и транспортировку) и хранение материалов на складе.

Условия не отрицательности: x _{k ≥ 0}; x _k ≥ 0

Такого рода задачи при большом числе переменных (при больших n) и при нелинейности функции, это задача не может быть решена классическими методами, в особенности при целочисленных или дискретных x k. Поэтому для решения такого типа задач используется метод динамического программирования. Он используется если выполняется 2 условия: 1. Если эффективность всего процесса определяется как сумма пошаговых эффективностей. 2. Если выполняется свойство отсутствия последствия: Уровень запасов на каждом шаге будет зависеть только от пополнения и расхода принятого на этом шаге и не будет зависеть от других шагов.

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

1.определить на какое количество разделен процесс управления запасами.

2.для конкретно поставленной задачи выясняется, что есть состояние и что есть управление, определяется на какое число n шагов разбивается процесс; записываются уравнения состояния.

3.почти всегда весьма целесообразно «запроектировать» процесс решения представив его в виде графа, в виде схемы или каким либо другим образом это помогает сформулировать основные рекуррентные соотношения динамического программирования (уравнения Беллмана).

4.далее осуществляют условную оптимизацию обычно в форме специальных таблиц, «традиционным» при этом является развертывание процесса от конца к началу.

5.далее осуществляется безусловная оптимизация и определяется оптимальный процесс.

6.выдается анализ полученного решения (обычно на предмет единственности или не единственности решения) дается интерпретация полученных результатов в терминах поставленной задачи.