第 8 周作业：单纯形表与灵敏度分析

本周作业主要是教材编号 9、10、12 一组单纯形表与灵敏度题。原 PDF 只有 Lee 的手算过程，以下保留可辨认模型、参数分段和结论，并补全每类变化的判断依据。

第 9 题：由基矩阵读出最优解

源作答先计算

\bar b=B^{-1}b=\begin{bmatrix}2/3\\10/3\end{bmatrix},

并从当前基构造单纯形表，再换基得到

(x_1,x_2,x_3)=(2,0,0)^T,\qquad f^*=-4.

随后把某个目标系数改为 $c_1'$ ，逐列要求新检验数非正，得到当前基保持最优的范围

c_1'\le-1.

这类题的要点是：基变量目标系数变化会同时改变多个检验数，必须对所有非基列求范围交集。

原模型可辨认为

\begin{aligned} \max\quad &-5x_1+5x_2+13x_3\\ \text{s.t.}\quad &-x_1+x_2+3x_3+x_4=20,\\ &12x_1+4x_2+10x_3+x_5=90,\\ &x\ge0. \end{aligned}

初始迭代得到 $x=(0,20,0)$ 、目标 $100$ 。作答依次讨论：

改变非基变量 $x_3$ 的目标系数：只更新该列检验数；若仍满足最优符号，解不变。
改变右端使 $B^{-1}b=(30,-30)^T$ ：原基失去可行性，但检验数未变，用对偶单纯形得到新解，扫描记录为 $(0,0,9)^T$ 、目标 $117$ 。
另一组右端使 $B^{-1}b=(20,70)^T$ ：当前基仍可行，继续读解或换基，扫描记录目标 $90$ 。
新增变量：计算新列检验数；扫描中检验数为正，因此原解改变。
新增约束后追加一行，用对偶单纯形修复，扫描记录目标 $95$ 。

具体数值受手写表约定影响，使用时应以原表的检验数定义为准。

题中模型可辨为

\begin{aligned} \min\quad &-x_1-3x_2\\ \text{s.t.}\quad &x_1+x_2+x_3=6,\\ &-x_1+2x_2+x_4=6,\\ &x\ge0. \end{aligned}

原问题最优解为

(x_1,x_2,x_3,x_4)=(2,4,0,0),\qquad f^*=-14.

右端改为 $(6-\lambda,6+\lambda)^T$ 后，在原基下

x_B(\lambda)=(2-\lambda,4)^T.

因此 $0\le\lambda\le2$ 时基可行且检验数不变，

x=(2-\lambda,4,0,0),\qquad f^*=-14+\lambda.

$2\le\lambda\le6$ 时换基后扫描记录

x=(0,6-\lambda,0,-6+3\lambda),\qquad f^*=-18+3\lambda.

$\lambda>6$ 时原问题不可行。