运筹学整数规划清华大学出版社.ppt

一、整数规划的模型 二、分枝定界法 （二）、例题 练习：用分枝定界法求解整数规划问题 （图解法） 例2、用分枝定界法求解整数规划问题 （单纯形法） 练习：用分枝定界法求解整数规划问题 （单纯形法） 算法步骤 四、0－1 整数规划 练习：用隐枚举法求解0—1规划问题 五、指派问题 例1： 例2、 练习： 4/3 -1/3 1 0 0 4 x3 0 -5/9 2/9 0 1 0 4/3 x2 4 2/9 1/9 0 0 1 8/3 x1 11 -2/9 x5 -19/9 x4 0 0 0 －Z x3 x2 x1 b XB CB 6 0 -1 1 0 0 0 x3 0 -5/2 0 1/2 0 1 0 3 x2 4 1 0 0 0 0 1 2 x1 11 0 1 x5 -2 1/2 x4 -1 -9/2 s1 0 0 0 －Z 0 0 0 3 x5 0 x3 x2 x1 b XB CB （2 ，3） 0－1 整数规划是一种特殊形式的整数规划,这时的决策变量xi 只取两个值0或1,一般的解法为隐枚举法。 例1、求解下列0－1 规划问题 解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。 × 2 6 ( 1, 1, 1 ) × 3 ( 1, 1, 0 ) 8 ∨ 0 2 1 1 ( 1, 0, 1 ) × 1 5 ( 0, 1, 1 ) 3 ∨ 1 1 1 0 ( 1, 0, 0 ) －2 ∨ 2 4 1 4 ( 0, 1, 0 ) 5 ∨ －1 1 0 1 ( 0, 0, 1 ) 0 ∨ 0 0 0 0 ( 0, 0, 0 ) 是∨ 否× (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。 × 4 ( 1, 1, 1 ) × 1 ( 1, 1, 0 ) 8 ∨ 8 0 2 1 1 ( 1, 0, 1 ) × 3 ( 1, 0, 0 ) × 3 ( 0, 1, 1 ) × -2 ( 0, 1, 0 ) 5 ∨ 5 －1 1 0 1 ( 0, 0, 1 ) 0 ∨ 0 0 0 0 0 ( 0, 0, 0 ) 是∨ 否× (0) (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 例2、求解下列0－1 规划问题 解：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换： 令 x1 ＝1－ x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中，但需重新调整变量编号。令 x3′ = x1′, x4′ = x2′得到下式。 可以从( 1,1,1,1 )开始试算， x′(3)＝( 1,1,0,1 )最优解。 ∴ x(3)＝( 1,0,1,0 )是原问题的最优解，Z* =－2 例3、求解下列0－1 规划问题 令 y1=x5, y2=x4,