整数规划教学课件

《整数规划教学课件》由会员分享，可在线阅读，更多相关《整数规划教学课件（80页珍藏版）》请在金锄头文库上搜索。

1、第第4章章 整整 数数 规规 划划(Integer Programming)整数规划的模型整数规划的模型分支定界法分支定界法割平面法割平面法0 01 1 整数规划整数规划指派问题指派问题整数规划教学知识回顾：线性规划模型知识回顾：线性规划模型由前面学习可知，线性规划在生产实践中有重由前面学习可知，线性规划在生产实践中有重要作用，能够解决许多优化问题；要作用，能够解决许多优化问题；用单纯性算法能方便地对线性规划问题求解用单纯性算法能方便地对线性规划问题求解整数规划教学已知：已知： 两种货物装葙两种货物装葙 每种货物装葙利润每种货物装葙利润 体积限制体积限制 重量限制重量限制决策变量决策变量:两种

2、货物各多少箱两种货物各多少箱Max Z =利润最大？利润最大？货物货物 X1货物货物 X2限量限量体积体积5424重量重量2513利润利润2010但现在也有另一类现实问题：但现在也有另一类现实问题：思考：箱数？思考：箱数？整数规划教学实践中的其他问题举例实践中的其他问题举例背包问题：背包的容积一定，现有多种物品待装，背包问题：背包的容积一定，现有多种物品待装，各物品的价值、体积已知，求最优配装方案，使得各物品的价值、体积已知，求最优配装方案，使得在不超过背包的容量的前提下装入物品的价值最大。在不超过背包的容量的前提下装入物品的价值最大。选址问题：某商场在全市有数个连锁店，拟建立选址问题：某商场

3、在全市有数个连锁店，拟建立n个仓库对所有连锁店供货，有数个地点作为被选点。个仓库对所有连锁店供货，有数个地点作为被选点。问在何处建设仓库使得各仓库到所有连锁店的总距问在何处建设仓库使得各仓库到所有连锁店的总距离最小。离最小。投资决策问题：现有一定的资金，有数个可以考虑投资决策问题：现有一定的资金，有数个可以考虑的投资项目。每个项目需要的资金和利润已知。问的投资项目。每个项目需要的资金和利润已知。问如何选择投资项目，使得获得的利润最大。如何选择投资项目，使得获得的利润最大。整数规划教学分析分析以上问题的特点是：变量为整数以上问题的特点是：变量为整数背包问题：对每一件物品进行取舍，装或者不装；背包

4、问题：对每一件物品进行取舍，装或者不装；选址问题：对每一个被选点有两种选择，在这里建选址问题：对每一个被选点有两种选择，在这里建或者不在这里建；或者不在这里建；投资决策问题：对每一个考虑的项目，投资或者不投资决策问题：对每一个考虑的项目，投资或者不投资。投资。这类问题无法用线性规划求解！因为线性规划这类问题无法用线性规划求解！因为线性规划的解可能包含小数部分的解可能包含小数部分整数规划教学（一）、整数规划问题实例（一）、整数规划问题实例 例一、合理下料问题例一、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A1, A2,Am 的毛坯。在一根圆钢的毛坯。在一根圆钢上下料的方式有上下料的

5、方式有B1,B2, Bn 种，每种下料方式可以得到各种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？安排下料方式，使得即满足需要，所用的原材料又最少？零件 方 个数 式零件零 件毛坯数一、整数规划的模型一、整数规划的模型整数规划教学 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数种方式下料根数 模型：模型：例二、例二、某公司计划在某公司计划在m个地点建厂，可供选择的地点有个地点建厂，可供选择的地点有A1,A2Am ，他们的生产能力分别是他们的生产

