本节讲解线性规划的基本可行解、单纯形步骤与对偶证书。先备知识是基本矩阵代数;优化术语会在使用前逐一说明。
动机
编译器要安排几种可分割的计算工作,每种工作按固定比率耗用处理器时间及内存。若效能评分也是工作量的线性组合,便得到线性规划。解几条边界方程只会产生候选安排,还未说明其他可行安排为什么不能更好。我们需要寻找方法,也需要可独立核验的最优性证书。
“线性”指目标及限制的表达式,并不表示最优决策随数据线性变化。半空间的交集有角点,系数稍变便可能令最佳角点转移。几何说明这种现象,矩阵则把同一推理延伸到无法画图的高维空间。
变量是否可分割是模型假设。处理器时间可以是分数,已安装装置的数目通常必须是整数。本节先处理可分割模型;它的界也会用于后面的整数模型。先写清楚最大化还是最小化,才判断某个数值究竟是上界还是下界。
定义
定义 1.1.1
(可行性、松弛量及原始—对偶问题)
对实数数据 、、,考虑
不等式逐分量理解。满足全部限制的点称为可行点;在可行点中取得最佳目标值的点称为最优点。原始松弛量为 ,对偶余量为 。可行集是多面体,即有限个闭半空间的交集;有界多面体称为多胞体。
非负性必须由模型指定。自由变量可写成两个非负变量之差;上界不等式可加入非负松弛量改成等式。限制乘以负一时,不等号也必须反向。每一步转换都要保留原来决策的意义,不能只记公式外形。
单纯形法使用等式标准形 、,其中 有满行秩,行数为 。选取 个线性无关的列构成基矩阵 ,其余列记为 。基本解令 、;若基本值全部非负,便是基本可行解。某个基本值为零时称为退化,这与有多个最优点是不同概念。
顶点不能写成两个不同可行点的非平凡凸组合。在等式标准形中,顶点恰好是基本可行解:正坐标所对应的列若线性相关,便能向正负两个方向作小幅可行移动;若线性无关,这种分解便不可能。
定理/命题
定理 1.1.2
(已取得的最优值有基本解代表)
设 有满行秩。若 有已取得的有限最优值,则至少有一个最优点是基本可行解。特别地,非空有界可行集必有基本最优解。
“已取得”是明确假设。有界闭可行集的紧致性配合目标的连续性保证取得最优值;但有界并非必要。无界可行集也可能有有限而已取得的最优值。定理并没有声称每一个可行点或每一个最优点都是顶点。
反例模式
没有符号限制时,最优点未必在顶点上
错误说法:每个已取得最优值的线性规划都有最优顶点。在 中,只在 的限制下最大化 。最大值 在整条直线 上取得,但没有任何可行点是顶点,因为 。定理的标准形排除了这种情况: 意味着可行集不含直线。把 写成 ,其中 ,顶点便恢复: 是最优点,代表 。
定理 1.1.3
(对偶界与零差距证书)
若 原始可行而 对偶可行,则
等号成立当且仅当每个 及每个 。这些乘积条件称为互补松弛。若两个可行点目标值相等,两者都最优。
这份证书不需要先假设可行集有界:目标值相等的可行点已经界定所有竞争者。通常的强对偶定理还保证有限原始最优值有同值对偶最优解,但一般存在性证明不在本节范围内。下面会直接构造对偶点并核验,例题不依赖尚未证明的存在性结论。
证明思路
在最优点中,选正坐标数目最少的一个;这是有限个可能支撑大小中的最小值。若其正支撑所对应的列相关,便有非零 支撑于这些坐标且 。足够小的正数 令 及 都非负且满足等式。最优性迫使 ,否则其中一个方向立即改善目标。
选择 的符号,令至少一个坐标下降,再移动至第一个坐标碰到零。其他坐标仍非负,目标不变,原来支撑以外也没有新增正坐标,却得到更小的最优支撑,矛盾。所以正支撑列无关,可补成完整的基;补入的基本值为零。这也涵盖退化情况。
证明透视
缩小支撑如何得到顶点
这个论证从不直接寻找顶点,而是缩小一个最优点的支撑。首先用到“已取得”,才有最优点可用。支撑列线性相关给出只涉及支撑坐标、且 的方向 ,所以正负两个方向的小幅移动都保持可行。给出 的是最优性而非可行性,因此沿 移动不改变目标。真正的关键是最后的比值步:推进到第一个坐标变为零,支撑减少一个坐标而不新增任何坐标,与最小性矛盾。满行秩只在最后用到,用来把线性无关的列补成一组基。
第二个定理只需展开右边,含 的项互相抵消。余下每一项都非负,因此总和为零等价于逐项乘积为零。同值可行对把所有原始竞争者压在共同值之下,也把全部对偶竞争者托在其上,故双方最优。
证明透视
差距何时才是证书?
恒等式纯属代数,对不可行向量也成立。要把它变成不等式,必须分别检查原始松弛、原始变量、对偶乘数及对偶余量的非负性。四种符号条件令每个乘积非负,零总和才迫使逐项为零。最后用弱对偶比较所有竞争者,不依赖主元历史或强对偶存在性。未检查可行性的“很小差距”仍不是证明。
字典如何产生一步主元运算
选定基后,等式及目标写成
是约化成本。最大化时若全部约化成本非正,任何非基本变量的增加都不能改善目标。因为所有可行点都满足字典,这是全局证明,并非只检查附近方向。
若某个约化成本为正,让该变量增加 ,令 。基本坐标变成 ;只有 的行限制步长,取最小比值 。没有正分量时得到可行改善射线,证明目标无界。最小比值为零则可能退化,目标暂时不增。重复的零步长主元可能循环,除非采用 Bland 规则等防循环规则;本节讲解主元逻辑,并不声称任意处理平手都必定终止。
例题详解
例题 1.1.4
(两次主元完成求解)
最大化计算工作评分 ,限制为
初始松弛字典是 、、,目标 。让 进基,比值四及二中取二(第三行不限制这个方向),故 离基。代入得
再让 进基,可增加二或三中较小的二,故 离基。最终
松弛量非负使任何可行分数至多十。令 得 、,确实达到十。字典本身已是一份最优性证明。
例题 1.1.5
(独立对偶证书及敏感度范围)
上题取 ,则 ,而 。非负性、列不等式及同值性已证明最优,无须重看主元历史。第三限制有剩余容量,所以对应乘数为零;紧限制的乘数则不一定必须为正。
把第一容量改成 ,同一基给出 、、。可行范围恰为 ;在此范围,不变的对偶点证明最优值 。超出范围时,只要模型可行,该对偶点仍可提供上界,但这个原始候选点违反非负性。乘数的精确变化率有适用区间,不能无限外推。
例题 1.1.6
(区分三种不同结果)
与 无法同时成立,是不可行问题。只限制 而最大化 则有可行点,但射线 使目标无界。两者不能都称为“没有好解”。
最大化 、限制 及非负性时,、 及整条连线都最优。中点不是顶点,所以基本解定理只保证存在某个基本代表。零约化成本可能指向平坦最优方向;但退化时,一次零成本主元也可能没有移动到不同点。
常见错误
解出一组活动限制后,仍须检查全部未使用的不等式及符号限制。可行不等于最优,位于几条边界的交点甚至不一定可行。图中的候选角点必须有完整性理由,或配上独立上界证书。
对偶符号取决于原始惯例。这里是非负变量、上界限制的最大化;等式限制应配自由乘数,自由原始变量应配对偶等式。改了原始形式而照抄旧符号,便可能失去上界性。互补松弛也不表示松弛及乘数都必须为零:正松弛迫使乘数为零,紧限制却容许零乘数。同样,取零的决策变量也不迫使其对偶不等式严格成立。使用任何互补乘积前,先检查可行性。
比值检验只除以正方向分量。负分量表示基本值正在增加,不会威胁非负性。数值软件另需稳定线性求解及容差政策;本节的精确代数不等于已证明近奇异基的数值稳定性。
总结
多面体把可行性连到基,主元在保留可行性的同时改变表示,约化成本说明能否改善。最终字典与对偶点都可成为可核验证书。不可行、目标无界、已取得有限最优值及多重最优值,必须分别判断。
练习
快速检查
(最大化 ,限制 、 及非负性,求最优点及按上文原始惯例的对偶证书。)
解答 · 答案
的值为四。取 ,有 、,对偶值 。同值可行对证明最优;亦可直接合并限制得 。
快速检查
(把第一例的目标改为 ,描述全部最优点及一个对偶最优点。旧点是否仍最优?)
解答 · 答案
最优值四,全部最优点为 、。下界来自 ,上界来自 。旧点 仍最优,但不再唯一。对偶点 可行且值四。
快速检查
(基本值为 ,正约化成本的进基方向 ,求步长及重标基前的新基本值。方向改成 呢?)
解答 · 答案
第一行给 ,第二行随步长增加,故取二。旧基本值变成 ,进基变量为二。改成全负方向后,两个基本值均增加,没有有限步长上限;正约化成本遂给出改善射线,证明目标无界。
快速检查
(已核实可行的一对点有 、、、,是否足以证明最优?若只把第二乘数改为一,并重新核实所有可行条件呢?)
解答 · 答案
差距是 ,足以证明双方最优。改动后松弛贡献变为二,差距为正,这一对点不能证明同值。正差距本身未说明究竟哪一点次优,只说这份等值证书失败。
快速检查
(证明两个不同最优点之间整条线段都最优,并解释为什么线段内点不是基本可行解。)
解答 · 答案
线性不等式保持凸组合可行,线性目标保持其共同最优值。严格内点是两个不同可行点的非平凡凸组合,按定义不是顶点,因而不是基本可行解;端点本身也未必是顶点。