最优化方法第二章整数规划

1、1第四讲第四讲 整数规划整数规划(IP)(IP)l整数规划的模型整数规划的模型l分枝定界法分枝定界法l割平面法割平面法l0 01 1整数规划整数规划l指派问题指派问题21、整数规划、整数规划(Integer Programming)问题实例问题实例 合理下料问题合理下料问题4.1 整数规划的模型整数规划的模型建厂问题建厂问题机床分配问题机床分配问题 3 例例1、合理下料问题、合理下料问题 设用某型号的圆钢下零件设用某型号的圆钢下零件A1, A2,Am 的毛坯。在一根圆的毛坯。在一根圆钢上下料的方式有钢上下料的方式有B1,B2, Bn 种，每种下料方式可以得到各种，每种下料方式可以得到各种零件的

2、毛坯数以及每种零件的需要量，如表所示。问怎样种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？安排下料方式，使得即满足需要，所用的原材料又最少？零件 方 个数 式零件零 件毛坯数nBB 1mAA 1mbb 1mnmnaaaa 1111 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数种方式下料根数. . 模型：模型： 且且为为整整数数n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZ4例例2、（建厂问题）（建厂问题）某公司计划在某公司计划在m个地点建厂，可供选择的个地点建厂，可供选择的地点有地点有

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

4、AfacccABnBB 21212222221211112111215 设：设： xij 表示从工厂运往销地的运量表示从工厂运往销地的运量( (i=1.2m、j=1.2n), ), 1 1 在在Ai 建厂建厂 又设又设 Yi （i=1.2m） 0 0 不在不在Ai 建厂建厂 模型：模型： n)1.2jm1.2(i 1 0, 0n)1.2(j )2 . 1( min111、或或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ6 例例3、机床分配问题、机床分配问题 设有设有m台同类机床，要加工台同类机床，要加工n种零件。已知各种零件的种零件。已知各种零件的加工时间分别为加工

5、时间分别为a1,a2,an ，问如何分配，使各机床的总加，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。工任务相等，或者说尽可能平衡。设：设： 1 1 分配第分配第i台机床加工第台机床加工第j j种零件；种零件； xij （i i=1.2=1.2m,m,j j=1.2=1.2n n） 0 0 相反。相反。于是，第于是，第i台机床加工各种零件的总时间为：台机床加工各种零件的总时间为：njijjmixa1)2 . 1( 又由于一个零件只能在一台机床上加工，所以有又由于一个零件只能在一台机床上加工，所以有miijmix1)2 . 1( 17 因此，求因此，求xij ，使得，使得n)1.2j