6、能力分别是a1,a2,am（假设生（假设生产同一产品）。第产同一产品）。第i i个工厂的建设费用为个工厂的建设费用为fi (i=1.2m),又有又有n个地点个地点B1,B2, Bn 需要销售这种产品，其销量需要销售这种产品，其销量分别为分别为b1.b2bn 。从工厂运往销地的单位运费为。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？建设费用和总运输费用最省？整数规划教学单 销地厂址 价生产能力建设费用销量整数规划教学 设：设： xij 表示从工厂运往销地的运量表示从工厂运往销地的运量( (

7、i=1.2m、j=1.2n), 1 ), 1 在在Ai建厂建厂 又设又设 Yi （i=1.2m） 0 0 不在不在Ai建厂建厂 模型：模型：整数规划教学 例三、机床分配问题例三、机床分配问题 设有设有m台同类机床，要加工台同类机床，要加工n种零件。已知各种零件种零件。已知各种零件的加工时间分别为的加工时间分别为a1,a2,an ，问如何分配，使各机床，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。的总加工任务相等，或者说尽可能平衡。设：设： 1 1 分配第分配第i台机床加工第台机床加工第j j种零件；种零件； xij （i i=1.2m,=1.2m,j j=1.2n=1.2n） 0

8、0 相反。相反。于是，第于是，第i台机床加工各种零件的总时间为：台机床加工各种零件的总时间为：又由于一个零件只能在一台机床上加工，所以有又由于一个零件只能在一台机床上加工，所以有整数规划教学 因此，求因此，求xij ，使得，使得整数规划教学（二）、整数规划的数学模型（二）、整数规划的数学模型一般形式一般形式 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。整数规划。整数规划教学 纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数（这时引进

9、的松弛变量和剩余变量可以不要数（这时引进的松弛变量和剩余变量可以不要求取整数）。求取整数）。 全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时引也要求取整数（这时引进的松弛变量和剩余变量也必须是进的松弛变量和剩余变量也必须是 整数）。整数）。 混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。 01整数规划：整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数两个整数。整数规划教学（三）、

10、整数规划与线性规划的关系（三）、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。至不能保证所得倒的解是整数可行解。举例说明。举例说明。整数规划教学例：设整数规划问题如下例：设整数规划问题如下

11、首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。整数规划教学用用 解法求出最优解解法求出最优解x13/2, x2 = 10/3且有且有Z = 29/6x1x233(3/2,10/3) 现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1，3) (2，3)(1，4)(2，4)。显然，它。显然，它们都不可能是整数规划的们都不可能是整数规划的最优解。最优解。 按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规

12、划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图整数规划教学 因此，可将集合内的整数点一一找出，其最大因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。目标函数的值为最优解，此法为完全枚举法。 如上例：其中如上例：其中（2，2）（）（3，1）点为最大点为最大值，值，Z=4。 目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有： 分支定界法和割平面法；分支定界法和割平面法； 对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。整数规划教学（一

13、）、基本思路（一）、基本思路（一）、基本思路（一）、基本思路 考虑纯整数问题：考虑纯整数问题：考虑纯整数问题：考虑纯整数问题：整数问题的松弛问题：整数问题的松弛问题：整数问题的松弛问题：整数问题的松弛问题：二、分枝定界法二、分枝定界法整数规划教学 1、先不考虑整数约束，解、先不考虑整数约束，解( IP )的松弛问题的松弛问题( LP )，可能得到以下情况之一：，可能得到以下情况之一： .若若( LP )没有可行解，则没有可行解，则( IP )也没有可行解，停也没有可行解，停止计算。止计算。 .若若( LP )有最优解，并符合有最优解，并符合( IP )的整数条件，则的整数条件，则( LP )的

14、最优解即为的最优解即为( IP )的最优解，停止计算。的最优解，停止计算。 .若若( LP )有最优解，但不符合有最优解，但不符合( IP )的整数条件，的整数条件，转入下一步。为讨论方便，设转入下一步。为讨论方便，设( LP )的最优解为：的最优解为： 整数规划教学 2 2、定界：、定界：、定界：、定界： 记记记记( ( IP IP ) )的目标函数最优值为的目标函数最优值为的目标函数最优值为的目标函数最优值为Z Z* * , ,以以以以Z Z(0)(0) 作为作为作为作为Z Z* * 的上的上的上的上界，记为界，记为界，记为界，记为 Z(0) 。再用观察法找一个整数可行解。再用观察法找一个

