运筹学整数规划补例

1、运筹学难点辅导材料maxzx1x214x19x?1、对（ip）整数规划问题6X13x2s.txOK51整数规划补例1，问用先解相应的线性规划然后凑整的办法能否0x,X2为整数x51用图解法求出最优解1求到最优整数解？再用分支定界法求解。解先不考虑整数约束，得到线性规划问题（maxzx,x214x19x2st6x13x2%0,x229z如用（1，列举64）、（2，4）。代入约束条件发现他们都不是可行解。可将可行域内的所有整数点（完全枚举法），本例中（2，“舍入取整法”凑整可得到四个点，即（令X0T310029及最优值z一。可行域记为D，显然X0不是整数解。236定界:取z0z29，再用视察法找一

2、个整数可行解6X0,0T及z0,取zz0，即0*29z6分支:（关键点，在B的最优解中任选一个不符合整数条件的变量Xj，其值为bj，构造两2）、（3,1）点为最大值z4。个约束条件Xjbj1,Xjbj，这里用了取整函数呵！）任取最优解中一个不为整数的3 3变量值，例如x1一，根据-1，构造两个约束条件，形成下面两个子问题（IP1）22maxzx-ix2maxzx1x214x19x25114x19x2516x13x21和（IP2）6为3x21StX11s.tX22X10,X20X0,X20x1,x2为整数Xi,x2为整数i7解（IP1）和（IP2），得最优解分别为X113这两个都不是符合整数条件

3、的可行解。11023241,z和X2,z3994112*41zminz,z，0z99T再分支：由于z12z，故先对（IP2）进行分支，取X223，根据兰2，构造两个约修改上下界：根据个分支的最优解，可取新的上界第17页（共24页）maxzx1x2maxzxx214x19x25114为9x2516X13X216X13X21束条件，形成下面两个子冋题（IP3）N2和(IP4)N2s.tstX22X23X0,x20X0,x20Xi,X2为整数Xi,X2为整数解相应的松弛问题（IP3）和（IP4）,得（IP4）无可行解，（IP3）的最优解为X314,23,z61142，构造两个约束条件，形成下面在考虑

4、（IP1），由（IP1）的最优解，取x27根据-3 '3maxzX-!x2maxzx1x2149x25114x19屜516为3屜16%3x21两个子问题（IP5）X11和(IP6)X1，得（IP6）无可行解，（IP5）s.ts.tx22X?3X10,X20N0,X20X1,X2为整数X,X2为整数5T5的最优解为X1,2,z3。在修改上下界：根据上述两个最优解的情况，有6114再分支:由（IP3）的最优解XT33c计3333,2，取x，根据1414142，构造两个约束条件，形成下面两个子问题，得（IP7）的最优解为X7重新定界：由于的最优解为maxz2、对整数规划问题s.t2%2%优整

5、数解?解用单纯形法解对应的当凑为X|,X2T当凑为x,x2丁maxzxx2(IP7)s.t14为9x26x13x2251Xi(IP8)X2XiXi0,X2X-!,X2为整数maxzxx214为9x26凶3x22s.tX20,X251X|,X2为整数T2,27,z4，(IP8)的最优解为3,1T,z878X,X为整数解，且zT*4，故X3,1,z43x2X22x2149，问用先解相应的线性规划然后凑整的办法能否求到最0,X2X1,X2为整数XiLP问题，求到最优解T3,2时，为可行解,T4,2时，为非可行解F面用分支定界法来解整数规划问题。令13X1,X245,maxz259413；当凑为TX,

6、X2T3,3时，为非可行解；当凑为X1,X24,3时，为非可行解；59，显然4X1,X2T0,0为可行解，从而0z*59。将原问题分解为下面两个子问题（用4X22,X23分支,复杂些,不妨去试试！）(IP1)maxz2x2maxz2x22%3x2142为3x22%X29和（IP2）2nX2s.tX13X14X10,X20X10,X2TT亠343X1,X2(IP1)s.t14,maxz和（IP2）的为3TX1,X24,1丁,maxz14因为z14,z433，所以1443T，且z为整数，则z14,X14,X21为最优解。maxz3xiX23xi2X233、用割平面法求解5Xi4X210s.t2xi