6、m,1.2(i 1 0n)1.2(j 1),max(min111121或或ijmiijnjnjnjmjjjjjjxxxaxanxaZ82、整数规划的数学模型、整数规划的数学模型一般形式一般形式 且且部部分分或或全全部部为为整整数数或或 n)1.2(j 0)2 . 1( )max(min11jnjijijnjjjxmibxaxcZZ 依照决策变量取整要求的不同，整数规划可分为依照决策变量取整要求的不同，整数规划可分为纯整数规纯整数规划、全整数规划、混合整数规划、划、全整数规划、混合整数规划、0 01 1整数规划整数规划。9 纯整数规划纯整数规划：所有决策变量要求取非负整数（这时引所有决策变量要求

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

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

9、,13651914max21212121xxxxxxxxz 首先不考虑整数约束，得到线性规划问题（一般称为首先不考虑整数约束，得到线性规划问题（一般称为松弛问松弛问题题或或伴随问题伴随问题）。）。 0,13651914max21212121xxxxxxxxz12用用图解法图解法求出最优解求出最优解x13/2, x2 = 10/3且有且有 = 29/6x1x233(3/2,10/3) 现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得到可得到4个点即个点即(1，3) (2，3) (1，4) (2，4)。显然，它们都不可能。显然，它们都不可能是整数规划的最优解。是整数

10、规划的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题的可按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。如图所示。z13 因此，可将集合内因此，可将集合内的整数点一一找出，的整数点一一找出，其最大目标函数的值其最大目标函数的值为最优解，此法为完为最优解，此法为完全枚举法。全枚举法。 如上例：其中如上例：其中（2，2）（）（3，1）点为最大点为最大值，值， =4。 目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有： 分枝定界法和割平面法；分枝定界

11、法和割平面法； 对于特别的对于特别的0 01 1规划问题采用规划问题采用隐枚举法隐枚举法和和匈牙利法匈牙利法。x1x233(3/2,10/3)z141、基本思路、基本思路 且为整数且为整数)2 . 1( , 0)2 . 1( )IP(min11mjxmibxaxczjnjijijnjjj考虑纯整数问题：考虑纯整数问题： ),2 . 1( , 0),2 . 1( )LP(min11mjxmibxaxczjnjijijnjjj整数问题的伴随整数问题的伴随(松弛松弛)问题：问题：4.2 分枝定界法分枝定界法15 （1）先不考虑整数约束，解）先不考虑整数约束，解( IP )的松弛问题的松弛问题( LP

12、 )，可，可能得到以下情况之一：能得到以下情况之一： 若若( LP )没有可行解没有可行解，则，则( IP )也没有可行解，停止计算。也没有可行解，停止计算。 若若( LP )有最优解有最优解，并，并符合符合( IP )的整数条件的整数条件，则，则( LP )的的最优解即为最优解即为( IP )的最优解，停止计算。的最优解，停止计算。 若若( LP )有最优解，但有最优解，但不符合不符合( IP )的整数条件的整数条件，转入下，转入下一步。一步。 为讨论方便，设为讨论方便，设( LP )的最优解为：的最优解为： 不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为), 2 , 1(.)

