单纯形法（二）：初始基与特殊情形

普通单纯形法要求起点已经是基本可行解。但含 $\ge$ 或 $=$ 约束时，松弛变量不一定能直接组成单位阵，于是需要先“制造一个起点”。

人工变量为什么有用

例如

$$x_1+x_2\ge2$$

写成

$$x_1+x_2-s_1+a_1=2,\qquad s_1,a_1\ge0.$$

$a_1$ 的列可作为初始基列。它不属于原问题，算法必须最终把它压到零并移出基。

大 $M$ 法

最小化问题给人工变量一个巨大惩罚：

$$\min c^Tx+M\sum_i a_i,\qquad M>0\text{ 足够大}.$$

然后把 $M$ 当符号做单纯形迭代。若最优表中仍有正的人工变量，原问题不可行。

大 $M$ 法适合手算，但数值实现不宜真的取一个极大浮点数，否则会放大舍入误差。

两阶段法

第一阶段暂时丢开原目标，求

$$\min w=\sum_i a_i.$$

• 若第一阶段最优值 $w^*>0$，原问题不可行；
• 若 $w^*=0$，删掉人工变量列，以当前基作为第二阶段初始基，换回原目标继续求解。

第一阶段结束时若某个人工变量为零但仍在基中，应尽量用一个原变量列做零步长换基；若该行除人工列外全为零，则相应等式可能冗余。

四类特殊情形

不可行

两阶段法第一阶段无法把人工变量和降到零。几何上，各约束没有公共交集。

无界

存在能改善目标的进基变量，但其变换后列没有正元素，无法通过比值检验限制步长。无界指目标能无限改善，不是可行域一定在所有方向都无界。

退化

某个基本变量为零。比值检验可能得到 $\theta^*=0$，换基后几何点不变，目标值也不变。连续退化换基可能循环；Bland 规则可保证有限终止。

多重最优

到达最优表后，若某个非基变量检验数为零，它进基不会改变目标值，通常意味着存在另一最优极点以及连接它们的最优边。

冗余约束与秩

若约束行线性相关，$A$ 不满行秩。此时可能出现人工变量为零却无法换出的行。应先判断该行是否由其他行线性组合得到；若是，可删除冗余约束，但答题时要说明原因，不能悄悄删行。

考试要点

• $\ge$ 约束通常是“减剩余变量，再加人工变量”。
• 大 $M$ 法中人工变量惩罚符号取决于 min/max，先统一目标方向。
• 第一阶段最优值为零只说明找到原问题可行点，不说明已经对原目标最优。
• 区分“无界”和“不可行”：前者有可行点但目标没下界，后者连可行点都没有。