基于线性规划的分布式鲁棒优化中Wasserstein模糊集下多阶段库存管理问题的求解示例

我来为你讲解一个结合了分布式鲁棒优化、Wasserstein模糊集以及多阶段决策的库存管理问题。这个问题在供应链管理中非常重要，因为它考虑了需求的不确定性，并且使用Wasserstein距离来度量概率分布的模糊性，比传统的鲁棒优化更加精细。

问题描述

假设一个零售商销售单一产品，需要制定一个T期的库存管理计划。

已知参数：

• 计划期：T个时间段（t=1,2,...,T）
• 单位采购成本：c_t（第t期）
• 单位库存持有成本：h_t
• 单位缺货惩罚成本：p_t（或单位销售价格，代表缺货机会损失）
• 初始库存：I_0
• 每期需求：d_t，是一个随机变量，其真实概率分布P*未知。

决策变量（第t期）：

• x_t：采购量（非负）
• I_t：期末库存量（可为负，负值表示未满足的需求积累为缺货量）

目标：最小化总期望成本，包括采购成本、库存持有成本和缺货惩罚成本。

核心挑战：我们不知道需求d_t的真实分布P*。我们只知道一些历史需求数据样本，并假设真实分布P*位于一个以经验分布为中心的“Wasserstein球”内。这比简单的箱型不确定集更能捕捉分布的几何形状。

问题建模与求解过程（循序渐进）

步骤1：经典多阶段随机规划的基准模型

如果我们知道需求的真实分布P*，这就是一个经典的多阶段随机线性规划问题。

模型 (SP)：

Minimize  E_P* [ Σ_{t=1}^T ( c_t * x_t + h_t * [I_t]⁺ + p_t * [ -I_t ]⁺ ) ]
Subject to:
    I_t = I_{t-1} + x_t - d_t,  ∀t  (库存平衡方程)
    x_t ≥ 0, I_t ∈ R, ∀t
    [I_t]⁺ = max(0, I_t),  [-I_t]⁺ = max(0, -I_t)

这里E_P*表示关于真实分布P求期望。但P未知，所以此模型不可直接求解。

步骤2：引入分布式鲁棒优化（DRO）框架

我们不假设已知P*，而是假设它属于一个模糊集（Ambiguity Set） D。我们寻求最坏情况（Worst-case）下的最优决策，即最小化最大期望成本。

模型 (DRO)：

Minimize_{x, I}   Sup_{P ∈ D}  E_P [ Σ_{t=1}^T ( c_t * x_t + h_t * [I_t]⁺ + p_t * [ -I_t ]⁺ ) ]
Subject to:
    库存平衡方程（同上）
    x_t 需满足非预期性约束（Non-anticipativity）：第t期的决策x_t只能依赖于前t-1期已实现的需求信息。

这里的 Sup（上确界）就是最大化，即考虑模糊集D中“最坏”的那个分布P。

步骤3：定义Wasserstein模糊集

我们使用1-型Wasserstein距离来定义模糊集D。假设我们有N个历史需求样本 {d̂^1, d̂^2, ..., d̂^N}，对应的经验分布为P_N。

Wasserstein距离 W1(P, Q) 定义为：
W1(P, Q) = inf_{Π} ∫ ||ξ - ζ|| Π(dξ, dζ)，其中下确界取自所有边缘分布为P和Q的联合分布Π。直观上，它表示将一个分布“搬土”变成另一个分布的最小“移动成本”。

Wasserstein模糊集定义为：
D = { P : W1(P, P_N) ≤ ε }
其中，ε > 0 是预算（Radius），反映了决策者对历史数据可靠性的怀疑程度。ε=0则退化为仅相信经验分布（即随机规划），ε越大则表示考虑的不确定性范围越广。

步骤4：将DRO模型转化为可求解形式（关键步骤）

对于具有线性目标（在随机参数上）和Wasserstein模糊集的问题，存在一个强对偶定理，可以将内部的最大化问题（Sup）转化为一个有限维的凸优化问题。这是Wasserstein DRO的一大优点。

转换过程简述：

1. 成本函数线性化：目标函数中的 [I_t]⁺ 和 [-I_t]⁺ 是关于需求d_t的分段线性函数（通过库存平衡方程，I_t 线性依赖于历史需求）。我们可以引入辅助变量将其线性化。
2. 应用对偶理论：对于形如 Sup_{P: W1(P, P_N)≤ε} E_P [ f(d) ] 的问题，其对偶形式为：

   Inf_{λ ≥ 0} { λ * ε + (1/N) * Σ_{i=1}^N Sup_{d ∈ Ξ} [ f(d) - λ * ||d - d̂^i|| ] }
   

   其中，Ξ是需求的支撑集（例如，非负实数集），||·||是Wasserstein距离中用的范数（常取L1范数）。
3. 针对具体问题的应用：在我们的库存问题中，f(d) 是关于多期需求向量 d=(d1,...,dT) 的分段线性凸函数。将上述对偶形式代入原DRO模型，我们得到一个两层的极小化极大化问题。

步骤5：进一步转化为单层线性规划

