线性规划理论与模型应用课件.ppt

1、主要内容4.1 整数规划模型及穷举法整数规划模型及穷举法整整数数规规划划模模型型及及穷穷举举法法Zxxxxxxxxtsxxz21212121210054956.65max，654595611每台利润资源数量乙甲BA整整数数规规划划模模型型及及穷穷举举法法项目不投资项目投资jjxj01),.,2,1(10.max11njxbxatsxczjnjjjnjjj或整整数数规规划划模模型型及及穷穷举举法法址不建厂第址建厂第iiyi01整整数数规规划划模模型型及及穷穷举举法法10,0),.,2,1(.min11111或iijmiiijnjiiijminiiinjijijyxnjbxyaxtsydxcz例例

2、4.1是一个全整数规划问题，例是一个全整数规划问题，例4.2是一个是一个01规划规划问题，例问题，例4.4是一个混合整数规划问题。是一个混合整数规划问题。整整数数规规划划模模型型及及穷穷举举法法Zxxxxxxxxtsxxz21212121210054956.65max，整整数数规规划划模模型型及及穷穷举举法法4.2 分支定界法分支定界法分分支支定定界界法法ZxxbAxtscxz，0.min0*txZxxxxbAxtscxzt,0.min*ZxxxxbAxtscxzt,01.min*分分支支定定界界法法ZxxxxxxtsxxzP，054956.65max)(2121210Zxxxxxxxtsxx

3、zP，0254956.65max)(12121211ZxxxxxxxtsxxzP，0354956.65max)(12121212分分支支定定界界法法分分支支定定界界法法ZxxxxxxxxtsxxzP，03254956.65max)(212121213ZxxxxxxxxtsxxzP，04254956.65max)(212121214分分支支定定界界法法ZxxxxxxxxxtsxxzP，014254956.65max)(1212121215ZxxxxxxxxxtsxxzP，024254956.65max)(1212121216分分支支定定界界法法P0z=135/4x1=9/4x2=15/4P1z=

4、100/3x1=2x2=35/9P2z=33x1=3x2=3P3z=28x1=2x2=3P4z=33x1=9/5x2=4分分支支定定界界法法00065451095601115443210 xxxxxxP41354141541549452494149143210001001xxxxxxP从这一表格可以建立从这一表格可以建立P1和和P2的初始单纯形表格。如下所示的初始单纯形表格。如下所示分分支支定定界界法法ZxxxxxxxxxxtsxxzP，0254956.65min)(5142132121193535329194913935959121413541415414149541541452494149

5、14135414155415414524941491543211000100010210001000100010001000210001010001xxxxxxxxxxxxxxP对对P2、P2、类似处理。类似处理。分分支支定定界界法法4.3 割平面法割平面法割割平平面面法法ZxxbAxtscxz，0.min0*qx)(*qijFjijqxbxyx)10()10(iiiiijijijijffNbffNy割割平平面面法法FjjijiiFijijqiiFjjijFijijqxffNxNxfNxfxNx010Fjjijixff在此不等式约束中加入一个松弛变量变为等式约束，此方在此不等式约束中加入一个松

6、弛变量变为等式约束，此方程即被称为程即被称为割平面方程割平面方程，将该方程添入到原问题的松弛问，将该方程添入到原问题的松弛问题中去，必然切割掉可行域中的题中去，必然切割掉可行域中的x*，但没有切割掉任何整，但没有切割掉任何整数解。数解。0Fjjijixff割割平平面面法法割割平平面面法法iknFjjijfxxf1割割平平面面法法Zxxxxxxtsxxz,02452.max212121Zxxxxxxxxtsxxz,02452.min42132121割割平平面面法法6165676161138313224145214141121*23343434321000110000141000112101450

7、11200112101450112xxxxxxxxxxxx割割平平面面法法0)3132(3243xx323132543xxx2121423212112616532313256761611383132254321000231200001210010000100001010 xxxxxxxxxxx割割平平面面法法212121653xxx100000121010004510001110001201001000001000203120000012010010341221212121216523212112654321xxxxxxxxxxxxxx0)2121(2153xx割割平平面面法法3,)2,1(*

8、zxT3,)1,2(*zxT4.4 0-1规划及隐枚举法规划及隐枚举法),.,2,1(10),.,2,1(.min11njxmibxatsxczjinjjijnjjj或0|1规规划划及及隐隐枚枚举举法法是等式约束是等式约束iiinjjijbxa1如如225322121xxxx7322532212121xxxxxx0|1规规划划及及隐隐枚枚举举法法0|1规规划划及及隐隐枚枚举举法法0|1规规划划及及隐隐枚枚举举法法)5,.,2,1(1042352333.57428min543215432154321jxxxxxxxxxxxtsxxxxxzj或解：本问题已经是标准形，即原问题为解：本问题已经是标准

9、形，即原问题为P0，全为自由变量，全为自由变量均取均取0 0值，显然不是可行解。取值，显然不是可行解。取x1为固定变量，进行分支为固定变量，进行分支P0z=0 x=(0,0,0,0,0)TP1z1=0 x=(0,0,0,0,0)TP2z2=8x=(1,0,0,0,0)T可行解，停止分支可行解，停止分支继续分支继续分支0|1规规划划及及隐隐枚枚举举法法P1z1=0 x=(0,0,0,0,0)TP3z3=0 x=(0,0,0,0,0)TP4z4=2x=(0,1,0,0,0)T不可行，停止分支不可行，停止分支P5z5=2x=(0,1,0,0,0)TP6z5=6x=(0,1,1,0,0)T可行解，停止分支可行解，停止分支继续分支继续分支0|1规规划划及及隐隐枚枚举举法法P5z5=2x=(0,1,0,0,0)TP7z7=2x=(0,1,0,0,0)T不可行，停止分支不可行，停止分支P8z8=9x=(0,1,0,1,0)T目标值目标值66，停止分支，停止分支所有分支均已停止分支，存在可行解，最优解为：所有分支均已停止分支，存在可行解，最优解为：x*=(0,1,1,0,0)T，z*=z6=6。0|1规规划划及及隐隐枚枚举举法法