运筹学第三章课件.ppt

1、第第3 3章整数规划章整数规划2线性规划的决策变量取值可以是任意非负实数，但线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有许多实际问题中，只有当决策变量的取值为整数时才有意义。意义。例如，产品的件数、机器的台数、装货的车数、完例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。成工作的人数等，分数或小数解显然是不合理的。对某一个项目要不要投资的决策问题，可选用一个对某一个项目要不要投资的决策问题，可选用一个逻辑变量逻辑变量 x，当，当x=1表示投资，表示投资，x=0表示不投资。表示不投资。3.1 整数规划的数学模

2、型整数规划的数学模型 纯整数规划纯整数规划(IP)：xj全部取整数全部取整数 混合整数规划混合整数规划(MIP)：xj部分取整数部分取整数 0-1整数规划整数规划(BIP)：整数变量只能取：整数变量只能取0或或1分类分类第第3 3章整数规划章整数规划3【例【例3-1】某人有一背包可以装某人有一背包可以装10公斤重、公斤重、0.025m3的物品。的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表值如表3-1所示。问两种物品各装多少件，才能使所装物品的所示。问两种物品各装多少件，才能使所装物品的总价值最大？总价值最大？表表3-13

3、-1【解】【解】设甲、乙两种物品各装设甲、乙两种物品各装x1、x2件，则数学模型为：件，则数学模型为：且为整数且为整数,0,255.22108.02.134max21212121xxxxxxxxZ(3-1)物品物品重量（公斤重量（公斤/件）件）体积（体积（m3/件）件）价值价值(元元/件件)甲甲乙乙1.21.20.80.80.0020.0020.00250.00254 43 33.1 整数规划的数学模型整数规划的数学模型 第第3 3章整数规划章整数规划4 【补充例】【补充例】投资决策问题。某公司有投资决策问题。某公司有5个项目被列入投资计划，个项目被列入投资计划，各项目的投资额和期望的投资收益

4、如下表各项目的投资额和期望的投资收益如下表3.1 整数规划的数学模型整数规划的数学模型 该公司只有该公司只有600万元资金可用于投资，由于技术上的原因，万元资金可用于投资，由于技术上的原因，投资受到以下约束：投资受到以下约束：（1）在项目）在项目1、2和和3中必须且只有一项被选中；中必须且只有一项被选中；（2）项目）项目3和项目和项目4最多只能选中一项；最多只能选中一项；（3）项目）项目5被选中的前提是项目被选中的前提是项目1必须被选中。必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大？如何在上述条件下选择一个最好的投资方案，使投资收益最大？项目投资额（万元）投资收益（万元）

5、121016023002103150604130805260180第第3 3章整数规划章整数规划5【解】【解】设设xj 为选择第为选择第 j（j=1,2,3,4,5)个项目的决策个项目的决策 )5,4,3,2,110116002601301503002101808060210160max15433215432154321jxxxxxxxxxxxxxxxxxxzj（或或)5,4,3,2,101 jjjxj（没有选中没有选中项目项目选中选中项目项目设设3.1 整数规划的数学模型整数规划的数学模型 第第3 3章整数规划章整数规划6【例【例3-2】在例在例3-1中，假设此人还有一只旅行箱，最大中，假设

6、此人还有一只旅行箱，最大载重量为载重量为12公斤，其体积是公斤，其体积是0.02m3。背包和旅行箱只能。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品选择其一，建立下列几种情形的数学模型，使所装物品价值最大。价值最大。（1）所装物品不变；）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，）如果选择旅行箱，则只能装载丙和丁两种物品，每件物品的重量、体积和价值如下表所示每件物品的重量、体积和价值如下表所示3.1 整数规划的数学模型整数规划的数学模型 物品物品重量（公斤重量（公斤/件）件）体积（体积（m3/件）件）价值价值(元元/件件)丙丙丁丁1.81.80.60.6

