第11章 综合例题讲解与解析

例1 线性规划：建模、求解与预算削减

题目。 冰淇淋店做三种口味，每杯的配料成本、人工成本和包装材料如下；每天包装材料最多 10 kg，配料支出不超过 100 元，人工成本不超过 30 元。三种口味每杯利润分别为 2.5、2.3、2.0 元。(a) 建立利润最大的模型；(b) 每天各做多少杯；(c) 老板想削减人工预算，最多能削减多少，而(b)的方案仍可行？

(a)

(b) 加松弛变量 $s_1,s_2,s_3$，化为最小化 $-z$。

表 0：检验行 $(-2.5,\ -2.3,\ -2,\ 0,0,0\ |\ 0)$。$x_1$ 进基，比值 $10/0.2=50$、$100/1.5=66.7$、$30/0.5=60$，$s_1$ 出基。

表 1：

$x_2$ 的检验数 −1/20 仍为负，$x_2$ 进基；比值 $50\div\frac{9}{10}=55.6$、$25\div\frac{7}{20}=71.4$，$x_1$ 出基。

表 2：

检验行全部非负。线性规划最优解：只做巧克力 $x_2=500/9\approx55.6$ 杯，利润 $1150/9\approx127.8$ 元。只有包装材料是紧约束（影子价格 $115/9\approx12.8$ 元/kg）。

上述是允许产量连续变化的线性规划解。实际按整杯生产时，需要另加整数约束：简单取整为 55 杯巧克力，利润为 126.5 元；精确的整数最优方案是 52 杯巧克力 + 4 杯草莓，利润 127.6 元（包装恰好 $9.36+0.64=10$ kg）。直接取整不保证整数最优。

(c) 对连续产量的最优解，人工成本只用了 $0.35\times500/9=175/9\approx19.44$ 元，人工约束的松弛 $s_3=95/9\approx10.56$。人工预算从 30 降到 $175/9$ 之前，当前解都可行，最多削减约 10.56 元。用第3章的语言：右端变化 $\Delta$ 时 $s_3$ 变成 $95/9+\Delta$，要求 $\ge0$，即 $\Delta\ge-95/9$。若采用整杯最优方案 $(0,52,4)$，人工成本为 $0.35\times52+0.6\times4=20.6$ 元，可削减的预算相应为 9.4 元。

例2 含等式约束的单纯形法与目标系数灵敏度

题目。 (a) 用单纯形法求 $\min\ z=2x_1+3x_2$，s.t. $3x_1-2x_2\le3$，$8x_1+4x_2=5$，$x_1,x_2\ge0$。(b) 目标变为 $2x_1+(3+\Delta)x_2$ 时，$\Delta$ 在什么范围内(a)的解仍最优？(c) 若问题是最大化型，第一阶段中人工变量的目标系数应如何取？

(a) $3x_1-2x_2+s_1=3$，$8x_1+4x_2+a_1=5$，初始基 $(s_1,a_1)$。检验行拆成常数行和 M 行：

M 行最负 −8，$x_1$ 进基；比值 $3/3=1$、$5/8$，$a_1$ 出基：

人工变量已出基（删去该列和 M 行），常数行全部非负，最优：**$x_1=5/8,\ x_2=0$，$z=5/4$**。

(b) $x_2$ 是非基变量，只影响它自己的检验数：$2+\Delta\ge0$，即 **$\Delta\ge-2$**（$c_2\ge1$）时解不变；$c_2$ 增大不会改变最优解。

(c) 最大化问题中人工变量取 $-M$（目标越大越好，人工变量越大越被惩罚）；若先把目标乘 $-1$ 化为最小化，则取 $+M$。第一阶段等价于最小化人工变量之和，与原问题是最大还是最小无关。

例3 运输问题与运价灵敏度

题目。 三个工厂向三个地区供货（箱），单位运费如下。(a) 写成平衡运输问题；(b) 用 Vogel 法求初始解并求最优解；(c) 工厂 3 到地区 3 的运费变化 $\Delta$，求当前解保持最优的范围。

(a) 总供应 180 = 总需求 180，已平衡：$\min\sum c_{ij}x_{ij}$，$\sum_jx_{ij}=s_i$，$\sum_ix_{ij}=d_j$，$x_{ij}\ge0$。

(b) Vogel 法：