15、整数可行解。再用观察法找一个整数可行解。再用观察法找一个整数可行解 X X ，并以其相应的目标函数值，并以其相应的目标函数值，并以其相应的目标函数值，并以其相应的目标函数值 Z Z 作为作为作为作为Z Z* * 的下界，记为的下界，记为的下界，记为的下界，记为Z Z Z Z ，也可以令，也可以令，也可以令，也可以令Z Z ，则有：，则有：，则有：，则有： Z Z* 3 3、分枝：分枝：分枝：分枝： 在在在在( ( LPLP ) )的最优解的最优解的最优解的最优解 X X(0)(0)中，任选一个不符合整数条中，任选一个不符合整数条中，任选一个不符合整数条中，任选一个不符合整数条件的变量，例如件的

16、变量，例如件的变量，例如件的变量，例如x xr r= = （不为整数），以（不为整数），以（不为整数），以（不为整数），以 表示不超表示不超表示不超表示不超过过过过 的最大整数。构造两个约束条件的最大整数。构造两个约束条件的最大整数。构造两个约束条件的最大整数。构造两个约束条件 x xr r 和和和和x xr r 1 1 1 1整数规划教学如此反复进行，直到得到如此反复进行，直到得到ZZ* 为止，即得最优解为止，即得最优解 X* 。 将这两个约束条件分别加入问题将这两个约束条件分别加入问题( IP ) ，形成两个，形成两个子问题子问题( IP1)和和( IP2 ) ，再解这两个问题的松弛问题，

17、再解这两个问题的松弛问题( LP1)和和( LP2) 。 4、修改上、下界：按照以下两点规则进行。修改上、下界：按照以下两点规则进行。 . .在各分枝问题中，找出目标函数值最大者作为在各分枝问题中，找出目标函数值最大者作为新的上界新的上界 ； . .从已符合整数条件的分枝中，找出目标函数值从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界最大者作为新的下界Z 。 5、比较与剪枝比较与剪枝 ： 各分枝的目标函数值中，若有小于各分枝的目标函数值中，若有小于Z 者，则剪掉此者，则剪掉此枝，表明此子问题已经探清，不必再分枝了枝，表明此子问题已经探清，不必再分枝了;否则继续否则继续分枝。分枝。

18、整数规划教学例例1：用分枝定界法求解整数规划问题（用图解法计算）：用分枝定界法求解整数规划问题（用图解法计算）记为（记为（IPIP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题记为（记为（LPLP）（二）、例题（二）、例题整数规划教学用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64， 取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值，取值x2 3 ，x2 4先将先

19、将（LP）划分为（）划分为（LP1）和（）和（LP2）, ,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IPIP）最小值的最小值的下限。下限。整数规划教学有如下子式有如下子式（LP1）和（）和（LP2） ：现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。整数规划教学x1x233(18/11,40/11) 先求先求（LP1）, ,如图所示。如图所示。此时在此时在B 点取得最优解。点取得最优解。x11, x2 =3, Z(1)16找到整数解，问题已探找到整数解，问题已探明，此枝停止计算。明

20、，此枝停止计算。11同理求同理求（LP2） ,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即x12, x2 =10/3, Z(2) 56/318.7 Z2 Z-19.8但但x112/5不是整数，不是整数，可继续分枝。即可继续分枝。即 3x1， x1 2。D求求（LP4），），如图所示。如图所示。无可行解，不再分枝。无可行解，不再分枝。整数规划教学 在在（LP3）的基础上继续分枝。加入条件）的基础上继续分枝。加入条件3x12有有下式：下式：只要求出（只要求出（LP5）和（）和（LP6）的最优解即可。）的最优解即可。整数规划教学x1x233(18/11,40/11)11BACD先求先

21、求（LP5）, ,如图所示。如图所示。此时在此时在E 点取得最优解。点取得最优解。即即 x12, x2 =3, Z(5)17找到整数解，问题已探明，找到整数解，问题已探明，此枝停止计算。此枝停止计算。E求求（LP6），），如图所示。如图所示。此时在此时在F点取得最优解。点取得最优解。x13, x2 =2.5, Z(6)31/215.5 Z(5) F 如对如对 Z(6) 继续分解，其最小值也不会低于继续分解，其最小值也不会低于15.5，问题探明问题探明, ,剪枝。剪枝。整数规划教学 至此，原问至此，原问题（题（IP）的最优）的最优解为：解为： x1=2， x2 =3, Z* = Z(5) 17以

