动态批量问题

动态批量问题（dynamic lot-sizing problem）在各期需求已知但不恒定时，联合决定什么时候订货、一次订多少。每次订货要付一笔固定费用，提前订货又会产生库存费；单独优化某一期，可能错过把相邻需求合成一批的机会。

考虑四周需求依次为 $3,2,4,1$ 件的教学模型。每次订货固定费五元，期末库存每件每周收一元；补货立即到达，没有容量限制和缺货，初、末库存均为零。单位采购价固定时，总采购数量必为十件，采购费对所有方案相同，以下只比较订货与持有费用。

用库存守恒写出模型

令 $q_t\ge 0$ 为第 $t$ 周初订量，$I_t\ge 0$ 为该周期末库存，$d_t$ 为需求。先补货再满足需求，因此 $$\begin{array}{cc}{I}_t& =I_{t-1}+q_t-d_t,\\ I_0& =I_T=0.\end{array}$$ 固定费 $K$ 仅在 $q_t>0$ 时发生，目标为 $\sum _{t=1}^T[K{\mathrm{𝟏}}_{\{q_t>0\}}+h{I}_t]$，其中 $h$ 是每件跨一个周期的库存费。本篇先取 $K,h\ge 0$ 为常数，需求确定且非负；提前期、产能上限和延期交货均暂不加入。

逐周订货的四笔固定费共二十元，库存费为零。若第一周把十件全部买来，期末库存为 $7,5,1,0$，费用为 $5+7+5+1=18$ 元。两种简单方案都可行，却还不是最便宜的方案。

一批货覆盖连续需求

在上述条件下，存在一个最优方案，使每次正订货之前库存为零。说明这一性质时，可以把货品逐件标记：若本周仍有旧货留到周初，且本周也在订货，就把尚未用掉的那部分旧货推迟到本周这笔订单。此前需求仍由已被消耗的货满足，本周及以后可用量不变；没有新开订单，旧订单还可能被取消，持有费用只会减少或不变。反复作这种调整，就得到所述结构。这个论证用到了固定采购单价和无限订量；有产能上限时推迟采购可能不可行。

因此一笔订单可以看成负责某段连续需求。若在第 $j$ 周订货，覆盖到第 $t$ 周，相关费用为 $$C(j,t)=K+h\sum _{r=j}^t(r-j)d_r.$$ 第 $r$ 周要用的 $d_r$ 件提前存放了 $r-j$ 周，故乘上该距离。整段需求为零时，无须实际订货，费用应为零。

递推与完整计算

记 $F(t)$ 为满足前 $t$ 周需求、结束时清空库存的最小费用，$F(0)=0$。最后一笔正订单从某个 $j$ 开始，前面必须已最优地解决前 $j-1$ 周，因此 $$F(t)=\underset{1\le j\le t}{min}\{F(j-1)+C(j,t)\}.$$ 任意结构化方案都落在其中一个分支，给出不小于右端的下界；反过来，取前段最优方案与这笔订单拼接，就得到右端对应的可行方案。向前归纳证明递推确实求得最优值，而非只给出一种启发式。

主例中 $F(1)=5$，$F(2)=min(7,10)=7$；第三周三种最后起点的费用为 $15,14,12$，所以 $F(3)=12$。第四周对应四个候选为 $18,16,13,17$，最小值为十三。回溯得第一周订五件、第三周再订五件。

柱高表示件数；第一笔订单覆盖前两周，第二笔覆盖后两周。订单不是每周需求的逐项复制。

订单后的期末库存为 $2,0,1,0$，故固定费为十元、库存费为三元，总费用十三元，和递推值一致。

图连接的是各周期末记账点；两段正库存分别对应提前一周存放的两件和一件货。

可复算实现与变式

下例输入非负有限需求、固定费和持有费，返回一组最优订单及相关费用，不修改输入。前缀需求和与“时期乘需求”的前缀和，使每段费用可用常数次运算求出；共检查 $T(T+1)/2$ 段，时间为 $O(T^2)$，额外空间为 $O(T)$。比较采用浮点数，接近相等的费用可能受舍入影响。

Python 3

import math

def dynamic_lots(demand, setup, holding):
    d = tuple(float(v) for v in demand)
    setup, holding = float(setup), float(holding)
    if any(not math.isfinite(v) or v < 0 for v in d + (setup, holding)):
        raise ValueError("finite nonnegative data required")
    n = len(d)
    p, w = [0.0], [0.0]
    for k, value in enumerate(d):
        p.append(p[-1] + value)
        w.append(w[-1] + k * value)
    f, previous = [0.0] + [math.inf] * n, [0] * (n + 1)
    for t in range(1, n + 1):
        for j in range(t):
            quantity = p[t] - p[j]
            cost = 0.0 if quantity == 0 else setup + holding * (
                w[t] - w[j] - j * quantity)
            if f[j] + cost < f[t]:
                f[t], previous[t] = f[j] + cost, j
    orders, t = [], n
    while t:
        j = previous[t]
        quantity = p[t] - p[j]
        if quantity > 0:
            orders.append((j + 1, quantity))
        t = j
    return list(reversed(orders)), f[n]

print(dynamic_lots([3, 2, 4, 1], 5, 1))
# ([(1, 5.0), (3, 5.0)], 13.0)

变式。 固定费降到每次二分之一元，持有费仍为一元时，逐周订货只需两元。任何把正需求提前存放一周的方案至少多付一元，却至多省下二分之一元，因此逐周订货最优。需求全为零或没有周期时，代码返回空订单、零费用。

容量约束、随时间变化的采购价、损耗或批量折扣会改变段费用与结构证明。使用相同的库存守恒式，并不保证还能使用这条无容量动态规划。