如果有m个互相排斥的约束条件 amxn≤b 为了保证这m个约束条件只有一个起作用,我们引入m个0-1变量y(=1,2,…,m) 和一个充分大的常数M,而下面这一组m+1个约束条件 anY ≤b+yM ,2, 就合于上述的要求。这是因为,由于(2),m个y中只有一个能取0值,设y,=0, 代入(1),就只有i=1的约束条件起作用,而别的式子都是多余的 3.1.3关于固定费用的问题( Fixed Cost problem) 在讨论线性规划时,有些问题是要求使成本为最小。那时总设固定成本为常数,并 在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线 性规划来描述,但可改变为混合整数规划来解决,见下例。 例5某工厂为了生产某种产品,有几种不同的生产方式可供选择,如选定的生产 方式投资高(选购自动化程度高的设备),由于产量大,因而分配到每件产品的变动成 本就降低;反之,如选定的生产方式投资低,将来分配到每件产品的变动成本可能增加。 所以必须全面考虑。今设有三种方式可供选择,令 x,表示采用第j种方式时的产量 c,表示采用第j种方式时每件产品的变动成本 k,表示采用第j种方式时的固定成本。 为了说明成本的特点,暂不考虑其它约束条件。采用各种生产方式的总成本分别为 k+cx,当x>0 P j=1,2,3 在构成目标函数时,为了统一在一个问题中讨论,现引入0-1变量y,令 「1,当采用第种生产方式,即x;>0时 y (3) 0,当不采用第神种生产方式,即x;=0时 于是目标函数 min :=(k,y, +Cx1)+(k2y2+C2x2)+(k3J3+Csx) (3)式这个规定可表为下述3个线性约束条件 yE≤x≤y,M,j=1,2,3 其中E是一个充分小的正常数,M是个充分大的正常数。(4)式说明,当x>0时y 必须为1:当x,=0时只有y为0时才有意义,所以(4)式完全可以代替(3)式。 3.20-1型整数规划解法之一(过滤隐枚举法) 解0-1型整数规划最容易想到的方法,和一般整数规划的情形一样,就是穷举法, 即检査变量取值为θ或1的每一种组合,比较目标函数值以求得最优解,这就需要检查 变量取值的2″个组合。对于变量个数n较大(例如n>100),这几乎是不可能的。因 此常设计一些方法,只检査变量取值的组合的一部分,就能求到问题的最优解。这样的 方法称为隐枚举法( Implicit Enumeration),分枝定界法也是一种隐枚举法。当然,对-20- 如果有 m 个互相排斥的约束条件： ai1x1 +L+ ain xn ≤ bi i =1,2,L,m 为了保证这 m 个约束条件只有一个起作用，我们引入 m 个0 −1变量 y (i 1,2, ,m) i = L 和一个充分大的常数 M ，而下面这一组m +1个约束条件 ai1x1 +L+ ain xn ≤ bi + yi M i =1,2,L,m （1） y1 +L+ ym = m −1 （2） 就合于上述的要求。这是因为，由于（2），m 个 i y 中只有一个能取 0 值，设 * = 0 i y ， 代入（1），就只有 * i = i 的约束条件起作用，而别的式子都是多余的。 3.1.3 关于固定费用的问题（Fixed Cost Problem） 在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并 在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线 性规划来描述，但可改变为混合整数规划来解决，见下例。 例 5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产 方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成 本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。 所以必须全面考虑。今设有三种方式可供选择，令 j x 表示采用第 j 种方式时的产量； j c 表示采用第 j 种方式时每件产品的变动成本； j k 表示采用第 j 种方式时的固定成本。 为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为 ⎪⎩ ⎪ ⎨ ⎧ = + > = 0, 0 , 0 j j j j j j x k c x x P 当 当 j = 1,2,3. 在构成目标函数时，为了统一在一个问题中讨论，现引入0 −1变量 j y ，令 ⎪⎩ ⎪ ⎨ ⎧ = = > 0 . 0 0, 1, 当不采用第 种生产方式，即 时 当采用第 种生产方式，即 时， j j x j j x j y （3） 于是目标函数 min ( ) ( ) ( ) 1 1 1 1 2 2 2 2 3 3 3 3 z = k y + c x + k y + c x + k y + c x （3）式这个规定可表为下述 3 个线性约束条件： y j ε ≤ x j ≤ y jM , j = 1,2,3 （4） 其中ε 是一个充分小的正常数，M 是个充分大的正常数。（4）式说明，当 x j > 0时 j y 必须为 1；当 x j = 0时只有 j y 为 0 时才有意义，所以（4）式完全可以代替（3）式。 3.2 0 −1型整数规划解法之一（过滤隐枚举法） 解0 −1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法， 即检查变量取值为 0 或 1 的每一种组合，比较目标函数值以求得最优解，这就需要检查 变量取值的 n 2 个组合。对于变量个数 n 较大（例如 n >100 ），这几乎是不可能的。因 此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的 方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对