西北农林科技大学运筹学课件第五章整数规划

1、第五章第五章 整数规划整数规划一、整数规划数学模型及解的特点二、解纯整数规划的割平面法三、分支定界法四、01型整数规划五、指派问题第五章例1、集装箱运货 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 5 2 20 乙 4 5 10装运限制 24 13 一、数学模型及解的特点一、数学模型及解的特点第五章解：设x1 , x2 为甲、乙两货物各托运箱数5x1+4x2 242x1+5x2 13x1 , x2 0 x1 , x2为整数maxZ = 20 x1 + 10 x2纯整数线性规划纯整数线性规划一、数学模型及解的特点一、数学模型及解的特点第五章例2、背包问题背包可再装入8单位重

2、量，10单位体积物品物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 一、数学模型及解的特点一、数学模型及解的特点第五章解：xi为是否带第 i 种物品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 ，建

3、2个Bj: 商店，需求dj ( j=14 )Cij: 仓库 i 到商店 j 的单位 运费问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。一、数学模型及解的特点一、数学模型及解的特点第五章解：设xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=14)由 i仓库向 j商店运货量313141miniijijijiiyCxbZ混合整数规划混合整数规划y11 + y21 = d1y12 + y22 + y32 = d2y23+ y33 = d3y14 + y24 + y34 = d4x1 + x2 + x3= 2y11 + y12 + y14 a1x1y21

4、+ y22 + y23 + y24a2x2y32 + y33 + y34 a3x3xi 为01， yij 0s.t.一、数学模型及解的特点一、数学模型及解的特点第五章整数规线性划数学模型的一般形式：0max11iniiiniiiXbXaXCZ,部分或全部为整数一、数学模型及解的特点一、数学模型及解的特点第五章一、数学模型及解的特点一、数学模型及解的特点几个概念：1、整数规划（IP）-要求一部分或全部决策变量必须取整数值的规划问题。2、松弛问题-不考虑整数条件，由余下的目标函数和约束条件构成的规划问题，称为该整数规划问题的松弛问题。3、整数线性规划若松弛问题是一个线性规划，则称该整数规划为整数线

5、性规划。第五章常用问题 ： 1背包问题 2指派问题整数规划的常用解法： 1分枝定界法 2割平面法 分类 0 1 规划 纯整数规划 整数规划 . 混合整数规划一、数学模型及解的特点一、数学模型及解的特点第五章V m3 G 100kg利润甲5220乙4510托运限制2413问：如何托运才能使利润最大？例 某厂拟用集装箱托运甲.乙两种货物。解的特点解的特点1 整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定）。前者最优解的目标函数值不会优于后者最优解的目标函数值。2 松弛问题的最优解的简单取整，不一定是最优解。一、数学模型及解的特点一、数学模型及解的特点第五章 最优解 ： 甲 4 乙

6、1 调整 ： 1 ） “ 凑整” 甲 5 乙 02 ） “ 舍尾” 甲 4 乙 0松弛问题的解：甲 4.8 乙 0一、数学模型及解的特点一、数学模型及解的特点第五章二、解纯整数规划的割平面法二、解纯整数规划的割平面法纯整数规划问题取整数jjnjijijnjjjxXbXaXCZ0max11第五章 在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。QibxaxKjijijiCj3501000CBXBbx1x2x3x4x5x6x70 x39.5-20100.5-0.5-0.55x22631000.50.50.51x414.5-20010.5-0.50.5 j=c

