整数规划的建模ppt课件.ppt

《整数规划的建模ppt课件.ppt》由会员分享，可在线阅读，更多相关《整数规划的建模ppt课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、整数规划的建模ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本章包含四部分的内容：第一部分：整数规划的建摸第二部分：整数规划的应用（0-1型整数规划）第三部分：分支定界法第四部分：指派问题1、整数规划的建摸整数规划问题的数学模型和线性规划基本相同，只是约束条件有所不同，下面我们以例题说明整数规划的建模。1、问题的提出例1某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表，问两种货物各托运多少箱可获利润最大？货物体积每箱（m

2、3)重量每箱（m3)利润每箱（百元）甲5220乙4510托运限制2413解：设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、整数规划的应用（0-

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

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

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

8、完成第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+x22+x32+x42=1 (B工作只能一人干)x

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

10、例求解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由小由小大排列大排列例：例：maxZ=3x1-2x2+5x3x1+2x2-x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6 x1,x2,x3为为0或或1解：观察得解解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件过滤条件：3x1-2x2+5x3 3 将将(x1 x2 x3)(x2 x1 x3)解解(x2 x1 x3)目标值目标值 Z0 当前最好值当前最好

12、值 (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 10/3，所以优先选择B2再进行分枝。分别加上约束条件X223/9和X223/9+1，将分枝为和两个子问题，继续求解。按照这一方法不断分枝和定界，可行域不断缩小，上界不断减少，下界逐渐增大，当上界和下界相等时，便得到最优整数解。本题有两个最优解，分别为X1=3,X2=1和X1=2,X2=2上述分枝定界法的求解过程还可用图来表示 4、指数问题在整数规划中还有一类特殊的情形就是指派问题。指派问题在现实生活中经常遇到，例如：有若干项工作需要分配给若干人来完成，由于每个人的专长不同

13、，所以完成工作所需的时间也不同，那么就产生了如何合理安排哪个人去完成哪项工作，才能使总效率最高，这是一类典型的指派问题。由此引伸到学校如何安排班级在各教室上课，以及工程选择投标者承包等。这类问题的共同要求就是在满足特定的指派要求条件下，使指派方案的总体效果最佳。4、1指派问题的标准形式及数学模型指派问题标准形式是：有n个人和n件事，已知第I个人做第j件事的费用为cij,I,j=1,2,n（cij还可表示成本、时间等含义），要求确定人与事之间的一一对应的指派方案，使完成n件事的总费用最少。为了建立上述指派问题的数学模型，引入个0-1变量：这样它的数学模型为：模型中，约束条件（3.7）表示每件事必

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

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

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

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

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

19、变换为：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。总之要把这些非标准的指派问题转化成人与事一一对应，且寻求费用极小化的标准形式来处理。