运筹学——整数规划PPT课件

1、 对于对于0 01 1 规划问题，由于每个变量只取规划问题，由于每个变量只取0 0，1 1两个值，一般会用穷举法来解，即将所有的两个值，一般会用穷举法来解，即将所有的0 0，1 1 组合找出，使目标函数达到极值要求就可求组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。件，就能较快的求得最优解。第1页/共23页第2页/共23页第3页/共23页第4页/共23页第5页/共23页第6页/共23页第7页/共23页第8页/共23页第

2、9页/共23页第10页/共23页第11页/共23页第12页/共23页第13页/共23页 例例3、求解下列、求解下列01 规划问题规划问题4 . 3 . 2 . 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：由于目标函数中变量解：由于目标函数中变量x1, x2 , x4 的系数均为负数，的系数均为负数，可作如下变换：可作如下变换： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4带入原题带入原题中，但需重新调整变量编号。令中，但需重新调整变量编号。令 x3 = x1, x4 = x2得到下

3、式。得到下式。第14页/共23页 1 0,435 2 461 2 1173max4321432432143214321或或xxxxxxxxxxxxxxxxxxxZ 可以从可以从( )开始试算，开始试算， x(3)( 1.1.0.1 )最优解。最优解。 x(3)( 1.0.1.0 )是原问题的最优解，是原问题的最优解，Z* =2第15页/共23页例例4、求解下列、求解下列01 规划问题规划问题 )5 . 4 . 3 . 2 . 1( 1054 24423 248510min543215432154321jxxxxxxxxxxxxxxxxZj或或令令 y1=x5, y2=x4, y3=x2, y4

4、=x3, y5=x1 得到下式得到下式 )5 . 4 . 3 . 2 . 1( 10(2) 524(1) 4342 108542min543215432154321jyyyyyyyyyyyyyyyyZj或或第16页/共23页y1 . y2. y3 . y4. y5约束条件约束条件满足条件满足条件Z 值值 (1) (2)是是 否否( 0. 0. 0. 0. 0 ) 0 0( 1. 0. 0. 0. 0 ) 1 -1( 0. 1. 0. 0. 0 ) -1 1 ( 0. 0. 1. 0. 0 ) -2 1( 0. 0. 0. 1. 0 ) 4 -48( 0. 0. 0. 0. 1 ) 3 -2 所以，所以， Y*= （），原问题的最优解为：（），原问题的最优解为： X* （），（），Z* =8第17页/共23页练习：用隐枚举法求解练习：用隐枚举法求解0101规划问题规划问题 )5 , 2 , 1( 1 01 2 02236224 53 31075min5432543215432154321jxxxxxxxxxxxxxxxxxxxxZj或或第18页/共