13、0 , 0 ,( )0(21)0(mibzbbbbXiTmr 16记记( IP )的目标函数最优值为的目标函数最优值为 ,以以 作为作为 的下界，记的下界，记为为 。令。令 ，则有，则有 （2）定界：）定界： 在在( LP )的最优解的最优解 X(0)中，任选一个不符合整数条件的变量，中，任选一个不符合整数条件的变量，例如例如xr= br （不为整数），以（不为整数），以br表示不超过表示不超过br的最大整数。的最大整数。构造两个约束条件构造两个约束条件 xr br 和和 xr br1 将这两个约束条件分别加入问题将这两个约束条件分别加入问题( IP ) ，形成两个子问题，形成两个子问题( I

14、P1)和和( IP2 ) ，再，再解这两个子问题的松弛问题解这两个子问题的松弛问题( LP1)和和( LP2) 。 （3）分枝：分枝：zzz *)0(zz *z)0(z z*z17如此反复进行，直到得到如此反复进行，直到得到 为止，为止，即得最优解即得最优解 X* 。 （4）修改上、下界修改上、下界：按照以下两点规则进行。按照以下两点规则进行。 在各分枝问题中，找出目标函数值最小者作为在各分枝问题中，找出目标函数值最小者作为新的下新的下界界； 从已符合整数条件的分枝中，找出目标函数值最小者从已符合整数条件的分枝中，找出目标函数值最小者作为作为新的上界新的上界。 （5）比较与剪枝比较与剪枝 ：

15、各分枝的目标函数值中，若有大于各分枝的目标函数值中，若有大于 者，则剪掉此枝，表者，则剪掉此枝，表明此子问题已经探清，不必再分枝了明此子问题已经探清，不必再分枝了;否则继续分枝。否则继续分枝。 （1 1）先不考虑整数约束，解）先不考虑整数约束，解( (IP) )的松弛问题的松弛问题( (LP) )：（2 2）定界：）定界：（3 3）分枝：）分枝：zzz *z18例例1：用分枝定界法求解整数规划问题（用图解法计算）：用分枝定界法求解整数规划问题（用图解法计算）且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（IP）解解：首先去掉整数约束，变成一般

16、线性规划问题：首先去掉整数约束，变成一般线性规划问题0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（LP）2、例题、例题19用图解法求用图解法求（LPLP）的最优解，的最优解，如图所示。如图所示。x1x233(18/11,40/11)对于对于x118/111.64， 取值取值x1 1， x1 2（对于（对于x2 =40/11 3.64，取值取值x2 3 ，x2 4）先先取取x1 1, x1 2，将将（LPLP）划分为（）划分为（LPLP1）和（）和（LPLP2）, , x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z(0) 也是（

17、也是（IP）最小值的）最小值的下限。下限。20有下式：有下式：且且为为整整数数0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且且为为整整数数0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。21同理求同理求（LP2） ,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即 原问题有比原问题有比16更小的最优解，更小的最优解，但但 x2 不是整数，故利用不是整数，故利用 3 10/34 加入条件。加入条件。（问题：假如问题：假如

18、 ，会得出什么结论？，会得出什么结论？）x1x233 先求先求（LP1）, ,如图所示。如图所示。此时此时B 在点取得最优解。在点取得最优解。找到整数解，问题已探明，找到整数解，问题已探明，此枝停止计算。此枝停止计算。11BAC16, 3, 1)1(21 zxx7 .183/56, 3/10, 2)2(21 zxx16)1()2( zz16)1()2( zz22加入条件：加入条件： x23, x24 有下式：有下式： 且且为为整整数数0,3 2 4 30 652 )3IP(5min21211212121xxxxxxxxxxxZ 且且为为整整数数0,4 2 4 30 652 )4IP(5min2

19、1211212121xxxxxxxxxxxZ只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。23x1x23311BAC先求先求（LP3）, ,如图所示。如图所示。此时此时D 在点取得最优解。在点取得最优解。即即 D求求（LP4），），如图所示。如图所示。无可行解，不再分枝。无可行解，不再分枝。8 .194 .175/87, 3, 4 . 25/12)0()3(21 zzxx但但 不是整数，不是整数，可继续分枝。可继续分枝。即即5/121 x2,311 xx24 在在（LP3）的基础上继续分枝。加入条件）的基础上继续分枝。加入条件 ： 且且为为整整数数0,2 3 2

20、4 30 652 )5IP(5min211211212121xxxxxxxxxxxxZ 且且为为整整数数0,3 3 2 4 30 652 )6IP(5min211211212121xxxxxxxxxxxxZ只要求出（只要求出（LP5）和（）和（LP6）的最优解即可。）的最优解即可。2,311 xx25x1x23311BACD先求先求（LP5）, ,如图所示。如图所示。此时在此时在E 点取得最优解。点取得最优解。即即 x12, x2 =3, Z(5)17找到整数解，问题已探明，找到整数解，问题已探明，此枝停止计算。此枝停止计算。E求求（LP6），），如图所示。如图所示。此时此时 F在点取得最优解

21、。在点取得最优解。x13, x2 =2.5, Z(6)31/215.5 Z(5) F如对如对 Z(6) 继续分解，其最小值也不会低于继续分解，其最小值也不会低于15.5 ，问题，问题探明探明, ,剪枝。剪枝。26至此，原问题至此，原问题（IP）的最优解）的最优解为：为： x1=2， x2 =3, Z* = Z(5) 17以上的求解过程以上的求解过程可以用一个树形可以用一个树形图表示如右：图表示如右：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.4

22、LP4无可无可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13 27 且且为为整整数数0,143292)IP(23max21212121xxxxxxxxz3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4 -1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解获得最优解。初始表初始表最终表

23、最终表例例2、用分枝定界法求解整数规划问题（单纯形法）用分枝定界法求解整数规划问题（单纯形法）28选选 进行分枝，即增加两个约束，进行分枝，即增加两个约束， 有下式：有下式： 且且为为整整数数0,2 14329 2)1IP(23max212212121xxxxxxxxxZ 且且为为整整数数0,3 14329 2)2IP(23max212212121xxxxxxxxxZ 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将新加约束条件，将新加约束条件加入上表计算。即加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表得下表:75.144/59, 2/5,

24、 4/13)0(21 zxx2x2,322 xx2932000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝，加继续分枝，加入约束入约束 3 x1 4LP13032000CB

25、 XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2先不考虑分枝先不考虑分枝 )1()2()2(215 .132/273, 2/5zzzxx31接接(LP1)继续分枝，加入约束继续分枝，加入约束 ，有下式：有下式： 且且为为整整数数0,3

26、 2 14329 2)3IP(23max2112212121xxxxxxxxxxZ 且且为为整整数数0,4 2 14329 2)4IP(23max2112212121xxxxxxxxxxZ分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。3411 xx 和和32CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-2

27、9/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP333CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1

28、/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP434树形图如下：树形图如下：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, x2=1Z(4) 14x22x23x13x14 练习练习351.原理：原有最优解要被割去正正好好是

29、是整整数数最最优优解解。剩剩余余部部分分有有一一个个极极点点割割去去部部分分不不含含整整数数解解可可行行域域中中割割去去一一部部分分,x1x24.3 割平面法割平面法362、计算步骤：（1）用单纯形法求解）用单纯形法求解( IP )对应的松弛问题对应的松弛问题( LP )： 若若( LP )没有可行解，则没有可行解，则( IP )也没有可行解，停止计算。也没有可行解，停止计算。 若若( LP )有最优解，并符合有最优解，并符合( IP )的整数条件，则的整数条件，则( LP )的的最优解即为最优解即为( IP )的最优解，停止计算。的最优解，停止计算。 若若( LP )有最优解，但不符合有最优

30、解，但不符合( IP )的整数条件，转入下的整数条件，转入下一步。一步。 4.3 割平面法割平面法37 （2 2）从）从( (LP) )的最优解中，任选一个不为整数的分量的最优解中，任选一个不为整数的分量xr, , ,将最优单纯形表中该行的系数将最优单纯形表中该行的系数 和和 分解为整数部分和分解为整数部分和小数部分之和，并以该行为小数部分之和，并以该行为源行源行，按下式作割平面方程：，按下式作割平面方程：rjarb 1rnmjjrjfxf （3 3）将所得的割平面方程作为一个新的约束条件置于最优单）将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯

31、形法求出纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回新的最优解，返回1 1。的小数部分的小数部分 的小数部分的小数部分rja rb38例例1：用割平面法求解整数规划问题：用割平面法求解整数规划问题 且为整数且为整数0,023623 max2121212xxxxxxxZ解：解：增加松弛变量增加松弛变量x3和和x4 ，得到，得到(LP)的初始单纯形表和最的初始单纯形表和最优单纯形表优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4

32、Z-3/2 00 -1/4 -1/4 此题的最优解为：此题的最优解为：X= (1 , 3/2) Z = 3/2 但不是整数最但不是整数最优解，引入割平面。以优解，引入割平面。以x2 为源行生成割平面。为源行生成割平面。39 此题的最优解为：此题的最优解为：X= (1 , 3/2) Z = 3/2 但不是整数最但不是整数最优解，引入割平面。以优解，引入割平面。以x2 为源行生成割平面，由于为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 生成割平面的条件为生成割平面的条件为: 21414143 xxCj0100CBXBbx1x2x3x40 x11101/6-1/61x23/20

33、11/41/4Z-3/2 00 -1/4 -1/440将将 x3=6-3x1-2x2 , x4=3x1-2x2 , 代入代入 中，得中，得到等价的割平面条件：到等价的割平面条件：x2 1 ； 见下图。见下图。21414143 xxx1x233第一个割平面第一个割平面Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z0010041Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加

34、入松弛变量，然后加到表中：134111442xxs CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-142 此时，此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源行为源行生成割平面，其条件为：生成割平面，其条件为：32323214 sx 用上表的约束解出用上表的约束解出x4 和和s1 ，将它们带入上式得到等价的割平，将它们带入上式得到等价的割平面条件：面条件：x1 x2 ，见图：，见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面43将生成的割平面条件加入松弛变量，然

35、后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：241222333xss CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/244CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解

36、为至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这也是原这也是原问题的最优解。问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过程中始有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为终保持对偶可行性，因此，这个算法也称为分数对偶割平面算分数对偶割平面算法法。45例例2：用割平面法求解数规划问题：用割平面法求解数规划问题 且且为为整整数数0, 205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105

37、/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表46在松弛问题最优解中，在松弛问题最优解中，x1, x2 均为非整数解，由上表有：均为非整数解，由上表有：383132356165432431 xxxxxx将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 32231)311(321)651(65432431 xxxxxx47 以上式子只须考虑一个即可，以上式子只须考虑一个即可，解题经验表明，考虑式子解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束右端最大真分数的式子，往往会较快地找到所需割平面约束

38、条件。条件。以上两个式子右端真分数相等，可任选一个考虑。现以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：选第二个式子，并将真分数移到右边得： )(313224332xxxx 32)(3143 xx引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续后得到下式，将此约束条件加到上表中，继续求解。求解。 323131143 sxx48Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x

39、10100101x24010120 x3200113Z400001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 49 01 整数规划是一种特殊形式的整数规划，这时的决策变量整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值只取两个值0或或1，一般的解法为，一般的解法为隐枚举法隐枚举法。例例1、求解下列、求解下列01 规划问题规划问题 10,(4) 64 (3) 3 (2) 44(1) 22523max321322

40、1321321321或或xxxxxxxxxxxxxxxxZ4.4 04.4 01 1 整数规划整数规划50 解：解：对于对于01 规划问题，由于每个变量只取规划问题，由于每个变量只取0，1两个值，两个值，一般会用穷举法来解，即将所有的一般会用穷举法来解，即将所有的0，1 组合找出，使目标组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过量相当大。而隐枚举法就是在此基础上，通过加入一定的加入一定的条件条件，就能较快的求得最优解。，就能较快的求得最优解。x1 . x2. x3约束条件约束条件满

41、足条件满足条件Z 值值 (1) (2) (3) (4)是是 否否( 0. 0. 0 )( 0. 0. 1 )( 0. 1. 0 )( 1. 0. 0 )( 0. 1. 1 )( 1. 0. 1 )( 1. 1. 0 )( 1. 1. 1 )51x1 . 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 ) 0 2 1 18( 1. 1. 0 )

