整数规划的建模.ppt

《整数规划的建模.ppt》由会员分享，可在线阅读，更多相关《整数规划的建模.ppt（69页珍藏版）》请在三一办公上搜索。

1、第八章 整数规划,在线性规划问题中，有一类特殊的情形，称为整数规划，这类问题的最优解必须是整数。如求解完成工作所需的最少人数，或加工一批零件所需机器的台数。由于这类问题并不是由简单的“四舍五入”法或“去零化整”法就能求得最优解，因此有必要对它作专门的讨论。,本章包含四部分的内容：第一部分：整数规划的建摸第二部分：整数规划的应用（0-1型整数规划）第三部分：分支定界法第四部分：指派问题,1、整数规划的建摸,整数规划问题的数学模型和线性规划基本相同，只是约束条件有所不同，下面我们以例题说明整数规划的建模。1、问题的提出例1 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限

2、制如表，问两种货物各托运多少箱可获利润最大？,解：设x1,x2分别为甲、乙两种货物的托运箱数（应为大于或等于零的整数），这是一个整数规划问题，数学模型如下,从上式可见，它和线性规划问题的区别仅在于 x1,x2为整数这一条件。如果我们暂不考虑 这一条件，很容易求得相应线性规划问题的最优解为，但不满足整数要求，如按四舍五入取，又破坏了 这一条件，如舍去尾数取x1=4,x2=0 虽然满足了约束条件，但此时z=80，不是最优解，因为当时x1=4,x2=1，既满足约束条件，且z=9080。由此可见整数规划问题并非通过“化整”求其最优解。,从以上的例题可以看出：由于相应的线性规划的可行域包含了其整数规划的

3、可行解，就可有如下的性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值。,2、定义 规划中的变量（部分或全部）限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。3、整数规划分类 如不加特殊说明，一般指整数线性规划。对于整数线性规 划模型大致可分为两类：（1）变量全限制为整数的，称纯（完全）整数规划。（2）变量部分限制为整数的，称混合整数规划。,4、整数规划特点 整数规划标准形式（实际为整数线性规划）AX=b，X0，CTX=min，xj为整数（j=1，n）(1)（1原线性规划有最优解，当自变量限制为整

4、数后，其整数规划解出现下述情况；原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。,有可行解（当然就存在最优解），但最优解值变差。原线性规划为：2x1+4x2=6，X0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=3/2，min CTX=3/2。若限制整数则得：x1=1，x2=1，min CTX=2。,5、求解方法分类：（1 割平面法主要求解纯整数线性规划（2 分枝定界法可求纯或混合整数线性规划（3 隐枚举法求解“01”整数规划：过滤隐枚举法；分枝隐枚举法（4 匈牙利法解决指派问题（“01”规划特殊情形）。（5蒙特卡洛法求解各种类型规划。,2、整

5、数规划的应用（0-1型整数规划）,在整数规划中有一类特殊的情形，它的变量xi仅能取0或1，这时的xi称为0-1变量，这类问题也就称为0-1型整数规划。2、1 0-1型数规划的建模0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态或者决策时是否采取某个特定方案。,当问题含有多项要素，而每项要素皆有两种选择时，也可用0-1变量来描述 设某问题有有限要素E1,E2,E n，其中每项Ej有两种选择Aj和(j=1.2.-,n)则：,2、1、2下面讨论0-1整数规划的几种应用实例。,1相互排斥的计划问题例3 某超市连锁店的布点问题。某超市连锁店在分析某城市的特征后，将该城市划分成四个区域：东片、

6、西片、南片、北片。在四个区域中共确定了10个连锁店的备选点，记作 在连锁店选择时需考虑以下限制：,东片的三个点 中,至少应选择一个;西片的两个点 中，应恰好选择一个；南片的四个点 中，最多只能选三个；北片只有一个备选点，可选可不选。,如果选中 点，其投资为 元，每年的预期收益为 元。现要求总投资不超过Z元，问应选择哪些备选点，既可满足限制，又可使每年的总收益最大。试建立这个问题的0-1型整数规划数学模型。解：设 则可建立如下0-1型整数规则数学模型：,例4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为，相应的钻探费用为，并且井位选择上要满足

