《五章整数规划.ppt》由会员分享，可在线阅读，更多相关《五章整数规划.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章五章整数规划 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第五章一、数学模型及解的特点一、数学模型及解的特点几个概念：1、整数规划（IP）-要求一部分或全部决策变量必须取整数值的规划问题。2、松弛问题-不考虑整数条件，由余下的目标函数和约束条件构成的规划问题，称为该整数规划问题的松弛问题。3、整数线性规划若松弛问题是一个线性规划，则称该整数规划为整数线性规划。第五章例1、集装箱运货 货物 体积(米3/箱)重量(百公斤/箱)利润(千元/箱)甲 5 2 20
2、乙 4 5 10装运限制 24 13 一、数学模型及解的特点一、数学模型及解的特点第五章解：设x1 ,x2 为甲、乙两货物各托运箱数5x1+4x2 242x1+5x2 13x1,x2 0 x1,x2为整数maxZ=20 x1+10 x2纯整数线性规划纯整数线性规划一、数学模型及解的特点一、数学模型及解的特点第五章例2、背包问题背包可再装入8单位重量，10单位体积物品物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 一、数学模型及解的特点一、数学模型及解的特点第五章解：xi为是否带第 i 种物
3、品maxZ=20 x1+30 x2+10 x3+18x4+15x55x1+3x2+x3+2x4+4x5 82x1+x2+4x3+3x4+5xX5 10 xi为0,101型整数线性规划一、数学模型及解的特点一、数学模型及解的特点第五章例3、选址问题A1A3B2B4B3B1A2Ai:可建仓库地点，容量ai,投资费用bi，建2个Bj:商店，需求dj(j=14)Cij:仓库 i 到商店 j 的单位 运费问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。一、数学模型及解的特点一、数学模型及解的特点第五章解：设xi(i=1,2,3)为是否在 Ai 建仓库 yij(i=1,2,3,j=14)由 i仓
4、库向 j商店运货量混合整数规划混合整数规划y11+y21=d1y12+y22+y32=d2y23+y33=d3y14+y24+y34=d4x1+x2+x3=2y11+y12+y14 a1x1y21+y22+y23+y24a2x2y32+y33+y34 a3x3xi 为01，yij 0s.t.一、数学模型及解的特点一、数学模型及解的特点第五章整数规线性划数学模型的一般形式：,部分或全部为整数一、数学模型及解的特点一、数学模型及解的特点第五章常用问题 ：1背包问题 2指派问题整数规划的常用解法：1分枝定界法 2割平面法 分类 0 1 规划 纯整数规划 整数规划 .混合整数规划一、数学模型及解的特点
5、一、数学模型及解的特点第五章V m3 G 100kg利润甲5220乙4510托运限制2413问：如何托运才能使利润最大？例 某厂拟用集装箱托运甲.乙两种货物。解的特点解的特点1 整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定）。前者最优解的目标函数值不会优于后者最优解的目标函数值。2 松弛问题的最优解的简单取整，不一定是最优解。一、数学模型及解的特点一、数学模型及解的特点第五章 最优解：甲 4 乙 1 调整：1）“凑整”甲 5 乙 02）“舍尾”甲 4 乙 0松弛问题的解：甲 4.8 乙 0一、数学模型及解的特点一、数学模型及解的特点第五章二、解纯整数规划的割平面法二、解纯整数
6、规划的割平面法纯整数规划问题第五章 在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。Cj3501000CBXBbx1x2x3x4x5x6x70 x39.5-20100.5-0.5-0.55x22631000.50.50.51x414.5-20010.5-0.50.5 j=cj-zj-10000-3-2-3则m个约束方程可表示为：二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章对应的最优解：其中：全为整数时，为纯整数规划的最优解。B不全为整数时，则不是纯整数规划的可行解，也不是原整数规划的最优解。二、解纯整数规划的割平面法二、解纯整数规划的割平面
7、法第五章割平面法的思路：割平面法的思路：若松弛问题的最优解不全为整数，则从X的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。直到全为最优解为止。增加的约束条件具备的两个基本性质：其一：原松弛问题最优解不满足该条件；其二：凡整数可行解均满足该条件。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Xi0 A Xj=bi0分解A,b为两部分。A=Na+Fa b=Nb+Fb F为不超过该数的最大整数。则上式变为：Xi0（Na+Fa）XjNb+FbXi0 Na Xj Nb Fb Fa Xj 可以证明此条件满足上述两个基本性质。可以作为增加
8、的约束条件。Fb Fa Xj 0 0 Fa Xj -Fb 二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章割平面法求解步骤：割平面法求解步骤：1.求解原问题的松驰问题；2.若最优解全为整数，则达到最优；否则转3；3.从最优单纯形表中选择具有最大小数部分的非整分量所在行构造割平面约束条件；4.将新约束条件加入原问题最优单纯形表，求解；5.返2。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章例：以课本例6为例说明。Cj3-1000CBXBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/7 j=cj-z
9、j00-5/70-3/7增加约束条件：二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-10000CBXBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/71 j=cj-zj00-5/70-3/70二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-10000CBXBbx1x2x3x4x5x63x11100001-1x2001-1/2003/20 x4-500-210110 x53001/201-7/2 j=cj-zj00-1/1400-3/
10、2二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-10000CBXBbx1x2x3x4x5x63x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4 j=cj-zj000-1/40-17/4增加约束条件：二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-100000CBXBbx1x2x3x4x5x6x73x111000010-1x25/4010-1/40-5/400 x35/2001-1/20-11/200 x57/40001/41-3/400 x7-3/4000-1/40-1/4
11、1 j=cj-zj000-1/40-17/40二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-100000CBXBbx1x2x3x4x5x6x73x111000010-1x2201000-1-10 x3400100-5-20 x5100001-110 x43000101-4 j=cj-zj00000-4-1原问题的最优解为：x1=1,x2=2二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章三、三、分枝定界法分枝定界法maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的松弛问题。目前求解纯整数规划和混和整数规划最常用的方法。分支概念
12、：第五章(C)(D)(B)Xj i+1(B)Xj iX*Xj*i+1i三、三、分枝定界法分枝定界法第五章三、三、分枝定界法分枝定界法定界概念定界概念：是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可作为衡量处理其他分支的一个依据。线性规划问题当约束区域缩小后，所得到的目标函数最优值不会更优于原来的约束区域所得到的最优值。对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以剔除而不再考虑了。如果出现更好的“界限”，则以它来取代原来的界限。第五章求解步骤：求解步骤：1）设有最大整数规划问题A，相应的松弛问题为B。以Zb表
13、示问题A的目标函数的初始界。（下界）2）解 B a）B没有可行解，则A也没有可行解.b）B有最优解且为整数解，则A的最优解即得。c）B有最优解但非整数解，B的最优值 Za为z*的上界3）分枝:在B的最优解中取xi(=bi)bi不为整数。构造二约束条件 xibi xi bi+1 将此二约束条件分别加入B后得到二后继规划问题B1,B2 三、三、分枝定界法分枝定界法第五章4）解后继问题。若有最优解，且满足A的整数要求。则以其目标函数值Zb与Zb比较。若Zb优于Zb，则称此后继问题为问题问题C，以Zb作为下界。否则，Zb不变。5）不属于C的后继问题中，称存在最优解，且其目标函数值比界Zb更优的后继问题
14、为待检查的后继问题待检查的后继问题。若不存在待检查的后继问题。当C存在时，C最优解为A最优解。当C不存在时，与界Zb对应的可行解为A的最优解。若存在待检查的后继问题，则选择其中目标函数值最优的一个后继问题，改称其为问题B。回3）。三、三、分枝定界法分枝定界法第五章例7 用分支定界法求解下列整数规划问题maxZ=X1+X2 X1+9/14 X2 51/14-2X1+X2 1/3X1,X2 0 整数三、三、分枝定界法分枝定界法第五章LP1LPX1 2(2,23/9)max z=41/9LP2LPX1 1(1,7/3)max z=10/3LP11LP1X2 3无解LP12LP1X2 2(33/14,
15、2)max z=61/14LP122LP1X1 2(2,2)max z=4LP121LP12X1 3(3,1)max z=4解：记整数规划问题为IP，其松驰问题为LP。解LP，得最优解为（32，103），MAXZ296 以X132进行分支。(下界zb=0,上界za=29/6)下界zb=4三、三、分枝定界法分枝定界法第五章三、三、分枝定界法分枝定界法第五章三、三、分枝定界法分枝定界法第五章三、三、分枝定界法分枝定界法第五章分支定界法的优点：(1)、任何模型均可用；(2)、思路简单、灵活；(3)、速度快；(4)、适合上机。三、三、分枝定界法分枝定界法第五章四、四、01规划规划一、01变量及其应用
16、01变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。当问题有多项要素，每项要素皆有两种选择时，可用一组01变量来描述。在应用中，有时会遇到变量可以取多个整数值的问题。如果用01变量来表示，也可以用一组01变量来取代。如x取09之间的任意整数时。x=20 x0+21x1+22x2+23x3 9 9第五章1.含有相互排斥的约束条件的问题：（1）两个约束中，只有一个起作用。例：a11x1+a12x2B1 a21x1+a22x2B2 a11x1+a12x2B1+M1Y1 a21x1+a22x20s.t.四、四、01规划规划第五章例如：ai1x1+ai2x2+ainxn bi(i
17、=1,m)互相排斥m个约束，只有一个起作用ai1x1+ainxn bi+yi M(i=1,m)y1+ym=m-1yi为0或1 M0（2）互相排斥的多个约束中，只有一个起作用（3）若a个约束条件中只能有b个起作用。则令01变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。四、四、01规划规划第五章2.固定费用问题：单耗量 产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012四、四、01规划规划第五章设Xj是第j种产品的产量。Yj是01变量，表示是（Yj=1）否（Yj=0）生产第j种产品。maxZ=4X1+5X
18、2+6X3 100Y1 150Y2 200Y3 2X1+4X2+8X3 5002X1+3X2+4X3 300X1+2X2+3X3 100X1 M1Y1 X2 M2Y2X3 M3 Y3X1,X2,X3 0 整数Y1,Y2,Y3为01变量。s.t.四、四、01规划规划第五章 由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1产品2产品3a11机床1a21机床1a13机床3a22机床2a23机床2a33机床3a14机床4a24机床43.工件排序问题：例：用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时ai
19、j见表。四、四、01规划规划第五章x11+a11 x13x13+a13 x14x21+a21 x22x22+a22 x24 x32+a32 x33x11+a11 x21+My1x21+a21 x11+M(1-y1)x22+a22 x32+My2x32+a32 x22+M(1-y2)x13+a13 x33+My3x33+a33 x13+M(1-y3)x14+a14 x24+My4x24+a24 x14+M(1-y4)x24+a24-x21 dw x14+a14w x24+a24w x33+a33min z=wmin z=max(x14+a14,x24+a24,x33+a33)设产品i在机床j上开
20、始加工的时间为xij四、四、01规划规划第五章0-1规划的解法隐枚举法(一)、基本思想：对maxZ=CXAX=bX为0或1的2n个可能解，只检查其中一部分例：maxZ=2x1+4x2+x33x1-8x2+5x3-1x1,x2,x3为 0,1 四、四、01规划规划第五章X1=1X1=0111010101X2=0X3=00X2=0X2=1X1=1X3=10001maxZ=2x1+4x2+x33x1-8x2+5x3-1x1,x2,x3为 0,1 四、四、01规划规划第五章(二)、简单隐枚举法(max)原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件Z Z0(
21、3)、将xi 按ci由小大排列。最小化问题反之。四、四、01规划规划第五章解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件：3x1-2x2+5x3 3 将(x1 x2 x3)(x2 x1 x3)例：maxZ=3x1-2x2+5x3x1+2x2-x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6 x1,x2,x3为0或1s.t.四、四、01规划规划第五章四、四、01规划规划解解(x2 x1 x3)目标值目标值 Z0 当前最好当前最好值值 (0,0,0)0 5 (0,1,0)3 8 (1,0,0)-2 (1,0,1)3 (1,1,0)1 (1,1,1)6 最优解最优
22、解 x=(1,0,1)T Z=8maxZ=-2x2+3x1+5x32x2+x1-x3 2 4x2+x1+x3 4 x2+x1 3 4x2 +x3 6 第五章例例12例：例：minZ=3x1+7x2-x3+x4 2x1-x2+x3-x4 1 x1-x2+6 x3-4x4 8 5x1+3x2+x4 5 x1,x2,x3,x4为为0或或1第五章 minZ=7x2+3x1+x4-x3-x2+2x1 -x4+x3 1 -x2+x1 +4x4+6 x3 8 3x2+5x1+x4 5 x1,x2,x3,x4为0或1 (x2 x1 x4 x3)目标值 Z0 当前最好值 (0,0,0.0)0 (0,0.0,1)
23、-1 (0,0,1,0)1 (0,0,1,1)0 (0,1,0,0)3 (0,1,0,1)2 (0,1,1,1)3 3 (1,0,0,0)7 (1,0,0,1)第五章练习题练习题1 试利用01变量对下列各题分别表示成一般线性约束条件(1)x1+x2 2 或 2x1+3x2 8；(2)变量 x3只能取值0、5、9、12；(3)若 x2 4 ，则 x5 0，否则x5 3；(4)以下四个约束条件中至少满足两个：x6+x7 2 x6 1 x7 5 x6+x7 3第五章2 某校篮球队准备从以下六名预备队员中选取三名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示：队员的挑选要满足下列条件：
24、至少补充一名后卫队员；小李或小田中间最多只能入选一名，最多补充一名中锋；无论小李或小赵入选，小周就不能入选。试建立这个问题的数学模型。预备队员号码身高位置大张4193中锋小李5191中锋小王6187前锋小赵7186前锋小田8180后卫小周9185后卫练习题练习题第五章练习题练习题第五章3：某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2.s10。相应的钻探费用为c1,c2.c10。并且井位选择上要满足下列限制条件：或选择s1和s7，或选择钻探s8选择了s3或s4就不能选s6或反过来也一样在s5、s6、s7、s8中最多只能选两个。试建立
25、这个问题的整数规划模型。练习题练习题第五章当选择si时令xi=1，否则令xi=0s.t.练习题练习题第五章minZ=4x1+3x2 +2x3 2x1-5x2+3 x3 4 4x1+x2+3 x3 3 x2+x3 1 x1,x2,x3 为0或1 4：解下面的：解下面的0-1型整数规划型整数规划第五章五、指派问题五、指派问题（一）指派问题的标准形式及其数学模型现实生活中，有各种性质的指派问题。指派问题的标准形式是：有n个人和n件事，已知第i人做第j事的费用为cij，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。系数矩阵：C=(cij)nn=c11 c11 c11 c11 c1
26、1 c11 c11 c11 c11 费用成本时间第五章引入01变量：xij(1，若指派第 i人做第j事)(=0，若不指派第 i人做第j事）则指派问题的数学模型为：五、指派问题五、指派问题第五章 例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i1,2,.,5)对新商店Bj(j1,2,5)的建造费用的报价(万元)为cij(i，j1，2,.,5)，见表。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少?BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106五、
27、指派问题五、指派问题第五章问题的数学模型为：minZ=4x11+8x12+10 x54+6x55 五、指派问题五、指派问题第五章例：有一 份中文说明书，需译成英.日.德.俄四种文字。分别记作E.J.G.R。现有甲.乙.丙.丁 四人。他们将中文说明书译成不同语种的说明书所需时间 cij 如表：EJGR甲215134乙1041415丙9141613丁78119?应指派何人去完成何工作，使所需总时间最少。五、指派问题五、指派问题第五章五、指派问题五、指派问题第五章（二）匈牙利解法是一类特殊的运输问题和01整数规划问题。匈牙利法：库恩W.W.Kuhn 利用匈牙利数学家康尼格关于独立零元素的定理 195
28、5理论依据：系数矩阵中独立0元素的最多个数=能覆盖所有0元素的最少直线数。最优解性质：从系数矩阵cij的一行（或列）减去该行（或列）的最小元素，得到的新矩阵bij。它们的最优解相同。关键：寻找n个独立0元素。五、指派问题五、指派问题第五章 计算步骤：1.化系数矩阵。EJGR甲013112乙60311丙0574丁0142EJGR甲01380乙6009丙0552丁0110EJGR甲215134乙104715丙9141613丁78119五、指派问题五、指派问题第五章2.进行试指派，以寻求最优解。（确定独立零元素）在只有一个零元素的行（或列）的零元素加圈。把位于同列（或同行）的其它零元素划去。如此反复
29、，直至所有零元素都被圈去或划去为止。如有多个零元素，任选。如有n个独立零元素，得解。否则，转3。EJGR甲01380乙6009丙0552丁0110五、指派问题五、指派问题第五章 3.作最少直线覆盖所有0元素。方法：1)对没有划圈零元素的行打“”；2)在已打“”的行中，对划去零元素所在列打“”；3)在已打“”的列中，对划圈零元素所在行打“”；4)重复(2)相(3)，直到再也不能找到打“”的行或列为止；5)对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。五、指派问题五、指派问题第五章 4.进行矩阵变换增加0元素。找出没被直线覆盖的最小元素，打“”
30、的行减去该元素，打“”的列加上该元素，若得到n个独立0元素，得解。否则转入第三步。EJGR甲01380乙6009丙0552丁0110五、指派问题五、指派问题第五章EJGR甲01270乙70010丙0442丁0000EJGR甲01270乙70010丙0442丁0000五、指派问题五、指派问题第五章例：拟派甲.乙.丙.丁四人去完成四项工作。已知甲.乙.丙.丁完成各项工作的时间如表：ABCD甲5333乙1683丙11226丁581110？如何指派，使总的消耗时间最少。五、指派问题五、指派问题第五章 解：1、化系数矩阵 5333168311226581110 5 0 0 0 0 5 7 2 9 0 0
31、 4 0 3 6 5五、指派问题五、指派问题第五章2、确定独立零元素 5 0 0 0 0 5 7 2 9 0 0 4 0 3 6 5000五、指派问题五、指派问题第五章 3、变换矩阵 5 6 3 0 4 0 0 9 2 7 5 0 0 0 0 5000 0 0 0 0 0 0 4 0 最优委派：甲C,乙，丙，丁最少的耗费时间：+五、指派问题五、指派问题第五章一般的指派问题一般的指派问题1、最大化指派问题：化成最小化。让最大的系数减去所有的系数。2、人数和事数不等的指派问题：人少事多，则添人。人多事少，则添事。费用系数均取03、一个人可做几件事的指派问题：一人化几人，费用系数相同4、某事一定事不能由某人做的指派问题：将费用系数取足够大的M五、指派问题五、指派问题第五章例 由A1，A2，A3来承建，每家公司可以承建一家或二家商店，求使总费用最少的指派方案。BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106第五章 BjAiB1B2B3B4B5B6A148715120A2791714100A36912870A148715120A2791714100A36912870第五章作作 业业5456（1）59（2）514