7、0.00150.00150.0020.0024 43 3第第3 3章整数规划章整数规划7【解】【解】（1）引入）引入01变量变量 yj，令，令)2,1(0,1 jjjyj种种方方式式装装载载时时不不采采用用第第，种种方方式式装装载载时时采采用用第第 j=1,2分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。3.1 整数规划的数学模型整数规划的数学模型 )2,1(10)2,1(,0120255.2212108.02.134max212121212121jyixyyyyxxyyxxxxZji或或且取整数且取整数(3-2)此问题也可以建立两个整数规划模型。此问题也可以建立两个整数规划模型。第

8、第3 3章整数规划章整数规划8 )2,1(10)2,1(,01)33(2025.1)33(126.08.1)33(255.22)33(108.02.134max2112112122122121iyjxyydMyxxbMyxxcMyxxaMyxxxxZij或或且且取取整整数数（2）由于不同载体所装物品不一样，数学模型为）由于不同载体所装物品不一样，数学模型为3.1 整数规划的数学模型整数规划的数学模型 其中其中MM为充分大的正数。为充分大的正数。当使用背包时当使用背包时(y1=1,y2=0)，式，式(b)和和(d)是多余的；是多余的；当使用旅行箱时当使用旅行箱时(y1=0,y2=1)，式，式(a

9、)和和(c)是多余的。是多余的。背包约束背包约束旅行箱约束旅行箱约束第第3 3章整数规划章整数规划9（1）右端常数是）右端常数是k个值中的一个时，类似式个值中的一个时，类似式(3-2)的约束的约束条件为条件为1111kiikiiinjjijyybxa，3.1 整数规划的数学模型整数规划的数学模型 同样可以讨论对于有同样可以讨论对于有m个条件互相排斥、有个条件互相排斥、有m（m、m）个条件起作用的情形。）个条件起作用的情形。第第3 3章整数规划章整数规划10 （2 2）对于）对于m 个（组）个（组）条件中有条件中有k（m）个（组）起）个（组）起作用时，作用时，类似式类似式(3-3)的的约束条件写

10、成约束条件写成这里这里yi=1表示第表示第 i 组约束不起作用（如组约束不起作用（如y1=1式式(3-3b)、(3-3d)不起作用），不起作用），yi=0表示第表示第 i个约束起作用。当约个约束起作用。当约束条件是束条件是“”符号时右端常数项应为符号时右端常数项应为iibMy3.1 整数规划的数学模型整数规划的数学模型 miinjiijijkmyMybxa11,第第3 3章整数规划章整数规划11【例【例3-3】试引入试引入01变量将下列各题分别表达为一般线性约变量将下列各题分别表达为一般线性约束条件束条件（1）x1+x26或或4x1+6x210或或2x1+4x220（2）若）若x15，则，则x

11、20，否则，否则x28（3）x2取值取值0，1，3，5，7【解】【解】（1）3个约束只有个约束只有1个起作用个起作用1211221231236461024202011,2,3jxxy Mxxy Mxxy Myyyyj或，3,2,1101)1(2042)1(1064)1(6321321221121jyyyyMyxxMyxxMyxxj，或或或3.1 整数规划的数学模型整数规划的数学模型 如果要求至少一个条件满足，模型如何改变？如果要求至少一个条件满足，模型如何改变？第第3 3章整数规划章整数规划12（3）右端常数是）右端常数是5个值中的个值中的1个个 4,3,2,1101753432143211j

12、yyyyyyyyyxj，或或 10)1(8)1(552121或或yMyxMyxyMxyMx（2）两组约束只有一组起作用）两组约束只有一组起作用3.1 整数规划的数学模型整数规划的数学模型(1)(2)(3)(4)10,1855212112112221或或yyyyMyxMyxMyxMyx第第3 3章整数规划章整数规划13【例【例3-4】企业计划生产企业计划生产4000件某种产品，该产品可自件某种产品，该产品可自己加工、外协加工任意一种形式生产。已知每种生产的己加工、外协加工任意一种形式生产。已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的固定费用、生产该产品的单件成本以及每种生产形式

13、的最大加工数量（件）限制如表最大加工数量（件）限制如表32所示，怎样安排产品所示，怎样安排产品的加工使总成本最小。的加工使总成本最小。表表 32 固定成本（元）固定成本（元）变动成本变动成本（元件）（元件）最大加工数最大加工数（件）（件）本企业加工本企业加工50081500外协加工外协加工80052000外协加工外协加工6007不限不限3.1 整数规划的数学模型整数规划的数学模型 第第3 3章整数规划章整数规划14【解】【解】设设xj为采用第为采用第 j（j=1,2,3）种方式生产的产品数量，）种方式生产的产品数量，生产费用为生产费用为3.1 整数规划的数学模型整数规划的数学模型 其中其中kj

14、是固定成本，是固定成本，cj是可变成本。是可变成本。设设01变量变量yj )0(0)0()(jjjjjjjxxxckxC)3,2,1()00)01 jxjxjyjjj种种加加工工方方式式（不不采采用用第第（种种加加工工方方式式采采用用第第第第3 3章整数规划章整数规划15)7600()5800()8500(min332211xyxyxyZ )3,2,1(01)3,2,1(0200015004000)3,2,1(21321jyjxxxxxxjMyxjjjj或或（3-4）用用WinQSB软件求解得到：软件求解得到：X(0，2000，2000)T ，Y(0，1，1)T，Z=254003.1 整数规划

15、的数学模型整数规划的数学模型 配合目标，使得只配合目标，使得只有选用有选用第第j 种种加工方加工方式才产生相应成本，式才产生相应成本，不选用第不选用第j 种种加工方加工方式就没有成本。式就没有成本。第第3 3章整数规划章整数规划16整数规划的一般形式：整数规划的一般形式：),2,1(),2,1(0),2,1(),(.min)max(11njxnjxmibxatsxczjjnjijijnjjj或或称线性规划模型称线性规划模型（）（）(LP)为（为（）的）的松弛问题松弛问题。),2,1(0),2,1(),(min)max(11njxmibxaxczjnjjijnjjj或或 每一个整数规划都对应一个

16、松弛问题，整数规划比它的松每一个整数规划都对应一个松弛问题，整数规划比它的松弛问题约束得更紧。弛问题约束得更紧。部分或全部取整3.1 整数规划的数学模型整数规划的数学模型 第第3 3章整数规划章整数规划173.1 整数规划的数学模型整数规划的数学模型 习题习题3.4【解】【解】令运动员甲、乙、丙、丁、戊编号为令运动员甲、乙、丙、丁、戊编号为1、2、3、4、5，项目，项目 高低杠、平衡木、鞍马、自由体操编号为高低杠、平衡木、鞍马、自由体操编号为1、2、3、4。设设)4,3,2,1;5,4,3,2,1(01 jijijixij号号运运动动员员参参加加项项目目不不选选号号运运动动员员参参加加项项目目

17、选选 项目项目运动员运动员1234高低杠高低杠平衡木平衡木鞍马鞍马自由体操自由体操1甲甲x11x12x13x142乙乙x21x22x23x243丙丙x31x32x33x344丁丁x41x42x43x445戊戊x51x52x53x54第第3 3章整数规划章整数规划18max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24+8.8x31 +8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52 +8.2x53+7.7x54x11+x12+x13+x143x21+x22+

18、x23+x243x31+x32+x33+x343x41+x42+x43+x443x51+x52+x53+x543x11+x21+x31+x41+x511x12+x22+x32+x42+x521x13+x23+x33+x43+x531x14+x24+x34+x44+x541x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44+x51+x52+x53+x54=10 xij=0 或或 1(i=1,2,3,4,5;j=1,2,3,4)3.1 整数规划的数学模型整数规划的数学模型 第第3 3章整数规划章整数规划191.整数规划模型

19、的特征整数规划模型的特征2.什么是纯（混合）整数规划什么是纯（混合）整数规划3.01规划模型的应用规划模型的应用下一节：纯整数规划的求解下一节：纯整数规划的求解3.1 整数规划的数学模型整数规划的数学模型 本节学习要点本节学习要点第第3 3章整数规划章整数规划20 整数规划解的特点整数规划解的特点u整数规划（整数规划（）的可行解集是其松弛问题（）的可行解集是其松弛问题（）的）的可行解集的子集。线性规划问题的可行解集是一个可行解集的子集。线性规划问题的可行解集是一个凸集凸集（稠密的），但整数规划的可行解集（稠密的），但整数规划的可行解集不是凸集不是凸集（离散型）。（离散型）。u如果松弛问题（如果

20、松弛问题（）的最优解是整数解，则一定是）的最优解是整数解，则一定是整数规划（整数规划（）的最优解。）的最优解。u整数规划（整数规划（）的最优值）的最优值不会优于不会优于松弛问题（松弛问题（）的最优值。的最优值。3.2 整数规划的求解整数规划的求解第第3 3章整数规划章整数规划213.2 整数规划的求解整数规划的求解 且均取整数且均取整数,0,255.22108.02.134max21212121xxxxxxxxZ 点点B为最优解为最优解 X(3.57，7.14)Z35.7用图解法求解例用图解法求解例3-1的松弛问题的松弛问题整数规划问题的可行解集是图中可行域内的整数点。整数规划问题的可行解集是

21、图中可行域内的整数点。8.3310108.02.121xx255.2221xx松弛问题的最优解松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B第第3 3章整数规划章整数规划22 松弛问题的最优解松弛问题的最优解 X(3.57，7.14)，Z35.7u “四舍五入四舍五入”得得 X=(4,7)不是可行解；不是可行解；u 用用“取整取整”法来解时，法来解时，X=(3,7)虽属可行解，但代入虽属可行解，但代入目标函数得目标函数得Z=33,并非最优。并非最优。u 该整数规划问题的该整数规划问题的最优解是最优解是X=(5,5)，最优值是，最优值是Z=35 即甲、乙两种物品各装

22、即甲、乙两种物品各装5件，总价值件，总价值35元。元。由图由图31知，点（知，点（5，5）不是）不是LP可行域的顶点，直可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊解，因此求解整数规划问题的最优解需要采用其它特殊方法。方法。3.2 整数规划的求解整数规划的求解8.3310108.02.121xx255.2221xx松弛问题的最优解松弛问题的最优解X=(3.57,7.14),z=35.7x1x2oAC10B第第3 3章整数规划章整数规划23【例【例3-5】用分支定界法求解例用分支定

23、界法求解例3-1【解】【解】先求对应的松弛问题先求对应的松弛问题 0,255.22108.02.1:34max212121021xxxxxxLPxxZ用图解法得到最优解用图解法得到最优解X（3.57,7.14）,Z0=35.7 且且均均取取整整数数,0,255.22108.02.134max21212121xxxxxxxxZ3.2.1 分支定界法分支定界法第第3 3章整数规划章整数规划248.3310108.02.121xx255.2221xx松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2.1 分支定界法分支定界法1010 x1x20

24、ABC 0,3255.22108.02.1:34max2112121121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255.22108.02.1:34max2112121221xxxxxxxLPxxZ得得到到两两个个线线性性规规划划及及增增加加约约束束4311 xxLP2:X=(4,6.5),Z2=35.51010 x10ACLP134LP1:X=(3,7.6),Z1=34.8x1B 0,64255.22108.02.1:34max21212121321xxxxxxxxLPxxZ，32222776LPxxxLP不不可可行行，得得到到，显显然然及及

25、进进行行分分枝枝，增增加加约约束束选选择择目目标标值值最最大大的的分分支支 67LP3:X=(4.33,6),Z3=35.33LP2LP3x1x1 0,464255.22108.02.1:34max211212121421xxxxxxxxxLPxxZ，：及及，得得到到线线性性规规划划及及进进行行分分枝枝，增增加加约约束束，选选择择由由于于541131354LPLPxxLPZZ 0,65255.22108.02.1:34max21212121521xxxxxxxxLPxxZ，1010 x10ACLP134LP1:X=(3,7.6),Z1=34.8x1B67LP2LP3LP5LP4:X=(4,6)

26、,Z4=34LP5:X=(5,5),Z5=35此为原此为原IP最优解最优解5的可行域是一条线段的可行域是一条线段4LP第第3 3章整数规划章整数规划28 尽管尽管LP1的解中的解中x2不为整数，但不为整数，但Z5Z1，因此，因此LP5的最优解就是原整数规划的最优解。若的最优解就是原整数规划的最优解。若Z5Z1，则要对则要对LP1进行分支。进行分支。3.2.1 分支定界法分支定界法第第3 3章整数规划章整数规划29上述分枝过程可用下图表示上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13

27、x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15 无可行解无可行解x27最优解3.2.1 分支定界法分支定界法第第3 3章整数规划章整数规划30分支定界法的步骤：分支定界法的步骤：1.求整数规划的松弛问题最优解；求整数规划的松弛问题最优解；2.若松弛问题的最优解满足整数要求，得到整数规划若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；的最优解，否则转下一步；3.2.1 分支定界法分支定界法3.任意选一个非整数解的变量任意选一个非整数解的变量xi，在松弛问题中加上，在松弛问题中加上约束约束xi

28、xi及及xixi+1组成两个新的松弛问题，称为分支组成两个新的松弛问题，称为分支。新的松弛问题具有特征：当原问题是求最大值时，目。新的松弛问题具有特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题是求最小值时，目标标值是分支问题的上界；当原问题是求最小值时，目标值是分支问题的下界；值是分支问题的下界；第第3 3章整数规划章整数规划314.检查所有分支的解及目标函数值，检查所有分支的解及目标函数值，若某分支的解是若某分支的解是整数并且目标函数值大于（整数并且目标函数值大于（max）等于其它分支的目标）等于其它分支的目标值，则将其它分支剪去不再计算值，则将其它分支剪去不再计算,若还存在非

29、整数解并且若还存在非整数解并且目标值大于（目标值大于（max）整数解的目标值，需要继续分支，）整数解的目标值，需要继续分支，再检查，直到得到最优解。再检查，直到得到最优解。分支原则：分支原则：始终选始终选Z值大的，且值大的，且xi中有分数的中有分数的LP进行进行分支。分支。定界原则：定界原则：满足取整要求，且目标函数值较已定的满足取整要求，且目标函数值较已定的 “界界”更优，则用该目标函数值替换，重新定界。更优，则用该目标函数值替换，重新定界。3.2.1 分支定界法分支定界法说明：说明：分支定界法适用于求解分支定界法适用于求解纯整数规划和混合整数规划纯整数规划和混合整数规划第第3 3章整数规划

30、章整数规划32设纯整数规划设纯整数规划 ),2,10max11njxbxaxcZjinjjijnjjj且为整数（且为整数（松弛问题的最优解松弛问题的最优解TmTbbbbBbbBX),()0,(2111 3.2.2 割平面法割平面法 ),2,10max11njxbxaxcZjinjjijnjjj（设设xi=不为整数，不为整数，为为非非基基变变量量kkkikiixxabx ib第第3 3章整数规划章整数规划33将将 分离成一个分离成一个整数整数与一个与一个非负真分数非负真分数之和：之和：ikiab及及 10,10,ikiikikikiiifffaafbb则有则有kkikkkijiiixfxafbx

