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

Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу. Поэтому иногда лучше выполнять одной партией заказы нескольких месяцев, а затем хранить изделия, пока они не потребуются, чем выполнять заказ в тот именно месяц, когда этот заказ должен быть отправлен. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение изделий. Обозначим:

x_j - число изделий, производимых в j -й месяц;

y_j - величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);

d_j - число изделий, которые должны быть отгружены в j -й месяц;

f_j (x_j,y_j+1) - затраты на хранение и производство изделий в j -м месяце.

Будем считать, что величины запасов к началу первого месяца y₁ и к концу последнего y_n+1 заданы.

Задача состоит в том, чтобы найти план производства (x₁, x₂, ..., x_n)

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

x_j + y_j - d_j = y_j+1 j = 1,n

и минимизируют суммарные затраты за весь планируемый период

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d₁=3 единицы, на второй – d₂=2, на третий - d₃=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y₁=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁=5, h₂=4, h₃=0. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

j_j(x_j) = 4x_j² + 5x_j , т.е. а=4; b=5; с=0.

Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

Исходные данные задачи можно кратко записать одной строкой:

d₁ d₂ d₃ a b c h₁ h₂ h₃ y₁

3 2 1 4 5 0 5 4 0 2

Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F₁ (x = y₂), F₂ (x = y₃), ..., F_k (x = y_k+1), ... и соответственно находим

₁ (x= y₂), ₂ (x = y₃ ), ..., ` _k (x = y_k+1), ...

Положим k = 1. Тогда

Параметр состояния x = у₂ может принимать целые значения на отрезке

0 у₂ d₂ + d₃ 0 y₂ 2 + 1 т.е. у₂ = 0, 1, 2, 3.

При этом каждому значению параметра состояния должна отвечать определенная область изменения переменной x₁, 0 х₁ 3 + у₂

Однако, на первом этапе объем производства х₁ не может быть меньше единицы, так как спрос d₁ = 3, а исходный запас у₁ = 2. Более того, из балансового уравнения х₁ + у₁ - d₁ = у₂ непосредственно следует, что объем производства связан со значением параметра состояния x= у₂ соотношением x₁ = y₂ + d₁ - y₁ = y₂ + 3 - 2 = y₂ +1

Если задан уровень запаса к началу первого этапа, то каждому значению у₂ отвечает единственное значение х₁ и потому F₁(x = y₂) = W₁ (x₁, y₂)

Придавая у₂ различные целые значения от 0 до 3, находим

y₂ = 0, x₁ = 0+1 = 1, W₁ (1;0) = 4×1² + 5×1 + 1×0 = 10

y₂ = 1, x₁ = 1+1 = 2, W₁ (2;1) = 4×2² + 5×2 + 1×1 = 27

y₂ = 2, x₁ = 2+1 = 3, W₁ (3;2) = 4×3² + 5×3 + 1×2 = 53

y₂ = 3, x₁ = 3+1 = 4, W₁ (4;3) = 4×4² + 5×4 + 1×3 = 87

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F₂(x = y₃)

Здесь минимум берется по единственной переменной х₂, которая может изменяться в пределах 0 £ x₂ £ d₂ + y₃ или 0 £ x₂ £ 2 + y₃, где верхняя граница зависит от параметра состояния x = у₃, который принимает значения на отрезке 0 £ y₃ £ d₃ , т.е. 0 £ y₃ £ 1,

а аргумент у₂ связан с х₂ и у₃ балансовым уравнением x₂ + y₂ - d₂ = y_{3 ,}

откуда следует y₂ = y₃ + d₂ - x₂ = y₃ + 2 - x₂

Придавая параметру состояния значения 0 и 1, будем последовательно вычислять W₂ (x₂, x), а затем определять F₂(x ) и ₂(x ).

Пусть x = у₃ = 0. Тогда 0 £ x₂ £ 2, т.е. переменная х₂ может принимать значения: 0, 1, 2, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле у₂ = 0 + 2 - х₂

Последовательно находим:

если x₂ = 0, то y₂ = 2 – 0 = 2, W₂ (0,0) = 4×0² + 5×0 + F₁(2) = 53,

x₂ = 1, y₂ = 2 – 1 = 1, W₂ (1,0) = 4×1² + 5×1 + F₁(1) = 9 + 27 = 36,

x₂ = 2, y₂ = 2 – 2 = 0, W₂ (2,0) = 4×2² + 5×2 + F₁(0) = 26 + 10 = 36,

Наименьшее из полученных значений W₂ есть F₂ (0), т.е.

F₂ (x = y₃ = 0) = min W₂ (x₂,0) = min (53, 36, 36) = 36,

x₂

причем минимум достигается при двух значениях х₂, равных ` ₂ (x = y₃ = 0) = 1 или 2.