基格 5 个 $=3+3-1$。$z=24\cdot55+24\cdot5+20\cdot70+20\cdot40+25\cdot10=3890$。

位势（$u_1=0$）：$v_2=24,\ v_3=24,\ u_2=-4,\ u_3=1,\ v_1=19$。非基格检验数：格(1,1) $=1$，(2,1) $=3$，(2,2) $=3$，(3,3) $=1$，全部为正。Vogel 初始解已经最优，最小运费 3890。

(c) 格(3,3) 是非基格，位势不变，只需 $1+\Delta\ge0$：**$\Delta\ge-1$**，即运费不低于 25 时方案不变（低于 25 改走这条线路更便宜）。

例4 生产—库存问题

题目。 某器材 11 月—2 月的需求为 100、200、180、300 套，各月产能 50、180、280、270 套，生产成本 40 元/套。提前生产要付保管费，每套每月 0.5 元；延期交货要付罚金，每套每月 2 元。求最优生产计划。

产能合计 780 = 需求合计 780，平衡。运价 $c_{ij}$ = 40 + 保管或罚金：

Vogel 法依次分配：格(4,4)=270、(1,1)=50、(2,1)=50、(2,2)=130、(3,2)=70、(3,4)=30、(3,3)=180，共 7 个基格。位势检验所有非基格检验数 $\ge0$（格(3,1) 为 0，存在另一个同样最优的方案），最小总成本 31455 元。

计划解读：

例5 不平衡且有禁止格的指派问题

题目。 4 人 5 项任务，“—”表示此人不能做此任务。求总成本最小的指派。

“—”记为 $M$，加虚拟人 P5（成本全 0）。行化简（减 15、16、11、12；P5 不变），列最小值全为 0：

P2、P3 都只在 J3 有 0，最多 4 个独立的 0。最少 4 条线：P1、P4、P5 三行和 J3 列。未覆盖的最小元素为 1（P2→J5、P3→J1），未覆盖减 1、交叉加 1：

最优指派：P1→J2，P2→J3，P3→J1，P4→J5，J4 无人承担。总成本 $15+16+12+12=55$。

例6 拉格朗日乘子：两个等式约束与右端扰动

题目一。 $\min\ f=x_1^2+x_2^2+x_3^2$，s.t. $x_1+x_2+3x_3=2$，$5x_1+2x_2+x_3=5$。

解出 $x$ 用 $\lambda$ 表示后代入两条约束：

得 $\lambda_1=-\tfrac{2}{23}$，$\lambda_2=-\tfrac{7}{23}$，于是

$\nabla^2_{XX}L=2I$ 正定，是极小点（也是全局最小：凸目标 + 线性约束）。

题目二。 $\min\ f=3x_1^2+2x_2^2+\tfrac12x_3^2$，s.t. $x_1+x_2=15$，$x_3=1$。(a) 求最优解；(b) 第一条约束改为 $x_1+x_2=15+\Delta$，最优值约变化多少？

(a) $6x_1+\lambda_1=0$，$4x_2+\lambda_1=0$，$x_3+\lambda_2=0$。由前两式 $x_2=1.5x_1$，代入 $x_1+x_2=15$ 得 $x_1=6,\ x_2=9$，$x_3=1$；$\lambda_1=-36,\ \lambda_2=-1$。$f^*=108+162+0.5=270.5$。

(b) $\Delta f^*\approx-\lambda_1\Delta=36\Delta$。精确值 $f^*(\Delta)=270.5+36\Delta+1.2\Delta^2$，小 $\Delta$ 时二次项可忽略。

例7 容器设计

题目。 设计有盖长方体容器装 98 cm³ 化学粉末，长 $x_1$ 与高 $x_2$ 之比必须为 2.5，宽为 $x_3$，材料 10 元/cm²。(a) 建立成本最小的模型；(b) 用拉格朗日乘子求尺寸和最低成本。

(a)

(b) 用 $f=x_1x_2+x_1x_3+x_2x_3$（成本 $=20f$）。$L=f+\lambda_1(x_1x_2x_3-98)+\lambda_2(x_1-2.5x_2)$：

令 $x_2=t$，$x_1=2.5t$。第三式：$3.5t+2.5\lambda_1t^2=0\Rightarrow\lambda_1=-\tfrac{1.4}{t}$。第一式乘 2.5 加第二式消去 $\lambda_2$：

