生产计划依赖预计利润;估计改变时,原计划是否还最优?可行集合没有移动,但衡量改进的方向变了。约化成本可先检验原有的基,再决定是否需要重新优化。本节讨论一般的基检验。
改变成本后的证书
定义 22.1.1
(改变目标后的基与约化成本)
考虑有限维线性规划:在 、 下最小化 ,其中 满行秩。基是由 的列组成的可逆方阵 ;余下的列组成 ,相应地分割 及 ,并令 。若 ,称此基原始可行。对成本向量 ,其乘子及约化成本为
以下始终假设基 原始可行。
定理 22.1.2
(成本变化的精确基检验)
若 ,基本解 对新目标最优。反过来,如果存在对偶可行乘子且在所有基列上取等,那么必有 。所以这些不等式精确描述使此基同时原始可行、对偶可行的成本向量;零约化成本和退化基也包含在内。
证明
(把基变量代入目标)
任一可行解满足 。代入目标得
若 ,由于 ,最后一项对每个可行解都非负,基本解达到全局最小值。等价地, 和 给出相等的对偶下界。反过来,基列上的等式唯一确定乘子为 ;其余列的对偶可行条件正是上述不等式。
证明透视
代入恒等式能决定什么、不能决定什么
假设在哪里用上: 可逆,令每个可行点都能用非基坐标表示; 令基本点可行,才有资格作候选; 把 变成非负的余项。
关键一步:恒等式 对每个可行 都成立,所以检查有限个系数的符号便控制了整个可行集。
逆命题比表面看来窄:它利用所有基列上的等式唯一确定乘子,所以是关于这个基作为证书的陈述,而非关于基本点。下面的退化反例显示二者的区别。
如何收尾: 只依赖 ,而 与 无关。成本改变从不威胁原始可行性,因此一组关于 的不等式就是整个检验。
定理的逆命题针对的是基证书:退化时同一点可能由另一基表示,因此原基失去对偶可行性也不能断言该点不最优。
反例模式
最优退化点上基检验失败
一个看似合理的说法是:负约化成本证明基本点不最优。在 、 下最小化 。唯一可行点是 ,所以它最优。以 为基:、、, 的约化成本是 。此基未通过检验,但其基本点最优;改以 为基,得 , 的约化成本为 ,证明同一点最优。正确说法是:检验失败只表示这个基不是对偶证书。
单参数与同时变化
令 。先解 ,再计算 。每一分量都是 的仿射函数;相交所有 就得到精确的基证书区间。非基成本变化直接影响其自身约化成本;基成本变化则改变 ,可能影响所有非基约化成本。只改变 时, 不变,原始可行性自动保留。在证书区间内,最优值为 ;区间外此检验本身不告诉我们新最优解。
常见错误
(以为基变量的成本变化只有局部影响)
改变基变量的成本,不会改变它自己的约化成本(仍为零);它改变乘子 ,再经 影响每个非基约化成本。在下面的例子中,把基变量 的利润改为 ,两个松弛变量的系数都会改变,分别变成 和 。以为“ 是基变量,所以任何 都无妨”是错的: 时第二个系数为 ,此基不再最优。
每个系数单独变化时的允许范围一般不能直接同时使用。应把所有新系数一起代入约化成本。下面的规则是一个充分的快捷方法。
命题 22.1.3
(100% 规则)
设此基对 及每个成本向量 都已获认证,即其约化成本全部非负。若 且 ,则此基对 也获认证。
证明
(已认证成本向量的凸组合)
写 ,这是凸组合。映射 是线性的,所以组合的约化成本是非负向量的同一凸组合,因而非负。
实际应用时, 是沿指定方向最大的已认证单项变化, 是实际用去的比例。该规则充分但非必要,且依赖所指定的方向与单项范围。
常见错误
(把单项范围直接叠加)
每个报告的范围都假设其他系数不变。两项各自在范围内的变化,合起来仍可能越出区域:下面关于同时改变两个系数的练习中 、 各自获认证,合起来此基却失效。应检验合并后的约化成本,或确认所用比例之和不超过一。
例:利润改变
例题 22.1.4
(范围、端点与范围之外)
最大化 ,约束为 、、。引入松弛变量:
选 为基,得到 、,于是
两个松弛变量的系数都非正,当且仅当 。此时基本计划 最优,值为 ;最大化问题的对偶价格 在此范围非负且满足列约束。 时第二个系数为零,所有 ()均最优。当 ,目标等于 ,由 取到,值为 。端点处的折角说明不能把旧仿射公式延伸到证书区间以外。
同一模型中的同时变化
下面关于同时改变两个系数的练习给出把两个利润改为 时的精确区域: 的基保持最优,当且仅当 且 。单项范围则是 及 。以下两个例子比较 100% 规则与精确区域。
概念视角几何
可认证的成本构成一个锥
把利润写成 ,精确区域便成为 ,即 ,其中 :目标落在 处两条紧约束的法向量所张成的锥内。在定理的最小化形式中,可认证的成本向量恰好是 ,这是一个凸锥。100% 规则正是这种凸性的推论。
例题 22.1.5
(100% 规则认证一个合并变化)
取 。第一个利润的下降用去其至 的范围的 ;第二个利润的上升用去其至 的范围的 。比例之和为 ,所以规则认证此基。
与精确区域核对: 且 。值为 。直接计算, 给出 ,顶点 给出 , 给出 ,所以 确是各顶点中最好的。
例题 22.1.6
(100% 规则看不见的已认证变化)
取 。 超出单项范围 ,所以 100% 规则根本不适用。精确区域仍认证它: 且 。
验证:字典系数为 及 ,均非正。值为 。直接计算, 给出 , 给出 。提高第一个利润扩大了第二个利润的空间;单项范围无法记录这种相互作用,所以规则充分而非必要。
练习与解答
快速检查
(约束不变,最大化 。求保持同一基证书的范围。)
代入 及 。
解答 · 答案
代入得 。两系数非正给出 ;此范围内值为 。
快速检查
(从 出发,把两个系数同时变成 。求同一基证书的精确区域,并检验 。)
两项变化进入同一个字典。
解答 · 答案
字典为 ;区域是 且 。所给点违反后者。两项变化单独看都在允许范围,合起来却不被认证: 的值为 ,大于 的 。
快速检查
(在最小化定理中,退化基有负约化成本意味着什么?)
回想定理的逆命题是关于什么的。
解答 · 答案
只说明这个基未通过对偶检验,不能单凭它判定基本点非最优。上面的唯一可行零点就是反例;需要可行改进方向或其他证书。