Пусть x = у₃ = 1. Тогда 0 £ x₂ £ 3, т.е. переменная х₂ может принимать значения: 0, 1, 2, 3.

Последовательно находим:

если x₂ = 0, то y₂ = 3 – 0 = 3, W₂ (0,1) = 4×0² + 5×0 + 4×1 + F₁(3) = 4 + 87,

x₂ = 1, y₂ = 3 – 1 = 2, W₂ (1,1) = 4×1² + 5×1 + 4×1 + F₁(2) = 13 + 53 = 66,

x₂ = 2, y₂ = 3 – 2 = 1, W₂ (2,1) = 4×2² + 5×2 + 4×1 + F₁(1) = 30 + 27 = 57,

x₂ = 3, y₂ = 3 – 3 = 0, W₂ (3,1) = 4×3² + 5×3 + 4×1 + F₁(0) = 51 + 10 = 61

Наименьшее из полученных значений W₂ есть F₂ (1), т.е.

F₂ (x = y₃ = 1) = min W₂ (x₂,1) = min (87, 66, 57, 61) = 57,

x₂

причем минимум достигается при значении х₂, равном ` ₂ (x = y₃ = 1) = 2.

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F₃ (x = y₄):

Вычисляем значение функции состояния только для одного значения аргумента x = у₄ = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода.

0 £ x₃ £ d₃ + y₄ или 0 £ x₃ £ 1 + y₄, 0 £ x₃ £ 1 , y₃ = y₄ + d₃ – x₃ = 1 – x₃

Пусть x₃ = 0, y₃ = 1 – 0 = 1: W₃ (0,0) = 4×0² + 5×0 + F₂(1) = 36,

x₃ = 1, y₃ = 1 – 1 = 0, W₃ (1,0) = 4×1² + 5×1 + F₂(0) = 9 + 36 = 45,

Получаем F₃ (x = y₄ =0) = min W₃ (x₃,0) = min (36, 45) = 36, минимум достигается при значении переменной х₃, равной ` ₃ (x = y₄ = 0) = 0.

Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна = 0.

Чтобы найти предпоследнюю компоненту, учтем, что х₃ + у₃ - d₃ = y₄ или 0 + у₃ - 1 = 0,

oткуда у₃ = 1. Находим

Учитывая, что x₂ + y₂ – d₂ = y₃ или 0 + y₂ – 2 = 1, y₂ = 3 ,

Таким образом, оптимальный план производства имеет вид х₁ = 4, х₂ = 0, х₃ = 0, а минимальные общие

затраты составляют 36 единиц.

Полезна самопроверка полученного результата. Для этого по исходным данным и найденному плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом этапе выполняются

у₁ + х₁ ³ d₁ у₂ + х₂ ³ d₂ у₃ + х₃ ³ d₃

2 + 4 ³ 3 3 + 0 ³ 2 1 + 0 ³ 1

и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности

у₁ + х₁ + х₂ + х₃ = d₁ + d₂ + d₃

2 + 4 + 0 + 0 = 3 + 2 + 1