整数规划的建模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=4

3、,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个钻井探油，使总的钻探费用为最小。假设10个井位

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

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

10、2+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任务只

11、能一人干任务只能一人干) 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，由于其目的函数值为-1，不满足过滤

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

14、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再进展分枝。分别加上约束条件X223/9和X223/

15、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 ninjijijxcMinz11njixnixnjxijnjijniij2

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

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

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

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

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