本节处理先前单纯形一节中,现成可行松弛基所掩盖的问题:如何开始、如何节省更新工作,以及如何避免退化主元重复。
动机
纸上字典容易逐项核对,但大型矩阵若每次更新全部项目,会浪费大量工作。修订单纯形法保留当前基的分解,只在考虑某个进基列时求所需数据。变的是存储与计算安排,不是主元的数学意义。
另一障碍更基本:下限需求或等式限制未必提供可行松弛基。不能随意猜一点便使用原始比值检验,因为该检验依赖目前基本值非负。第一阶段以另一个优化问题决定原系统能否满足,而非把违反限制当成可接受安排。
合法主元也可能没有移动决策点。若某基本值已为零,即使进基约化成本为正,容许步长仍可为零。有限个基不保证算法停止,除非有规则防止重访。下面列出真实六步循环,再用字典序扰动证明如何排除它。
定义
定义 4.1.1
(修订单纯形所需数据)
最大化标准形为 , 有满行秩。对可行基 ,求解
非基本列的约化成本是 。若其为正,增加 达 时,基本向量变为 ;只在 的行取最小比值 决定离基者。
这些是线性求解,不要求显式形成逆矩阵。转置求解后,各约化成本只需一次列内积;选定进基列后,再求一次方向。基分解可作更新,但浮点稳定性及重新分解策略另需分析。
基本值测试原始可行性,约化成本测试目前基是否提供目标上界,两种小数值不能混淆。精确算术有明确符号;数值容差则要配合尺度并重新核验。防循环规则本身不会修复病态基的求解误差。
选好进基列后,方向中非正的行不限制步长,因其基本值不降。若所有方向分量都非正,且约化成本严格为正,便有保持等式及非负性的改善射线;这不是“找不到离基者”的算法故障,而是问题目标无界的证书。反之,某个零基本值所在行若有正方向分量,就会把步长压到零。把这两种情况分开,才能理解退化与无界为什么需要完全不同的处理。
定义 4.1.2
(第一阶段问题与人工变量)
按需要将等式行乘负一,使 ,再每行加一个非负人工变量,组成 ,求解
人工单位列给出可行初始基 。
不等式先加入普通松弛或扣除剩余变量,再只在需要处加入人工列。人工量只是计算工具,不是原模型的新决策。
定义 4.1.3
(退化基与循环)
若基本可行解至少有一个基本坐标为零,称为退化。若一串主元回到一个已访问过的基,称为循环。
两者不同:退化主元可以无害,数个基代表同一点也不一定形成循环。
定理/命题
定理 4.1.4
(第一阶段究竟证明什么)
原非负等式系统可行,当且仅当第一阶段最小值为零。正最小值证明不可行。零最小值时,可用结构列的非零系数作零步长主元移除零值人工基本变量,或删除冗余的变换后等式,得到第二阶段的结构基。
定理 4.1.5
(字典序扰动排除循环)
精确算术下,设 为可行初始基,形式上把右端改为
其中正 小于每个正实常数。依升幂第一个非零系数比较步长。采正约化成本进基与此字典序比值检验时,基不会重复,有限步到达最优基或改善无界射线。终止最优基取常数项便给原问题最优解。
扰动必须配合初始基。直接在任意右端加一个正向量,未必使其基本坐标为正。把形式符号改成任意很小的浮点数,也不等于获得精确防循环保证。
概念视角几何
扰动把退化顶点拉开
在退化顶点处,经过同一点的限制超平面 多于其位置所需,所以几个可行基指向同一点,它们之间的主元步长为零。在扰动后的问题中没有基本坐标为零,所以不同的可行基给出不同的顶点:拥挤的顶点被拉开成邻近的多个顶点,每个顶点恰有一个基。于是每次主元都沿一条形式长度为正的真正的棱移动,这就是严格改善的几何含义。
证明思路
证明
(第一阶段的值与清理主元)
人工量非负,故第一阶段 。原系统若可行,附上 就有值零;反之,非负人工量之和为零迫使每项为零,留下原可行点。正最小值因此排除可行性。第一阶段可行且下有界,有限最小值能取得;下一节会以有限维方法证明线性规划的取得性。
在零最优值处,人工基本量必为零。消去其他基本变量并把人工量设零后,若该行仍有非基本结构变量的非零系数,便可用它换走人工量。进出值都是零,所以即使主元系数为负,表示的可行点仍不变。若已没有任何结构系数,便只剩 ,可删除。反复处理后只留原变量及普通松弛、剩余变量。恢复原目标,重算转置系统及约化成本,不能沿用辅助目标。
证明
(形式非退化给出严格改善)
防循环证明中,初始基本向量为 ,在形式次序下严格为正。任意基的基本坐标是 的多项式;它不可能恒零,因为扰动系数构成可逆矩阵 的一行。
因此可行扰动基没有形式退化。两个候选行的比值也不可能完全相同,否则 的两行成比例,违反可逆性。最小比值唯一且正,每次有界主元遂严格提高形式目标。每个基唯一决定一个目标多项式,不能回到旧基;基只有有限个,所以必停止或发现改善射线。
终止时约化成本是非正实数,因扰动没有改成本。基本多项式的常数项非负,否则负常数会压过所有扰动项。故常数项形成原可行基,非正约化成本证明最优。改善射线只取决于方向及约化成本,不取决于右端,所以也证明原问题无界。
这个证明为每个基附上一个严格递增的量,把有限搜索变成必然终止的过程。下面的剖析记录每个假设在哪里使用。
证明透视
只有有限个基还不够
证明的核心是一个由基决定、并在每次有界主元严格递增的量。在有限集合中取值的严格递增序列不能重复取值,所以基不能重现。普通目标值也由基决定,但在零步长时不严格增加;下面的六步循环正是这种失效。
各假设在不同位置使用。 可行,加上扰动中的因子 ,使初始向量 形式上为正。 可逆用了两次:没有基本坐标恒为零,也没有两行给出相同比值,于是离基行唯一,每个步长 形式上为正。正的进基约化成本再把 变成严格的形式增量 。精确算术不可少,因为比较读的是 的系数;舍入可能抹掉两个比值首个不同的系数。
收尾一步回到原问题。约化成本从不涉及 ,而负常数项会压过所有扰动项,所以终止基的常数项给出原问题的可行点及最优性凭证。
例题详解
例题 4.1.6
(第一阶段找起点,第二阶段改善它)
最大化 ,限制 、 及非负性。引入剩余 、松弛 、人工 :
起始 、、。让 进基降低 ,比值二及四取二, 离基。得
非基本量全零即 ,证明原可行。删人工列后,原目标是 。让 进基, 增而 减,步长二时 离基:
最优 ,值十二。两阶段分别回答可行性及原目标最优性。
例题 4.1.7
(不用完整表格重现主元)
第一阶段后基本次序为 ,有
转置求解给 ,所以 、。剩余列为 ,解 得 。只第二行限制步长,故取二;旧基本值成 , 进基, 离基,与字典计算完全相同。
例题 4.1.8
(精确六次主元循环)
最大化 ,全部变量非负,限制
普通松弛标为 。每次取最大正约化成本进基,进基成本平手时取变量编号最小者;最小比值平手时取编号最小基本量离基,精确求解得:
| 当前基的行次序 | 进基 | 离基 | 约化成本 | 步长 |
|---|---|---|---|---|
| 1 | 5 | |||
| 2 | 6 | |||
| 3 | 1 | |||
| 4 | 2 | |||
| 5 | 3 | |||
| 6 | 4 |
回到 ,决策点始终是原点,目标零。每步都合法,但规则循环;字典序比值会分开零比值平手,阻止重返。这是精确算术障碍,并非只由舍入引起。
常见错误
常见错误
(人工变量不是决策)
人工量不能当成原模型可随意使用的实际决策。正值表示原等式尚未满足,并非可以接受的违反。即使辅助目标已为零,人工量仍可能以零值占据基本列,所以“第一阶段值为零”本身并未完成清理。
最后一点容易被低估,下面用具体系统说明。
反例模式
第一阶段值为零仍可留下基本人工变量
声称:第一阶段最小值为零时,最后的第一阶段基只含原变量,可以直接开始第二阶段。考虑冗余系统 、,,人工变量为 :
让 进基。两个比值都是一;让 离基。代入得
中 的系数为 、 的系数为 ,没有进基变量能降低 ,最小值 已经达到。可是 仍是基本变量,值为零,所以上述声称不成立。修正就是定理中的清理:把人工量设为零后, 所在行为 ,没有结构系数,予以删除,剩下方程 及结构基 。
常见错误
(冗余行与矛盾行)
冗余要在消去其他基本变量后的变换系统中判断,不能凭系数看似重复便下结论。若变换后的行为 且常数非零,那是矛盾,不是冗余。秩检查与删行都必须保留这个区别。
常见错误
(只选小离基编号不能防止循环)
最大约化成本规则可以循环,上表已经示范。另一种精确防循环法 Bland 规则,要求进基者取最小合格编号,离基平手时也取最小编号基本量;其证明与本节的字典序证明不同。只在离基平手时选小编号并不足够,因为上面的循环例子已经这样做。
总结
修订法以基求解代替完整字典更新;第一阶段取得或排除起点,清理后才恢复原目标。退化使普通目标不再严格增长,字典序扰动恢复形式上的严格改善,才可用有限个基证明终止。
练习
快速检查
(对 ,写一个只有一个人工量的第一阶段模型并求最小值。)
解答 · 答案
用 及全部非负,最小化 。第二式使 ,所以 。取 达到一,证明原系统不可行。
快速检查
(修订例的目标改成 ,求基 的 约化成本,判断可否改善。)
解答 · 答案
,故 ,、,两者皆可进基。进 得方向 、步长二,到 ;进 到 。两点值均四,这个目标有多个最优点。
快速检查
(比较 与 ;两者都舍入零会失去什么?)
解答 · 答案
首个不同系数在二次项,一小于三,故第一个比值较小。它们都是不同的正形式量;把两者都当零正是抹掉选离基行的信息,精确终止证明便不适用。
快速检查
(零人工基本行消去后为 ,应如何处理?与 比较。)
解答 · 答案
用任一非零结构系数换走人工量,进基值为零,负主元系数也不改目前可行点。该行仍限制结构变量,不可删; 才是真正不施加限制的冗余行。