五章整数规划

1、第五章第五章 整数规划整数规划一、整数规划数学模型及解的特点二、解纯整数规划的割平面法三、分支定界法四、01型整数规划五、指派问题第五章一、数学模型及解的特点一、数学模型及解的特点几个概念：1、整数规划（ip）-要求一部分或全部决策变量必须取整数值的规划问题。2、松弛问题-不考虑整数条件，由余下的目标函数和约束条件构成的规划问题，称为该整数规划问题的松弛问题。3、整数线性规划若松弛问题是一个线性规划，则称该整数规划为整数线性规划。第五章例1、集装箱运货 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 5 2 20 乙 4 5 10装运限制 24 13 一、数学模型及解的特点一

2、、数学模型及解的特点第五章解：设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 种物品maxz=20 x1 + 30 x2 +1

3、0 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)由

4、i仓库向 j商店运货量313141miniijijijiiycxbz混合整数规划混合整数规划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.一、数学模型及解的特点一、数学模型及解的特点第五章整数规线性划数学模型的一般形式：0max11iniiiniiixbxaxcz,部分或全部为整数一、数学模型及解的特点一、数学模型及

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个非基变量的下标集合。qibxaxkjijijicb051 j=cj-zjcjxbx3x2x4b9.52614.53x1-23-2-105x201000 x310001x400100 x50.50.50.5-30 x6-0.50.5-0.

7、5-20 x7-0.50.50.5-3则m个约束方程可表示为：二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章对应的最优解：tnixxxx*)*,.,*,(21其中：kjqjbxjj0*全为整数时，为纯整数规划的最优解。b不全为整数时，则不是纯整数规划的可行解，也不是原整数规划的最优解。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章割平面法的思路：割平面法的思路：若松弛问题的最优解不全为整数，则从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 二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章割平面法求解步骤：割平面法求解步骤： 1.求解原问题的松驰问题；2.若最优解全为整数，则达到

9、最优；否则转3；3.从最优单纯形表中选择具有最大小数部分的非整分量所在行构造割平面约束条件；4.将新约束条件加入原问题最优单纯形表，求解；5.返2。二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章例：以课本例6为例说明。cb3-10 j=cj-zjcjxbx1x2x4b13/79/731/73x11000-1x201000 x31/7-2/7-3/7-5/70 x400100 x52/73/722/7-3/7增加约束条件：76572371xx766572371xxx二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章cb3-100 j=cj-zjcjxbx1x2x4x6b13/

10、79/731/7-6/73x110000-1x2010000 x31/7-2/7-3/7-1/7-5/70 x4001000 x52/73/722/7-2/7-3/70 x600010二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章cb3-100 j=cj-zjcjxbx1x2x4x5b10-533x110000-1x2010000 x30-1/2-21/2-1/140 x4001000 x5000100 x613/211-7/2-3/2二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章cb3-100 j=cj-zjcjxbx1x2x3x5b15/45/27/43x11000

11、0-1x2010000 x3001000 x40-1/4-1/21/4-1/40 x5000100 x61-5/4-11/2-3/4-17/4增加约束条件：43641441xx437641441xxx二、解纯整数规划的割平面法二、解纯整数规划的割平面法第五章cb3-1000 j=cj-zjcjxbx1x2x3x5x7b15/45/27/4-3/43x1100000-1x20100000 x30010000 x40-1/4-1/21/4-1/4-1/40 x50001000 x61-5/4-11/2-3/4-1/4-17/40 x7000010二、解纯整数规划的割平面法二、解纯整数规划的割平面法

12、第五章cb3-1000 j=cj-zjcjxbx1x2x3x5x4b124133x1100000-1x20100000 x30010000 x40000100 x50001000 x61-1-5-11-40 x70-1-21-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/14lp122l

16、p1x1 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.534110.

17、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)、思路简单、灵活；(3)

18、、速度快；(4)、适合上机。三、三、 分枝定界法分枝定界法第五章四、四、01规划规划一、01变量及其应用 01变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。 当问题有多项要素，每项要素皆有两种选择时，可用一组01变量来描述。 在应用中，有时会遇到变量可以取多个整数值的问题。如果用01变量来表示，也可以用一组01变量来取代。 如x取09之间的任意整数时。 x=20 x0+ 21x1 + 22x2 + 23x3 9 9第五章1. 含有相互排斥的约束条件的问题： （1）两个约束中，只有一个起作用。 例：a11x1+a12x2b1 a21x1+a22x2b2 a11x1+a1