42、 3( 1. 1. 1 ) 2 6 10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或或xxxxxxxxxxxxxxxxZ52x1 . 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 ) 0 2 1 18( 1. 1. 0 ) 3( 1. 1. 1 ) 2 6 由下表可知，问题的最优解为由下

43、表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 )由下表可知：由下表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最是一个可行解，为尽快找到最优解，可将优解，可将3 x12 x25 x3 5 作为一个约束（也称为作为一个约束（也称为过滤条过滤条件件），凡是目标函数值小于），凡是目标函数值小于5 的组合不必讨论，如下表。的组合不必讨论，如下表。53x1 . x2. x3约束条件约束条件满足条件满足条件Z 值值(0) (1) (2) (3) (4)是是 否否( 0. 0. 0 ) 0( 0. 0. 1 ) 5 1 1 0 15( 0. 1. 0 )-2( 0.

44、1. 1 ) 3( 1. 0. 0 ) 3( 1. 0. 1 ) 8 0 2 1 18( 1. 1. 0 ) 1( 1. 1. 1 ) 4 由下表可知，问题的最优解为由下表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 )由下表可知：由下表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最是一个可行解，为尽快找到最优解，可将优解，可将3 x12 x25 x3 5 作为一个约束（也称为作为一个约束（也称为过滤条过滤条件件），凡是目标函数值小于），凡是目标函数值小于5 的组合不必讨论，如下表。的组合不必讨论，如下表。54 例例2、求解下列、求解下列01 规划问题规划