7、X25x1,x20,x1,x2为整数引入松弛变量X3,X4,X5和人工变量X6及一个充分大的数0,先解一个大M问题:maxz3为X2Mx63x12x2X335%st2x14x2X4X10X2X55解Xi,X2,X3,&,X5,X6,X7作初始单纯形表，并进行迭代运算Cj3-1000MCB基XB常数X1X2X3X4XX60X333*-21000MX610540-1010X5521001031035，检.CjZj35M14M00003X111-2/31/3000MX65022/3*-5/3-1010X5307/3-2/301053，检22/37/30221M31-M30003X116/11

8、102/11-1/1101/11-1X215/2201-5/22-3/2203/220X531/2200-3/227/22*1-7/223，检7/2200-17/223M2203M223X113/7101/702/70-1X29/701-2/703/700X431/700-3/7122/7-131/22，检7/220053M77-3/70略去人工变量，得最终单纯形表Cj3-1000CB基XB常数X1X2X3X4X53X113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7检00-5/7-3/7再略去松弛变量,最优解为1397'70,z1373

9、30，显然不是整数规划的7优解。引Xi源行x1X36的割平面7X312X3X573733Xi2X2,X5X32x-|2x56，X2代入得再将X-I13x-i2x2X33,2x1X2X55变形（该割平面确实割去了松弛问题最优解为0，但未割去原问题的任一整数可行点。1引入松弛变量X60,化一X372_X5712X3X577X6-写入上表，得7Cj3-10000CB基XB常数X1X2X3X4X5X63X113/7101/702/70-1X29/701-2/703/700X431/700-3/7122/700X6-6/700-1/70-2/7*1|卫！5/7，检2/71/700-5/70-3/703X

10、11100001-1X2001-1/2003/20X4-500-2*10110X53001/201-7/21/2，检200-1/200-3/23X11100001-1X25/4010-1/40-5/40X35/2001-1/20-11/20X57/40001/41-3/4检验数000-1/40-17/4再略去松弛变量，最优解为X记,z15731-7,显然仍不是整数规划的最优4 4131丄x61-的割平面441解。继续作割平面，以x5行为源行0-x4x54X1X23,（该割平面确实割去了松弛问3114产1x60,利用四个等式约束即可化为题最优解为X1，也未割去原问题的任一整数可行解。）引入松弛变

11、量x70,化3x4丄沧0为x4x6x7-写入上表,4 44444Cj3-100000CB基XB常数X1X2X3X4XX6X73X111000010-1X25/4010-1/40-5/400X35/2001-1/20-11/200X57/40001/41-3/400X7-3/4000-1/4*0-1/411/417/4丄4上父4检验数1/41/4000-1/40-17/403X111000010-1X2201000-1-10X3400100-5-20X5100001-110X43000101-4检验数00000-4-1T*解得X1,2,z3121maxzx23洛2x264、用割平面法求解s.t3

12、%2x20x-!,x20,x,x2为整数解引入松弛变量X31X4，得到对应LP问题的初始单纯形表计算如下:Cj0100CB基XB常数X1X2X3X40X3632100X40-320106检验数220100501000CB基XB常数X1X2X3X4Si0X11101/6-1/601X23/2011/41/400S1-1/200-1/4-1/411/44检验数1/400-1/4-1/400X12/3100-1/32/31X21010010X320011-4检验数0000-10X36601-11x0-3/2101/26检验数63/200-1/20X11101/6-1/61x3/2011/41/4检验

13、数00-1/4-1/4*T此时LP问题的最优解x1,3/2,z3/2,但不是整数最优解。引入割平面。以X2为源行X201X301X411442X2111X31x4，所以生成割平面11X31X40，244244利用两个等式约束解出X3,X代入即可化为等价割平面X21111现将生成的割平面条件加入松弛变量x3x4，然后得到下表442T此时LP问题的最优解x2/3,1,2,z1,但仍不是整数最优解。引入割平面。以x1为源行X,222221X40S0-X1-X42S.，所以生成割平面33333Si,X4代入即可化为等价割平面X203|x4£s0，利用三个等式约束解出333(1,3/2)第一个

14、割平面>xoo34IL2、1L123430一一一第二个割平面第一个割平面Cj01000CB基XB常数X1X2X3X4SiS20X12/3100-1/32/301X210100100X320011-400S2-2/3000-2/3-2/3101-检验数2/32/30000-100X3110001-1/21X210100100X310010-53/20X4100011-3/2现将生成的割平面条件加入松弛变量-X4-S1S2,然后得到下表333011检验数0000-102/32/3*t此时LP问题的最优解x1,1,Z1，是整数最优解，所以是原问题的最优解。（从解题过程可见，表中含有分数元素且算