7、j-zj-10000-3-2-3则m个约束方程可表示为：二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章对应的最优解：TnixxxX*)*,.,*,(21其中：KjQjbxjj0*全为整数时，为纯整数规划的最优解。bj不全为整数时，则不是纯整数规划的可行解，也不是原整数规划的最优解。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章割平面法的思路：割平面法的思路：若松弛问题的最优解不全为整数，则从X的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。直到全为最优解为止。增加的约束条件具备的两个基本性质：其一：原松弛问题最优解

8、不满足该条件；其二：凡整数可行解均满足该条件。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Xi0 A Xj = bi0分解A ,b为两部分。A=Na+Fa b=Nb+Fb F为不超过该数的最大整数。则上式变为：Xi0（ Na+Fa ）XjNb+FbXi0 Na Xj Nb Fb Fa XjKjijibxaxji0,00 可以证明此条件满足上述两个基本性质。可以作为增加的约束条件。Fb Fa Xj 0 0 Fa Xj - -Fb 二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章割平面法求解步骤：割平面法求解步骤： 求解原问题的松驰问题；若最优解全为整数，则达到最优；否则转

9、3；从最优单纯形表中选择具有最大小数部分的非整分量所在行构造割平面约束条件；将新约束条件加入原问题最优单纯形表，求解；1.返2。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章例：以课本例6为例说明。Cj3-1000CBXBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/7 03/70 x431/700-3/7 122/7 j=cj-zj00-5/7 0-3/7增加约束条件：76572371xx766572371xxx二、解纯整数规划的割平面法二、解纯整数规划的割平面法767135723711)0(xx第五章Cj3-10000CBXBbx1x2x3x4x

10、5x63x113/7101/702/70-1x29/701-2/7 03/700 x431/700-3/7 122/700 x6-6/700-1/7 0-2/71 j=cj-zj00-5/7 0-3/70二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-10000CBXBbx1x2x3x4x5x63x11100001-1x2001-1/2003/20 x4-500-210110 x53001/201-7/2 j=cj-zj00-1/1400-3/2二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章Cj3-10000CBXBbx1x2x3x4x5x63x11100001-

11、1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4 j=cj-zj000-1/40-17/4增加约束条件：43641441xx437641441xxx二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章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/41 j=cj-zj000-1/40-17/40二、解纯整数规划的割平面法二、解纯整数规划的

12、割平面法第五章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)的松弛问题。目前求解纯整数规划和混和整数规划最常用的方法。分支概念：第五章(C)(D)(B)Xj i+1(B)Xj iX*Xj*i+1i三、三、 分枝定

13、界法分枝定界法第五章三、三、 分枝定界法分枝定界法定界概念定界概念：是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可作为衡量处理其他分支的一个依据。线性规划问题当约束区域缩小后，所得到的目标函数最优值不会更优于原来的约束区域所得到的最优值。对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以剔除而不再考虑了。如果出现更好的“界限”，则以它来取代原来的界限。第五章求解步骤：求解步骤：1）设有最大整数规划问题A ，相应的松弛问题为B 。以Zb表示问题A的目标函数的初始界。（下界）2）解 B a） B没有可行解，则A也没有

14、可行解. 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更优的后继问题为待检查的后继问题待检查的后继问题。若不存在待检查的

15、后继问题。当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,2) max z=61/14LP12

16、2LP1X1 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三、三、 分枝定界法分枝定界法第五章为非负整数例：21212121,7020756799040maxxxxxxxxxz35682.1,81.4021zxx最优解为：解：相应的松弛问题的3560:* zz原问题的最优解541111xxx：中分别添加两个子约束非整数，在原约束问题） 三、三、 分枝定界法分枝定界法第五章57.100.53411

17、0.200.4349;212211121xxzBxxzBBB最优解为：同样不考虑整数条件其得到两个子问题：3490*z三、三、 分枝定界法分枝定界法第五章B82. 181. 4356210 xxz3490* z3560* z341340* z340*z1B10. 200. 4349210 xxz2B57. 100. 5341210 xxz51x41x6B无可行解5B00.144.5308210 xxz22x12x4B3B00.342.1327210 xxz24340210 xxz32x22x三、三、 分枝定界法分枝定界法第五章分支定界法的优点：(1)、任何模型均可用；(2)、思路简单、灵活；(

18、3)、速度快；(4)、适合上机。三、三、 分枝定界法分枝定界法第五章简单隐枚举法(max)原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件Z Z0(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或1

19、s.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 最优解最优解 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

20、 +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) -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