45、问题4 . 3 . 2 . 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解解：由于目标函数中变量：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作的系数均为负数，可作如下变换：如下变换： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4带入原题中，带入原题中，但需重新调整变量编号。令但需重新调整变量编号。令 x3 = x1, x4 = x2得到下式。得到下式。55 1 0,435 2 461 2 1173max4321432432143214321或或xxxxxxxxxxxx

46、xxxxxxxZ 可以从可以从( 1.1.1.1 )开始试算，开始试算， x(3)( 1.1.0.1 )最优解。最优解。 x(3)( 1.0.1.0 )是原问题的最优解，是原问题的最优解，Z* =2 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4带入原题中，带入原题中，但需重新调整变量编号。令但需重新调整变量编号。令 x3 = x1, x4 = x2得到下式。得到下式。练习练习56bintprog函数0-1整数规划 f = -9; -5; -6; -4; A = 6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1; b = 9; 1;

47、0; 0; x, z = bintprog(f,A,b) 57 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任务，需项不同的任务，需要要n 个人分别完成其中的一项，但由于任务的性质和各人的专个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最项任务的总效率最高（或所需时间最少），这类

48、问题称为少），这类问题称为指派问题指派问题或或分派问题分派问题。 1、指派问题的数学模型、指派问题的数学模型 设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i 个人去做第个人去做第j 件工作的的效件工作的的效率（率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应。问应如何分配才能使总效率（如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？4.5 指派问题指派问题58设决策变量设决策变量 1 分配第分配第i 个人去做第个人