31、 kkikikkijiixffxabx 等式两边都为整数等式两边都为整数,并且有并且有1 ikkikifxff3.2.2 割平面法割平面法第第3 3章整数规划章整数规划34加入松弛变量加入松弛变量si得得ikkikifxfs 此式称为以此式称为以xi行为源行（来源行）的行为源行（来源行）的割平面方程割平面方程，或分数切割，或分数切割式，或式，或R.E.Gomory(高莫雷高莫雷)约束方程。约束方程。将将Gomory约束加入到松弛问题的最优表中，用对偶单纯约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部形法计算，若最优解中还有非整数解，再继续切割，直

32、到全部变量为整数。变量为整数。0 kkikixff则则3.2.2 割平面法割平面法第第3 3章整数规划章整数规划35 324313322344613651xxxxxx例如，例如，311)651(65431 xxxx1行：行：移项：移项：43416565311xxxx 065653143 xx加入松弛变量加入松弛变量s1得割平面方程得割平面方程311465365 sxx同理，对于同理，对于x2行有：行有：322431331 sxx3.2.2 割平面法割平面法第第3 3章整数规划章整数规划36【例【例3-6】用割平面法求解下列用割平面法求解下列IPIP问题问题 且为整数且为整数0,10230463

33、4max21212121xxxxxxxxZ【解】【解】对应的松弛问题是对应的松弛问题是 0,102304634max21212121xxxxxxxxZ3.2.2 割平面法割平面法第第3 3章整数规划章整数规划37加入松弛变量加入松弛变量x3及及x4后，用单纯形法求解，得到最优表后，用单纯形法求解，得到最优表3-3。最优解最优解X(0)(5/2，15/4),不是不是IP的最优解。的最优解。选择表中的第一行选择表中的第一行(也可以选第二行也可以选第二行)为源行为源行Cj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4表表3-33.2.2

34、 割平面法割平面法252141431 xxx第第3 3章整数规划章整数规划38分离系数后改写成分离系数后改写成212)211(41431 xxx021412124341 xxxx加入松弛变量加入松弛变量x5得到高莫雷约束方程得到高莫雷约束方程22543 xxx将此式作为约束条件添加到表将此式作为约束条件添加到表33中，用对偶单纯形法计中，用对偶单纯形法计算，如表算，如表34所示所示 3.2.2 割平面法割平面法252141431 xxx第第3 3章整数规划章整数规划39Cj43000bCBXBx1x2x3x4x5430 x1x2x51000101/41/811/23/420015/215/42

35、j005/81/40430 x1x2x41000101/21/21/2001 1/43/81/2331j001/201/8最优解最优解X(1)(3，3)，最优值，最优值Z21。表表343.2.2 割平面法割平面法第第3 3章整数规划章整数规划40 x2x1ACBx1+2x2=100DC6x1+4x2=30Ex1+x26几何意义几何意义 由约束条件得：由约束条件得：x3=30-6x1-4x2 ,x4=10-x1-2x2 代入割平面方程代入割平面方程-x3-2x4-2，得，得 x1+x26 说明：说明：利用割平面法求利用割平面法求解整数规划问题时解整数规划问题时,若从若从最优单纯形表中选择具最优单

36、纯形表中选择具有有最大最大小（分）数部分小（分）数部分的非整分量所在行构造的非整分量所在行构造割平面方程，往往可以割平面方程，往往可以提高提高“切割切割”效率，减效率，减少少“切割切割”次数。次数。3.2.2 割平面法割平面法不含任何不含任何整数解整数解第第3 3章整数规划章整数规划415x15x1+9x245x2x1+x266960思考：思考：对于两个变量的纯整数规划问题是否可采用图解法。对于两个变量的纯整数规划问题是否可采用图解法。最优解最优解 x1=0,x2=5 且为整数且为整数0459568521212121xxxxxxxxz,max3.2.3 整数规划的图解法整数规划的图解法第第3

37、3章整数规划章整数规划42步骤：步骤：1.1.作出松弛问题的可行域。作出松弛问题的可行域。2.2.在可行域内作出所有的整数网格。在可行域内作出所有的整数网格。3.3.作目标函数等值线，将等值线平行移动，最后接触到作目标函数等值线，将等值线平行移动，最后接触到的网格点（或平行移动到松弛问题的最优解点再往回的网格点（或平行移动到松弛问题的最优解点再往回移，首先接触到的网格点），就是整数规划的最优解。移，首先接触到的网格点），就是整数规划的最优解。3.2.3 整数规划的图解法整数规划的图解法第第3 3章整数规划章整数规划431.理解分支与定界的含义理解分支与定界的含义2.选择合适的选择合适的“枝枝”

38、生生“枝枝”3.掌握何时停止生掌握何时停止生“枝枝”4.领会割平面法的基本原理领会割平面法的基本原理5.分离源行，求出分离源行，求出Gomory约束约束6.在最优表中增加在最优表中增加Gomory约束，用对偶单纯形法迭代约束，用对偶单纯形法迭代下一节：下一节：01规划的求解规划的求解3.2 整数规划的求解整数规划的求解本节学习要点本节学习要点第第3 3章整数规划章整数规划443.3.1 求解求解01整数规划的隐枚举法整数规划的隐枚举法隐枚举法的步骤：隐枚举法的步骤：1.找出任意一可行解，目标函数值为找出任意一可行解，目标函数值为Z0 2.原问题求最大值时，则增加一个约束原问题求最大值时，则增加

39、一个约束 1 1220(*)nnc xc xc xZ作为作为过滤条件过滤条件。当求最小值时，上式改为当求最小值时，上式改为小于等于小于等于约束。约束。列出所有可能解，对每个可能解先检验是否满足过滤条件，列出所有可能解，对每个可能解先检验是否满足过滤条件，若满足再检验其它约束，若不满足约束，则不可行，若所若满足再检验其它约束，若不满足约束，则不可行，若所有约束都满足，且目标值超过有约束都满足，且目标值超过Z0,则应更换过滤条件。则应更换过滤条件。3.4.目标函数值最大（最小）的解就是最优解。目标函数值最大（最小）的解就是最优解。3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划45【

40、例例3-7】用隐枚举法求解下列用隐枚举法求解下列BIPBIP问题问题 4,3,2,11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或或3.3 01规划的求解规划的求解(1)(2)(3)(4)第第3 3章整数规划章整数规划46jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)Zj1(0,0,0,0)9(1,0,0,0)2(0,0,0,1)10(1,0,0,1)3(0,0,1,0)11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)5(0,1,0,0)13(1,1,0,0)6(0,1

41、,0,1)14(1,1,0,1)7(0,1,1,0)15(1,1,1,0)8(0,1,1,1)16(1,1,1,1)表表35最优解：最优解：X(1,0,1,1)T，最优值，最优值Z143.3 01规划的求解规划的求解 z53 275 10616z119z14813118z8第第3 3章整数规划章整数规划473.3.2 分枝隐枚举法求解分枝隐枚举法求解BIP问题问题 将分枝定界法与隐枚举法结合起来用，得到分枝隐枚将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下：举法。计算步骤如下：（1）将）将BIP问题的目标函数的系数化为非负，如问题的目标函数的系数化为非负，如332max,13

