3.2整数规划的建模ppt课件

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

2、种货物各托运多少箱可获利润最大？ 货物体积每箱（m3)重量每箱（m3)利润每箱（百元）甲 5220乙4510托运限制2413解：设x1,x2分别为甲、乙两种货物的托运箱数应为大于或等于零的整数），这是一个整数规划问题，数学模型如下211020 xxMaxz取整数21212121,0,13522445xxxxxxxx从上式可见，它和线性规划问题的区别仅在于 x1,x2为整数这一条件。如果我们暂不考虑 这一条件，很容易求得相应线性规划问题的最优解为 ，但不满足整数要求，如按四舍五入取 ，又破坏了 这一条件，如舍去尾数取x1=4,x2=0 虽然满足了约束条件，但此时z=80，不是最优解，因为当时x1

3、=4,x2=1，既满足约束条件，且z=9080。由此可见整数规划问题并非通过“化整求其最优解。21,xx21,xx96, 0, 8 . 421Maxzxx96, 0, 8 . 421Maxzxx0, 521xx244521xx从以上的例题可以看出：由于相应的线性规划的可行域包含了其整数规划的可行解，就可有如下的性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值。 2、定义 规划中的变量部分或全部限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。 3、整数规划分类 如不加特殊说明，一般指整数线性规划。

4、对于整数线性规 划模型大致可分为两类： （1） 变量全限制为整数的，称纯完全整数规划。 （2变量部分限制为整数的，称混合整数规划。 4、整数规划特点 整数规划标准形式实际为整数线性规划） AX=b，X0，CTX=min，xj为整数j=1，n） (1) （1原线性规划有最优解，当自变量限制为整数后， 其整数规划解出现下述情况； 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 整数规划无可行解。 有可行解当然就存在最优解），但最优解值变差。 原线性规划为： 2x1+4x2=6，X0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=3/2，min CTX =3/2。 若

5、限制整数则得：x1=1，x2=1，min CTX =2。 5、求解方法分类： （1 割平面法主要求解纯整数线性规划 （ 2 分枝定界法可求纯或混合整数线性规划 （3 隐枚举法求解“01整数规划： 过滤隐枚举法； 分枝隐枚举法 （4 匈牙利法解决指派问题（“01规划特殊情形）。 （ 5蒙特卡洛法求解各种类型规划。2、整数规划的应用0-1型整数规划）在整数规划中有一类特殊的情形，它的变量xi仅能取0或1，这时的xi称为0-1变量，这类问题也就称为0-1型整数规划。2、1 0-1型数规划的建模0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态或者决策时是否采取某个特定方案。当问题含有多项要

6、素，而每项要素皆有两种选择时，也可用0-1变量来描述 设某问题有有限要素E1,E2, ,E n，其中每项Ej有两种选择Aj和 (j=1.2.-,n)那么：)(01PPPx即采取时不采取方案时采取方案jAjAjA)2 , 1(01njAEAExjjjjj时选择时选择2、1、2下面讨论0-1整数规划的几种应用实例。 1相互排斥的计划问题例3 某超市连锁店的布点问题。某超市连锁店在分析某城市的特征后，将该城市划分成四个区域：东片、西片、南片、北片。在四个区域中共确定了10个连锁店的备选点，记作 在连锁店选择时需考虑以下限制： 1021,sss1021,sss东片的三个点 中,至少应选择一个;西片的两

7、个点 中，应恰好选择一个；南片的四个点 中，最多只能选三个；北片只有一个备选点 ，可选可不选。321,sss54,ss9876,ssss10s如果选中 点，其投资为 元，每年的预期收益为 元。现要求总投资不超过Z元，问应选择哪些备选点，既可满足限制，又可使每年的总收益最大。试建立这个问题的0-1型整数规划数学模型。解：设 则可建立如下0-1型整数规则数学模型： jsjzjp点未被选中点被选中jjjssx,0, 1101jjjxpMaxz10,2,1,10311101987654321jxzxzssxxxxxxxjjjj或例4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费

8、用为最小。若10个井位的代号为 ，相应的钻探费用为 ，并且井位选择上要满足下列限制条件：或选择S1和S7，或选择S8；选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；在S5S8中最多选两个。建立这个问题的0-1型整数规划模型1021,SSS1021,ccc解：101jjjxcMinz井位不选井位选择jjjjjSSxxxxxxxxxxxxxx01211115876554538781101例5指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，

9、使得完成 n 项任务的总的效率最高，这就是指派问题例有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。 工 作工 人ABCD甲15182124乙19232218丙26171619丁19212317解：引入解：引入01变量变量 xij，并令，并令 xij = 1(当指派第当指派第 i人去完成第人去完成第j项工作时项工作时)或或0当不指派第当不指派第 i人去完成第人去完成第j项工作时项工作时)这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题： Minz=15x11+18x12+21x13+24x14+19

10、x21+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=

11、1 ( B工作只能一人干工作只能一人干) x13+ 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时，上面

