动机
模型已解好,某项工作需求却增加。旧基仍描述相同列及价格,但重新求出的基本值可能变负。若立即从无关起点重做,便丢掉已有证书信息。对偶单纯形保留价格可行性,改为修补决策点。
这与原始单纯形的不变量相反:原始法保留可行点,利用约化成本改善目标;对偶法保留可行约化成本,逐步消除负基本值。计算中暂容负基本值,不等于模型接受负决策。只有最后双方可行才可报告最优;若修补失败,则要给乘数证明新限制根本无法满足。
成本变动与需求变动不同。成本不改旧点可行性,却可破坏价格不等式。不能只因问题名叫“重新优化”就固定使用一种算法。我们先推不变量,再据此判断每类变动后什么计算合法。
定义
定义 21.1.1
(对偶可行的最小化字典)
采 , 有满行秩。基 及其余列 给
其中 。 等价于 ,称为基对偶可行;原始可行还要求 。
两者同时成立时,非基本量设零便得目标 的原始可行点,与对偶界相等,故最优。
即使目前基本点不可行,对偶乘数仍限制全部真正原始可行点的成本。下界有效不要求我们已找出一个可行点,只要求全部乘数不等式成立。这解释为什么修补期间还有可保留的信息;反过来,若成本变动令某个约化成本负,该下界论证便不能照搬,哪怕目前基本值全部正。判断算法前须分别检查这两边,不能只看目标数字是否合理。
若 ,其行为
只有 的非基本列能修补此行。基本位置是行位置,离基变量另有原列编号,重排基时不可混淆。 选变换后行,乘 才回到原限制坐标;不能直接把行号当乘数。
可选列的对偶比值为 。其分子是约化成本,不是基本值,所以不是原始步长比值。未写出标准行便照抄已解行的加减号,容易把可选方向反转。
定理/命题
定理 21.1.2
(对偶比值保留价格证书)
选 的行。若有可选列,取达到
的列进基,换走 。令 ,则新乘数 仍对偶可行,值 ;新进基值为正 。
定理 21.1.3
(失败行给 Farkas 证书)
若 ,但全部非基本系数 ,则 满足 。原始系统不可行,且此结论与成本无关。
最小比值可为零,造成对偶退化主元而界不增加,任意选择可能循环。若每步比值严格正,对偶值严格增、基数有限,便有限终止。不能只说基有限就当证完;下面的定理给出有限的精确规则。
概念视角几何
对偶单纯形是沿对偶多面体的棱行走
对偶问题是 ,它在基乘数处的松弛量恰好是约化成本。对偶可行基就是这个多面体的一个顶点,基本列对应的限制在该处取等号。步骤 沿一条棱移动:只放松 的限制,目标的变化率为 。因此负基本值就是一条改进棱,对偶比值是走到某个非基本限制取等号为止的距离,而可选集为空则给出一条改进射线,对偶目标沿它无界。
定理 21.1.4
(字典序成本扰动使对偶单纯形有限终止)
从对偶可行基开始,把其非基本编号排为 ,形式上以 取代 ,并按 多项式的字典序执行对偶比值检验。则任何基都不会重复出现;经有限次主元后,方法必到达对原问题原始对偶皆最优的基,或到达一条失败行,其 Farkas 证书证明原系统不可行。
证明思路
证明
(约化成本在对偶比值步后的变化)
新乘数令每个旧非基本列 的约化成本变成 。非负行系数使它增加;负行系数要求 才保非负。取最小比值使进基列恰紧。旧离基列的新约化成本是 ;其他基本列与 内积零,保持紧。故新乘数对新基可行且基本列全紧,正是新基乘数。
对偶值变化是 。以新非基本量全零解主元行,便得所述正进基值。但其他基本值仍可能负,不能因此立即声称原始可行;要重算并继续修补,直到没有负值。
这里没有证明负基本值的个数每步都减少,也没有保证每个基本值都更接近零。后面的第一题正展示修补一行后另一行仍会变负。真正单调的是对偶下界,在退化时还要以形式目标加强为严格单调;把错误的“违反数量一定减少”当进度量,会误解终止证明。
证明透视
主元规则每个假设各保证什么
证明检查三件事,各自依赖不同假设。符号条件 使进基值 为正,所以这次交换确实修补第 行。比值取最小,使每个约化成本 保持非负:只有行系数为负的列会减少,而最小比值正是它们全部都能承受的最大步长。离基列得到约化成本 ,因为 与它的内积为一、与其他基本列的内积为零;因此 恰好是新基的乘数,而不只是某个对偶可行向量。
论证并不给出原始方面的进展。其他基本值可能变得更负,而且只有 时界才严格上升。最优性只在最后得出:当所有基本值都非负,相等的原始值与对偶值互相证明。 的退化步正是需要扰动定理的原因。
证明
(失败行是 Farkas 证书)
若没有可选列,该行对任何非负决策的左端都非负,右端却负。原坐标下,基本列乘积为 ,非基本列乘积为 ,右端乘积为 ,正是择一定理的不可行证书。零比值仍可作主元运算,空可选集才是这种失败,两者不能混为一谈。
退化时的有限精确规则
证明
(字典序成本扰动永不重访基)
前节扰动右端,这里有成本侧对应。把初始非基本编号排为 ,保持初始基本成本,形式上以 取代非基本成本。初始约化成本成为 ,在字典序严格正。在字典序有序多项式环或其分式域使用对偶比值;每步选任一负基本行,需要确定轨迹时可固定选行规则。
对任意基,成本向量模去 行空间后,到非基本约化成本的映射是同构。理由是约化成本全零,恰等价于整个成本向量为某个 ;反向也成立。商空间及约化成本空间的维数都是 。所以不同基之间的约化成本由可逆线性映射连接。
每个新约化成本的扰动多项式不会恒零,因其系数是可逆映射的一个非零行作用在不同幂上。对偶可行遂令它在形式次序严格正。因此每个候选比值正,负的实基本值令每步形式对偶目标严格增加。同一基唯一决定形式目标,不能重访;有限个基使算法有限到达可行或失败行。
取常数项保留非负约化成本,基本值则只由未改的右端及基决定。故终止可行基给原问题最优,失败行证书也仍属原系统。任意小浮点容差不能代替这个形式证明;它会抹掉证明中用来区分零值的信息。
例题详解
例题 21.1.5
(两次对偶主元得到可行最优)
最小化 ,需求 ,全部变量非负。用剩余量写成
起始 。约化成本非负,基本值却都负。选第一行, 比值三、二,故 进基:
第二行仍负, 比值一、二,故 进基:
现点 可行,约化成本非负;等式乘数 给界七,与原始值一致。
例题 21.1.6
(右端变动只需一次修补)
只把第一需求由三提高至五,旧基变成
约化成本仍各一,但 不可行。其行只有 的标准系数负,让它进基得
故 最小十,乘数 也给新界十。旧乘数仍给合法下界九,却因原始基不可行而不再精确。
例题 21.1.7
(成本变动反而要原始修补)
回到需求三、四,改最小化 。旧点仍可行,但目标成 , 约化成本负,对偶法起始不变量失效。
原始法则可增加 ,令 。,步长二时 离基,得 。故 最优值三,乘数 同值。成本变动破坏的是最优检验,不是旧决策可行性。
例题 21.1.8
(失败行的明确证书)
要求 ,最小化 。起始方程 。第一行进 后,。负第二行无可选列。
原坐标证书 对两决策列乘积零,对松弛列乘积一,右端乘积 。这证明限制本身不可行,不只是目前目标搜索失败。
哪个不变量在扰动后保留?
改为 时,乘数及约化成本不变,基本值改为 。 改为 时,基本值不变,乘数改为 ,约化成本为 。这些给精确基范围。成本及右端同时变,两种可行性都可能失去,须先用有证明的可行阶段,不能盲目指定原始或对偶方向。
常见错误
常见错误
(从已解行读取比值检验的符号)
对偶比值使用 中的负 系数。在右端变动的例子中,已解行写作 ,所以 在 的元素是 ,在 是 。若直接照抄 前的加号,便会以为 可选而 不可选,正好把正确选择颠倒。取比值前先写出标准方程。
常见错误
(把负基本值或上升的界当作更好的方案)
负基本值不是模型接受的负决策,对偶界增加也不是不可行点已变成更好的实际方案,而只是下界证书变强了。基本值全部通过符号检查,才有真正的原始答案。
常见错误
(把零对偶步长当作不可行)
零对偶步长不证明不可行。无可选列才产生分离行;退化要另用已证明的防循环策略。只有固定平局规则、却没有相应证明,不能当成一般终止保证。
比值检验中的最小值也不是可有可无的方便做法,下面的计算说明这一点。
反例模式
任意可选列都可以进基是错的
声称:对偶比值检验中,任何行系数为负的列都可以进基。在第一个例题中,第一行的可选列是比值为 的 及比值为 的 。若让 而非 进基,得 、、。 的约化成本为 ,所以新乘数不对偶可行,其值 也不是下界:真正的最小值是 。取最小比值正是保持证书有效的条件。
总结
对偶法保护乘数不等式并修补负基本值。比值由约化成本变化推导,失败行成为 Farkas 证书。右端变动自然保留其起始不变量,成本变动通常保留原始不变量。形式成本扰动处理普通步长可为零的退化情形。
练习
快速检查
(第一例需求改 ,从松弛基选第一行开始,作对偶主元求 最小值。)
解答 · 答案
第一主元得 ;再进 得 。负 行只容 进基,标准系数负二、比值半。故 。最优 ,值 。
快速检查
(原最终基把 成本改为 , 成本仍三。求该基保持最优的精确区间。)
解答 · 答案
代入原字典,常数为 ,约化成本 ,同时非负恰为 。基本点保持 ,所以闭区间内该基最优。
快速检查
(负行 ,,约化成本 。求进基列、对偶步长及界改善。)
解答 · 答案
只前两列可选,比值三及一,故第二列进基,,界增加 。旧非基本约化成本变 ,离基量约化成本一,确认对偶可行。
快速检查
(对 构造非负不可行的 Farkas 向量,解释为何与成本无关。)
解答 · 答案
给决策列乘积零,两松弛列一,所以 ;右端乘积负一。这与任何非负可行点矛盾,全程不需成本向量。