单纯形法每次换基,都会改变所使用的基,却不一定改变可行点。如果所有算例的比值检验步长都大于零,这个差别很容易被忽略:目标值每步严格增加,自然不能回到旧基。然而,在退化点上,一个值已经是零的基变量可以离基。即使进基变量的约化成本为正,目标值仍可能保持不变。
较早的单纯形笔记用字典序扰动证明了终止性。Bland 规则采取另一种方法:保留原问题,始终按变量的固定编号作选择。规则本身很短,但其证明揭示进基和离基的选择为何必须配合。本节会直接证明这种配合,避免把零步长也错当成目标严格改善。
基、它代表的点,以及主元方向
考虑有限维标准形式问题
其中 的行秩为 。假设已经找到一个可行起始基。把所有变量固定编号为 ,包括松弛变量及模型中的其他变量。这些编号不会随表格的行次序改变。
定义 15.1.1
(以变量编号标记的字典式)
基是由 个列编号组成的集合 ,使基矩阵 非奇异。把基列按一致次序排列,并用 表示其补集。解出基变量后得到
这里 、、,而 。标记为 的行,是以 为基变量的那一行。令 便得到基本点;若每个 ,这个基就是可行基。
不同的基可以代表同一个点,因为某个零坐标可能在一个字典式中是基变量,在另一个字典式中却是非基变量。基记录要解出哪些列所对应的变量;点则记录全部变量的数值。若可行基至少有一个基变量的值为零,就称该基为退化;它代表的点便少于 个正坐标。循环是经过非空的一串主元步后回到同一个基。
设 且 。把 从零增加,同时把其他非基变量固定为零,所得方向 为
它满足 及 。比值检验所允许的步长是
如果没有任何 ,则 的所有基坐标均非负。因此,对每个 ,点 都可行,而且目标值趋向正无穷。否则,上述最小值可以取得;把其中一个取到最小值的基列换成 ,就得到另一个非奇异可行基。事实上,在原基坐标下,替换矩阵的行列式除列次序所造成的正负号外,就是非零的 。目标值增加 ,只有在 时才可能没有增加。
定义 15.1.2
(Bland 规则的两个选择)
在每个可行字典式中:
- 若所有非基约化成本均满足 ,便在最优解停止。否则,选取满足 的最小编号 进基。
- 若进基列没有正的字典式系数,便以上述改善射线停止。否则,进行比值检验,让所有最小比值候选中基变量编号最小的一个离基。
符号和比值都使用精确比较。只有在并列最小比值的行中,最先列出的行恰好含有这些候选中最小的基变量编号时,选第一行才与这条规则相同。
最优性停止条件直接来自字典式。任何可行点的非基坐标均非负;若所有 ,便有 。当前基本点取得 ,所以最优。零约化成本可能容许其他最优解,但规则不必先走遍它们才确认最大值。
换基后仍成立的成本恒等式
证明会用两个不同的字典式观察同一个方向。两组约化成本的数值看来可能没有关系,所以先找出它们共同计算的量。
命题 15.1.3
(约化成本可计算每个零空间方向的成本)
对任何基 、其非基集合 及约化成本 ,只要向量 满足 ,就有
不一定是从该基所代表的点出发、能沿正步长前进的可行方向。
证明
(消去基坐标)
齐次约束给出 ,因此 。代入目标内积便有
这是代数恒等式。在零步长主元步中,进基方向可能令某个零基坐标在任何正步长下立即变负,但这并不妨碍使用此恒等式。
有限终止定理
定理 15.1.4
(Bland 主元规则不会重复一个基)
假设变量数有限、约束矩阵行满秩、起始基可行,并以固定变量编号及精确运算执行 Bland 规则的两个选择。则原始单纯形法不会重复一个基,因而在有限次主元步后终止:不是得到最优基本可行点,就是得到证明目标向上无界的改善可行射线。
证明
(最大变动编号导出符号矛盾)
假设某个基重复出现。只考虑从第一次出现到再次出现之间的非空有限主元序列,包括回到原基的那一步。以下分四步导出矛盾。
第一步:序列中的每一步都是零步长。 每个进基约化成本严格为正,每个比值检验步长均非负,所以目标值不会减少。一个基唯一决定其基本点及目标值,回到它便回到相同目标值。因此,各步非负增量 的总和为零;每个 都只能是零。序列中所有字典式于是代表同一个点 。
若一个变量在序列中的某些字典式是基变量、另一些却是非基变量,就称它为此序列的变动变量。每个进基或离基变量都是变动变量。所有变动变量亦满足 ,因为它曾在某处非基,而整个序列的点没有改变。
第二步:选取最大的变动编号。 设 是最大的变动变量编号。选取 某次离基之前的字典式 ,并设该步让 进基。两个变量都是变动变量,而且 ,所以 。以 表示这一步的方向,特别有
把这段序列视为从 开始的封闭循环,必要时绕过原来列出的终点。由于序列回到起始基, 离基之后必定再次进基。以 表示某次重新进基之前的字典式,其非基集合为 ,约化成本为 。Bland 进基规则给出
第三步:判断旧方向 的相关坐标符号。 若 且 ,则由 的最大性可知, 的基或非基身份从未改变。因此,它在 中也非基。因为 ,方向定义给出 。
现在考虑 且 。若它在 中也非基,则 为零;当 时则为一,两种情况均有 。若它在 中是基变量,它就是变动变量,所以 。假如 ,便有 ,令其比值 。离基变量 的比值同样是零。于是, 便是一个比 更小编号的并列最小比值候选,与 中的离基规则矛盾。因此
第四步:在 中计算同一个成本变化。 由 及前面的恒等式,
当 时,每一项均非正;当 时,每一项均为零;而 那一项严格为负,因为 、。所以 ,与在 中算得的严格正值矛盾。
故没有基会重复。大小为 的列集合最多只有 个,因而可用基的数目有限。每个未停止的迭代都会进行一个定义明确的可行主元步,所以算法必定到达其中一个停止条件;前面已证明这两种停止条件分别给出最优性或无界性的证书。
证明透视
各个假设在哪里发挥作用?
严格为正的进基约化成本,迫使假想循环内所有步长均为零。固定编号让我们选出最大的变动变量。进基规则控制它重新进基时、较小非基编号的约化成本符号;离基规则则控制它离基时、旧方向相关坐标的符号。成本恒等式把这两种符号限制变成矛盾。只有排除重复后,“基的数目有限”才足以推出终止。
证明没有使用数据为有理数的假设:它讨论的是精确实数比较。它亦没有声称主元步数存在多项式上界。粗略计数 可随问题大小以指数速度增长。防止循环解决的是逻辑上的终止问题;选择规则在实际计算中有多快,是另一个问题。
算例:两次零步长后才真正前进
例题 15.1.5
(点可以不变,但有用的基仍会改变)
最大化 ,约束为
依次加入松弛变量 ,起始字典式和目标为
基是 ,对应点为 。只有 的约化成本为正。基变量编号 的比值分别为 。Bland 规则在零比值并列中选编号 ,所以 进基、 离基,步长为零。解出 后得到
现在让 进基。会减少的基变量是 ,比值分别为零和一。因此, 又以零步长离基,下一个字典式为
例题 15.1.6
(离开退化点并确认最优)
接续上例的第三个字典式。至此三个基都代表 。现在 以约化成本一进基。 均增加;只有 限制步长,其比值为一。让 离基后得到
非基变量是 ,约化成本为零及负一,故解为 ,目标值一。独立地,约束 亦证明此值最优。保持 并增加 ,会得到 的其他最优解;所以出现零约化成本与停止完全相容。
| 作选择前的基 | 进基 | 离基 | 步长 | 换基后目标值 |
|---|---|---|---|---|
| 1 | 3 | |||
| 2 | 4 | |||
| 3 | 5 |
头两步没有改善点,但也没有重复基。终止定理正是容许这种行为。
反例模式
零步长不是最优性证书
此例的起始点只允许第一步取零步长,但可行点 的目标值更高。若一遇到零步长便宣布最优,就会交出错误答案。另一方面,零约化成本也不是 Bland 规则的合格进基条件:必须严格为正。只按最小编号选变量、却不检查符号,便失去了证明所用的目标单调性。
另一种停止条件是改善射线:进基列没有正的字典式系数时便会出现。
例题 15.1.7
(以改善射线终止)
最大化 ,约束为 及 。加入松弛变量 后,起始字典式为
只有 的约化成本为正,Bland 规则让它进基。唯一的比值是 ,所以 以步长一离基:
现在 、,所以 进基。它在唯一一行的系数是 ,并非正数,比值检验没有候选,规则停止。方向为 、、,即 。它满足 ,所以对每个 ,点 都可行,目标值为 。问题向上无界,而这条射线就是证书。
容易混淆的地方
常见错误
(单靠最小离基编号不能防止循环)
单靠最小离基编号并不足够。较早笔记的六步循环例子,已在离基并列时选最小基变量编号,但进基时选最大的正约化成本。Bland 定理还要求选最小的合格进基编号。
常见错误
(误以为规则包办第一阶段或容差处理)
定理从可行基出发。它没有代替第一阶段,也没有允许对含负基本值的字典式直接套用原始单纯形比值检验。它同样不会消除浮点歧义:用数值容差取代精确的零,会改变合格候选和并列集合。程序可能需要数值保障,但那要另作分析。
常见错误
(把不重复理解为点不重复)
最优点或其他退化点的基未必唯一。定理排除的是这条主元序列中重复的基,而不是重复的点。运行前把变量重新编号一次,仍可得到另一个适用此证明的固定次序;在主元步之间不断改编号,则不再满足假设。
练习
快速检查
(某可行字典式的非基编号是 ,约化成本分别为 。对选出的进基列,基编号 的 分别是 。选出 Bland 主元步。最后一行会限制正步长吗?)
解答 · 答案
正约化成本中最小的编号是 ,不是 。编号 的比值并列为零,所以编号 离基,步长为零。编号 的系数为负,故进基变量增加时该基变量也增加,不能提供步长上界。只有 的行可参与取最小值;零或负系数都不限制步长。
快速检查
(在退化算例的第一次换基后,写出让 进基的完整五坐标方向。为何其目标斜率为正,却不能从该字典式的点走任何正步长?)
解答 · 答案
按坐标 排列,方向为 。由于目标是 ,有 。但当前点的 且 ,任何正步长都会令 变负。方向给出代数上的目标斜率;比值检验则另行施加可行性限制 。
快速检查
(在终止证明中,为何对 中非基且 的编号,可以断言 ?为何不能把同一句话直接套在每个 上?)
解答 · 答案
大于 的编号不是变动变量,所以它在 非基就表示在 也非基。旧方向唯一非零的非基坐标是进基编号 。较小的编号却可能改变身份,在 中为基,其方向坐标由字典式系数决定;必须结合离基并列规则和零基本值,才可证明该坐标非负。
快速检查
(设 ,起始可行基已固定。不重复基能给出多少次主元步的粗略上界?这个计数是否证明任意维数下的计算都很有效率?)
解答 · 答案
基集合最多有 个,包括起始基。每个主元步到达另一个集合,因此到达终止基之前最多进行九步。奇异或不可行的集合只会令此数减少。一般维数的相应二项式计数可以是指数级,所以这不是多项式复杂度保证。
快速检查
(把退化算例的目标改成 ,在起始松弛基套用 Bland 停止条件。说明为何强行让 进基不属定理的范围,即使它的编号最小。)
解答 · 答案
起始非基约化成本是 ,两者均非正,所以当前点已最优,值为零; 也给出独立证书。强行让 进基违反严格正约化成本的资格条件。第一次强行换基恰好是零步长、没有改变目标值,但这个巧合并不满足单调性及防循环证明的假设。