22、上的求解过程以上的求解过程可以用一个树形可以用一个树形图表示如右：图表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4无可无可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13整数规划教学练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （图解法）（图解法）JIXU整数规划教学LP1x1=1, x2=7/3Z(1) 10/3LPx1

23、=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP5x1=1, x2=2Z(5) 3LP6无可无可行解行解x22x23LP3x1=33/14, x2=2Z(3) 61/14LP4无可无可行解行解x22x23LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x12x13整数规划教学LP1x1=1, x2=7/3Z(1) 10/3LPx1=2/3, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9LP3x1=33/14, x2=2Z(3) 61/14LP4无可无可行解行解LP7x

24、1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x11x12x22x23x12x13整数规划教学3200CB XB b x1x2x3x40x3921109/20x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解。获得最优解。初始表初始表最终表最终表例二、用分枝定界法求解整数规划问题（单纯形法）例二、用分枝定界法求解整数规划问题（单纯形法）整数规划教学 x1=13/4

25、 x2=5/2 Z(0) =59/414.75选选 x2 进行分枝，即增加两个约束，进行分枝，即增加两个约束，2 x2 3 有下式：有下式： 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将新，将新加约束条件加入上表计算。即加约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表得下表:整数规划教学32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/20

26、01/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝，加继续分枝，加入约束入约束 3 x1 4LP1整数规划教学32000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x

27、15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝先不考虑分枝整数规划教学接接(LP1)继续分枝，加入约束继续分枝，加入约束 4 x1 3，有下式：有下式：分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。整数规划教学CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20

28、-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP3整数规划教学CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x2201001

29、00x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP4整数规划教学树形图如下：树形图如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4,

30、x2=1Z(4) 14x22x23x13x14整数规划教学练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （单纯形法）（单纯形法）整数规划教学cj-1-5000cBxBbx1x2x3x4x50x32-111000x4 30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1 18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/110整数规划教学LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0

31、) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4无可无可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13整数规划教学应用举例：布点问题应用举例：布点问题 共同目标：满足公共要共同目标：满足公共要求，布点最少，节约投求，布点最少，节约投资费用。资费用。学校、医院、商业区、消防队学校、医院、商业区、消防队等公共设施的布点问题。等公共设施的布点问题。例：某市例：某市6 6个区，希望设个区，希望设置最少消防站以便节省置最少消防站以便节省费用。条件：费

32、用。条件：必须保证在城区任何地方必须保证在城区任何地方发生火警时，消防车能在发生火警时，消防车能在1515分钟之内赶到现场。各分钟之内赶到现场。各区之间消防车行驶的时间区之间消防车行驶的时间见右表。见右表。请确定设站方案。请确定设站方案。地地点点一一区区二二区区三三区区四四区区五五区区六六区区一一区区0二二区区100三三区区16240四四区区2832120五五区区271727150六六区区20102125140整数规划教学布点问题的数学模型：布点问题的数学模型：设设0 0 1 1为决策为决策变量，当变量，当x xi i=1=1表示表示i i地区设站地区设站，表示，表示x xi i=0=0 i

33、i地区不设站。地区不设站。这样根据消防这样根据消防车车1515分钟赶到分钟赶到现场的限制，现场的限制，可得到如下模可得到如下模型型: :整数规划教学 01 整数规划是一种特殊形式的整数规划，这时的整数规划是一种特殊形式的整数规划，这时的决策变量决策变量xi 只取两个值只取两个值0或或1，一般的解法为隐枚举法。，一般的解法为隐枚举法。例一、求解下列例一、求解下列01 规划问题规划问题四、四、0 01 1 整数规划整数规划整数规划教学 解：对于解：对于01 规划问题，由于每个变量只取规划问题，由于每个变量只取0，1两个两个值，一般会用穷举法来解，即将所有的值，一般会用穷举法来解，即将所有的0，1

