《运筹学——整数规划.pptx》由会员分享，可在线阅读，更多相关《运筹学——整数规划.pptx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 对于对于0 01 1 规划问题，由于每个变量只取规划问题，由于每个变量只取0 0，1 1两个值，一般会用穷举法来解，即将所有两个值，一般会用穷举法来解，即将所有的的0 0，1 1 组合找出，使目标函数达到极值要求组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。定的条件，就能较快的求得最优解。第1页/共23页 隐枚举法隐枚举法(Implicit Enumeration)(Implicit Enumeration)这种方法
2、可以从所有变量等于零出发这种方法可以从所有变量等于零出发（初始点），然后依次指定一些变量（初始点），然后依次指定一些变量取值为取值为1 1，直到获得一个可行解，于是，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为可行解，再重复，依次检查变量为0 0，1 1的各种组合，对迄今为止最好的可行的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。解加以改进，直到获得最优解。第2页/共23页例例1 1 求下列问题：求下列问题：Max Z=3xMax Z=3x1 1-2x-2x2 2+5x+5x3 3 s.t.xs.t.x1
3、1+2x+2x2 2 -x-x3 3 2 (1)2 (1)x x1 1+4x+4x2 2+x+x3 3 4 (2)4 (2)x x1 1+x+x2 2 3 (3)3 (3)4x 4x2 2+x+x3 3 6 (4)6 (4)x xj j 0 0或或1 (5)1 (5)第3页/共23页解：解：容易看出容易看出(1,0,0)(1,0,0)满足约束条满足约束条件，对应件，对应Z=3Z=3，对，对Max ZMax Z来说，希望来说，希望Z Z 3,3,所以增加约束条件：所以增加约束条件：Z=3xZ=3x1 1-2x-2x2 2+5x+5x3 3 3 3 (0)(0)称为过滤性条件。初看起来，增加称为过
4、滤性条件。初看起来，增加约束条件需增加计算量，实际减少约束条件需增加计算量，实际减少了计算量。了计算量。第4页/共23页循环循环循环循环(X(X1 1,X,X2 2,X,X3 3)s.t.s.t.0 0s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满足足足足Z Z值值值值1 1(0,0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10 01 1yesyes5 53 3(0,1,0)(0,1,0)-2-2nono4 4(0,1,1)(0,1,1)3 31 15 5nono5 5(1,0,0)(1,0,0)3
5、31 11 11 10 0yesyes3 36 6(1,0,1)(1,0,1)8 80 02 21 11 1yesyes8 87 7(1,1,0)(1,1,0)1 1nono8 8(1,1,1)(1,1,1)6 62 26 6nono最优解最优解（1，0，1）Z=8第5页/共23页增加约束条件（增加约束条件（0 0）（）（Z Z 3)3)后实际做了后实际做了2424次运算，次运算，而原问题需要计算而原问题需要计算2 23 3*4=32*4=32次运算（次运算（3 3个变量，个变量，4 4个约束条件个约束条件）。）。第6页/共23页注意：注意：改进过滤性条件，在计算改进过滤性条件，在计算过程中随
6、时调整右边常数。过程中随时调整右边常数。价值系数按递增排列。价值系数按递增排列。以上两种方法可减少计算量。以上两种方法可减少计算量。第7页/共23页循循循循环环环环(X(X2 2,X,X1 1,X,X3 3)s.t.s.t.0 0s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满足足足足Z Z值值值值1 1(0,0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10 01 1yeyes s5 5改进过滤性条件改进过滤性条件Z Z 5 5 (0)(0)循循循循环环环环(X(X2 2,X,X1 1,X,X3 3)s
7、.t.s.t.00s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满足足足足Z Z值值值值3 3(0,1,0)(0,1,0)3 3nono4 4(0,1,1)(0,1,1)8 80 02 21 11 1yeyes s8 8第8页/共23页改进过滤性条件Z 8 (0)循循循循环环环环(X(X2 2,X,X1 1,X,X3 3)s.t.s.t.00s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满足足足足Z Z值值值值5 5(1,0,0)(1,0,0)-2-2nono6 6(1,0,1)(1,0,1)3 3
8、nono7 7(1,1,0)(1,1,0)1 1nono8 8(1,1,1)(1,1,1)6 6nono最优解(X2,X1,X3)=（0，1，1）Z=8实际只计算了16次第9页/共23页例例2 2 求下列问题：求下列问题：Max Z=3xMax Z=3x1 1+4x+4x2 2+5x+5x3 3+6x+6x4 4 s.t.2xs.t.2x1 1+3x+3x2 2+4x+4x3 3+5x+5x4 4 15 15 x xj j 0 0且为整数且为整数解：先变换解：先变换x xj j为为0-10-1变量变量 x=yx=y0 0+2y+2y1 1+2+22 2y y2 2+.2+.2k ky yk k
9、第10页/共23页解：解：先变换先变换x xj j为为0-10-1变量变量 x=yx=y0 0+2y+2y1 1+2+22 2y y2 2+.2+.2k ky yk kx x1 1 7 x 7 x1 1=y=y0101+2y+2y1111+2+22 2y y2121x x2 2 5 x 5 x2 2=y=y0202+2y+2y1212+2+22 2y y2222x x3 3 3 x 3 x3 3=y=y0303+2y+2y1313x x4 4 3 x 3 x4 4=y=y0404+2y+2y1414代入原问题，得到：代入原问题，得到：第11页/共23页Max Z=3 y01+6y11+12y2
10、1 +4y02+8y12+16y22 +5 y03+10y13 +6 y04+12y14 s.t.2y01+4y11+8y21+3y02+6y12 +12y22+4 y03+8y13 +5 y04 +10y14 15 yij=0或=1第12页/共23页用隐枚举法可得到：用隐枚举法可得到：y y1111=y=y21 21=y=y02 02=1 =1 其他全为零其他全为零最优解最优解（6 6，1 1，0 0，0 0）Z=22Z=22 第13页/共23页 例例3、求解下列、求解下列01 规划问题规划问题 解：由于目标函数中变量解：由于目标函数中变量x1,x2,x4 的系数均为负数，可的系数均为负数，
11、可作如下变换：作如下变换：令令 x1 1 x1,x2=1-x2,x3=x3,x4=1-x4带入原题带入原题中，但需重新调整变量编号。令中，但需重新调整变量编号。令 x3=x1,x4=x2得到下式。得到下式。第14页/共23页 可以从可以从()开始试算，开始试算，x(3)(1.1.0.1)最优解。最优解。x(3)(1.0.1.0)是原问题的最优解，是原问题的最优解，Z*=2第15页/共23页例例4、求解下列、求解下列01 规划问题规划问题令令 y1=x5,y2=x4,y3=x2,y4=x3,y5=x1 得到下式得到下式第16页/共23页y1.y2.y3.y4.y5约束条件约束条件满足条件满足条件
12、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 -4 8(0.0.0.0.1)3 -2 所以，所以，Y*=（），原问题的最优解为：（），原问题的最优解为：X*（），（），Z*=8第17页/共23页练习：用隐枚举法求解练习：用隐枚举法求解0101规划问题规划问题第18页/共23页0-10-1规划应用规划应用华美公司有华美公司有华美公司有华美公司有5 5 5 5个项目被列入投资计划，各项目个项目被列入投资计划，各项目个项目被列入投资计划，各项目个项目被列入投资计划，各项
13、目的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：项目项目项目项目 投资额投资额投资额投资额(万元万元万元万元)投资收益投资收益投资收益投资收益(万元万元万元万元)1 12102101501502 23003002102103 310010060604 413013080805 5260260180180第19页/共23页该公司只有该公司只有600600万元资金可用于投资，万元资金可用于投资，由于技术原因，投资受到以下约束：由于技术原因，投资受到以下约束：在项目在项目1 1、2 2和和3 3中必须有一项被选中；中必
14、须有一项被选中；项目项目3 3和和4 4只能选中一项；只能选中一项；项目项目5 5被选中的前提是项目被选中的前提是项目1 1必须被选必须被选中。中。如何在上述条件下，选择一个最如何在上述条件下，选择一个最好的投资方案，使收益最大。好的投资方案，使收益最大。第20页/共23页解：令 1 选中该项目选中该项目 0 未选中该项目未选中该项目xi=Max Z=150 xMax Z=150 x1 1+210 x210 x2 2+60 x60 x3 3+80 x+80 x4 4+180 x180 x5 5 s.t.s.t.210 x210 x1 1+300 x300 x2 2+100 x+100 x3 3+130 x+130 x4 4+260 x260 x5 5 600 600 x x1 1+x x2 2+x x3 3 =1=1 x x3 3+x+x4 4 1 1 x x5 5 x x1 1 xi=1或0第21页/共23页点击这里进入“指派问题”的学习第22页/共23页感谢您的观看！第23页/共23页