21、,0 ,0) 7 (1 ,0,0 ,1)第五章某校篮球队准备从以下六名预备队员中选取三名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示：队员的挑选要满足下列条件： 至少补充一名后卫队员； 小李或小田中间最多只能入选一名， 最多补充一名中锋； 无论小李或小赵入选，小周就不能入选。试建立这个问题的数学模型。预备队员号码身高位置大张4193中锋小李5191中锋小王6187前锋小赵7186前锋小田8180后卫小周9185后卫练习题练习题第五章练习题练习题第五章某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2.s10。相应的钻探

22、费用为c1,c2.c10。并且井位选择上要满足下列限制条件：或选择s1和s7，或选择钻探s8选择了s3或s4就不能选s6或反过来也一样在s5、s6、s7、s8中最多只能选两个。试建立这个问题的整数规划模型。练习题练习题第五章101miniiixcz10,.,1, 102)1(1)1(258765643643871871101iorxxxxxMyxxMyxxMxxxMxxxxiii当选择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

23、 为0或1解下面的解下面的0-1型整数规划型整数规划第五章五、指派问题五、指派问题（一）指派问题的标准形式及其数学模型现实生活中，有各种性质的指派问题。指派问题的标准形式是：有n个人和n件事，已知第i人做第j事的费用为cij，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。系数矩阵：C=(cij)nn =c11 c11 c11 c11 c11 c11 c11 c11 c11 费用成本时间第五章引入01变量： xij(1，若指派第 i人做第j事) ( =0， 若不指派第 i人做第j事）则指派问题的数学模型为：五、指派问题五、指派问题第五章 例： 某商业公司计划开办五家新商店。

24、为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i1,2,.,5)对新商店Bj(j1,2,5)的建造费用的报价(万元)为cij(i，j1，2,.,5)，见表。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少? BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106五、指派问题五、指派问题第五章问题的数学模型为：minZ = 4x11 + 8x12 +10 x54 +6x55 105,4,3,2,115,4,3,2,1155orxixjxijjijiij时不承建当0时承建当1jijiijBA

25、BAx令：五、指派问题五、指派问题第五章例：有一 份中文说明书，需译成英.日.德.俄四种文字。分别记作E.J.G.R。现有甲.乙.丙.丁 四人。他们将中文说明书译成不同语种的说明书所需时间 cij 如表：EJGR甲215134乙1041415丙9141613丁78119? 应指派何人去完成何工作，使所需总时间最少。五、指派问题五、指派问题第五章项工作人去完成第不指派第项工作人去完成第指派第令：jijixij01104,3,2,114,3,2,11minorxixjxxczijjijiijijijij 五、指派问题五、指派问题第五章（二）匈牙利解法是一类特殊的运输问题和01整数规划问题。匈牙利法

26、： 库恩W.W.Kuhn 利用匈牙利数学家康尼格关于独立零元素的定理 1955理论依据： 系数矩阵中独立0元素的最多个数=能覆盖所有0元素的最少直线数。最优解性质：从系数矩阵cij的一行（或列）减去该行（或列）的最小元素，得到的新矩阵bij 。它们的最优解相同。关键：寻找n个独立0元素。五、指派问题五、指派问题第五章 计算步骤： 1 . 化系数矩阵。 EJGR甲013112乙60311丙0574丁0142EJGR甲01380乙6009丙0552丁0110EJGR甲215134乙104715丙9141613丁78119五、指派问题五、指派问题第五章2 . 进行试指派，以寻求最优解。（确定独立零元

27、素） 在只有一个零元素的行（或列）的零元素加圈。把位于同列（或同行）的其它零元素划去。如此反复，直至所有零元素都被圈去或划去为止。如有多个零元素，任选。如有n个独立零元素，得解。否则，转3。 EJGR甲01380乙6009丙0552丁0110五、指派问题五、指派问题第五章 3. 作最少直线覆盖所有0元素。方法： 对没有划圈零元素的行打“”；在已打“”的行中，对划去零元素所在列打“”；在已打“”的列中，对划圈零元素所在行打“”；重复(2)相(3)，直到再也不能找到打“”的行或列为止；1)对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。 五、指派问题五、指派问题第五章 4.进行矩阵变换增加0元素。找出没被直线覆盖的最小元素，打“”的行减去该元素，打“