49、去做第j 件工作件工作 xij = 0 相反相反 ( i, j=1.2. n )其数学模型为：其数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或59 2、解题步骤：、解题步骤： 指派问题是指派问题是0-1 规划的特例，当然可用整数规划，规划的特例，当然可用整数规划，0-1 规划规划的解法去求解，但运算繁琐。利用指派问题的特点可有更简便的解法去求解，但运算繁琐。利用指派问题的特点可有更简便的解法，这就是的解法，这就是匈牙利法匈牙利法( (匈牙利数学家匈牙利数学家D.KonigD.Konig提出提出)

50、，即，即系数系数矩阵中独立矩阵中独立 0 0 元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有 0 0 元素的最少元素的最少直线数直线数 P73P73定理定理2 2 。 第一步：变换指派问题的系数第一步：变换指派问题的系数(也称效率也称效率)矩阵（矩阵（cij）为）为(bij)，使，使在在(bij)的各行各列中都出现的各行各列中都出现0元素，元素，即即 (1) 从（从（cij）的）的每行元素都减去该行的最小元素每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的再从所得新系数矩阵的每列元素中减去该列的最小元素每列元素中减去该列的最小元素。P70 P70 定理定理1 160 第二

51、步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的中找尽可能多的独立独立0元素元素，若能找出，若能找出n个独立个独立0元元素，就以这素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余，其余为为0，这就得到最优解。，这就得到最优解。找独立找独立0元素，元素，常用的步骤为常用的步骤为： (1)从从只有一个只有一个0元素的元素的行行(列列)开始，给这个开始，给这个0元素加圈，元素加圈，记作记作 。然后划去。然后划去 所在所在列列(行行)的其它的其它0元素，记作元素，记作 ；这；这表示这列所代表的任务已指派完，不必再

52、考虑别人了。表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个给只有一个0元素的元素的列列(行行)中的中的0元素加圈，记作元素加圈，记作；然后划去然后划去 所在行的所在行的0元素，记作元素，记作 (3)反复进行反复进行(1)，(2)两步，直到尽可能多的两步，直到尽可能多的0元素都被圈元素都被圈出和划掉为止。出和划掉为止。61 (4)若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两元素至少有两个，则从剩有个，则从剩有0元素最少的元素最少的行行(列列)开始，比较这行各开始，比较这行各0元素所元素所在列中在列中0元素的数目，选择元素的数目，选择0元

53、素少的那列的这个元素少的那列的这个0元素加圈元素加圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同。然后划掉同行同列的其它列的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划元素都已圈出和划掉为止。掉为止。 （5）若）若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指派问，那么这指派问题的最优解已得到。若题的最优解已得到。若m n, 则转入下一步。则转入下一步。 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素元素。 (1)对没有对没有的行打的行打号；号； (2)对已打对已打号的行中所有含号的行中

54、所有含元素的元素的列列打打号；号； (3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； 62 (4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； (5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得号的列画纵线，这就得到覆盖所有到覆盖所有0元素的最少直线数元素的最少直线数 l 。l 应等于应等于m，若不相等，若不相等，说明试指派过程有误，回到第二步说明试指派过程有误，回到第二步(4)，另行试指派；若，另行试指派；若 lm n，须再变换当前的系数矩阵，以找到，须再变换当前的系数矩阵，以找到n个独立的个独立的

55、0元素，为元素，为此转第四步。此转第四步。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素元素。在没有被直线覆盖的所有元素中找出最小元素，然后打在没有被直线覆盖的所有元素中找出最小元素，然后打各各行都减去这最小元素；打行都减去这最小元素；打各列都加上这最小元素（以保证各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。仍相同。转回第二步。 63例例1： 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁7811964 911871316149151441

56、0413152 24104750111006211130-2-4-9-7 第一步：变换指派问题的系数矩阵（第一步：变换指派问题的系数矩阵（cij）为）为(bij)，使在，使在(bij)的各行各列中都出现的各行各列中都出现0元素，元素，即即 (1) 从（从（cij）的）的每行元素都减去该行的最小元素每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的再从所得新系数矩阵的每列元素中减去该列的最小元每列元素中减去该列的最小元素素。-4-2 0010235096060713065 00102350960607130 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(b

57、ij)中找尽可能多的中找尽可能多的独立独立0元素元素，若能找出，若能找出n个独立个独立0元素，就以这元素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余为，其余为0，这就得到最优解。，这就得到最优解。找独立找独立0元素，元素，常用的步骤为常用的步骤为： (1)从从只有一个只有一个0元素的元素的行行(列列)开始，给这个开始，给这个0元素加圈，记作元素加圈，记作 。然后划去。然后划去 所在所在列列(行行)的其它的其它0元素，记作元素，记作 ；这表示这列所代表的任务已指派完，不必再；这表示这列所代表的任务已指派完，不必再考虑别人了。考虑别人了。 (2)给只有

58、一个给只有一个0元素的元素的列列(行行)中的中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 (3)反复进行反复进行(1)，(2)两步，直到尽可能多的两步，直到尽可能多的0元素都被圈出和划掉为止。元素都被圈出和划掉为止。 911871316149151441041315266 00102350960607130 0100000100101000 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的中找尽可能多的独立独立0元素元素，若能找出，若能找出n个独立个独立0元素，就以这元素，就以这n个独立个独立0

59、元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余为，其余为0，这就得到最优解。，这就得到最优解。找独立找独立0元素，元素，常用的步骤为常用的步骤为：（5）若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指派问题的最优解已得到。，那么这指派问题的最优解已得到。 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指派问题的最优解，那么这指派问题的最优解: 4+4+9+11. 911871316149151441041315267例例2、 有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作分别记作

60、A、B、C、D。现有甲、乙、丙、丁四人，他们将。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，中文说明书译成不同语种的说明书所需时间如下表所示，问问如何分派任务，可使总时间最少？如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁598268求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，试指派：第二步，试指派：找到找到 3 3