第五章整数规划.ppt

《第五章整数规划.ppt》由会员分享，可在线阅读，更多相关《第五章整数规划.ppt（76页珍藏版）》请在三一文库上搜索。

1、第五章 整数规划,一、整数规划数学模型及解的特点 二、解纯整数规划的割平面法 三、分支定界法 四、01型整数规划 五、指派问题,一、数学模型及解的特点,几个概念： 1、整数规划（IP）-要求一部分或全部决策变量必须取整数值的规划问题。 2、松弛问题-不考虑整数条件，由余下的目标函数和约束条件构成的规划问题，称为该整数规划问题的松弛问题。 3、整数线性规划若松弛问题是一个线性规划，则称该整数规划为整数线性规划。,例1、集装箱运货,一、数学模型及解的特点,解：设x1 , x2 为甲、乙两货物各托运箱数,maxZ = 20 x1 + 10 x2,纯整数线性规划,一、数学模型及解的特点,例2、背包问题

2、,背包可再装入8单位重量，10单位体积物品,一、数学模型及解的特点,解：xi为是否带第 i 种物品,maxZ=20x1 + 30x2 +10x3+18x4 +15x5,01型整数线性规划,一、数学模型及解的特点,例3、选址问题,Ai: 可建仓库地点，容量ai ,投资费用bi ，建2个,Bj: 商店，需求dj ( j=14 ),Cij: 仓库 i 到商店 j 的单位 运费,问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。,一、数学模型及解的特点,解：设xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=14)由 i仓库向 j商店运货量,混合整数规划,一、

3、数学模型及解的特点,整数规线性划数学模型的一般形式：,部分或全部为整数,一、数学模型及解的特点,常用问题 ： 1背包问题 2指派问题 整数规划的常用解法： 1分枝定界法 2割平面法,一、数学模型及解的特点,问：如何托运才能使利润最大？,例 某厂拟用集装箱托运甲.乙两种货物。,解的特点,1 整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定）。前者最优解的目标函数值不会优于后者最优解的目标函数值。 2 松弛问题的最优解的简单取整，不一定是最优解。,一、数学模型及解的特点,最优解 ： 甲 4 乙 1,调整 ：,1 ） “ 凑整” 甲 5 乙 0,2 ） “ 舍尾” 甲 4 乙 0,松弛

4、问题的解：甲 4.8 乙 0,一、数学模型及解的特点,二、解纯整数规划的割平面法,纯整数规划问题,在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。,则m个约束方程可表示为：,二、解纯整数规划的割平面法,对应的最优解：,其中：,全为整数时，为纯整数规划的最优解。 B不全为整数时，则不是纯整数规划的可行解，也不是原整数规划的最优解。,二、解纯整数规划的割平面法,割平面法的思路：若松弛问题的最优解不全为整数，则从X的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。直到全为最优解为止。,增加的约束条件具备的两

5、个基本性质： 其一：原松弛问题最优解不满足该条件； 其二：凡整数可行解均满足该条件。,二、解纯整数规划的割平面法,Xi0 A Xj = bi0 分解A ,b为两部分。 A=Na+Fa b=Nb+Fb F为不超过该数的最大整数。 则上式变为： Xi0（ Na+Fa ）XjNb+Fb Xi0 Na Xj Nb Fb Fa Xj,可以证明此条件满足上述两个基本性质。可以作为增加的约束条件。,Fb Fa Xj 0 Fa Xj -Fb,二、解纯整数规划的割平面法,割平面法求解步骤： 求解原问题的松驰问题； 若最优解全为整数，则达到最优；否则转3； 从最优单纯形表中选择具有最大小数部分的非整分量所在行构造

6、割平面约束条件； 将新约束条件加入原问题最优单纯形表，求解； 返2。,二、解纯整数规划的割平面法,例：以课本例6为例说明。,增加约束条件：,二、解纯整数规划的割平面法,二、解纯整数规划的割平面法,二、解纯整数规划的割平面法,增加约束条件：,二、解纯整数规划的割平面法,二、解纯整数规划的割平面法,原问题的最优解为：x1=1,x2=2,二、解纯整数规划的割平面法,三、 分枝定界法,(B)为(A)的松弛问题。,目前求解纯整数规划和混和整数规划最常用的方法。 分支概念：,三、 分枝定界法,三、 分枝定界法,定界概念：是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就