34、组合找出，组合找出，使目标函数达到极值要求就可求得最优解。但此法太使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。通过加入一定的条件，就能较快的求得最优解。x1 . x2. x3约束条件约束条件满足条件满足条件Z 值值 (1) (2) (3) (4)是是 否否( 0. 0. 0 ) 0 0 0 00( 0. 0. 1 ) 1 1 0 15( 0. 1. 0 ) 2 4 1 42( 1. 0. 0 ) 1 1 1 03( 0. 1. 1 ) 1 5( 1. 0. 1

35、 ) 0 2 1 18( 1. 1. 0 ) 3( 1. 1. 1 ) 2 6整数规划教学 由上表可知，问题的最优解为由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 )由上表可知：由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快是一个可行解，为尽快找到最优解，可将找到最优解，可将3 x12 x25 x3 5 作为一个约束，作为一个约束，凡是目标函数值小于凡是目标函数值小于5 的组合不必讨论，如下表。的组合不必讨论，如下表。x1 . x2. x3约束条件约束条件满足条件满足条件Z 值值(0) (1) (2) (3) (4)是是 否否( 0. 0. 0 )

36、0 0 0 0 00( 0. 0. 1 ) 5 1 1 0 15( 0. 1. 0 )-2( 0. 1. 1 ) 3( 1. 0. 0 ) 3( 1. 0. 1 ) 8 0 2 1 18( 1. 1. 0 ) 1( 1. 1. 1 ) 4整数规划教学 例二、求解下列例二、求解下列01 规划问题规划问题 解：由于目标函数中变量解：由于目标函数中变量x1, x2 , x4 的系数均为负数，的系数均为负数，可作如下变换：可作如下变换： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4带带入原题中，但需重新调整变量编号。令入原题中，但需重新调整变量编号。令 x3 =

37、x1, x4 = x2得到下式。得到下式。整数规划教学 可以从可以从( 1.1.1.1 )开始试算，开始试算， x(3)( 1.1.0.1 )最优解。最优解。 x(3)( 1.0.1.0 )是原问题的最优解，是原问题的最优解，Z* =2整数规划教学例三、求解下列例三、求解下列01 规划问题规划问题令令 y1=x5, y2=x4, y3=x2, y4=x3, y5=x1 得到下式得到下式整数规划教学y1 . y2. y3 . y4. y5约束条件约束条件满足条件满足条件Z 值值 (1) (2)是是 否否( 0. 0. 0. 0. 0 ) 0 0( 1. 0. 0. 0. 0 ) 1 -1( 0.

38、 1. 0. 0. 0 ) -1 1 ( 0. 0. 1. 0. 0 ) -2 1( 0. 0. 0. 1. 0 ) 4 -48( 0. 0. 0. 0. 1 ) 3 -2 所以，所以， Y*= （0.0.0.1.0），原问题的最优解为：），原问题的最优解为： X* （0.0.1.0.0），），Z* =8整数规划教学（0 . 1 . 1 . 0 . 0）练习：用隐枚举法求解练习：用隐枚举法求解0101规划问题规划问题整数规划教学 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任务，项不同的任务，需要需要n 个人分别完成其中的一项，但由于任务的性质和个人分别完成其中

39、的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成问题，应指派哪个人去完成哪项任务，使完成 n 项任项任务的总效率最高（或所需时间最少），这类问题称为务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题或分派问题。 （一）、指派问题的数学模型（一）、指派问题的数学模型 设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件件工作，规定每个人只做一件工作，每件工作只

40、有一个人去做。已知第工作，每件工作只有一个人去做。已知第I 个人去做第个人去做第j 件工作的的效率（件工作的的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应如何分配。问应如何分配才能使总效率（才能使总效率（ 时间或费用）最高？时间或费用）最高？五、指派问题五、指派问题整数规划教学设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相反 ( I,j=1.2. n )其数学模型为：其数学模型为：整数规划教学 （二）、解题步骤：（二）、解题步骤： 指派问题是指派问题是0-1 规划的特例，也是运输问题

41、的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即匈牙利法，即系数矩阵中独立系数矩阵中独立 0 0 元素的最多个数等于元素的最多个数等于能覆盖所有能覆盖所有 0 0 元素的最少直线数。元素的最少直线数。 第第一一步步：变变换换指指派派问问题题的的系系数数矩矩阵阵（cij）为为(bij)，使使在在(bij)的各行各列中都出

42、现的各行各列中都出现0元素，即元素，即 (1) 从（从（cij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素； (2) 再再从从所所得得新新系系数数矩矩阵阵的的每每列列元元素素中中减减去去该该列列的的最最小元素。小元素。整数规划教学 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这这就就得得到到最最优优解解。找找独独立立0元元素素，常常用的步骤

