第5章 整数-割平面法和0-1整数规划.ppt

第3节 Gomory割平面解法;基本思路示意; 不考虑条件⑤，可求得相应线性规划的最优解(即问题B)： x1=3/4，x2=7/4，max z=10/4但不合于整数条件。 ;思路:  寻找左图中像CD那样的直线切割域R，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R’的一个极点，从而进入单纯型法中顶点的选择之列.;在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束： -x1+x2+x3 =1 ⑥ 3x1+x2 +x4=4 ⑦ 不考虑条件⑤，用单纯形表解题，见表5-2。;表5-2; 上述解不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。就可以得到整数的最优解。; 为得到整数最优解，将上式变量的系数和常数项都分解成整数和非负真分数两部分之和;1) 要求x1、x2都是非负整数，于是由条件⑥、⑦可知x3、x4也都是非负整数; 否则，则应在引入x3、x4之前乘以适当常数，使之都是整数。 2) 在上式中从等式左边看是整数；等式右边也应是整数。但在等式右边的(·)内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是得到下面新的约束: ;即 -3x3-x4≤-3 ⑧ 这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。 引入松弛变量x5，得到等式 -3x3-x4+x5=-3 将新的约束方程加到表5-2的最终计算表，得表5-3。 ;表5-3; 从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算;将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。;注意：新得到的约束条件⑧ -3x3-x4≤-3如用x1、x2表示，由⑥、⑦式得;求一个切割方程的步骤归纳为：;例如： 若b=2.35，则N=2，f=0.35 若b=-0.45，则N=-1,f=0.55 代入(5-4)式得 ;小结: 由前面公式可知： ① 切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。 ② 没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。;第4节 0-1型整数线性规划;注：;4.1 引入0-1变量的实际问题;解题时先引入0-1变量xi (=1,2，…，7);2. 相互排斥的约束条件;于是(5-9)式和(5-10)式可由下述的条件(5-11)式和(5-12)式来代替： 5x1+4x2≤24+yM (5-11) 7x1+3x2≤45+(1-y)M (5-12) ; 为了保证这m个约束条件只有一个起作用，引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，而下面这一组m+1个约束条件 αi1x１+αi2x2+…+αinxn≤bi+yiM， i=1,2,…，m (5-13) y1+y2+…+ym=m-1 (5-14) 就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取非0值，设yi*=0，代入(5-13)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。;例5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令 xj ——表示采用第j种方式时的产量； cj ——表示采用第j种方式时每件产品的变动成本； kj ——表示采用第j种方式时的固定成本。 为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为;在构成目标函数时，为??统一在一个问题中讨论，现引入0-1变量yj，令 ;(5-15)式这个规定可由以下3个线性约束条件表示：;4.2 0-1型整数线性规划的解法;举例说明一种解0-1型整数线性规划的隐枚举法;解题时先通过试探的方法找一个可行解，(x1，x2，x3) =(1，0，0) ，算出相应的目标函数值z=3。;表5-5; 本例计算过程如表5-5，于是求得最优解(x1，x2，x3)=(1，0，1),