第五章 整数规划 运筹学 课件

第五章整数规划本章要求•理解整数规划的含义•掌握分枝定界法的思想和方法•掌握0-1变量的含义和用法•掌握指派问题的算法6.1整数规划问题的提出•决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢•问题分类：纯整数规划、混合整数规划、0-1整数规划•专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法问题举例•某集装箱运输公司，箱型标准体积24m3，限制重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？•maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数•解此LP问题，得：X1=4.8，X2=0•显然不是可行解整数规划图解法x2x11234567231BAZ=2000x1+1000x25x1+4x2＝242x1+5x2＝13图解法的启示•A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解•纯整数规划的可行解就是可行域中的整数点•非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化•IP问题的最优解不优于LP问题的最优解6.2分枝定界法•思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解•例1.maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8x2=0Z=9600不是可行解Z=9600是IP问题的上界，记为：Z=9600分枝定界法（续）•X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1≤4和x1≥5•原问题分解为两个maxZ=2000x1+1000x2maxZ=2000x1+1000x25x1+4x2≤245x1+4x2≤242x1+5x2≤13(IP1)2x1+5x2≤13(IP2)x1≤4x1≥5x1.x2≥0且为整数x1.x2≥0且为整数分枝定界法（续）•不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记为Z=9000•由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000分枝定界法的解题步骤•1、不考虑整数约束，解相应LP问题•2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步•3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi≤[bi],xi≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。•4、不考虑整数要求，解分枝问题。若整数解的Z值所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto3（例题2讲解）例2分枝定界法求解整数规划问题A:为整数2121212121,0,4595685maxxxxxxxxxxxf解：1、先求解A对应的线性规划问题B:0,4595685max21212121xxxxxxxxf25.4175.325.221fxx最优值为：最优解为：00021fxx对应的目标函数值为：容易知道：25.410*f2、分枝定界1）第一次分枝如下图所示：（即两枝）和分为两个子问题则原问题和分成将212223475.3BBBxxx分枝后的可行域为：0,44595685max2122121211xxxxxxxxxfB为：子问题0,34595685max2122121212xxxxxxxxxfB为：子问题分别求解得：和对问题21BB4148.11211fxxB最优值为：最优解为：39332212fxxB最优值为：最优解为：4139*f2）第二次分枝：218.148.11112112xxxxxBB分两枝为：将最优解为：枝已是整数解，无须再分（即两枝）和分为两个子问题则问题431BBB0,244595685max21122121213xxxxxxxxxxfB为：子问题0,144595685max21122121214xxxxxxxxxxfB为：子问题分别求解得：和对问题43BB（无须再分枝）无可行解3B954094414214fxxB最优值为：最优解为：954039*f549449441222214xxxxxB分两枝为：将最优解为：（即两枝）和分为两个子问题则问题654BBB分别求解得：和对问题65BB0,5144595685max212122121216xxxxxxxxxxxfB为：子问题0,4144595685max212122121215xxxxxxxxxxxfB为：子问题40506216fxxB最优值为：最优解为：37415215fxxB最优值为：最优解为：954040*f本题求解完毕！40*f例3用分枝定界法求解：MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。012344321x1x2分枝：X11,x12P1P2两个子问题：（P1）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20，x11，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4)（P2）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20，x12，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)012344321x1x2再对（P1）分枝：X11（P3）x22（P4）x23P1P2P3P4（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x22整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=10（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x23整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=9X12X22X11X23P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原问题的最优解（1，2）Z=10例4用分枝定界法求解：MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。012345687654321x1x2p012345687654321x1x2p选x1进行分枝：(P1)x13(P2)x14为空集P1（P1）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20x13整数用单纯形法可解得（P1）的最优解（3，3/2）Z=9（P2）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20x14整数无可行解。012345687654321x1x2p对(P1)x13选x2进行分枝：(P3)x21无可行解(P4)x22P4（P3）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20，x13，x21整数无可行解。（P4）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20，x13，x22整数用单纯形法可解得（P4）的最优解（2，2）Z=10X14X21X13X22P1:(3,3/2)Z=9P4:(2,2)Z=10P2:无可行解P3:无可行解P:(10/3,4/3)Z=26/3原问题的最优解（2，2）Z=106.4指派问题•例8甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，表中数据为时耗，如何指派不同的人去做不同的工作使效率最高？任务人时间ABCD甲乙丙丁41075276333444663数模：minZ=ΣΣcijxijΣxij=1i=1,…,nΣxij=1j=1,…,nXij=0或1指派问题解法—匈牙利法解：类似运输问题的最小元素法第一步造0——各行各列减其最小元素3664443336725710403311100145013600231100013501260第二步圈0——寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉0231100013501260第三步打——无的行打，打行上0列打，打列上行打，打行上0列打…0231100013501260第四步划线——无行、打列划线0231100013501260第五步造0——直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Goto20231100013501260023210010240015002321001024001500122200201300040最优解：x13=1,x21=1,x32=1,x44=1Z=15例：某厂拟用五台机床加工五种零件，其加工费用（元）如下表所示。若每台机床只限加工一种零件，则应如何分配任务才能使总加工费用最少？零件机床123451418422984773846634657625554311345526756366487748924814023440453403315330451370300341025310131231042117000033002520013013103122800解：最少的总加工费用4+4+4+2+3=17相关问题：非标准型的转化maxZ=ΣΣcijxijminZ’=ΣΣ(-cij)xijminZ’’=ΣΣ(M-cij)xij=ΣΣbijxijM是足够大的常数，新问题的最优解就是原问题的最优解特殊约束的处理互斥约束矛盾约束在建立数学模型时，有时会遇到相互矛盾的约束，模型只要求其中的一个约束起作用。例5-4：下面两个约束是相互矛盾f(x)-50(1)f(x)0(2)引入一个整数变量来处理-f(x)+5M（1-y)(3)f(x)My(4)M是足够大的整数，y是0-1变量当y=1时,(1)(3)无差别,(4)式显然成立;当y=0时,(2)(4)无差别,(3)式显然成立。以上方法可以处理绝对值形式的约束f(x)a(a0)此时f(x)a(5)f(x)-a(6)是矛盾约束。引入一个整数变量来处理-f(x)+aM（1-y)f(x)+aMyM是足够大整数，y是0-1变量注意：对|f(x)|a(a0)不必引入0-1变量，因为f(x)a和f(x)-a并不矛盾。例5-5：两个约束条件2x1+3x28x1+x22只能有一个成立，试用0-1变量来表示这个要求。解：引入0-1变量y和足够大的正数M，则8-2x1-3x2M（1-y)x1+x2-2My当y=0,x1+x22成立，而2x1+3x2