15、法过程始终保持对偶可行性,为分数对偶割平面算法）maxzx1x22xx265、用割平面法求解s.t4x5x220因此这个算法也称I32I1312LjL2y4?1.(1,3/2)T5/3,8/3,z13/3，但不是整数最优解。引入割平面。由于X15 50X31X46 62匕1与3X21-X301X422的右端的真分数相等，可任选2333（如果不等，根据经验选其中较大的一个式子效果较好）现在x-!,x20,x,x2为整数51100CB基XB常数X1X2X3X40X3621100X4204501-1检验数5111000X326/501-1/51X244/5101/5卩5卩5检验数6/54/51/50

16、0-1/51X15/3105/6-1/61X28/301-2/31/3检验数00-1/6-1/6解引入松弛变量x3,x4，得到对应LP问题的初始单纯形表计算如下:此时LP问题的最优解x*、一c211_211c以X?为源行X2X32X3X4，所以生成割平面X3X40,利用两333333个等式约束解出X3,x4代入即可化为等价割平面x1x24112现将生成的割平面条件加入松弛变量XXiS,，然后得到下表333Cj11000CB基XB常数X1X2X3X4Si1X15/3105/6-1/601X28/301-2/31/300S1-2/300-1/3-1/312/32/3检验数00-1/6-1/601/

17、3/3-1X10100-15/21X240101-20X320011-3检验数000*0-1/2*T得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解x0,4,z4T或X2,2,z4。maxz3x-i2x25x3x12x2x326、求解下列0-1规划问题X1X14x2x34x234x-|x36解用观察法求一个可行解。易看出X1，X2，X30,1x11,x2x30是一个可行解，对应z3。由于目标函数求最大，故凡是目标函数值小于这个3的都不必讨论，于是有了一个过滤性条件约束3x12x25x33优先考虑过虑性条件*，若遇到Z值超过过虑性条件右边的值，则应修改过虑性条件，继续做，列表如下

18、：（最好重排Xj的顺序，使目标函数中Xj的系数保持不减,X2,X,x3为最快！）X1,X2,X3约束条件左边值满足与否Z值*1234(0,0,0)0不满足(0,0,1)5-1101满足5(0,1,0)-2不满足小于5不需讨论:(0,1,1)315不满足小于5不需讨论(1,0,0)31110满足小于5不需讨论3(1,0,1)80211满足8(1,1,0)11不满足小于8不需讨论(1,1,1)6626不满足小于8不需讨论用过滤法（隐枚举法的一种）求解过程可以列表简化表示X1,X2,X3Z值约束条件满足与否过滤条件*123(0,0,0)0满足满满满Z0(0,0,1)5满足满满满Z5(0,1,0)-2

19、(0,1,1)3(1,0,0)3(1,0,1)8满足满满满Z8(1,1,0)1(1,1,1)6minz4x13x22x3解用观察法求一个可行解。易看出X1X20,X31是一个可行解，对应z2。由于目2为5x23x347、求解下列0-1规划问题4为x23x33X1X21标函数求最小，故凡是目标函数值大于这个2的都不必讨论，于是有了一个过滤性条件约束4x13x22x32*优先考虑过虑性条件*，列表如下：最优解0,0,1T，目标函数最优值minz2X1,X2,X3约束条件满足与否Z值*123(0,0,1)满足满满满2(0,0,0)满足满不(0,1,0)不(0,1,1)不minz5x24x43x32x

20、iX28、求解下列0-1规划问题4x2X4X34为4X42X3X2X4X3Xi，X?,X3，X4Xi0,12%1解用观察法求一个可行解。易看出x1X2X30,X41是一个可行解，对应z4。由于目标函数求最小，故凡是目标函数值大于这个的都不必讨论，于是有了一个过滤性条件(1,0,0)不(1,0,1)不(1,1,0)不(1,1,1)不0,1,0,0T，目标函数最优值约束5x24x43x32x14*优先考虑过虑性条件*，列表如下：最优解X2,X4,X3,X1minz4X2,X4,X3,X1约束条件满足与否Z值*123(0,1,0,0)满足满满满4(0,0,0,0)满足满不(0,0,0,1)满不(0,

21、0,1,0)满满不(0,0,1,1)不(0,1,0,1)不(0,1,1,0)不(0,1,1,1)不(1,0,0,0)不(1,0,0,1)不(1,0,1,0)不(1,0,1,1)不(1,1,0,0)不(1,1,0,1)不(1,1,1,0)不(1,1,1,1)不maxz3x17x22x1X2X3X4X1X26X34x45为3屜X45X1,X2,X3iX40,19、求解下列0-1规划问题X3X41解由于目标函数中变量X1,X2,X4的系数均为负数，可作如下变换，再调整次序:第13页（共24页）maxzy1y2Y1y22y36y14y2y3y25y33y43y37y4y41y42411，可以从1,1,