7、是一个“界限”，可作为衡量处理其他分支的一个依据。 线性规划问题当约束区域缩小后，所得到的目标函数最优值不会更优于原来的约束区域所得到的最优值。 对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以剔除而不再考虑了。如果出现更好的“界限”，则以它来取代原来的界限。,求解步骤： 1）设有最大整数规划问题A ，相应的松弛问题为B 。以Zb表示问题A的目标函数的初始界。（下界） 2）解 B a） B没有可行解，则A也没有可行解. b） B有最优解且为整数解，则A的最优解即得。 c） B有最优解但非整数解，B的最优值 Za为z*的上界 3）分枝 : 在B的最优解中取xi(=bi)

8、 bi不为整数。 构造二约束条件 xibi xi bi +1 将此二约束条件分别加入B后得到二后继规划问题B1,B2,三、 分枝定界法,4）解后继问题。 若有最优解，且满足A的整数要求。则以其目标函数值Zb与Zb比较。 若Zb优于Zb，则称此后继问题为问题C，以Zb作为下界。否则， Zb不变。 5）不属于C的后继问题中，称存在最优解，且其目标函数值比界Zb更优的后继问题为待检查的后继问题。 若不存在待检查的后继问题。当C存在时，C最优解为A最优解。当C不存在时，与界Zb对应的可行解为A的最优解。 若存在待检查的后继问题，则选择其中目标函数值最优的一个后继问题，改称其为问题B。回3）。,三、 分

9、枝定界法,例7 用分支定界法求解下列整数规划问题,maxZ=X1 + X2,三、 分枝定界法,解：记整数规划问题为IP，其松驰问题为LP。 解LP，得最优解为（32，103），MAXZ296 以X132进行分支。(下界zb=0,上界za=29/6),下界zb=4,三、 分枝定界法,三、 分枝定界法,三、 分枝定界法,三、 分枝定界法,分支定界法的优点：,(1)、任何模型均可用；,(2)、思路简单、灵活；,(3)、速度快；,(4)、适合上机。,三、 分枝定界法,四、01规划,一、01变量及其应用 01变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。 当问题有多项要素，每项

10、要素皆有两种选择时，可用一组01变量来描述。 在应用中，有时会遇到变量可以取多个整数值的问题。如果用01变量来表示，也可以用一组01变量来取代。 如x取09之间的任意整数时。 x=20x0+ 21x1 + 22x2 + 23x3 9,1. 含有相互排斥的约束条件的问题： （1）两个约束中，只有一个起作用。 例：a11x1+a12x2B1 a21x1+a22x2B2 a11x1+a12x2B1+M1Y1 a21x1+a22x2B2+M2Y2 Y1+Y2=1,实际问题,四、01规划,maxZ=20x1 + 10x2,当 x3 =0 火车 x3 =1 船,例如、假设例1中，运输方式：火车、船。 火车

11、：5x1+4x2 24 (体积) 船： 7x1+3x2 45 (体积),四、01规划,例如：ai1x1+ai2x2 +ainxn bi (i=1,m),互相排斥m个约束，只有一个起作用,（2）互相排斥的多个约束中，只有一个起作用,（3）若a个约束条件中只能有b个起作用。 则令01变量之和为a-b。 注意：可用统一M，但M的取值必须足够的大。,四、01规划,2.固定费用问题：,四、01规划,设Xj是第j种产品的产量。Yj是01变量，表示是（Yj=1）否（Yj=0）生产第j种产品。,四、01规划,由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工

12、完全部产品。,3. 工件排序问题： 例：用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时aij见表。,四、01规划,x11+a11 x13 x13+a13 x14 x21+a21 x22 x22+a22 x24 x32+a32 x33,x11+a11 x21 +My1 x21+a21 x11 +M(1-y1 ) x22+a22 x32 +My2 x32+a32 x22 +M(1-y2 ) x13+a13 x33 +My3 x33+a33 x13 +M(1-y3 ) x14+a14 x24 +My4 x24+a24 x14 +M(1-y4 ),x24+a24 -x21

