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

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

2、料方式可以得到各 种零件的毛坯数以及每种零件的需要量，如表所示。问怎样种零件的毛坯数以及每种零件的需要量，如表所示。问怎样 安排下料方式，使得即满足需要，所用的原材料又最少？安排下料方式，使得即满足需要，所用的原材料又最少？ 零件 方 个数 式 零件 零 件 毛坯数 n BB 1 m A A 1 m b b 1 mnm n aa aa 1 111 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数种方式下料根数. . 模型：模型： 且且为为整整数数n)1.2(j 0 )2 . 1( min 1 1 j n j ijij n j j x mibxa xZ 4 例例2、（建厂问题）（

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

4、费 用最省？用最省？ 销量 建设 费用 生产 能力 单 销地 厂址 价 n mmmnmmm n n bbb facccA facccA facccA BnBB 21 21 22222212 11112111 21 5 设：设： xij 表示从工厂运往销地的运量表示从工厂运往销地的运量( (i=1.2m、 j=1.2n), ), 1 1 在在Ai 建厂建厂 又设又设 Yi （i=1.2m） 0 0 不在不在Ai 建厂建厂 模型：模型： n)1.2jm1.2(i 1 0, 0 n)1.2(j )2 . 1( min 1 1 1 、或或 iij m i jij n j iiij m i iiijij

5、 yx bx miyax yfxcZ 6 例例3、机床分配问题、机床分配问题 设有设有m台同类机床，要加工台同类机床，要加工n种零件。已知各种零件的种零件。已知各种零件的 加工时间分别为加工时间分别为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台机床加工各种零件的总时间为：台机床加工各种零件的总时间为： n j

6、ijj mixa 1 )2 . 1( 又由于一个零件只能在一台机床上加工，所以有又由于一个零件只能在一台机床上加工，所以有 m i ij mix 1 )2 . 1( 1 7 因此，求因此，求xij ，使得，使得 n)1.2jm,1.2(i 1 0 n)1.2(j 1 ),max(min 1 111 21 或或 ij m i ij n j n j n j mjjjjjj x x xaxanxaZ 8 2、整数规划的数学模型、整数规划的数学模型 一般形式一般形式 且且部部分分或或全全部部为为整整数数 或或 n)1.2(j 0 )2 . 1( )max(min 1 1 j n j ijij n j

7、jj x mibxa xcZZ 依照决策变量取整要求的不同，整数规划可分为依照决策变量取整要求的不同，整数规划可分为纯整数规纯整数规 划、全整数规划、混合整数规划、划、全整数规划、混合整数规划、0 01 1整数规划整数规划。 9 纯整数规划纯整数规划：所有决策变量要求取非负整数（这时引所有决策变量要求取非负整数（这时引 进的松弛变量和剩余变量可以不要求取整数）。进的松弛变量和剩余变量可以不要求取整数）。 全整数规划全整数规划：除了所有决策变量要求取非负整数外，除了所有决策变量要求取非负整数外， 系数系数aij和常数和常数bi也要求取整数（这时引进的松弛变量和剩也要求取整数（这时引进的松弛变量和

8、剩 余变量也必须是余变量也必须是 整数）。整数）。 混合整数规划混合整数规划：只有一部分的决策变量要求取非负整只有一部分的决策变量要求取非负整 数，另一部分可以取非负实数。数，另一部分可以取非负实数。 01整数规划整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数。两个整数。 10 3、整数规划与线性规划的关系、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性规划的一种从数学模型上看整数规划似乎是线性规划的一种 特殊形式，求解只需在线性规划的基础上，通过特殊形式，求解只需在线性规划的基础上，通过舍入舍入 取整取整，寻求满足整数要求的解即可。，寻求满足整数要求的解即

9、可。 但实际上两者却有很大的不同，通过舍入得到的但实际上两者却有很大的不同，通过舍入得到的 解（整数）也不一定就是最优解，有时甚至不能保证解（整数）也不一定就是最优解，有时甚至不能保证 所得到的解是整数可行解。所得到的解是整数可行解。 举例说明。举例说明。 11 例：例：设整数规划问题如下设整数规划问题如下 且且为为整整数数0, 136 51914 max 21 21 21 21 xx xx xx xxz 首先不考虑整数约束，得到线性规划问题（一般称为首先不考虑整数约束，得到线性规划问题（一般称为松弛问松弛问 题题或或伴随问题伴随问题）。）。 0, 136 51914 max 21 21 21

10、 21 xx xx xx xxz 12 用用图解法图解法求出最优解求出最优解 x13/2, x2 = 10/3 且有且有 = 29/6 x1 x2 3 3 (3/2,10/3) 现求整数解（最优解）：现求整数解（最优解）： 如用如用“舍入取整法舍入取整法”可得到可得到4 个点即个点即(1，3) (2，3) (1，4) (2，4)。显然，它们都不可能。显然，它们都不可能 是整数规划的最优解。是整数规划的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题的可按整数规划约束条件，其可行解肯定在线性规划问题的可 行域内且为整数点。故整数规划问题的可行解集是一个有限集，行域内且为整数点。故整数规划

11、问题的可行解集是一个有限集， 如图所示。如图所示。 z 13 因此，可将集合内因此，可将集合内 的整数点一一找出，的整数点一一找出， 其最大目标函数的值其最大目标函数的值 为最优解，此法为完为最优解，此法为完 全枚举法。全枚举法。 如上例：其中如上例：其中（2， 2）（）（3，1）点为最大点为最大 值，值， =4。 目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有： 分枝定界法和割平面法；分枝定界法和割平面法； 对于特别的对于特别的0 01 1规划问题采用规划问题采用隐枚举法隐枚举法和和匈牙利法匈牙利法。 x1 x2 3 3 (3/2,10/3) z 14 1、基本思路、基本

12、思路 且为整数且为整数)2 . 1( , 0 )2 . 1( )IP( min 1 1 mjx mibxa xcz j n j ijij n j jj 考虑纯整数问题：考虑纯整数问题： ),2 . 1( , 0 ),2 . 1( )LP( min 1 1 mjx mibxa xcz j n j ijij n j jj 整数问题的伴随整数问题的伴随 (松弛松弛)问题：问题： 4.2 分枝定界法分枝定界法 15 （1）先不考虑整数约束，解）先不考虑整数约束，解( IP )的松弛问题的松弛问题( LP )，可，可 能得到以下情况之一：能得到以下情况之一： 若若( LP )没有可行解没有可行解，则，则

13、( IP )也没有可行解，停止计算。也没有可行解，停止计算。 若若( LP )有最优解有最优解，并，并符合符合( IP )的整数条件的整数条件，则，则( LP )的的 最优解即为最优解即为( IP )的最优解，停止计算。的最优解，停止计算。 若若( LP )有最优解，但有最优解，但不符合不符合( IP )的整数条件的整数条件，转入下，转入下 一步。一步。 为讨论方便，设为讨论方便，设( LP )的最优解为：的最优解为： 不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为), 2 , 1(. )0 , 0 ,( )0( 21 )0( mibz bbbbX i T mr 16 记记( I

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

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

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

17、般线性规划问题：首先去掉整数约束，变成一般线性规划问题 0, 4 30 65 2 5min 21 1 21 21 21 xx x xx xx xxZ 记为（记为（LP） 2、例题、例题 19 用图解法求用图解法求（LPLP）的最优解，的最优解， 如图所示。如图所示。 x1 x2 3 3 (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

18、(0) =218/11(19.8) 即即Z(0) 也是（也是（IP）最小值的）最小值的 下限。下限。 20 有下式：有下式： 且且为为整整数数0, 1 4 30 65 2 )1( 5min 21 1 1 21 21 21 xx x x xx xx IP xxZ 且且为为整整数数0, 2 4 30 65 2 )2( 5min 21 1 1 21 21 21 xx x x xx xx IP xxZ 现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。 21 同理求同理求（LP2） ,如图所示。如图所示。 在在C 点取得最优解。点取得最优解。 即即 原问题有比原问题有

19、比16更小的最优解，更小的最优解， 但但 x2 不是整数，故利用不是整数，故利用 3 10/34 加入条件。加入条件。 （问题：假如问题：假如 ，会得出什么结论？，会得出什么结论？） x1 x2 3 3 先求先求（LP1）, ,如图所示。如图所示。 此时此时B 在点取得最优解。在点取得最优解。 找到整数解，问题已探明，找到整数解，问题已探明， 此枝停止计算。此枝停止计算。 1 1 B A C 16, 3, 1 )1( 21 zxx 7 .183/56 , 3/10, 2 )2( 21 z xx 16 )1()2( zz 16 )1()2( zz 22 加入条件：加入条件： x23, x24 有

20、下式：有下式： 且且为为整整数数0, 3 2 4 30 65 2 )3IP( 5min 21 2 1 1 21 21 21 xx x x x xx xx xxZ 且且为为整整数数0, 4 2 4 30 65 2 )4IP( 5min 21 2 1 1 21 21 21 xx x x x xx xx xxZ 只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。 23 x1 x2 3 3 1 1 B A C 先求先求（LP3）, ,如图所示。如图所示。 此时此时D 在点取得最优解。在点取得最优解。 即即 D 求求（LP4），），如图所示。如图所示。 无可行解，不再分枝。无可

21、行解，不再分枝。 8 .19 4 .175/87 , 3, 4 . 25/12 )0( )3( 21 z z xx 但但 不是整数，不是整数， 可继续分枝。可继续分枝。 即即 5/12 1 x 2,3 11 xx 24 在在（LP3）的基础上继续分枝。加入条件）的基础上继续分枝。加入条件 ： 且且为为整整数数0, 2 3 2 4 30 65 2 )5IP( 5min 21 1 2 1 1 21 21 21 xx x x x x xx xx xxZ 且且为为整整数数0, 3 3 2 4 30 65 2 )6IP( 5min 21 1 2 1 1 21 21 21 xx x x x x xx xx

22、 xxZ 只要求出（只要求出（LP5）和（）和（LP6）的最优解即可。）的最优解即可。 2,3 11 xx 25 x1 x2 3 3 1 1 B A C D 先求先求（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) 继续分解，其最小值也不会低于继续分解，其最小值

23、也不会低于15.5 ，问题，问题 探明探明, ,剪枝。剪枝。 26 至此，原问题至此，原问题 （IP）的最优解）的最优解 为：为： x1=2， x2 =3, Z* = Z(5) 17 以上的求解过程以上的求解过程 可以用一个树形可以用一个树形 图表示如右：图表示如右： LP1 x1=1, x2=3 Z(1) 16 LP x1=18/11, x2=40/11 Z(0) 19.8 LP2 x1=2, x2=10/3 Z(2) 18.5 LP3 x1=12/5, x2=3 Z(3) 17.4 LP4 无可无可 行解行解 LP5 x1=2, x2=3 Z(5) 17 LP6 x1=3, x2=5/2

24、Z(6) 15.5 x11x12 x23x24 x12 x13 27 且且为为整整数数0, 1432 92 )IP( 23max 21 21 21 21 xx xx xx xxz 3200 CB XB b x1x2x3x4 0 x3 921109/2 0 x4 142301 14/2 -Z03200 3200 CB XB b x1x2x3x4 3 x1 13/4 103/4 -1/4 2 x2 5/201 -1/21/2 -Z -59/4 00-5/4 -1/4 解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解获得最优解。 初始表初始表最终表最终表 例例

25、2、用分枝定界法求解整数规划问题（单纯形法）用分枝定界法求解整数规划问题（单纯形法） 28 选选 进行分枝，即增加两个约束，进行分枝，即增加两个约束， 有下式：有下式： 且且为为整整数数0, 2 1432 9 2 )1IP( 23max 21 2 21 21 21 xx x xx xx xxZ 且且为为整整数数0, 3 1432 9 2 )2IP( 23max 21 2 21 21 21 xx x xx xx xxZ 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将新加约束条件，将新加约束条件 加入上表计算。即加入上表计算。即 x2+ x5= 2 , x2+x

26、6=3 得下表得下表: 75.144/59, 2/5, 4/13 )0( 21 zxx 2 x 2,3 22 xx 29 32000 CB XB b x1x2x3x4x5 3 x1 13/4 103/4 -1/40 2 x2 5/201 -1/21/20 0 x5 201 001 -Z-59/400-5/4-1/40 3 x1 13/4 103/4 -1/40 2 x2 5/201 -1/21/20 0 x5 -1/20 01/2 -1/21 -Z-59/400-5/4-1/40 3 x1 7/210 1/20-1/2 2 x2 201 001 0 x4 100-1 1-2 -Z-29/200

27、-3/20-1/2 x1=7/2, x2=2 Z(1) =29/2=14.5 继续分枝，加继续分枝，加 入约束入约束 3 x1 4 LP1 30 32000 CB XB b x1x2x3x4x6 3 x1 13/4 103/4 -1/40 2 x2 5/201 -1/21/20 0 x6 -30-1 001 -Z-59/400-5/4-1/40 3 x1 13/4 103/4 -1/40 2 x2 5/201 -1/21/20 0 x6 -1/20 0-1/2 1/21 -Z-59/400-5/4-1/40 3 x1 5/210 01/23/2 2 x2 301 00-1 0 x3 1001

28、-1-2 -Z-27/2000-3/2-5/2 LP2 先不考虑分枝先不考虑分枝 )1()2( )2( 21 5 .132/27 3, 2/5 zz z xx 31 接接(LP1)继续分枝，加入约束继续分枝，加入约束 ，有下式：有下式： 且且为为整整数数0, 3 2 1432 9 2 )3IP( 23max 21 1 2 21 21 21 xx x x xx xx xxZ 且且为为整整数数0, 4 2 1432 9 2 )4IP( 23max 21 1 2 21 21 21 xx x x xx xx xxZ 分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。 3

29、4 11 xx 和和 32 CB XB b x1x2x3x4x5x7 3x17/2101/20-1/20 2x22010010 0 x4100-11-20 0 x73100001 -Z-29/200-3/20-1/20 3x17/2101/20-1/20 2x22010010 0 x4100-11-20 0 x7-1/200-1/201/21 -Z-29/200-3/20-1/20 3x13100001 2x22010010 0 x420001-3-2 0 x310010-1-2 -Z-130000-2-3 x1=3, x2=2 Z(3) =13 找到整数解，找到整数解， 问题已探明，问题已探

30、明， 停止计算。停止计算。 LP3 33 CB XB b x1x2x3x4x5x8 3x17/2101/20-1/20 2x22010010 0 x4100-11-20 0 x8-4-100001 -Z-29/200-3/20-1/20 3x17/2101/20-1/20 2x22010010 0 x4100-11-20 0 x8-1/2001/20-1/21 -Z-29/200-3/20-1/20 3x1410000-1 2x21011002 0 x4300-310-4 0 x5100-101-2 -Z-1400-200-1 x1=4, x2=1 Z(4) =14 找到整数解，找到整数解，

31、问题已探明，问题已探明， 停止计算。停止计算。 LP4 34 树形图如下：树形图如下： LP1 x1=7/2, x2=2 Z(1)29/2=14.5 LP x1=13/4, x2=5/2 Z(0) 59/4=14.75 LP2 x1=5/2, x2=3 Z(2)27/2=13.5 LP3 x1=3, x2=2 Z(3) 13 LP4 x1=4, x2=1 Z(4) 14 x22x23 x13x14 练习练习 35 1.原理： 原有最优解要被割去 正正好好是是整整数数最最优优解解。 剩剩余余部部分分有有一一个个极极点点 割割去去部部分分不不含含整整数数解解 可可行行域域中中割割去去一一部部分分

32、, , x1 x2 4.3 割平面法割平面法 36 2、计算步骤： （1）用单纯形法求解）用单纯形法求解( IP )对应的松弛问题对应的松弛问题( LP )： 若若( LP )没有可行解，则没有可行解，则( IP )也没有可行解，停止计算。也没有可行解，停止计算。 若若( LP )有最优解，并符合有最优解，并符合( IP )的整数条件，则的整数条件，则( LP )的的 最优解即为最优解即为( IP )的最优解，停止计算。的最优解，停止计算。 若若( LP )有最优解，但不符合有最优解，但不符合( IP )的整数条件，转入下的整数条件，转入下 一步。一步。 4.3 割平面法割平面法 37 （2

33、2）从）从( (LP) )的最优解中，任选一个不为整数的分量的最优解中，任选一个不为整数的分量xr, , , 将最优单纯形表中该行的系数将最优单纯形表中该行的系数 和和 分解为整数部分和分解为整数部分和 小数部分之和，并以该行为小数部分之和，并以该行为源行源行，按下式作割平面方程：，按下式作割平面方程： rj a r b 1 r n mj jrj fxf （3 3）将所得的割平面方程作为一个新的约束条件置于最优单）将所得的割平面方程作为一个新的约束条件置于最优单 纯形表中（同时增加一个单位列向量），用对偶单纯形法求出纯形表中（同时增加一个单位列向量），用对偶单纯形法求出 新的最优解，返回新的最

34、优解，返回1 1。 的小数部分的小数部分 的小数部分的小数部分 rj a r b 38 例例1：用割平面法求解整数规划问题：用割平面法求解整数规划问题 且为整数且为整数0, 023 623 max 21 21 21 2 xx xx xx xZ 解：解：增加松弛变量增加松弛变量x3和和x4 ，得到，得到(LP)的初始单纯形表和最的初始单纯形表和最 优单纯形表优单纯形表： Cj0100 CBXBbx1x2x3x4 0 x363210 0 x40-3201 Z00100 Cj0100 CBXBbx1x2x3x4 0 x11101/6-1/6 1x23/2011/41/4 Z-3/2 00 -1/4

35、-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, 生成割平面的条件为生成割平面的条件为: 2 1 4 1 4 1 43 xx Cj0100 CBXBbx1x2x3x4 0 x11101/6-1/6 1x23/201

36、1/41/4 Z-3/2 00 -1/4 -1/4 40 将将 x3=6-3x1-2x2 , x4=3x1-2x2 , 代入代入 中，得中，得 到等价的割平面条件：到等价的割平面条件：x2 1 ； 见下图。见下图。 2 1 4 1 4 1 43 xx x1 x2 3 3 第一个割平面第一个割平面 Cj0100 CBXBbx1x2x3x4 0 x363210 0 x40-3201 Z00100 41 Cj01000 CBXBbx1x2x3x4s1 0 x11101/6-1/60 1x23/2011/41/40 0s1-1/200-1/4-1/41 Z-3/200-1/4-1/40 现将生成的割平

37、面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中： 134 111 442 xxs CBXBbx1x2x3x4s1 0 x12/3100-1/32/3 1x2101001 0 x320011-4 Z-10000-1 42 此时，此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源行为源行 生成割平面，其条件为：生成割平面，其条件为： 3 2 3 2 3 2 14 sx 用上表的约束解出用上表的约束解出x4 和和s1 ，将它们带入上式得到等价的割平，将它们带入上式得到等价的割平 面条件：面条件：x1 x2 ，见图：，见图： x1

38、 x2 3 3 第一个割平面第一个割平面 第二个割平面第二个割平面 43 将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中： 241 222 333 xss CBXBbx1x2x3x4s1s2 0 x12/3100-1/32/30 1x21010010 0 x320011-40 0s2-2/3000-2/3-2/31 Z-10000-10 CBXBbx1x2x3x4s1s2 0 x10100-101 1x20010-103/2 0 x3600150-6 0s1100011-3/2 Z000010-3/2 44 CBXB bx1x2x3x4s1s2 0

39、x1110001-1/2 1x21010010 0 x310010-53/2 0 x4100011-3/2 Z -10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这也是原这也是原 问题的最优解。问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过程中始有以上解题过程可见，表中含有分数元素且算法过程中始 终保持对偶可行性，因此，这个算法也称为终保持对偶可行性，因此，这个算法也称为分数对偶割平面算分数对偶割平面算 法法。 45 例例2：用割平面法求解数规划问题：用割平面法求解数规划问题 且且为为整整数数0, 2054 62 m

40、ax 21 21 21 21 xx xx xx xxZ Cj1100 CBXBbx1x2x3x4 0 x362110 0 x4204501 Z1100 CBXBbx1x2x3x4 1 x15/3105/61/6 1x28/3012/31/3 Z-13/3001/61/6 初初 始始 表表 最最 优优 表表 46 在松弛问题最优解中，在松弛问题最优解中，x1, x2 均为非整数解，由上表有：均为非整数解，由上表有： 3 8 3 1 3 2 3 5 6 1 6 5 432 431 xxx xxx 将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 3 2 2 3 1

41、) 3 1 1( 3 2 1) 6 5 1( 6 5 432 431 xxx xxx 47 以上式子只须考虑一个即可，以上式子只须考虑一个即可，解题经验表明，考虑式子解题经验表明，考虑式子 右端最大真分数的式子，往往会较快地找到所需割平面约束右端最大真分数的式子，往往会较快地找到所需割平面约束 条件。条件。以上两个式子右端真分数相等，可任选一个考虑。现以上两个式子右端真分数相等，可任选一个考虑。现 选第二个式子，并将真分数移到右边得：选第二个式子，并将真分数移到右边得： )( 3 1 3 2 2 4332 xxxx 3 2 )( 3 1 43 xx 引入松弛变量引入松弛变量s1 后得到下式，将

42、此约束条件加到上表中，继续后得到下式，将此约束条件加到上表中，继续 求解。求解。 3 2 3 1 3 1 143 sxx 48 Cj 11000 CBXBbx1x2x3x4s1 1 x1 5/3105/61/60 1 x2 8/3012/31/30 0 s1 2/3001/31/31 Z 13/3001/61/60 Cj 11000 CBXBbx1x2x3x4s1 1 x1 010010 1 x2 401012 0 x3 200113 Z 400001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划得到整数最优解，即为整数规划的最优解，而且此整数规划 有两个最优解：有两个最优解： X

43、= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 49 01 整数规划是一种特殊形式的整数规划，这时的决策变量整数规划是一种特殊形式的整数规划，这时的决策变量 xi 只取两个值只取两个值0或或1，一般的解法为，一般的解法为隐枚举法隐枚举法。 例例1、求解下列、求解下列01 规划问题规划问题 10, (4) 64 (3) 3 (2) 44 (1) 22 523max 321 32 21 321 321 321 或或xxx xx xx xxx xxx xxxZ 4.4 04.4 01 1 整数规划整数规划 50 解：解：对于对于01 规划问题，由于每个变量只取规划问题，由于

44、每个变量只取0，1两个值，两个值， 一般会用穷举法来解，即将所有的一般会用穷举法来解，即将所有的0，1 组合找出，使目标组合找出，使目标 函数达到极值要求就可求得最优解。但此法太繁琐，工作函数达到极值要求就可求得最优解。但此法太繁琐，工作 量相当大。而隐枚举法就是在此基础上，通过量相当大。而隐枚举法就是在此基础上，通过加入一定的加入一定的 条件条件，就能较快的求得最优解。，就能较快的求得最优解。 x1 . x2. x3 约束条件约束条件满足条件满足条件 Z 值值 (1) (2) (3) (4)是是 否否 ( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0

45、 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 ) 51 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 ) 0 2 1 18 ( 1. 1. 0 ) 3 ( 1. 1. 1 ) 2 6 10, (4) 64 (3) 3 (2) 44 (1) 22 523max 32

46、1 32 21 321 321 321 或或xxx xx xx xxx xxx xxxZ 52 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 ) 0 2 1 18 ( 1. 1. 0 ) 3 ( 1. 1. 1 ) 2 6 由下表可知，问题的最优解为由下表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=