42、2max212221 xxZxxxxZ令令3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划48当变量作了代换后，约束条件中的变量也相应作代换。当变量作了代换后，约束条件中的变量也相应作代换。（3）求主枝：目标函数是）求主枝：目标函数是max形式时令所有变量等于形式时令所有变量等于1，得到，得到目标值的上界；目标函数是目标值的上界；目标函数是min形式时令所有变量等于形式时令所有变量等于0，得到，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；否则转下一步；（4）分枝与定界：从第一个变量开始依次取）分

43、枝与定界：从第一个变量开始依次取“1”或或“0”，求，求极大值时其后面的变量等于极大值时其后面的变量等于“1”，求极小值时其后面的变量等，求极小值时其后面的变量等于于“0”，用分枝定界法搜索可行解和最优解。，用分枝定界法搜索可行解和最优解。分枝隐枚举法是从非可行解中进行分枝搜索可行解，第分枝隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（）步到第（3）步用了隐枚举法的思路，第（）步用了隐枚举法的思路，第（4）步用了分）步用了分枝定界法的思路。枝定界法的思路。3432max,1432max4213224321 xxxxZxxxxxxZ令令 (2)变量重新排序：变量依据目标函数系数值按升

44、排序；变量重新排序：变量依据目标函数系数值按升排序；3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划49停止分枝和需要继续分枝的原则：停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；停止分枝并剪枝；（3）后续分枝变量无论取）后续分枝变量无论取“1”或或“0”都不能得到可行解都不能得到可行解时停止分枝并剪枝；时停止分枝并剪枝；（4）当某一子问题不可行但目标值优于现有保留分枝的）当某一子问题不可行但目标值

