整数规划算法不能修正一个表达错误的模型。本节把常见的逻辑条件化成线性不等式,再证明转换后恰好保留原来允许的决策。
用开关表示一项活动
定义 3.4.1
(启停开关、最低产量与固定费用)
假设机器的产量 介于零与已知产能 之间。二元变量 以 表示已启用、 表示关闭;若
便称 为 的启停开关。最低产量 ()则再加上 。启用机器所需的固定费用 用目标函数中的 表示,另加变动成本 。
定理 3.4.2
(受开关控制的活动的可行产量)
启停约束投影到 上是 ,而 时强制 。加上最低产量后,投影恰为 。
证明
(两个二元情况)
若 ,约束化为 (及 ),故 。若 ,约束化为 ,或加上最低产量后的 。反过来, 配 可行,而所述区间内每个 配 都可行。投影就是两个情况的并集。
这是启停约束,并没有说启用时必须有正产量: 仍然可行。若连续产量可以是任意小的正数,就不能随意选一个正的 来表达“ 当且仅当 ”:这样会错误排除较小的正产量。
只要 ,即使机器闲置,固定费用也要支付。若在最小化问题中 ,而在 时只把 从一改成零仍满足其他所有约束,最优解不会选 :因为这样改动可以降低成本。但若其他约束也涉及 ,这个论证未必成立;固定费用为零时,也不能推断闲置的开关必然为零。
例题 3.4.3
(含固定费用的产能选择)
需求为 单位,不允许超额供应。机器 A 产能为 ,单位成本为 ,启用费用为 ;机器 B 产能为 ,单位成本为 ,没有启用费用。令 ,,模型是
当 ,唯一选择是 ,成本为 。当 ,代入平衡式得成本 ;由 ,最佳选择为 ,成本 。所以启用 A 最佳。A 的物理产能是 ,但本模型的平衡式和非负性也给出 ,故 是此模型有效而更紧的表述。已比较两个二元情况,因而证明了全局最优性。
条件约束与有效界限
设 包含不论开关状态均适用的约束。要表达
可使用 ,其中 是二元变量。
定义 3.4.4
(有效的大 常数)
若有限常数 满足
便称 对这个蕴涵有效。若不启用的分支没有可行点,每个 都有效。
定理 3.4.5
(大 蕴涵的精确性)
若 有效,约束 在 时施加 ,在 时不排除任何允许的点。若在 中各变量都有有限界限 ,则
是有效的。
证明
(分情况检查与逐项界限)
当 ,不等式还原为 。当 ,它成为 ,按有效 的定义,每个允许的不启用点都满足它。至于方盒界限: 时每项 至多为 , 时至多为 ;相加便在整个 上,因而在不启用分支上,为 给出上界。
反方向的蕴涵并未被加入:不启用时,原不等式也可能刚好成立。若违反量没有有限上界,就无法用此方法找到有效的有限 ;无穷大不是线性规划的系数,必须寻找其他有效界限或改用别的表述。
太小会悄悄排除本来允许的决策;有效但过大的 则会削弱线性松弛,也可能造成数值问题。因此不能只凭“够大”选值。
例题 3.4.6
(检验两个 值)
设 ,要求 ,而 时整个区间均允许。不启用时最大的违反量是 ,所以 是最小的有效值,方盒公式也给出同一数值。取 得 ,在 处成为 ,错误排除该点;取 则得 ,保留该点。
择一决策
例题 3.4.7
(表达两个不相交的区间)
假设 ,并要求 或 。令 选第一分支, 选第二分支:
当 ,这两式成为 和 ;当 ,则成为 和 。常数 和 是由整体界限得出的有效大 M 值,分别是第一及第二分支约束可能被违反的最大量。反过来,两个区间内每个点都可配上相应的 。所以投影到 的可行集合恰好是 。
一般而言“或”包括两者同时成立:如果两个分支重叠,重叠处可以允许两个开关值。若没有开关而同时施加两条分支约束,得到的是交集。
二元变量与连续变量的乘积
定理 3.4.8
(二元与连续变量乘积的精确线性化)
假设已知有限界限 , 是二元变量。则满足 的 符合
当且仅当 。
证明
(检查两个二元情况)
若 ,第一组不等式强制 ;第二组化为 ,由 可知成立。若 ,第二组强制 ,第一组便只是 原有的界限。因此每个可行三元组均满足 ;反过来,每个有界的 和二元 ,连同 ,也满足全部四条不等式。
证明透视
每组不等式在一个情况收紧、在另一情况多余
四条不等式是两组大 M 不等式。 是开关:它在 时把 固定为 ,而在 时无害,只因 本已成立。 是连结:它在 时把 固定为 ,在 时则成为 ,又恰好是 的界限。所以 与 在两组中都担当有效大 M 常数的角色。
证明任何地方都没有用到正负假设; 时同样成立。用到的是 与 确实是界限。若 小于 可能取得的最大值, 的情况便会施加 ,排除可行点。
下面的反例说明表述的各部分被改动时如何失效。
反例模式
界限为何重要
若 、、,正确的乘积是 。若错误加入只适用于非负情况的约束 ,便会排除此点。反过来,如果省去在 时连结 与 的不等式,便允许例如 ,但这并非正确乘积。完整表述及其定义域都不可忽略。
常见错误
常见错误
(把启停开关理解为强制正产量)
约束 在 时强制 ,但在 时并不强制 ; 可行。若启用后产量必须至少为 ,须明确加上 。
常见错误
(使用对模型无效的界限)
对 ,若以 写乘积表述, 的情况便施加 ,排除了允许的点 。用作大 M 常数的界限必须对每个允许点成立,而不只是对预期的最优点成立。
练习
快速检查
(一项活动要么关闭,要么产出 至 单位;启用固定费用为 ,每单位变动成本为 。写出可行集合及成本。 可行吗?)
解答 · 答案
取 、,成本为 。 时 ; 时 ,所以 不可行。
快速检查
(若 ,而 时允许定义域内所有点,用最小的有效非负 表达 。指出取 时会被错误排除的点。)
解答 · 答案
最大违反量为 ,故 有效,而 是最小有效非负值。若 ,原本允许的不启用点 会违反 。
快速检查
(若 ,写出表达 的四条不等式,并求 和 时的 。)
解答 · 答案
四条不等式为 和 。在 ,第二组给出 ,故 ;在 ,第一组给出 。
快速检查
(在 和“ 或 ”下最小化 。用上面的择一表述求解两个分支。 可行吗?)
解答 · 答案
时 ,最小值为 ; 时 ,最小值为 。因此整体最小值是 。 不属于任何一个区间,配任何开关值都不可行。