43、为：用的步骤为： (1)从从只只有有一一个个0元元素素的的行行(列列)开开始始，给给这这个个0元元素素加加圈圈，记记作作 。然然后后划划去去 所所在在列列(行行)的的其其它它0元元素素，记记作作 ；这这表表示示这这列列所所代代表表的的任任务务已已指指派派完完，不不必必再再考考虑虑别人了。别人了。 (2)给给只只有有一一个个0元元素素的的列列(行行)中中的的0元元素素加加圈圈，记记作作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 (3)反反复复进进行行(1)，(2)两两步步，直直到到尽尽可可能能多多的的0元元素素都被圈出和划掉为止。都被圈出和划掉为止。整数规划教学 (4)若若仍仍

44、有有没没有有划划圈圈的的0元元素素，且且同同行行(列列)的的0元元素素至至少少有有两两个个，则则从从剩剩有有0元元素素最最少少的的行行(列列)开开始始，比比较较这这行行各各0元元素素所所在在列列中中0元元素素的的数数目目，选选择择0元元素素少少的的那那列列的的这这个个0元元素素加加圈圈(表表示示选选择择性性多多的的要要“礼礼让让”选选择择性性少少的的)。然然后后划划掉掉同同行行同同列列的的其其它它0元元素素。可可反反复复进进行行，直到所有直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。 （5）若）若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指，那么这指派问题的最

45、优解已得到。若派问题的最优解已得到。若m n, 则转入下一步。则转入下一步。 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素。元素。 (1)对没有对没有的行打的行打号；号； (2)对已打对已打号的行中所有含号的行中所有含 元素的列打元素的列打号；号； (3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； 整数规划教学 (4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； (5)对对没没有有打打号号的的行行画画横横线线，有有打打号号的的列列画画纵纵线线，这这就就得得到到覆覆盖盖所所有有0元元素素的的最最少少直直线线数数

46、l 。l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第二二步步(4)，另另行行试试指指派派；若若 lm n，须须再再变变换换当当前前的的系系数数矩矩阵阵，以找到以找到n个独立的个独立的0元素，为此转第四步。元素，为此转第四步。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素。元素。在没有被直线覆盖的所有元素中找出最小元素，然后在没有被直线覆盖的所有元素中找出最小元素，然后打打各行都减去这最小元素；打各行都减去这最小元素；打各列都加上这最小元各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵素（以保证系数矩阵中不出现负元素）。新系

47、数矩阵的最优解和原问题仍相同。转回第二步。的最优解和原问题仍相同。转回第二步。 整数规划教学例一：例一： 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119整数规划教学2497整数规划教学42整数规划教学 整数规划教学 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A、B、C、D。现有甲、乙、丙、丁四。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？间如下表所示，问如何分派任务，可

48、使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982例二、例二、整数规划教学求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二步，试指派：第二步，试指派： 找到找到 3 3 个独立零元素个独立零元素 但但 m m = 3 3 n = 4整数规划教学 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素： 独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4； 第四步，变换矩阵第四步，变换矩阵( (bij) )以增加以增加0 0元素：没有被直线覆元素：没有被直线覆盖的所有元素

49、中的最小元素为盖的所有元素中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打；打各列都加上各列都加上1 1，得如下矩阵，并转第二步进行，得如下矩阵，并转第二步进行试指派：试指派： 整数规划教学000 0 00得到得到4 4个独个独立零元素，立零元素， 所以最优解所以最优解矩阵为：矩阵为： 15 整数规划教学练习：练习：115764戊戊69637丁丁86458丙丙9117129乙乙118957甲甲EDCBA费费 工作工作 用用人员人员整数规划教学-1 -2整数规划教学 整数规划教学 l =m=4 n=5整数规划教学 整数规划教学 整数规划教学 l =m=4 n=5整数规划教学 整数规划教学 此问题有多个最优解此问题有多个最优解28整数规划教学 整数规划教学 整数规划教学用匈牙利法求解下列指派问题，已知效率矩用匈牙利法求解下列指派问题，已知效率矩阵分别如下：阵分别如下： 整数规划教学