45、优于现有保留分枝的所有目标值，则要继续分枝。所有目标值，则要继续分枝。3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划50【例【例3-8】用分枝隐枚举法求解下列用分枝隐枚举法求解下列BIP问题问题1234123412341234max62353564(3 10)23(3 10)24510(3 10)011,2,3,4jZxxxxxxxxaxxxxbxxxxcxj或，3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划51【解【解】（1）目标函数系数全部非负，直接对变量重新排序）目标函数系数全部非负，直接对变量重新排序2341234123412341max23565634

46、(3 10)23(3 10)24510(3 10)011,2,3,4jZxxxxxxxxaxxxxbxxxxcxj或，（2）求主枝：令）求主枝：令X(1，1，1，1)得到主枝得到主枝1，检查约束条，检查约束条件知件知(3-10c)不满足，则进行分枝。不满足，则进行分枝。（3）令）令x2=0同时令同时令x3=0及及x3=1得到分枝得到分枝2和分枝和分枝3，X2和和X3是是可行解，分枝停止并保留，如表可行解，分枝停止并保留，如表3-8及图及图3-8所示。所示。3.3 01规划的求解规划的求解表表3-8 令令x2=1同时令同时令x3=0得到分枝得到分枝4，X4是可行解，分枝停止并保留。是可行解，分枝

