5. Задача управления производством и запасами

Предприятие производит партиями некоторые изделия. Оно получило заказы на nмесяцев. Необходимо составить план производства на указанныеnмесяцев с учетом затрат на производство и хранение. Обозначим:

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

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

производимых в j-й месяц, величина запаса к началу 1-го месяца (y₁) и к концу

последнего (y_n+1) заданы);

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

4) - функция затрат на производствоx_jизделий вj-м месяце (может

иметь и другой вид);

5) h_j– затраты на хранение единицы запаса, переходящей из месяцаjв месяц (j+1);

6) - функция затрат на производство и хранение вj-м месяце.

Задача состоит в определении плана производства (х₁,х₂,…,х_n), компоненты которого удовлетворяют условиям материального баланса

x_j+y_j–d_j=y_j+1

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

.

По смыслу , ,. Заметим, что:

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

,

то есть объем производимой продукции x_jвj-м месяце может быть настолько

велик, что запас y_j+1удовлетворяет спрос на всех последующих месяцах, но не

имеет смысла иметь y_j+1больше суммарного спроса всех последующих месяцев;

2) из балансового уравнения получим .

Если учесть, что x_j и y_jдолжны быть целыми и неотрицательными, то имеем задачу целочисленного нелинейного программирования.

Составим функциональные уравнения. Пусть F_k(y_k+1) - минимальные затраты за

первые k месяцев.

Для k = 1:

при и . На начальном этапе при фиксированном значенииy₁исходного запаса каждому значениюy₂отвечает только одно значениеx₁.

Для k 2 :

при , и .

Применив процедуру динамического программирования, на последнем шаге k=nопределяется значениеx_n* оптимального решения, а остальные компоненты определяются в результате прямого хода по формуле

.