19、2x2b1+m1y1 a21x1+a22x20s.t.四、四、01规划规划第五章例如：ai1x1+ai2x2 +ainxn bi (i=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单件售价

20、81012四、四、01规划规划第五章设xj是第j种产品的产量。yj是01变量，表示是（yj=1）否（yj=0）生产第j种产品。 maxz=4x1 +5x2 +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机床

21、1a13机床3a22机床2a23机床2a33机床3a14机床4a24机床43. 工件排序问题： 例：用4台机床加工3件产品。各产品的机床加工顺序，以及产品i在机床j上加工工时aij见表。四、四、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

22、 +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上开始加工的时间为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 =

23、10001maxz = 2x1+4x2 +x33x1 - 8x2+5x3 -1x1 , x2 , x3为 0 ,1 四、四、01规划规划第五章(二)、简单隐枚举法(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

24、+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 最优解最优解 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 = 3x

25、1 + 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) -1 (0 ,0,1 ,0) 1 (0 ,0,1 ,1) 0 (0 ,1,0

26、,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 某校篮球队准备从以下六名预备队员中选取三名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示：队员的挑选要满足下列条件： 至少补充一

27、名后卫队员； 小李或小田中间最多只能入选一名， 最多补充一名中锋； 无论小李或小赵入选，小周就不能入选。试建立这个问题的数学模型。预备队员号码身高位置大张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中最多只能选两个。试建立这个

28、问题的整数规划模型。练习题练习题第五章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 为0或1 4：解下面的：解下面的0-1型整数规划型整数规划第五章五、指派问题五、指派问题（一）指派问题的标准形式及其数学模型现实生活中，有各种性质的指派问题。指派问题的标准形式是：有n

29、个人和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事）则指派问题的数学模型为：五、指派问题五、指派问题第五章 例： 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司ai(i1,2,.,5)对新商店bj(j1,2,5)的建造费用的报价(万元)为cij(i，j1，2,.,5)，见

30、表。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少? bjaia1a2a3a4a5b147666b289979b3717121412b415148610b512107106五、指派问题五、指派问题第五章问题的数学模型为：minz = 4x11 + 8x12 +10 x54 +6x55 105,4,3,2,115,4,3,2,1155orxixjxijjijiij时不承建当0时承建当1jijiijbabax令：五、指派问题五、指派问题第五章例：有一 份中文说明书，需译成英.日.德.俄四种文字。分别记作e.j.g.r。现有甲.乙.丙.丁 四人。他们将中文说明书译成不同语种的说明

31、书所需时间 cij 如表：甲乙丙丁e21097j154148g13141611r415139? 应指派何人去完成何工作，使所需总时间最少。五、指派问题五、指派问题第五章项工作人去完成第不指派第项工作人去完成第指派第令：jijixij01104,3,2,114,3,2,11minorxixjxxczijjijiijijijij 五、指派问题五、指派问题第五章（二）匈牙利解法是一类特殊的运输问题和01整数规划问题。匈牙利法： 库恩w.w.kuhn 利用匈牙利数学家康尼格关于独立零元素的定理 1955理论依据： 系数矩阵中独立0元素的最多个数=能覆盖所有0元素的最少直线数。最优解性质：从系数矩阵ci

32、j的一行（或列）减去该行（或列）的最小元素，得到的新矩阵bij 。它们的最优解相同。关键：寻找n个独立0元素。五、指派问题五、指派问题第五章 计算步骤： 1 . 化系数矩阵。 甲乙丙丁e0600j13051g11374r21142甲乙丙丁e0600j13051g8051r0920甲乙丙丁e21097j154148g1371611r415139五、指派问题五、指派问题第五章2 . 进行试指派，以寻求最优解。（确定独立零元素） 在只有一个零元素的行（或列）的零元素加圈。把位于同列（或同行）的其它零元素划去。如此反复，直至所有零元素都被圈去或划去为止。如有多个零元素，任选。如有n个独立零元素，得解。否则，转3。 甲乙丙丁e0600j13051g8051r0920五、指派问