22、1,1开始试算，y(1,1,0,1)为最优解。、1门2小3,Y40,1所以X(0,1,1,1)，进而(1,0,1,0)minz10音5x28x33x2x4x10、求解下列0-1规划问题1232x1x24x34x42x5X4X5X1,X2,X3,X4,X5X4X50,1解令y1X5,y2X4,y3X2,y4X3,y5X1，得到下式minz2y14y25y38y410y5y1y22y34y43y§y1y2y34y42*%,y2,y3,y4,y50,1，计算过程见下表5y1,y2,y3,w,*约束条件满足与否Z值12是否满足(0,0,0,0,0)00否(1,0,0,0,0)1-1否(0,1

23、,0,0,0)-11否(0,0,1,0,0)-21否(0,0,0,1,0)4-4满足8(0,0,0,0,1)3-2否所以y(0,0,0,1,0)为最优解，原问题的最优解为x(0,0,1,0,0)最优解X2,X-!,X3T1,0,1T,Zmax8。由于采用了上述算法，实际只作了20次计算!maxZ3x12x25x32x43x5Xx2x32x4x5411、用隐枚举法求解下列0-1规划问题7m3x34x43x5811%6x23X43x53XpX2，X3，X4，X50,1解令X11X1,X21X2,X51X5，将模型化为标准形式如下:Xi1X1,X21X2,X3X3,X41X4；y1X3,y2X4,y

24、?人4X2第19页(共24页)maxZ83xi2x25x32x43x5x1x2x32x4x51?7x3x34x43x511x16x23x43x51Xi,X2,X3,X4,x50,1求解过程如右图所示。L8L3=5L1Z=4=ZL4：_L13Z(=L6L2.<-Zr=3<ZL9-非可行解10跖心可行解L12Zr=3<Z由X2X4X1X30,X51,Z5,知最优解x1x21,x4x3x50,Zmax5人费用工作ABCD甲15182124乙19232218丙26171619丁1921231712、设有甲乙丙丁四个工人，要指派他们分别完成ABCD四项工作，每个人做各项工作所消耗的时间

25、如下表。问如何分配工作才能使总耗费时间最小？试用匈牙利法求解。1518212419232218解系数矩阵为Cij26171619192123171)从系数矩阵的每行兀素减去该行的最小兀素，得1518212415036919232218181540CCijBj261716191610103192123171724602)从B的每列兀素减去该列的最小兀素,得03690269B15401440A,此时系数矩阵A的每行每列都有元素1010310003246023600。6刘4003L4L3°L5L1L6'L20269第2步：进行试分配，求初始分配方案，得A14401000323600

26、的数目34，试指派不成功，转入下一步。第3步：寻找覆盖所有零元素的最少直线，以确定最多零元素的个数。得覆盖所有零元素的最小直线数34（矩阵的阶数）第4步：调整aij，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小兀素1，然后对绿线未覆盖区所有兀素减去1，而绿线覆盖区的交叉元素加1，将A变02610为a；033010004125002610再返回第二步。进行试分配，得1aj0330j100041250610A工（IoL0斗IU.2_50L6L!,ioaL3L8L吩5第27页（共24页）再进行第4步：调整a!再进行第三步，寻找覆盖所有零元素的最少直线，得覆盖所有零元素的最小直线数00

27、410的最小兀素2，然后将a12ij变为aij0110120061030004100110再返回第二步。进行试分配，得2aiiu120061030于是已求得最优解x12x21*X33X441,其余*Xj0,即甲一B,乙一A,丙一C,丁-D。目标函数值为z*181191161仃170。注丿意：这个问题的最优解不惟一，例，使之增加一些零元素。为此，先找出没有被绿线覆盖的元素中如甲一A，乙一D，丙一C,丁一B也有最优值15+18+16+2仁70。13、设有5项工作ABCDE,需要分配甲乙丙丁戊五个人去完成，每个人只能完成一项工作,每件工作只能由1人去完成。5个人个人分别完成各项工作所需费用如下表。问