47、1 ) 由下表可知：由下表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最是一个可行解，为尽快找到最 优解，可将优解，可将3 x12 x25 x3 5 作为一个约束（也称为作为一个约束（也称为过滤条过滤条 件件），凡是目标函数值小于），凡是目标函数值小于5 的组合不必讨论，如下表。的组合不必讨论，如下表。 53 x1 . 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. 1. 1 ) 3 ( 1. 0. 0 )

48、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 规划问题规划问题 4 . 3 . 2

49、. 1 1 , 0 5 35 646 1 2 73max 421 4321 4321 4321 jx xxx xxxx xxxx xxxxZ j 解解：由于目标函数中变量：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作的系数均为负数，可作 如下变换：如下变换： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4带入原题中，带入原题中， 但需重新调整变量编号。令但需重新调整变量编号。令 x3 = x1, x4 = x2得到下式。得到下式。 55 1 0, 435 2 46 1 2 1173max 4321 432 4321 4321 4321 或或

50、xxxx xxx xxxx xxxx xxxxZ 可以从可以从( 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得到下式。得到下式。 练习练习 56 bintprog函数0-1整数规划 f = -9; -5; -6; -4; A = 6 3 5 2; 0 0 1 1; -1 0 1 0;

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

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

53、58 设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相反 ( i, j=1.2. n ) 其数学模型为：其数学模型为： ).2.1,1(0 ).2.1( 1 ).2.1( 1 min 1 1 11 njix njx nix xcZ ij n i ij n j ij n i n j ijij 或或 59 2、解题步骤：、解题步骤： 指派问题是指派问题是0-1 规划的特例，当然可用整数规划，规划的特例，当然可用整数规划，0-1 规划规划 的解法去求解，但运算繁琐。利用指派问题的特点可有更简便的解法去求解，但运算繁琐。利用指派问题的特点可有更简便

54、 的解法，这就是的解法，这就是匈牙利法匈牙利法( (匈牙利数学家匈牙利数学家D.KonigD.Konig提出提出) ，即，即系数系数 矩阵中独立矩阵中独立 0 0 元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有 0 0 元素的最少元素的最少 直线数直线数 P73P73定理定理2 2 。 第一步：变换指派问题的系数第一步：变换指派问题的系数(也称效率也称效率)矩阵（矩阵（cij）为）为(bij)，使，使 在在(bij)的各行各列中都出现的各行各列中都出现0元素，元素，即即 (1) 从（从（cij）的）的每行元素都减去该行的最小元素每行元素都减去该行的最小元素； (2) 再从所得新系数矩

55、阵的再从所得新系数矩阵的每列元素中减去该列的最小元素每列元素中减去该列的最小元素。 P70 P70 定理定理1 1 60 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的中找尽可能多的独立独立0元素元素，若能找出，若能找出n个独立个独立0元元 素，就以这素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余，其余 为为0，这就得到最优解。，这就得到最优解。找独立找独立0元素，元素，常用的步骤为常用的步骤为： (1)从从只有一个只有一个0元素的元素的行行(列列)开始，给这个开始，给这个0元素加圈，元素加圈，

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

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

58、 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素元素。 (1)对没有对没有的行打的行打号；号； (2)对已打对已打号的行中所有含号的行中所有含 元素的元素的列列打打号；号； (3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； 62 (4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； (5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得号的列画纵线，这就得 到覆盖所有到覆盖所有0元素的最少直线数元素的最少直线数 l 。l 应等于应等于m，若不相等，若不相等， 说明试指派过程有误，回到第二步说

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

60、。仍相同。转回第二步。 63 例例1： 任务任务 人员人员 ABCD 甲甲215134 乙乙1041415 丙丙9141613 丁丁78119 64 91187 1316149 1514410 413152 2410 4750 111006 211130 -2 -4 -9 -7 第一步：变换指派问题的系数矩阵（第一步：变换指派问题的系数矩阵（cij）为）为(bij)，使在，使在(bij) 的各行各列中都出现的各行各列中都出现0元素，元素，即即 (1) 从（从（cij）的）的每行元素都减去该行的最小元素每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的再从所得新系数矩阵的每列元素中减去