容积：$2.5t\cdot t\cdot\tfrac{10}{7}t=\tfrac{25}{7}t^3=98$，$t^3=27.44$，$t=\sqrt[3]{27.44}\approx3.016$。

尺寸：长 $x_1\approx7.54$ cm，高 $x_2\approx3.02$ cm，宽 $x_3\approx4.31$ cm。表面积 $2f\approx136.46$ cm²，最低成本约 1364.6 元。

例8 离散时间马尔可夫链：只在售罄时补货

题目。 店里每次进 3 块豪华手表，只有全部卖完才在下月初再进 3 块。每月需求 $D_k$ 独立，服从 $\lambda=1$ 的泊松分布；$L_k$ 为第 $k$ 月底剩余块数，$L_0=3$。(a) 写出状态空间和转移概率矩阵（用 $e$ 表示）；(b) 求各状态的平均逗留时间（3 位小数），哪个状态停留最短；(c) 若每次进 $m$ 块（$m>3$），写出状态空间和转移概率。

(a) 状态空间 $\{0,1,2,3\}$。月初库存：月底为 0 → 3；为 1 → 1；为 2 → 2；为 3 → 3。用“从库存 $s$ 卖到剩 $j$”：$j\ge1$ 时 $P(D=s-j)$，$j=0$ 时 $P(D\ge s)$。

(b) $E(T_i)=1/(1-p_{ii})$：

状态 0（售罄）停留最短：一旦售罄就会补货，下个月几乎总有剩余。

(c) 状态空间 $\{0,1,\dots,m\}$。$i\ge1$ 时月初库存为 $i$：

$i=0$ 时月初库存为 $m$，第 0 行与第 $m$ 行相同：$p_{0j}=\dfrac{e^{-1}}{(m-j)!}\ (1\le j\le m)$，$p_{00}=1-\sum_{k=0}^{m-1}\dfrac{e^{-1}}{k!}$。

例9 连续时间马尔可夫链：工作流程的速率

题目。 化妆师的工作：去客户家（速率 2/小时）→ 给新娘化妆（速率 3）→ 给新娘母亲化妆（速率 3）→ 去下一位客户。每次化妆中眼线可能花掉（速率 0.5），需要重画（速率 1），重画后继续原来的化妆。各时间独立且服从指数分布。状态：0 路上，1 新娘化妆，2 母亲化妆，3 新娘重画，4 母亲重画。求稳态概率和平均每小时完成的化妆数，并与只给新娘化妆的情况比较。

转移速率：$0\to1$：2；$1\to2$：3，$1\to3$：0.5；$3\to1$：1；$2\to0$：3，$2\to4$：0.5；$4\to2$：1。

速率平衡：

于是 $\pi_1=\pi_2=\tfrac23\pi_0$，$\pi_3=\pi_4=\tfrac13\pi_0$，$\pi_0(1+\tfrac23+\tfrac23+\tfrac13+\tfrac13)=1$，$\pi_0=\tfrac13$：

平均化妆速率 $=3\pi_1+3\pi_2=\tfrac43$ 次/小时。只给新娘化妆时（三状态：路上、化妆、重画），稳态为 $(\tfrac12,\tfrac13,\tfrac16)$，化妆速率 $3\times\tfrac13=1$ 次/小时。一次出行做两个人，路上的时间被分摊，化妆速率提高到 $4/3$（但每小时服务的客户家庭数从 1 降到 $2/3$）。

例10 排队：三种设计与汽修店

题目一。 食堂卖三类饭菜，到达为泊松过程、服务为指数分布。系统 1：三个窗口各卖一类，各自排队，每队到达率 $\lambda/3$、服务率 $\mu$；系统 2：一个窗口卖全部，到达率 $\lambda$、服务率 $3\mu$；系统 3：三个窗口都能卖全部，共用一条队（取号），到达率 $\lambda$、每窗口服务率 $\mu$。(a) 写出模型和 $W_i$，稳定条件；(b) $\lambda=\mu=1$ 时排序；(c) 一般情况下排序。

(a) 系统 1：三个 M/M/1，$W_1=\dfrac{1}{\mu-\lambda/3}=\dfrac{3}{3\mu-\lambda}$。系统 2：M/M/1，$W_2=\dfrac{1}{3\mu-\lambda}$。系统 3：M/M/3，代入第9章公式化简得

