6.2+分支定界解法

运筹学(OperationsResearch)Chapter6整数线性规划§6.1整数线性规划问题的提出§6.2分支定界解法§6.3割平面解法§6.40-1型整数线性规划§6.5指派问题本章主要内容：Page3§6.2分支定界解法Page4整数线性规划问题的求解方法：1.分支定界法（branchandboundmethod）——可用于解纯整数或混合整数规划问题。2.割平面法—可用于解纯整数或混合整数规划问题。3.隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。4.匈牙利法—解决指派问题（“0-1”规划特殊情形）。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。§6.2分支定界解法Page5最早的整数规划论文是在1954年发表的,1959年美国的R.E.Gomory提出了割平面法(依据性质1),为IP作出了开创性的工作.1960年美国的A.Land,A.G.Doig提出了分枝定界法(依据性质2),该方法概念简单,方法灵活,容易在计算机上运算,成为IP解法的基础.§6.2分支定界解法Page6§6.2分支定界解法6.2.1分支定界法的思想：考虑最大化整数规划问题A，与它相应的线性规划记为问题B。从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数值z*的上界，记作；而A的任意可行解的目标函数值将是z*的一个下界。zzzz分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小和增大，最终求到z*。Page71010108.02.121xx255.2221xxX=(3.57,7.14)Z=35.7x1x2oABC§6.2分支定界解法Page81.求整数规划IP的相应的LP的最优解；①若LP无可行解，则IP也没有可行解；②若LP有最优解且满足整数要求，则即为IP的最优解;③若LP有最优解但不满足整数要求，则转下一步；2.进行迭代：①分支与定界：在LP的最优解中任选一个非整数解的变量xi=b,在LP问题加上约束：6.2.2分支定界法的解题步骤：§6.2分支定界解法组成两个新的LP问题，称为分枝。[][]+1iixbxb和Page9定界：新的LP问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。②比较与剪枝：检查所有分枝的解及目标函数值，§6.2分支定界解法Page10序号问题1问题2说明1无可行解无可行解原问题无可行解2无可行解整数解此整数解为最优解3无可行解非整数解对问题2继续分支4整数解整数解较优的为最优解5整数解，优于问题2非整数解问题1为最优解6整数解非整数解，优于问题1问题1停止分支，继续对问题2分支7非整数解非整数解较优的一个继续分支§6.2分支定界解法Page11例6.3求解整数规划问题§6.2分支定界解法解：解相应的线性规划B，得最优解而x1=0，x2=0是问题A的一个整数可行解，这时z=0是z*的一个下界，记作1212121240909756720700maxzxxxxs.t.xxx,x,且全部是整数.**1204.81,1.82,356.xxz可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作0.z*0356.z即0.zzPage12§6.2分支定界解法Page13分支：问题B的解中有一个非整数变量x1=4.81。则在原问题中增加分别两个约束条件：x1≤4和x1≥5，将B分解为B1和B2。x1≤4，x1≥5§6.2分支定界解法(1)分支与定界Page14仍然不考虑整数条件约束，解问题B1和B2，得到最优解为：定界：显然没得到全部整数解。问题B1问题B2x1=4x1=5x2=2.1x2=1.57z1=349z2=341§6.2分支定界解法那么必存在最优整数解，且*0349.z12=349zz,z,Page15分支：因z1＞z2，故先分解B1为两支。B1增加条件x2≤2称为问题B3；B1增加条件x2≥3称为问题B4。§6.2分支定界解法（2）分支与定界Page16求解问题B3和B4，得到定界：显然问题B3已得到整数解。z3=340，故将问题B3问题B4x1=4x1=1.42x2=2x2=3z3=340z4=327而它大于z4=327，所以问题B4没有必要分解。340z那么必存在最优整数解，且§6.2分支定界解法*340349.zPage17分支：继续对问题B2进行分支，B2增加条件x2≤1称为问题B5；B2增加条件x2≥2称为问题B6。问题B5问题B6x1=5.44无可行解x2=1z5=308§6.2分支定界解法（3）分支与定界*340349.z故最优解为x1=4和x2=2，最优值为z*=340.Page18解题过程§6.2分支定界解法Page19•例6.4用分枝定界法求解:解:先求对应的LP问题用图解法得到最优解：§6.2分支定界解法1212121243120810225250B:maxzxx.x.xstx.xx,x1212121243120810225250A:maxzxx.x.xs.t.x.xx,x,且全部是整数.**1203.57,7.14,35.7,xxzPage201010108.02.121xx255.2221xxB的最优解X=(3.57,7.14),Z0=35.7x1x2oABC§6.2分支定界解法Page2110x2oABCB1B234B1:X=(3,7.6),z1=34.8①②B2:X=(4,6.5),z2=35.5§6.2分支定界解法1212121121:max431.20.81022.525..3,0Bzxxxxxxstxxx1212121122:max431.20.81022.525..4,0Bzxxxxxxstxxx1134xxLP增加约束及得到两个Page2210x1x2oABCB1B2134B21:X=(4.33,6),z3=35.33627x不可行§6.2分支定界解法121212121222:max431.20.81022.525..47,0Bzxxxxxxstxxxx，121212121221:max431.20.81022.525..46,0Bzxxxxxxstxxxx，22267LPxx选择目标值最大继续分枝，增加约束及得Page2310x1x2oACB1346B211:X=(4,6),z5=34B212:X=(5,5),z6=355B6§6.2分支定界解法121212121121211431208102252546404B:maxzxx.x.xx.xs.t.xxxx,xx,，，即可行域是一条线段12121212122124312081022525560B:maxzxx.x.xx.xs.t.xxx,x，31112145zzBxx，对进行分枝，增加约束及得：Page24•上述分枝过程可用下图表示：B:X=(3.57,7.14),Z0=35.7B1:X=(3,7.6)Z1=34.8B2:X=(4,6.5)Z2=35.5x1≤3x1≥4B21:X=(4.33,6)Z3=35.33x2≤6B211:X=(4,6)Z5=34B212:X=(5,5)Z6=35x1≤4x1≥5B22无可行解x2≥7§6.2分支定界解法Page25§6.2分支定界解法•例6.4用分枝定界法求解整数线性规划问题：1212121223573549360A:maxzxxxxs.t.xxx,x,且全部是整数.解step1确定与问题A对应的松弛线性规划问题B1212121223573549360B:maxzxxxxs.t.xxx,x.Page26step2先求出问题B的最优解为:§6.2分支定界解法**12012683,2,14.171717xxz可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作而x1=0，x2=0是问题A的一个整数可行解，这时z=0是z*的一个下界，记作*8014.17z即*0.z*0.zzPage27§6.2分支定界解法1212122121235735493620B:maxzxxxxxxs.t.xx,x.1212122122235735493630B:maxzxxxxxxs.t.xx,x.(1)分支与定界问题B的解中有一个非整数变量x2=26/17。于是在原问题中增加两个约束条件：x2≤2和x2≥3，将原问题分解为B1和B2(即两支)。B1的最优解1214.2,2,14.4.xxz1212.25,3,13.5.xxzB2的最优解*014.4.zPage28§6.2分支定界解法1212122112112357354936240B:maxzxxxxxxs.t.xxx,x.1212122112122357354936250B:maxzxxxxxxs.t.xxx,x.(2)分支与定界问题B1的解中有一个非整数变量x2=4.2。于是在原问题中增加两个约束条件：x1≤4和x1≥5，将原问题分解为B11和B12(即两支)。B11的最优解12114,2,14.xxz1212325,1,14.77xxzB12的最优解*1414.4.zPage29(3)分支与定界理论上对B12继续分支，即使再分支，最优目标函数值也不会超过14.§6.2分支定界解法12114,2,14.xxz所以最优解Page30小结学习要点：1.掌握一般整数规划问题概念及模型结构；2.掌握分支定界法原理。3.能够用分支定界法求解一般整数规划问题。Theend,thankyou!Page32例3-7用分枝定界法求解：12121212max43410..238,0zxxxxstxxxx且均为整数0116(,)55x0625zPage3312121212max43410..238,0zxxxxstxxxx且均为整数0116(,)55x0625zLPLP11x1=9/4x2=1z2=12x1=9/4x2=1z1=12LP2LP1x1=11/5x2=6/5z0=62/5无可行解LP12x1=2x2=1z11=11