47、停止并保留。令令x2=1、x3=1，x4取取“0”和和“1”得到分枝得到分枝5和和6，分枝，分枝5不可行并不可行并且且Z511小于小于Z3和和 Z4，分枝停止并剪枝。注意到分枝，分枝停止并剪枝。注意到分枝6，x41时只有时只有x10（x11就是主枝），就是主枝），X6不可行并且不可行并且Z610小于小于Z3和和 Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图，分枝停止并剪枝，分枝过程结束。整个计算过程可用图32和表和表3-8表示。表示。分枝(x2,x3,x4,x1)3-10a3-10b3-10cZj可行性1(1,1,1,1)16不可行2(0,0,1,1)11可行3(0,1,1,1)14

48、可行4(1,0,1,1)13可行5(1,1,0,1)11不可行6(1,1,1,0)10不可行第第3 3章整数规划章整数规划53 搜索到搜索到3个可行解，个可行解，3个目标值中个目标值中Z3最大，因此最大，因此X3是最优是最优解，转换到原问题的最优解为解，转换到原问题的最优解为X（1，0，1，1），最优），最优值值Z14，计算结束。，计算结束。图图323.3 01规划的求解规划的求解第第3 3章整数规划章整数规划54【例【例3-9】用分枝隐枚举法求解下列用分枝隐枚举法求解下列BIP问题问题123451234512345min362462712(3 11)45310(3 11)011,2,3,4j

49、Zxxxxxxxxxxaxxxxxbxj或，【解】【解】（1）令）令x2=1x2及及x5=1x5，代入模型后整理得，代入模型后整理得123451234512345min362476279(3 11)4533(3 11)011,2,3,4jZxxxxxxxxxxaxxxxxbxj或，3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划55（2）目标函数系数按升序将对应的变量重新排列得到模型）目标函数系数按升序将对应的变量重新排列得到模型142531425314253min234676729(3 11)4353(3 11)011,2,3,4jZxxxxxxxxxxaxxxxxbxj或，（

50、3）求主枝。由于目标函数求最小值，令所有变量等于零，）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解得到主枝的解X1（0，0，0，0，0），），Z17，检验约束条，检验约束条件知件知X1不可行，进行分枝。不可行，进行分枝。（4）取）取x1=1和和x1=0，分别其它变量等于，分别其它变量等于“1”和和“0”分枝，判分枝，判断可行性，计算过程参见表断可行性，计算过程参见表36及图及图33。3.3 01规划的求解规划的求解第第3 3章整数规划章整数规划56分枝j上一分枝Xj=(x1,x4,x2,x5,x3)3-11a3-11bZj可行性12345主枝1111(0,0,0,0,0)(0,