方案要承受所声明的不确定性
生产方案可能在实际资源消耗确定前已选定。名义约束只检查一个估计系数向量;稳健约束要求同一固定方案对指定不确定集合内每个系数向量都满足限制。这是最坏情况要求,不是概率陈述;若真实系数落在集合外,它也不提供保证。
以下使用精确实数运算,并假设决策在观察不确定系数前选定一次。
定义 8.5.1
(一条资源约束的稳健可行性)
设 是系数向量的不确定集合, 是已知容量。若
则称决策 稳健可行。等价地,。只含 、而解集与之完全相同的不等式,称为该约束的稳健对应式。
独立区间
定理 8.5.2
(独立区间及非负决策下的稳健对应式)
设 ,其中 均有限,并设 。则 稳健可行当且仅当
证明
(逐项上界与一个测试向量)
充分性。 对每个 及每个 ,由 与 得 。求和得 。
必要性。 所有上端点可在乘积集合中同时出现,所以 是容许向量。对它应用稳健可行性,便得 。
证明透视
证明的两半各用哪个假设
证明的两半依赖不同的假设。充分性只用到决策的正负:上端点使单一项 最大,是因为 非负。必要性只用到不确定集合的形状:端点向量 本身必须属于 ,而乘积结构保证了这一点。两半各自都可能失效。
若某个固定的 为负,最大值反而在下端点;对正负自由的决策,乘积集合的精确最坏值是对 求 与 中较大者之和。若 不是乘积集合,上端点之和仍是安全上界,但可能无法达到,因此该不等式不再精确;下文的耦合集合就是这种情况。
生产例子
例题 8.5.3
(独立区间下的稳健最优方案)
选 最大化 ;单位资源系数各自独立取 中的值,容量为 。由定理,稳健可行等价于 ,即 。因 ,而 达到 ,方案 稳健最优,目标值为 。
例题 8.5.4
(不稳健可行的名义最优方案)
若只代入名义系数 ,约束为 ,名义最优为 ,价值 。但容许系数 对此方案消耗 单位,超过容量 。因此名义最优不是稳健可行证书。在退化情形下,若所有 都有 ,两个模型便一致。
耦合不确定性改变答案
定理 8.5.5
(单参数耦合集合的最坏情况)
设 。对 ,
所以容量为 时,稳健对应式是两条不等式 、。
证明
(最大化参数的线性函数)
对固定的 , 是 的线性函数,所以在符号与 相配的端点取最大值,其值为 。恒等式 完成计算,而 等价于 且 。
例题 8.5.6
(耦合不确定性允许较大的方案)
两个系数各自都介于 和 ,但不能同时为 。在耦合集合下,最佳方案是在 上最大化 ,即 ,目标值 。若用较大的独立方盒 取代此集合,会要求 ,最优值变成 。该方盒对耦合集合是安全的,但较保守,因为它包含模型说明不会同时出现的系数组合。
常见错误
反例模式
单独的范围不能决定联合不确定性
在耦合集合的最优方案 ,每个容许的 都恰好消耗四单位,因为 。独立方盒中的系数向量 会消耗八单位,但任何单一 都不能产生它。相同的各系数范围因此可以给出不同的精确稳健可行集,必须说明哪些组合可以同时出现。
常见错误
(对负决策代入上端点)
若 、,则 取值于 ,在下端点最大。使用 会把最坏情况低估 ,并可能接受不可行的方案。
常见错误
(期望在声明的集合以外仍受保护)
稳健方案 对 中的系数是安全的。若第一个系数实际上是 ,它会消耗 单位,违反容量 。保证只覆盖所声明的不确定集合。
练习
快速检查
(独立区间 、容量 时, 和 各自稳健可行吗?)
解答 · 答案
最坏用量分别为 和 。前者可行,后者不可行。
快速检查
(在耦合模型取 、,求一个达到最大值的 和最坏资源用量。)
解答 · 答案
,故取 ,系数为 。最坏用量为 。
快速检查
(在耦合集合及容量 下,对稳健可行的非负 验证上界 。)
解答 · 答案
稳健可行给出 和 ,所以 ,在 取等号。
快速检查
(若 、,哪个端点使 最大?为什么非负变量公式失效?)
解答 · 答案
下端点给出 ,大于上端点的 。乘以负决策会颠倒端点的次序,所以证明的充分性部分不再适用。