13、d,w x14+a14 w x24+a24 w x33+a33,min z=w,min z=max(x14+a14 , x24+a24 , x33+a33),设产品i在机床j上开始加工的时间为xij,四、01规划,0-1规划的解法隐枚举法,四、01规划,四、01规划,(二)、简单隐枚举法(max),原则： (1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0 (2)、增加过滤条件Z Z0 (3)、将xi 按ci由小大排列。最小化问题反之。,四、01规划,解： 观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3 过滤条件：3x1 - 2x2+5x3 3 将(x1

14、x2 x3 ) (x2 x1 x3 ),四、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=8,maxZ = -2x2 + 3x1 +5x3,例12,练习题,1 试利用01变量对下列各题分别表示成一般线性约束条件,(1) x1 + x2 2 或 2x1 + 3x2 8；,(2)变量 x3只能取值0、5、9、12；,(3)若 x2 4 ，则 x5 0，否则x5 3；,2

15、某校篮球队准备从以下六名预备队员中选取三名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示：,队员的挑选要满足下列条件： 至少补充一名后卫队员； 小李或小田中间最多只能入选一名， 最多补充一名中锋； 无论小李或小赵入选，小周就不能入选。 试建立这个问题的数学模型。,练习题,练习题,3：某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2.s10。相应的钻探费用为c1,c2.c10。并且井位选择上要满足下列限制条件： 或选择s1和s7，或选择钻探s8 选择了s3或s4就不能选s6或反过来也一样 在s5、s6、s7、s8中最多只

16、能选两个。 试建立这个问题的整数规划模型。,练习题,当选择si时令xi=1，否则令xi=0,练习题,minZ = 4x1 + 3x2 +2x3,4：解下面的0-1型整数规划,五、指派问题,（一）指派问题的标准形式及其数学模型 现实生活中，有各种性质的指派问题。 指派问题的标准形式是：有n个人和n件事，已知第i人做第j事的费用为cij，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。 系数矩阵：,费用成本时间,引入01变量： xij(1，若指派第 i人做第j事) ( =0， 若不指派第 i人做第j事） 则指派问题的数学模型为：,五、指派问题,例： 某商业公司计划开办五家新商店

17、。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i1,2,.,5)对新商店Bj(j1,2,5)的建造费用的报价(万元)为cij(i，j1，2,.,5)，见表。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少?,五、指派问题,问题的数学模型为： minZ = 4x11 + 8x12 +10x54 +6x55,五、指派问题,例：有一 份中文说明书，需译成英.日.德.俄四种文字。分别记作E.J.G.R。现有甲.乙.丙.丁 四人。他们将中文说明书译成不同语种的说明书所需时间 cij 如表：,? 应指派何人去完成何工作，使所需总时间最少。,五、指派问题,五、指

18、派问题,（二）匈牙利解法,是一类特殊的运输问题和01整数规划问题。 匈牙利法： 库恩W.W.Kuhn 利用匈牙利数学家康尼格关于独立零元素的定理 1955 理论依据： 系数矩阵中独立0元素的最多个数=能覆盖所有0元素的最少直线数。 最优解性质：从系数矩阵cij的一行（或列）减去该行（或列）的最小元素，得到的新矩阵bij 。它们的最优解相同。,关键：寻找n个独立0元素。,五、指派问题,计算步骤： 1 . 化系数矩阵。,五、指派问题,2 . 进行试指派，以寻求最优解。（确定独立零元素） 在只有一个零元素的行（或列）的零元素加圈。把位于同列（或同行）的其它零元素划去。如此反复，直至所有零元素都被圈去

19、或划去为止。如有多个零元素，任选。如有n个独立零元素，得解。否则，转3。,五、指派问题,3. 作最少直线覆盖所有0元素。 方法： 对没有划圈零元素的行打“”； 在已打“”的行中，对划去零元素所在列打“”； 在已打“”的列中，对划圈零元素所在行打“”； 重复(2)相(3)，直到再也不能找到打“”的行或列为止； 对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。,五、指派问题,4.进行矩阵变换增加0元素。找出没被直线覆盖的最小元素，打“”的行减去该元素，打“”的列加上该元素，若得到n个独立0元素，得解。否则转入第三步。,五、指派问题,五、指派问题,

20、例 ：拟派甲.乙.丙.丁四人去完成四项工作。已知甲.乙.丙.丁完成各项工作的时间如表：,？如何指派，使总的消耗时间最少。,五、指派问题,解：1、化系数矩阵,五、指派问题,2、确定独立零元素,0,0,0,五、指派问题,3、变换矩阵,最优委派：甲C,乙，丙，丁,最少的耗费时间：+,五、指派问题,一般的指派问题,1、最大化指派问题： 化成最小化。让最大的系数减去所有的系数。 2、人数和事数不等的指派问题： 人少事多，则添人。人多事少，则添事。 费用系数均取0 3、一个人可做几件事的指派问题： 一人化几人，费用系数相同 4、某事一定事不能由某人做的指派问题： 将费用系数取足够大的M,五、指派问题,例 由A1，A2，A3来承建，每家公司可以承建一家或二家商店，求使总费用最少的指派方案。,作 业,54 56（1） 59（2） 514,