由于内层的 Sup_{d ∈ Ξ} [ ... ] 是针对一个分段线性凸函数减去一个L1范数惩罚项求极大值，且 Ξ 通常是一个多面体集合（如 d_t ≥ 0），这个内层极大化问题可以通过对每个样本i分别求解一个线性规划来完成。

最终得到的等价确定性问题：
这本质上是一个大规模的线性规划问题。

Minimize_{x_t, I_t, λ, η_i, s_t^i, o_t^i, z_t^i}
    λ * ε + (1/N) * Σ_{i=1}^N η_i

Subject to:
    ** 对于所有时期 t (t=1,...,T) **
    I_t = I_{t-1} + x_t - d_t^* (???) // 注意！这里需求是未知的，约束必须对所有可能的需求场景成立。
    x_t ≥ 0

    ** 对于每个历史样本 i (i=1,...,N) 和每个时期 t **
    // 我们需要用决策规则来关联决策和需求。在线性决策规则(LDR)近似下，我们假设采购量x_t是前期需求的线性函数。
    // 更实用的方法是采用“仿射决策规则（Affine Decision Rules, ADR）”。
    // 令 x_t = X_{t0} + Σ_{τ=1}^{t-1} X_{tτ} * d_τ，其中X_{tτ}是新的决策变量。
    // 代入库存平衡方程，I_t 也成为需求的仿射函数。

    // 对于每个样本i，计算其对应的成本上界约束：
    η_i ≥ Σ_{t=1}^T [ c_t * x_t^i + h_t * s_t^i + p_t * o_t^i ] - λ * Σ_{t=1}^T z_t^i
    // 其中 s_t^i = [I_t^i]⁺, o_t^i = [-I_t^i]⁺，需要线性化：
    s_t^i ≥ I_t^i,  s_t^i ≥ 0
    o_t^i ≥ -I_t^i, o_t^i ≥ 0
    // 并且，z_t^i 用于线性化L1范数惩罚项 ||d^i - d||_1。假设我们考虑的扰动是当期独立的。
    // 引入辅助变量 u_t^i, v_t^i ≥ 0，使得：
    d_t^i - d_t = u_t^i - v_t^i,  z_t^i = u_t^i + v_t^i
    // d_t 是内层Sup优化中的变量（对每个样本i独立），需要满足 d_t ∈ Ξ（例如 d_t ≥ 0）。
    // 同时，x_t^i, I_t^i, s_t^i, o_t^i 是通过决策规则，由这个特定的 d_t 计算出来的。

    ** 非预期性约束通过决策规则的结构自然满足**：x_t 只依赖于t-1期及之前的需求实现。
    λ ≥ 0, η_i ∈ R, 所有其他变量非负。

这个模型看起来很庞大，但结构清晰：外层最小化 λ 和 η_i，内层（已通过对偶消除）体现为对每个样本i的一组约束，这些约束确保了对于该样本邻域内最坏的需求情景，成本被 η_i 所控制。

步骤6：求解与解释

1. 输入数据：给定成本参数 (c, h, p)，历史需求样本集 {d̂^i}， Wasserstein半径 ε。
2. 建模：构建上述线性规划模型。决策变量包括：
   • 策略系数（如果使用仿射决策规则）：如 X_{tτ}。
   • 鲁棒性控制变量：λ（对应Wasserstein预算的拉格朗日乘子）。
   • 场景成本上界变量：η_i（每个样本对应一个）。
   • 辅助线性化变量：s, o, u, v, z。
3. 调用求解器：使用线性规划求解器（如CPLEX, Gurobi, 或开源GLPK）求解这个大规模LP。
4. 输出结果：
   • 最优仿射决策规则：x_t^* = X_{t0}^* + Σ_{τ=1}^{t-1} X_{tτ}^* * d_τ。这是一个可执行的策略：在实际运营中，每期观察到前期实际需求后，即可按此公式计算当期采购量。
   • 最坏情况期望成本：目标函数最优值。
5. 灵敏度分析：可以调整 ε 观察策略变化：
   • ε = 0：模型退化为基于经验分布的随机规划（样本平均近似，SAA）。策略相对激进。
   • ε 增大：模型考虑更多分布不确定性，策略趋于保守（通常会提高基线库存 X_{t0}）。
   • ε → ∞：模型退化为经典的（非分布式的）鲁棒优化，极度保守，可能只针对极端最坏情况优化。

总结与意义

通过以上步骤，我们将一个含有Wasserstein模糊集的多阶段分布式鲁棒库存管理问题，转化为了一个大规模的确定性线性规划问题进行求解。这个方法的优势在于：

1. 数据驱动：直接利用历史数据（样本），无需假设参数分布族。
2. 控制保守度：通过Wasserstein半径 ε，在随机规划（过于乐观）和经典鲁棒优化（过于保守）之间平滑地权衡。
3. 计算可处理性：得益于强对偶理论，最终模型是线性规划，尽管规模大，但现代商业求解器可以处理中等规模的问题。
4. 决策规则：采用仿射决策规则将多阶段动态问题静态化，虽然是一种近似，但对于许多实际问题效果良好且可求解。

这个示例展示了现代优化理论如何将随机性、动态性、分布模糊性等复杂因素整合到一个统一的线性规划框架中，为复杂环境下的决策提供强大的支持工具。