一罐可乐

1. 资源分配问题#

2. 设备负荷分配问题（连续变量）#

• 问题描述：某种机器可在高、低两种不同的负荷下生产。
  • 高负荷：年产量 $g(u) = 8u$（$u$ 为机器台数），年完好率（回收率） $a = 0.7$。
  • 低负荷：年产量 $h(y) = 5y$（$y$ 为机器台数），年完好率（回收率） $b = 0.9$。 设第一年年初完好机器数 $s_1 = 1000$ 台。求 5 年内如何安排负荷，使总产量最高。
• 模型构建： 设 $s_k$ 为第 $k$ 年初完好的机器数，$u_k$ 为当年分配到高负荷生产的机器数，则有： $s_{k+1} = 0.7 u_k + 0.9(s_k - u_k) = 0.9 s_k - 0.2 u_k$ $\text{递推方程： } f_k(s_k) = \max_{0 \le u_k \le s_k} \{ 8 u_k + 5(s_k - u_k) + f_{k+1}(0.9 s_k - 0.2 u_k) \}$
• 逆推求解过程：
  • $k=5$：$f_5(s_5) = \max \{ 8u_5 + 5(s_5 - u_5) \} = 8s_5$ （最优决策 $u_5^* = s_5$）。
  • $k=4$： $f_4(s_4) = \max_{0 \le u_4 \le s_4} \{ 3u_4 + 5s_4 + 8(0.9s_4 - 0.2u_4) \} = \max \{ 12.2s_4 + 1.4u_4 \} = 13.6s_4 \quad (\text{最优决策 } u_4^* = s_4)$
  • $k=3$：同理求得 $u_3^* = s_3$，$f_3(s_3) = 19.32s_3$。
  • $k=2$： $f_2(s_2) = \max \{ 3u_2 + 5s_2 + 19.32(0.9s_2 - 0.2u_2) \} = \max \{ 22.388s_2 - 0.864u_2 \} = 22.388s_2 \quad (\text{此时最优决策为低负荷：} u_2^* = 0)$
  • $k=1$：同理求得 $u_1^* = 0$，$f_1(s_1) = 23.7s_1$。
• 结论：最优策略为前两年完好机器全部用于低负荷生产，后三年全部用于高负荷生产。在初始 $s_1 = 1000$ 台机器时，5 年内最大总产量为 23,700 台。

3. 多期生产与存储问题#

• 问题描述：企业面临 4 个月的交货合同。

  • 参数限制：生产能力上限为 4 千件/月，仓库最大容纳 3 千件。
  • 成本结构：产品生产成本为 $C(x) = F + C \cdot x$（$F$ 为每次开工的生产准备固定费 4000 元，$C$ 为变动成本 5000 元/千件）；每千件产品每月的保管费 $H = 300$ 元。
  • 库存与交货：期初已有存货 3 千件，要求 4 月底完成交货后的剩余库存为 2 千件。各月交货合同需求量为：2, 3, 2, 2 千件。求总运营费用最低的生产计划。

  月份 ($k$)	1	2	3	4
  需求量 $d_k$（千件）	2	3	2	2

• 动态规划模型：

  • 状态变量 $S_k$：第 $k$ 月期初的产品库存量。
  • 决策变量 $x_k$：第 $k$ 月的产量。
  • 状态转移方程：$S_{k+1} = S_k + x_k - d_k$。
  • 费用递推公式： $f_k(S_k) = \min_{x_k} \{ C_k(x_k) + H \cdot S_{k+1} + f_{k+1}(S_{k+1}) \}$

• 求解结论：经过逆序查表递推，最优生产计划为：

  • 第 1 月生产 0 千件，第 2 月生产 4 千件，第 3 月生产 0 千件，第 4 月生产 4 千件。
  • 该方案完全满足各期交货限制，且使全期总生产和保管费用达到最低：49,800 元。

4. 随机性决策：不确定采购问题#

• 问题描述：某厂在未来 5 周内必须采购到一批原料。价格每周发生波动，估计价格和出现的概率分布如下表。要求制定采购策略，使采购单价的数学期望值最小。

  原料单价 ($y_k$)	出现概率
  500	0.3
  600	0.3
  700	0.4

• 模型构建：

  • 状态变量 $y_k$：表示第 $k$ 周的市场实际报价。
  • 决策变量 $x_k$：$x_k=1$ 表示采购；$x_k=0$ 表示继续等待。
  • 期望值递推方程： 设 $y_k^E$ 为第 $k$ 周若选择等待，则在后续周采取最优决策下的采购价格期望值。 $f_k(y_k) = \min(y_k, y_k^E)$ $y_k^E = E[f_{k+1}(y_{k+1})] = 0.3 f_{k+1}(500) + 0.3 f_{k+1}(600) + 0.4 f_{k+1}(700)$ 边界条件：第 5 周必须购买，因此 $y_5^E = \infty \implies f_5(y_5) = y_5$。

• 计算推导：

  • $k=5$：$E[f_5] = 0.3(500) + 0.3(600) + 0.4(700) = 610$ 元。
  • $k=4$：等待期望 $y_4^E = E[f_5] = 610$。 $f_4(y_4) = \min(y_4, 610) \implies f_4(500)=500, f_4(600)=600, f_4(700)=610$ $E[f_4] = 0.3(500) + 0.3(600) + 0.4(610) = 574$
  • $k=3$：等待期望 $y_3^E = E[f_4] = 574$。 $f_3(y_3) = \min(y_3, 574) \implies f_3(500)=500, f_3(600)=574, f_3(700)=574$ $E[f_3] = 0.3(500) + 0.7(574) = 551.8$
  • $k=2$：$y_2^E = E[f_3] = 551.8 \implies E[f_2] = 0.3(500) + 0.7(551.8) = 536.26$。
  • $k=1$：$y_1^E = E[f_2] = 536.26$。

• 最优决策策略结论：

  • 在第 1、2、3 周：若市场价格为 500 则买入；若为 600 或 700 则选择等待。
  • 在第 4 周：若市场价格为 500 或 600 则买入；若为 700 则等待。
  • 在第 5 周：无论价格是多少都必须买入。
  • 按此策略执行，采购单价的最低期望值为 536.26 元。

5. 背包问题（Knapsack Problem）#

• 多阶段决策划分：以装入背包的物品种类作为阶段，按 $k = 1, \dots, n$ 顺序递推。
• 状态变量 $w$：表示可供分配给第 1 种到第 $k$ 种物品的最大承重限额。
• 决策变量 $x_k$：第 $k$ 种物品的装入数量。
• 允许决策集：$0 \le x_k \le \lfloor w / w_k \rfloor$。
• 递推关系式： $f_k(w) = \max_{0 \le x_k \le \lfloor w / w_k \rfloor} \{ c_k(x_k) + f_{k-1}(w - x_k w_k) \}$ （若为二维背包，状态变量需增加体积维度 $v$，递推方程为 $f_k(w, v)$）。

复习思考题#

1. 对于多期生产与存储决策问题，在什么情况下适合使用动态规划算法，而在什么情况下适合采用线性规划（LP）建模？ 请对比分析两者的建模复杂度和对成本函数的适用范围（如包含固定开工成本）。
2. 不确定采购问题的决策具有怎样的风险与收益折衷？ 如果第 1 周的原料报价为 600 元，为什么最优决策是选择“等待”而不是立即买入？
3. 请解释二维背包问题的动态规划状态转移方程的构建思路。与一维背包问题相比，增加体积维度会导致计算复杂度发生怎样的变化？（介绍维度灾难概念）。