Skip to content

Математическая формулировка задачи

v2020.12.23

Базовая модель:

  • бинарные (0 или 1) переменные для каждого заказа (приняли/отклонили)
  • отгрузка продукции - это принятые заказы
  • объем производства ограничен сверху мощностью
  • запасы для каждого дня - это накопленное производство минус накопленная отгрузка
  • запасы неотрицательные
  • объем склада не ограничен
  • срок хранения каждого продукта ограничен
  • максимизиурем выручку минус затраты в деньгах
  • связанные продукты - для производства одного продукта нужны другие продукты
  • в ц.ф. добавляем штраф на величину запасов

(May change order in list above)

0. Размерность (время и продукты)

0.1 Мы решаем задачу отбора заказов и планирования выпуска на горизонте \(n_{days}\) дней

\[ t = 1, ... n_{days} \]

0.2 Мы рассматриваем производство четырех продуктов, которым присвоены буквенные обозначения.

\[ p \in [A, B, C, D] \]

1. Производство, отгрузка, запасы

1.1 Производство

\(prod_{pt}\) - объем производства продукта p в день t, тонн

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

На основе объемов производства рассчитываются затраты:

\[ costs = \sum_p \sum_t prod_{pt} \cdot unit\_cost_p \]

1.2 Отгрузка

\(ship_{pt}\) - отгрузка продукта p в день t, тонн

Рассчитывается исходя из выбранных заказов (см. ниже).

1.3 Совокупный объем использования

\(req_{pt}\) - требуемый объем использованием продукта p в день t, тонн

Он рассчитывается исходя из матрицы полных затрат. Расчет описан здесь, можем представить в виде матриц:

\(B_{ij}\) - количество единиц товара \(j\), напрямую необходимых для выпуска единицы товара \(i\) (матрица прямых затрат).

\(R_{ij}\) - количество единиц товара \(j\), непосредстванно или косвенно необходимых для выпуска единицы товара \(i\) (матрица полных затрат).

\(R = (I-B)^{-1}\)

Если \(y = [y_A, y_B, y_C, y_D]\) - вектор-строка с количеством каждого продукта для продажи, то \(x = yR\) - полный выпуск каждого продукта с учетом внутреннего потребления.

\[ \forall t: req_{t} = ship_{t}^T \cdot R \]

Пример:

from numpy import array, identity, matmul
from numpy.linalg import inv

B = array([[0. , 0. , 0. ],
           [0.1, 0. , 0. ],
           [0. , 1.2, 0. ]])
R = inv(identity(3) - B)
# array([[ 1.  ,  0.  ,  0.  ],
#        [ 0.1 ,  1.  , -0.  ],
#        [ 0.12,  1.2 ,  1.  ]])
y = array ([1, 1, 1])
x = matmul(y, R)
# array([1.22, 2.2 , 1.  ])

1.5 Запасы

\(inventory_{pt}\) - запасы продукта p в конец дня t, тонн

Запасы определяются как разница между накопленной суммой производства и накопленным использованием:

\[inventory_{pt} = cumsum(prod, t) - cumsum(ship, t)\]
\[cumsum(x_t, t^*) = \sum_{t=1}^{t^*}x_{t}\]

2. Заказы

2.1 Структура данных заказа

Завод на весь период планирования получает \(n_{orders}\) заказов на различные продукты:

\[order_k = [product_k, day_k, volume_k, price_k]\]
\[k = 1, ... n_{orders}\]

В каждом заказе указаны (k - порядковый номер заказа):

  • продукт \(product_k\), который заказан
  • объем поставки \(volume_k\) (тонн)
  • день поставки \(day_k\)
  • цена поставки \(price_k\) (долл. США за тонну)

2.2 Переменные выбора заказа

Для каждого заказа создается бинарная переменная accept, которая показывает решение принимать заказ или нет:

\[ accept_k \in (0, 1) \]

2.3 Расчеты на основе заказов

Объем поставок:

\[ ship_{pt} = \sum_{k\vert_{day_k=t}^{product_k = p}}accept_k \cdot volume_k \]

Объем продаж:

\[ sales = \sum_k accept_k \cdot volume_k \cdot price_k \]

3. Ограничения

3.1 Мощность

Ежедневный объем производства неотрицательный и ограничен сверху мощностью

\[0 \leq prod_{pt} \leq capacity_p\]

3.2 Запасы неотрицательные

\[inventory_{pt} \geq 0\]

3.3 Закрытая сумма за период

Сумма производства равна сумме отгрузки для каждого продукта:

\[\forall p: \sum_t prod_{pt} = \sum_t req_{pt} \]

Комментарий: возможно, это ограничение становится незначимо после введения ограничений на минимизацию запасов.

3.4 Ограничение срока хранения

Запасы на день d не должны превышать использования продукта за следующие \(s_p\) дней, где \(s_p\) - это максимальный срок хранения p продукта на складе.

\[inventory_{pd} \le \sum_{t = d+1}^{d+s_p} req_{pt}, s_p \ge 1 \]
\[inventory_{pd} = 0, если s_p = 0 \]

Комментарий: в первое неравенство можно подставить срок хранения s=1, тогда остаток на складе должен быть не больше объема следующего дня использования (\(req_{p,d+1}\))

Ключевые слова: shelf life, product life, "условие непротухания".

4. Целевая функция

\[(sales - costs - \lambda \cdot inventory)\to max\]

\(\lambda \cdot inventory\) - штраф, позволяющий минимзировать запасы. \(\lambda\) берется меньше цены продукта.

5. Результат расчетов

  • \(prod_{pt}\) - объем производства по дням
  • \(accept_{k}\) - бинерные переменные выбора заказов

Возможные изменения

  • разные варианты целевых функций
  • матричная форма записи
  • сроки производства продукта более 1 дня
  • веса для штрафа по запасам пропорциональны цене