运筹学：第05章 整 数规划.pdf

章整数规划_ J.(Integer Pr ogr amming JP)整数规划的数学模型及解的特点 解纯整数规划的割平面法痔 内容分支定界法 0-1型整数规划争指派问题资看题例 授缅闻案争某财团有5万元的资金，经出其 考察选中个投资项目，其中第j 个项目需投资金额为万元，预 计5年后获利J万元J=I，2.,n,问应如何选择项目使得5年后总收 益最大？目标一总收益最大约束一总金额不超过限制变量每个项目是否投资资含题型 授缠间模目标一总收益最大e约束一总金额不超过限制变量每个项目是否投资谷变量假设：1 L 投资第j个项目X aj=TbjXj Bj=iXj=1,0;j=1.2.n您有一旅行团从出发要遍游城 市匕#2,#勿已知从匕至1匕 的旅费为，问应如何安排行 程使总费用最小？e有一旅行团从出发要遍游城 市匕42,已知从匕至U匕 的旅费为与，问应如何安排行 程使总费用最小？变量一是否从i第个城市到第j 个城市；e约束一每个城市只能到达一次、离开一次；不能往返令目标一总费用最小；e变量一是否从i第个城市到第j个城市；e约束一每个城市只能到达一次、离开一次;e目标一总费用最小；n 几i=0 j=0n=每个城市离开一次J=。V 10 每个城市到达一次2xij=1;1=12,=，二0u：-u-+nx-z:-1;1 z ni j ej J _%-IQ f-1 2 n j-12 到j不能I 至UiHl GS 问题 皆，券邮递包裹把形状可变的包裹用尽量少的车辆运走电旅行背包容量一定的背包里装尽可能的多的物品色题例e某人出国留学打点行李，现有三个旅行包，容积大小 分别为1。0毫升、150。毫升和20。毫升，根据需要列 出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有1。件可带可不带物品，如果 不带将在目的地购买，通过网络查询可以得知其在目 的地的价格（单位美元）。这些物品的容量及价格分 别见下表，试给出一个合理的安排方案把物品放在三 个旅行包里。物品12345678910体积200350500430320120700420250100价格1545100705075200902030wa 问题 模型e变量对每个物品要确定是否带同时 要确定放在哪个包裹里，如果增加一个 虚拟的包裹把不带的物品放在里面，则 问题就转化为确定每个物品放在哪个包 裹里。如果直接设变量为每个物品放在 包裹的编号，则每个包裹所含物品的总 容量就很难写成变量的函数。为此我们 设变量为第i个物品是否放在第j个包裹 中“=1。=1217/=123Xj第i件物品放到第j个包否则二 10约束17包裹容量限制:（。=123 i=i必带物品限制:wa 问题 模型3:=1=12.,7JT选带物品限制:e目标函数3Z勺 1=8,2.,177117 3未带物品购买费用最小-Z马）i=8 J=1wa 向题 模型s.t.17 3minZPiQ ZX)，=8 J=1局。=1，2,3.=1,2.,7 ij%.V,i=8,2.,17 ljj=iI 马二1,0;，=1,2,17=1,2,3整数 规划 问题特征一变量整数性要求；来源问题本身的要求；引入的逻辑变量的需要；性质一可行域是离散集合;e一般整数规划模型0-1整数规划模型e混合整数规划模型整数线性规划线性数学问题模型的一般形式为max（或 min）=3%j=i%巧4（或二,或2地（，=1,2祖）j二is.t.0（j=%,%2X中全部取整数一整数现划模蛰max（或 min）二Z 4勺j=inv（或=，或）2（，=12.”加）S.t.0(，=L2,.,)玉,2,，中部分取整数例|2现有资金总额为B。可供选择的投资 项目有n个，项目j所需投资额和预期收益 分别为ay和C)(j=1,2,，n)o此外，由于 种种原因，有三个附加条件：第一，若选 择项目1,就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选 择一个；第三，项目5、项目6和项目7中恰 好选择两个。应当怎样选择投资项目，才 能使总预期收益最大？属于0-1规划问题例2现有资金总额为B。可供选择的投资 项目有n个，项目j所需投资额和预期收益 分别为ay和C)(j=1,2,，n)o此外，由于 种种原因，有三个附加条件：第一，若选 择项目1,就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选 择一个；第三，项目5、项目6和项目7中恰 好选择两个。应当怎样选择投资项目，才 能使总预期收益最大？属于0-1规划问题Xj1对项目，投资 、(7=1.。对项目,不投资令 11对项目，投资一、J o对项印不投资”问题模型为：nmax z=j=inN/J J j=lx2%1s.t.x3+x4%5+%6Xj=3j 1+X7=2式 ia,2,h)整数规划问题:max z=CXAX=bmax z=CX AX=bs.t0为为整数S.tX0(IP)问题的松弛问题整数规划问题：max z=CXAX=bs.t0当为整数max z=CXAX=b s.t0(1)的可行解域u松弛问题的可行解域若松弛问题无可行解)则户无可行解整数规划问题：max z=CXAX=bs.t0与为整数max z=CXAX=b s.t0(2)ZP的最优值与松弛问题的最优值松弛问题的最优值是原整数规划 的目标函数值的上界。整数规划问题：max z=CXAX=bs.t0当为整数max z=CXAX=b s.t0若松弛问题可以找到*整数解x,则X的目标函数值是0最优值的下界(4)若松弛问题的最优解X*为整数解则X*也是ZP的最优解(1)户的可行解域U松弛问题的可行解域 口若松弛问题无可行解，则3无可行解(2)3的最优值 松弛问题的最优值|、松弛问题的最优值是原整数规划 的目标函数值的上界。若松弛问题可以找到d整数解X,则X的目标函数值是肥最优值的下界(4)若松弛问题的最优解X*为整数解则X*也是m的最优解最优解不一定在顶点上达到OO最优解不一定是放松问题最优解 的邻近整数解您最优解不一定在顶点上达到您最优解不一定是放松问题最优 解的邻近整数解您整数可行解远多余于顶点，枚 举法不可取整数规划的困难之处整数规划的数学模型及解的特点e解纯整数规划的割平面法令分支定界法0-1型整数规划令指派问题_割平面法的基本思想：若整数规划IP的松弛规划L。的最优解不是 整数解，豺L。增加一个约束条件;得线性 规划Li，此过程缩小了松弛规划的可行解 域留松弛规划的任一整数解因此整数规划 IP的解均在Li中，若Li的最优解为整数解,则得IP的最优解。若Li的最优解不是整数 解，重复以上步骤，由于可行解域在不断 缩小，且保留IP所有的整数解，总可以在 有限次后得到IP的最优解.割平 面法您由放松问题的可行域向整数规 划的可行域逼近争方法一利用超平面切除要求整数解保留放松问题最优值向最优解逼 近您目标得到的新的可行域的某个 整数坐标的极点恰好是问题的 最优解对整数规划问题ZP:max z=CXAX=bs.t0，为整数 0设4的最优解X。不是整数解不妨设，X。=如,%，%,0,oj其中篇是分数即X，元”元切是基变量，xm+1%是非基变量设七0的最优解X。=010,狐，晨,0,0）是分数L。的最优单纯形表：Xl Xi XmXri+1 Xm+j Xn解检0 0 0 八m+j 院z-ZoX11 0 0lm+1 lm+j lnbioXi0 1 0im+1 a.31m+j inhoXjn0 0 1,mr n+1 a3mm+j ,r nnbmO品所在行的方程关.J源方程%+：+Vn=bi。对源方程:%+aim+lxm+l+aim+jxm+j+-+ainxn=biQn-mx-+7 a _-i 43im+jJ=1，而+j Jj _+fim+j Xm+j=io+fiOn-mj=lim+jI nm卜加+J+2L fim+jXm+j=bo+fiO7=1七一瓦11&r+:“加+j jm+j 力0-Z fim+n-mn-miXm+jj=lj Tn-m令力0 Z力帆+/X帆+J-0j=l对应于生成行i的割平面对源方程:%+aim+xxm+i+aim+jxm+j+-+ainxn=biQjXm+j-n-mn-mx-+7 a _-i 43im+jJ=1对应于生成行i的割平面线性规戈必i:max z=CXAX=bnm【于im+i工加+i f iO 割平j=lX 0对整数规划问EZP:max z=CXAX=bs.U X 0勺为整数4的最优解X。其松弛问题。max z=CX=b 10线性规戈氏:max z=CX AX=b nmS):fim+j Xm+j 于iO71X 0L的最优单纯形表:=伍。，品，心。o)其中“是分数生成行n。沛+/+fim+j 0fim+i 1 j=1,2,一机X Xi XmXm+1b 0 0Nj 0 0lm+1Xn解T匕甘Xm0 0 1mm+1 a 3mm+|mnh 非基对应于生成行i的割平面n-m n-m：Zo-E fim+j%n+j40，即Z 九+/京:fiO令求解整数线性规划max 2=3x-x2 max z=3xx-x2-2x2 10s.tA 2xx+x2 0J/为整数s.t A3xx-2x2+x3=35xx+4x2-x4=102xx+x2+x5=5%9%2,，元5。%/为整数第一步：解整数规划问题的松弛问题，见表5-3，Xi=13/7,x2=9/7；表5-3Cj3-1000CBXbbX1x2x3X4x53X113/7101/702/7-1x29/701-2/703/70X431/700-3/7122/7Cj-Zj00-5/70-3/7期第二步：写出割平面方程，选择第一行产生割 平面约束，1 2 6 Xq-W q 3 q D q求解整数线性规划max z=3xx-x2max z=3xx-x2s.t.3%j-2x2 102M+x2 0 J,毛为整数-2x2+x3=35%+4x2-x4=102xi+x2+x5=51 2 6-Xn-%+Xr=-7。7 3 o 7X,，尤6 0Jl.，4为整数表5-4cj3-10000CBXBiXlX2X3X4x5X63Xl13/7101/702/70-1X29/701-2/703/700X431/700-3/7122/700X6-6/700-1/70-2/71c/乙j-5/200-5/70-3/70 3X21100001-1Xl5/410-1/405/40X35/2001-1/20-11/20X57/40001/41-3/4c/乙j000-1/40-17/4表5-43X21100001-1X15/4010-1/40-5/40X35/2001-1/20-11/20 x57/40001/41-3/4c/乙j000-1/40-17/4写出割平面方程，选择第4行产生割平面约束1 1 3一产产 4求解整数线性规划max z=3%1-x2s,t,102xl+x2 0s.t.0看.，与为整数一力表5-5Cj3-100000CBXB储XlX2X3X4X5X6X73Xl11000010-1X2201000-1-10X3400100-5-20 x5100001-110X43000101-4%-Zj-100000-4-1原整数规划问题的最优解为，X=l,x2=2,max z=lN +N图 5-2第一步:笛一止 弟一少:四、割平面计算步骤：用单纯刑法解整数问题IP的松弛问题L。若L0没有最优解，则IP没有最优解。停止Lo有最优解X。：(l)Xo是整数解，则X。也是IP的最优解，停止X。不是整数解,转第二步上割平面方程任选X。的一个非整数分最论，储的最优单纯型表也。所在的行的数据nm得割平面:):j 之于ibj=lI n-m即Z 九+/-+s=力0j T-k I 匕 弟二少:第四步:将割平面加到L0得Li解Li在L。的最优单纯型表中增加一行一列，得Li的单纯型表，用对偶单纯刑法求解，若其解是整数解，则该解也是原整数规 划的最优解否则将该解记为X。，返回第二步争整数规划的数学模型及解的特点解纯整数规划的割平面法本簟 内容分支定界法 0-1型整数规划指派问题分支定期法分支定界法(br anch and bound method)是种 隐枚举法(implicit enumer ation)或部分枚举法。分支定界法的关键是分支和定界。最优解为 非整数最 P值比界max CXmax CXAX=bs.t.X20,X为整数AX=b s.t.xr br_ 为整数max CXAX=bs.t.X x 0,x为整数2是不超过久的最大整数Qo(booQQ O算例e例6求解下述整数规划max z=为+/f 9 51x+1 14 2 14c 1s.tJ-2xl+x2 0j.、再,2为整数e第一步：舍弃整数要求，用单纯形法求解,得X（o）=（3/2/O/3）,点 A,目标函数值z（）=29/6（上界），（0,0）显然是一个可行解，目标函数值0（下界）算例图 5-3算例图 5-4=1.5 c（1，2）区间不起作用 n 玉 go,iu2,+oo）第二步，由于X1，X2都不是整数，分解成子问题（分支）。max z=5+/先考虑X,Xi=3/2 omax z=玉+s.t.9,51X H-M 0%,巧为整数9,51X H-1 14 2 14 1-+%2-3%0J1,巧为整数X二(2,23/9),B 点X=(1,7/3),C点,z=41/9z(2)=10/3e 第三步，由于Z（2）2（1）2（。）（1）=41/9代 替Z成为新的上界。止匕时，问题（2）已 探明，结束。问题（1）需继续分支。max z=xi+x2f 9 511 14 2 14c 1-2X+V max z=玉+%9 51x1 14 2 14.1-+%2 s.t.2x23(3)0巧,为整数无可行解，删去（剪 枝）xx2/42,x2 0、/九2为整数(4)X(4)=(33/14,2),D点,z=61/147max图 5-5e第四步，由于z 继续分支。max z=项+f 9 51X H-X9 1 14 2 14c 1-2%+%s.t.3xpx2 0玉为整数X二（3,1）,E点,Z二4Z（4）z（。），问题（1）需max z=玉+%9,51H-羽 14 2 14-2+X2 0冷为整数(6)X二(2,2),F点,z二4得到原整数规划问题的最优解。:章 容整数规划的数学模型及解的特点e解纯整数规划的割平面法e分支定界法a 01型整数规划指派问题，、决策问题与0-1变量决策变量V,-是否做第件事i=1,2，.r 1 做第i件事xt=0）若不生产第j种产品（即%产0）max z=4x1+5x2+6x3-100yj-150y2-200y32.+4芯+8x3 5002%j+3x2+4x3 300Xj+2x2+3x3 100Mxyxs.t.“2 EM2y23 工也、3丫1i2，、3=Mxx,x2,X3、。且为整数其中约束条件玉4函如何理解？&隐枚举法（适合于变量个数较少的0-1规划）例10求解0-1整合规划max z=3尤-2x2+5x3s.txM+2x2-x3 2%+4x2+x3 4Xj+x2 34x2+x36xp x2,x3=0或 1(5.14a)(5.14b)(5.14c)(5.14d)&解:件，X,abCdZ(0,0,0)VVVV0（初始滤值）(0,0,1)VVVV5（新滤值）(0,1,0)一-2(0,1,1)一3(1,0,0)一一3(1A1)一8（最后过滤值）(1,1,。)一1(1,1,1)一6最优解（为，x2,=（L。）:max z=8整数规划整数规划的数学模型及解的特点解纯整数规划的割平面法分支定界法号0-1型整数规划指派问题(assignment problem)人 fl,若指派第认做第/事令第二 o,若不指派第，人做第;事模型问题 模型n nminz=ZZ*i=l j=ln X=1,/=12,1=1n0M-CnMZ指派问题最小化的数学模型:min Z，=ZZ(M chj i=8)j i用匈牙利什=22 cijxijJ i J i=M-ZX；1+X/?+%.+-+%.=1 i=l，2,n il il ij ms.t/+盯+/+/T j=12，n0,1 L2、;j=L2,jM=hax ZHS Sc/x/+者2+耳+/+与=1 i=12,nS.tM-Z Z Z2则X。也是max Z的可行解 且使max Z取到最大值乙Z0=M+ZminZf=j I%T i=l,2,，nS.t+&j+,-+4j+,+%=1=0,1，=1,2,;/=1,2,，”设X2是min Z的可行解，且对应的目标函数值Z；n 求解12 J ,nn+1n+2.m1GiC12%oo 02C21C22 c2j C2noo 0 .iCiCi2 Cinoo o mCmlCm2 Cjnj mnoo 0(b)mn3之12j.n1GiC12Gj2C2lC22 C2j C2n iCiCi2 Cu Cin mCmlCm2 c.fnjm+1oo-o-Om+2oo-o-Onoo-o-O用匈牙利法 求解(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题(4)某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事取费用系数%充分大如在max Z问题中，第k个人一定不能做第t件事，取效率系数=0