28、如何分配工作才能使总费用最省？试用匈牙利法求解。人费用工作ABCDE甲759811乙9127119丙85468丁73696戊467511解先将收益矩阵轲乍如口下变换75981152043620424912711972504225030q85469441025410127369634036340351467511402317023052042425030第2步：进彳亍试分卜配，求初刃始分配方案,得1q410124035102305第3步：寻找覆盖所有零元素的最少直线,以确定最多零元素的个数。最小直线数45（矩阵的阶数）cj2 04242 50304101240351得覆盖所有零元素的023051

29、031326030兀素1，然后将q变为Gj42013302400330510313J,3'wiJoL726030（乍）弓26；0.3:*QL3再返回第二步。进行试分配，得c24201330泌一.441*A0L10L530240to-3；3003305L6L2°L4再进行第三步，寻找覆盖所有零兀素的最少直线，得覆盖所有零兀素的最小直线数45。第4步：调整1Cij，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小再进行第4步：调整c2，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中0030316020的最小兀素1，然后将cj变为c；32003202300440

30、60106300230再返回第二步。进行试分配，得cj332003，此时，独立零兀素的个数m5。2023004406于是已求得最优解X12X23X34*X45*X511,其余*Xij0。目标函数值为z*517161614128。注意，甲乙丙丁四个工人，要指派他们分别完成0030316020ABCD这个问题有多个最优解，例如3Cij32003也疋最优解。202300440614、某地区从电网中分配得到的电力共有6GW，可用于工业，而该地区有机械、化工、轻纺、建材四大部类，各部类获得电力以后，可以为该地区提供的利润如下表。问应该如何分配电力可使该地区所获得的利润达到最大？（改为六人四项任务，即为指

31、派问题）电力/GW利润/万元部类机械化工轻纺建材135452676838981041010911512111012613121113解显然，这是一个非平衡的分配问题，虚设两个工业部类1,11,而令虚设的部类为该地区354500676800提供的利润为0，即可得到平衡分配问题的利润矩阵cij8981000U1010911001211101200131211130066CjXij，由式CjMCj,i,j1,2丄小将目标函数变为极小化目标函数为maxz问题minzMcijxiji1j1qXj,M13maxq，于是有1089813137675131354531313c，先将它变换为j334213131

32、231131301201313200000211033211055再进行试分配,得CjiU111066011077011088i1j1200000211033211055111066011077011088OL7QL10Lq0L5觀-丄皆或L3l4L2再画线，得最小直线数I36（矩整。先求出未被直线覆盖的元素中调整得阵的阶数），故需调3020002200C100100022044+，进055霽汕©02.25-:-：-0-D4。L81八住：賊芍-57冊询&&心L6C-O6%l：'o7"r?PL1L5L4L'L2L9的最小元素1，而再进行试分配，

33、得300100200022200044100055000066000077522300200000200022/口2，调整得c4，进而再进行试分配，得7IJ100033000044000055再画线，得最小直线数I56，故还需调整。先求出未被直线覆盖的元素中的最小元素522300200000420002*4j，即得最优解X16X25X34X43X52X611，其余100033000044000055x*j0。目标函数值为z*1019111113143。04617719181608701130119130170000M1$A61L3M|0111&13|01L2S17U-L315、设有5项

34、工作ABCDE，需要分配甲乙丙丁四个人去完成，由于工作任务数多于人数，故考虑：（1）任务E必须完成，其它四项任务中可以任选3项完成；（2）其中有一人完成两项其它每人完成一项。四个人分别完成各项工作所需费用如下表。试分别确定最优分配访案，使完成任务的总时间最少。人费时工作ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解（1）由于任务数多于人数，所以需要一名假想人，设为戊，因为任务E必须完成，故设戊完成E的时间为M（M为非常大的数），其余的假想时间为0，建立效率矩阵如下：人费时工作ABCDE甲2529314237乙3938262033丙34272

35、84032丁2442362345戊0000M用匈牙利法求解过程如下:25293142372504617120461773938262033201918160131918160834272840322770113570113024423623452311913022119130170000M00000M0000M00217319141204110117011590134004M00218318131103110118001480124005M得最优解X12X24X35X4102OL1120斗01170QL2n90110£LPL3ItTA190021H1岂11011011E0143仁C05L3L4-L5UoLi：2L2X531，其余Xij0,即甲一B,乙一D,丙一E,丁一A,C放弃。目标函数值为z*29203224105小时。(2)由于所有任务都必须由甲乙丙丁完成，所以假想的人戊的效率应该对每项工作而言,都是完成它的最好的人，而不能假设为0值，所以建立效率矩阵如下：人费时工作ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032用用匈牙利法求解，可得最优解X12X24X35X4