7、下列限制条件：或选择S1和S7，或选择S8；选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；在S5S8中最多选两个。建立这个问题的0-1型整数规划模型,解：,例5指派问题,有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题,例有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,解：引入01变量 xij，并令 xij=1(当

8、指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x2

9、2+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij 为0-1变量，i,j=1,2,3,4,2相互排斥约束条件问题,例6 在例1中，关于货运的体积限制为。5X1+4X224如设货运有车运和船运两种方式，上面的体积限制条件是针对车运的，如用船运时体积限制条件为7X1+3X245，为把这两个限制条件统一在一个问题中，我们引入0-1变量，令,这样数学模型的约束条件就应写为：其中M为一充分大数，当 y=0时，上面两个约束条件实际上就是第一个在起作用，当y=1时第一式自然满足，起作用的仅是第二式。,2

10、、2 0-1型整数规划的解法,例 求解0-1整数规划,解：先考虑可能的解的组合，共23=8个，列于表3.3中。先分析第一个解（0，0，0），经检查为可行解，而其目标函数值为0，则考察其它的解，只有其目标函数值满足（3、6）时，才检查其是否可行，否则不予检查。我们把条件（3.6）称为过滤条件。再分析解（0，0，1），由于其目标函数值为-1，不满足过滤条件（3.6），故不予检查。,分析解（0，1，0），其目标函数值为7，故要检查，经检查不满足约束条件，故过滤条件不予修改。类似于上述分析，直到将所有的解均检查完毕，最后得到结论，最优解为（1，1，1），最优目标函数值为9。我们将上述求解方法称为隐枚举

11、法。,(二)、简单隐枚举法(max),原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件Z Z0(3)、将xi 按ci由小大排列,解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件：3x1-2x2+5x3 3 将(x1 x2 x3)(x2 x1 x3),3、整数规划的分枝定界法,在求解整数规划问题时，如果可行域是有界的，人们很容易联想到的方法是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，如例1，此法是切实可行的，但对于大型问题，可行的整数组合很多，穷举法显然不能胜任求解任务。为此，在20世纪60年代初由

12、Land Doig和Dakin等人提出了分枝定界法，有效地解决了这一问题。,3、1分枝定界法的基本思想,设有最大化的整数规划问题A，与它相应的线性规划问题为B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数 的上界，记为；而A的任意可行解的目标函数值将是 的一下界，分枝定界法就是要将B的可行域分成子区域称为分枝，逐步减少 和增大 称为定界，最终求得。,分枝定界法的关键是分枝和定界，“分枝”为整数规划最优解的出现创造了条件，而“定界”则可以提出搜索的效率。经验表明，在可能的情况下，根据对实际问题的了解，事先选择一个合理的“界限”，可以提高分枝定界法的搜索效

13、率。,3、2分枝定界法求解整数规划（最大化）问题步骤为：,1求解相应于整数规划A的线性规划问题B，B的结果必为下列情况之一：（1）B无可行解，则A也无可行解。（2）B有最优解，并符合问题A的整数条件，则B的最优解即为A的最优解。（3）B有最优解，但不符合A的整数条件，则记它的目标函数值 为即 的上界。,2用观察法找出A的一个整数可行解，一般可取，试探，求得其目标函数值，记为z，这时有。,3对问题B，任选一个不符合整数要求的变量进行分枝。设选择xj=bj，且设bj为不超过bj的最大整数。对问题B分别构造两上约束条件：和将这两个约束条件，分别加入问题B，从而形成两个后继问题，解这两个后继问题。,4

14、以每个后继问题为一分枝标明求解结果，与其它分枝的解相比较，找出最优目标函数值最大者 作为新的上界，从已符合整数条件的各分枝中，找出目标函数值最大者作为新的下界z，如还未出现符合整数条件的解，则仍取原来的下界。,5继续分枝求解，各分枝的最优目标函数中若有小于z者，则剪去这枝（用表示）即以后不再考虑这枝。若大于z，但不符合整数条件，则继续分枝，直到找到 为止，最终求得整数规划问题A的最优解。,下面结合例题说明分枝定界法的解题步骤,例2 求解,解：先不考虑整数条件，求解相应于A的线性规划B，得最优解为,这个解不符合整数条件，将z=29/6定为问题A的最优解z*的上界；选择问题A的一个整数可行解x1=

15、0,x2=0,它的目标函数值z=0作为的下界，即0z*29/6。,将问题B分枝为两个子问题B1、B2，在B1中加上X13/2约束条件，在B2中加上X13/2+1约束条件。分别求解两个子问题，得到相应的最优解：B1：B2:,重新给Z*定界 由于41/910/3，所以优先选择B2再进行分枝。分别加上约束条件X223/9和X223/9+1，将分枝为和两个子问题，继续求解。按照这一方法不断分枝和定界，可行域不断缩小，上界不断减少，下界逐渐增大，当上界和下界相等时，便得到最优整数解。本题有两个最优解，分别为X1=3,X2=1和 X1=2,X2=2,上述分枝定界法的求解过程还可用图来表示,4、指数问题,在

16、整数规划中还有一类特殊的情形就是指派问题。指派问题在现实生活中经常遇到，例如：有若干项工作需要分配给若干人来完成，由于每个人的专长不同，所以完成工作所需的时间也不同，那么就产生了如何合理安排哪个人去完成哪项工作，才能使总效率最高，这是一类典型的指派问题。由此引伸到学校如何安排班级在各教室上课，以及工程选择投标者承包等。这类问题的共同要求就是在满足特定的指派要求条件下，使指派方案的总体效果最佳。,4、1指派问题的标准形式及数学模型,指派问题标准形式是：有n个人和n件事，已知第I个人做第j件事的费用为cij,I,j=1,2,n（cij还可表示成本、时间等含义），要求确定人与事之间的一一对应的指派方

17、案，使完成n件事的总费用最少。为了建立上述指派问题的数学模型，引入个0-1变量：,这样它的数学模型为：模型中，约束条件（3.7）表示每件事必有且只有一个人去做，约束条件（3.8）表示每个人必做且只做一件事。,指派问题的可行解可用矩阵表示：,解矩阵的每行每列元素中都有且只有一个1，以满足约束条件。指派问题有n！个可行解。下面以例题说明指派问题的建模。,下面以例题说明指派问题的建模。,例 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai对新商店Bj的建造费用的报价（万元）为Cij，见表所示。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建

18、造费用最少？,这是一个标准的指派问题。若设0-1变量则问题的数学模型为,4、2指派问题的匈牙利解法,从指派问题的数学模型可以看出，指派问题是0-1整数规划的特例，也是运输问题的特例，即，当然更是一个整数规划问题，所以指派问题可用隐枚举法、表上作业法和分枝定界法求解。但是我们可以利用指派问题数学模型的特点，找到更加简便的方法，这就是由匈牙利数学家康尼格（D.knig）提出的匈牙利解法。,4、2、1匈牙利解法的思想基础,从指派问题的系数矩阵 的某行（某列）各元素中分别减去一个常数k，得到的新矩阵 所代表的新指派问题与原指派问题有相同最优解。,例9 有一份中文说明书，要将其翻译成三种不同的文字，三位

19、不同人翻译三种不同的文字所花的时间见表。试确定翻译的最佳指派方案。,解：1.先对时间矩阵的各行减去最小值。,2确定独立0元素，即在每行和每列中各圈出一个“0”。当n较小时，可用观察法、试探法找出n个独立0元素，当n较大时，可按以下步骤进行：,（1）从只有一个0素的行（列）开始，给这个0元素加圈，称为独立0元素，记作，这表示对这行所代表的“人”只翻译该列所对应的语种，然后划去所在列或行的其他0元素，记作，这表明该行的“人”得到任务后，该人则不能再翻译其他语种。（2）再在剩下的元素中，从只有一个0元素的行（列），给这个0元素加圈。重复上述过程，直到所有0元素都被圈出或划掉。如果独立元素有n个，则表

20、明已可确定最优指派方案。此时令矩阵中和独立0元素相对应位置上的元素为1，其余元素为0，即可得最优矩阵。,按此步骤，本例可得独立0元素如下：,从而得指派方案：即：甲翻译日文乙翻译德文丙翻译英文所花总时间为：2+3+4=9。,是不是所有的问题都能像例9那样，方便地获得独立的0元素呢？现在我们再来看一则例子，以进一步说明匈牙利算法的详细解题步骤。,用匈牙利算法求解上上例所对应的问题的最优解。解：已知例指派问题的系数矩阵为：,1先对各行元素分别减去本行的最小元素，然后对各列也如此，即,此时，中各行和各列都已出现0元素，且没有负数。,2确定中的独立0元素，即：,3由于本例中只有4个独立0元素，少于系数矩

21、阵阶数n=5，表示还不能确定最优指派方案。此时，需要确定能覆盖所有0元素的最少直线数目的直线集合。可按下面步骤进行：,1）对没有的行打“”；（2）在已打“”的行中，对0所在列打“”；（3）在已打“”的列中，对所在行打“”；（4）重复（2）和（3），直到再也不能找到可以打“”的行或列为止；（5）对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。,本例可得下面矩阵：,4在未被直线覆盖的元素中找出一个最小元素，对未被覆盖元素所在行中各元素都减去这一最小元素，这样势必会出现0元素，但同时却又使已被直线覆盖的元素中出现负数，为了消除这些负数，只要对划了线

22、的列的各元素都加上这一最小元素即可。,本例矩阵变换为：,5返回步骤2，确定中的独立0元素,中已有5个独立0元素，故可确定指派问题的最优指派方案。本例的最优解为：,也就是说，最优指派方案是：让A1承建B3;A2承建B2;A3承建B1;A4承建B4;A5承建B5。这样安排能使总的建造费用最少，为7+9+6+6+6=34（万元）。,4、3、3非标准形式的指派问题,在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理原则是先将它们化为标准形式，再按匈牙利解法求解。1最大化指派问题设最大化指派问题系数矩阵 中最大元素为m，令矩阵 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题具有相同最优解。,2人数和工作件数不等的指派问题,若人少事多，则添上一些虚拟“人”。这些虚拟“人”的费用系数可取0。若人多事少，则添上一些虚拟“事”，完成这些虚拟“事”所需耗费各人的费用同样也取0。,3一个人可做若干件事的指派问题,如果某个人可做几件事，则可将该人“复制”成相同的几个“人”来接受指派，这几个人做同一件事的费用系数完全相同。转化成人与事一一对应，且寻求费用极小化的标准形式来处理。,4某事一定不能由某人做的指派问题,若某事一定不能由某人完成，则可将相应的费用系数取作足够大的数M。总之要把这些非标准的指派问题转化成人与事一一对应，且寻求费用极小化的标准形式来处理。,