12、两个约束条件实际上就是第一个在起作用，当y=1时第一式自然满足，起作用的仅是第二式。当采用船运方式当采用车运方式10yMyxxyMxx)1 (4537244521212、2 0-1型整数规划的解法 例 求解0-1整数规划 32173xxxMaxz10,03506202232121321321或xxxxxxxxxxx (3.5) 解：先考虑可能的解的组合，共23=8个，列于表3.3中。先分析第一个解0，0，0），经检查为可行解，而其目标函数值为0，则考察其它的解，只有其目标函数值满足 （3、6）时，才检查其是否可行，否则不予检查。我们把条件3.6称为过滤条件。再分析解0，0，1），由于其目标函数

13、值为-1，不满足过滤条件3.6），故不予检查。073321xxx分析解0，1，0），其目标函数值为7，故要检查，经检查不满足约束条件，故过滤条件不予修改。类似于上述分析，直到将所有的解均检查完毕，最后得到结论，最优解为1，1，1），最优目标函数值为9。我们将上述求解方法称为隐枚举法。(二二)、简单隐枚举法、简单隐枚举法(max)原则：原则：(1)、用试探法，求出一个可行解，以它的目、用试探法，求出一个可行解，以它的目标值作为当前最好值标值作为当前最好值Z0(2)、增加过滤条件、增加过滤条件Z Z0(3)、将、将xi 按按ci由小由小大排列大排列例：例：maxZ = 3x1 -2x2+5x3x1

14、 +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 当前最好当前最好值值 (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再进行分枝。分别加上约束条件X

15、223/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, ncij还可表示成本、时间等含义），要求确定人与事之间的一一对应的指派方案，使完成n件事的总费用最少。为了建立上述指派问题的数学模型，引入个0-1变量：这样它的数学模型为：模型中，约束条件3.7表示每件事必有且只有一个人去做，约束条件3.8表示每个人必做且只做一件事。件事个人做第若不指派第件事个人做第若指派第jijixij01 ninjijijxcMinz11njixnixnjxi

17、jnjijniij2, 1,10)8 .3(2, 11)7 .3(2, 1111或指派问题的可行解可用矩阵表示：解矩阵的每行每列元素中都有且只有一个1，以满足约束条件。指派问题有n！个可行解。下面以例题说明指派问题的建模。nnnnnnnnijxxxxxxxxxxx212222111211)(下面以例题说明指派问题的建模。例 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai对新商店Bj的建造费用的报价万元为Cij，见表所示。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？B1B2B3B4B5A14871512A2791714

18、10A3691287A46714610A56912106这是一个标准的指派问题。若设0-1变量则问题的数学模型为 )5 , 2 , 1,(01jiBABAxjijiij时不承建当时承建当55541211515161084xxxxxcMinzijijij52,1,1052,1152,115151jixixjxijjijiij或4、2指派问题的匈牙利解法 从指派问题的数学模型可以看出，指派问题是0-1整数规划的特例，也是运输问题的特例，即 ，当然更是一个整数规划问题，所以指派问题可用隐枚举法、表上作业法和分枝定界法求解。但是我们可以利用指派问题数学模型的特点，找到更加简便的方法，这就是由匈牙利数学

19、家康尼格D.knig提出的匈牙利解法。1,jibamn4、2、1匈牙利解法的思想基础 从指派问题的系数矩阵 的某行某列各元素中分别减去一个常数k，得到的新矩阵 所代表的新指派问题与原指派问题有相同最优解。nnijc)(nnijc )(例9 有一份中文说明书，要将其翻译成三种不同的文字，三位不同人翻译三种不同的文字所花的时间见表。试确定翻译的最佳指派方案。英文中文德文甲425乙463丙447解：1.先对时间矩阵的各行减去最小值。 2确定独立0元素，即在每行和每列中各圈出一个“0”。当n较小时，可用观察法、试探法找出n个独立0元素，当n较大时，可按以下步骤进行：300031302432744364

20、524（1从只有一个0素的行列开场，给这个0元素加圈，称为独立0元素，记作，这表示对这行所代表的“人只翻译该列所对应的语种，然后划去所在列或行的其他0元素，记作 ，这表明该行的“人得到任务后，该人则不能再翻译其他语种。（2再在剩下的元素中，从只有一个0元素的行列），给这个0元素加圈。重复上述过程，直到所有0元素都被圈出或划掉。如果独立元素有n个，则表明已可确定最优指派方案。此时令矩阵中和独立0元素相对应位置上的元素为1，其余元素为0，即可得最优矩阵。按此步骤，本例可得独立0元素如下： 从而得指派方案：即：甲翻译日文乙翻译德文丙翻译英文所花总时间为：2+3+4=9。001100010是不是所有的

21、问题都能像例9那样，方便地获得独立的0元素呢？现在我们再来看一则例子，以进一步说明匈牙利算法的详细解题步骤。用匈牙利算法求解上上例所对应的问题的最优解。解：已知例指派问题的系数矩阵为：610129610614767812961014179712157841先对各行元素分别减去本行的最小元素，然后对各列也如此，即此时，中各行和各列都已出现0元素，且没有负数。 CC043204050012320377108110300463040810126303710208113402确定中的独立0元素，即： 3由于本例中只有4个独立0元素，少于系数矩阵阶数n=5，表示还不能确定最优指派方案。此时，需要确定能覆盖所有0元素的最少直线数目的直线集合。可按下面步骤进行：1对没有的行打“”；（2在已打“”的行中，对0所在列打“”；（3在已打“”的列中，对所在行打“”；（4反复2和3），直到再也不能找到可以打“”的行或列为止；（5对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。本例可得下面矩阵： 4在未被直线覆盖的元素中找出一个最小元素，对未被覆盖元素所在行中各元素都减去这一最小元素，这样势