三者稳定条件都是 $0<\lambda<3\mu$（$\mu>0$）。

(b) $\lambda=\mu=1$：$W_1=\tfrac32=1.5$，$W_2=\tfrac12=0.5$，$W_3=\dfrac{18+6-1}{2(1+4+6)}=\tfrac{23}{22}\approx1.045$。排序 $W_2<W_3<W_1$。

(c) 两个比值的分母在稳定范围内都为正。比较分子与分母之差：

所以 $W_2<W_3<W_1$：一个快窗口的总停留时间最短，分开排队最长。这里的比较依赖“合力服务速率确实达到 $3\mu$”这一假设。

题目二。 汽修店每天来 10 辆车（泊松），3 名技师。A：每人独立修一辆，速率 6/天，共用一条队；B：三人合修一辆，速率 18/天。比较 L、Q、W、D 并给出建议。

A 是 M/M/3（$\rho=5/9$），B 是 M/M/1（$\rho=5/9$）：

B 的总停留时间短（合修更快），A 的排队等候短（更少需要排队）。车主最在意“多久能取车”，即 $W$，所以建议 B——前提是三人合作确实能把速度提高到 3 倍。

例11 决策树：最终资产及其概率

题目。 钻石贸易公司现有资产 2000（千元），一批原石要卖给客户，运费 50。不切割直接运：53% 被接受，利润 300（扣成本前）。切割（成本 75）：切得好的概率 70%，此时接受率 80%；切得不好时接受率只有 12%，但可以再花 25 抛光，抛光后接受率 90%。被拒收时只承担已发生的成本。求使期望最终资产最大的策略、可能的最终资产及概率、最可能的最终资产。

回推：

• 不切割：$0.53\times(2000+300-50)+0.47\times(2000-50)=0.53\times2250+0.47\times1950=2109$。
• 切割、切得好：$0.8\times(2300-75-50)+0.2\times(2000-75-50)=0.8\times2175+0.2\times1875=2115$。
• 切割、切得不好：直接运 $0.12\times2175+0.88\times1875=1911$；抛光 $0.9\times(2175-25)+0.1\times(1875-25)=0.9\times2150+0.1\times1850=2120$。选抛光。
• 切割的期望：$0.7\times2115+0.3\times2120=2116.5>2109$。

最优策略：切割；切得不好就抛光。 期望最终资产 2116.5。

最可能的最终资产是 2175（概率 0.56）。

例12 效用与 Hurwicz 准则

题目一。 某人有 10000 元，要买机票去开会。廉价票 300 元，有 5% 的概率严重延误，错过会议造成额外损失 2500 元；灵活票 $300+p$ 元，保证不会错过会议。效用函数 $u(x)=\sqrt{x/10000}$，$x$ 为最终财富。他最多愿付的升级费 $p$ 是多少？

最多愿付约 133.8 元，高于期望损失 $0.05\times2500=125$ 元，差额 8.8 元是风险溢价。

题目二。 四种生意在三种发展情景下的回报率（%）：便利店 (8, 12, 20)，理发店 (7, 11, 21)，咖啡店 (9, 13, 25)，补习中心 (6, 12, 30)。用悲观、乐观、Laplace、后悔和 Hurwicz 准则决策。

Hurwicz：$H_{\text{便利店}}=8+12K$，$H_{\text{理发店}}=7+14K$，$H_{\text{咖啡店}}=9+16K$，$H_{\text{补习}}=6+24K$。咖啡店在 $[0,1]$ 上始终高于便利店和理发店，只需比较咖啡店与补习中心：$9+16K=6+24K\Rightarrow K=3/8$。

总结：拿到题先想三件事

1. 这是哪一类模型？ 线性目标 + 线性约束 → 线性规划；供需表 → 运输；一人一事 → 指派；有平方、乘积 → 非线性规划；“每期”“每天” + 随机需求 → 离散时间马尔可夫链；指数时间、速率 → 连续时间马尔可夫链或排队；收益表 + 情景 → 决策分析。
2. 状态、变量、约束写全了吗？ 隐含的非负、平衡、容量限制最容易漏。
3. 结果合理吗？ 代回约束、检查概率和为 1、用 Little 公式交叉验证、看最优值是否随参数朝合理方向变化。