第五章 整数规划

1、第五章第五章 整数规划整数规划整数规划数学模型整数规划数学模型纯整数规划的求解纯整数规划的求解01规划的求解规划的求解分支定界法分支定界法割平面法割平面法指派问题指派问题非标准形式的指派问题非标准形式的指派问题一、整数规划的模型一、整数规划的模型 很多实际规划问题都属于整数规划问题很多实际规划问题都属于整数规划问题 1. 变量是人数、机器设备台数或产品件数等都要变量是人数、机器设备台数或产品件数等都要求是求是； 2. 对某一个项目要不要投资的决策问题，可选用对某一个项目要不要投资的决策问题，可选用一个逻辑变量一个逻辑变量 x，当，当x=1表示投资，表示投资，x=0表示不投资；表示不投资； 3.

2、 人员的合理安排问题，当变量人员的合理安排问题，当变量xij=1表示安排第表示安排第i人去做人去做 j工作，工作，xij=0表示不安排第表示不安排第i人去做人去做 j工工 作。逻作。逻辑变量也是只允许取整数值的一类变量。辑变量也是只允许取整数值的一类变量。 例例 合理下料问题合理下料问题 设用某型号的圆钢下零件设用某型号的圆钢下零件A1, A2,Am 的毛坯。在的毛坯。在一根圆钢上下料的方式有一根圆钢上下料的方式有B1,B2, Bn 种，每种下料方种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满

3、足需要，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少所用的原材料又最少？零件 方 个数 式零件零 件毛坯数nBB 1mAA 1mbb 1mnmnaaaa 1111 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数种方式下料根数 模型：模型：11min (1.2)0 (1.2)njjnijjijjZxa xbimxjn且为整数零件 方 个数 式零件零 件毛坯数nBB 1mAA 1mbb 1mnmnaaaa 1111单 销地厂址 价生产能力建设费用销量nmmmnmmmnnbbbfacccAfacccAfacccABnBB 21212222221211112111

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

5、用最省？ 设：设： xij 表示从工厂运往销地的运量表示从工厂运往销地的运量( (i=1.2m、j=1.2n), 1 ), 1 在在Ai建厂建厂 又设又设 Yi （i=1.2m） 0 0 不在不在Ai建厂建厂 模型：模型：111min (1.2) (1.2)0,0 1 (1.21.2)mijijiiinijiijmijjiijiZc xf yxa yimxbjnxyimjn或、 例例 机床分配问题机床分配问题 设有设有m台同类机床，要加工台同类机床，要加工n种零件。已知各种零件种零件。已知各种零件的加工时间分别为的加工时间分别为a1,a2,an ，问如何分配，使各机床，问如何分配，使各机床的总

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

7、jiijZa xa xa xxjnxim jn或例例 投资项目选取问题投资项目选取问题某单位拟利用闲置资金某单位拟利用闲置资金15 万元进行对外投资，现有万元进行对外投资，现有 5个投个投资项目可供选择，所需资金及投资回报收益期望值为资项目可供选择，所需资金及投资回报收益期望值为项目项目所需资金（万元）所需资金（万元）收益期望值（万元）收益期望值（万元） A B C D E 6 4 2 4 5 10 8 7 6 9A，B，C，D，E 之间的关系是：之间的关系是： A、C、E 三项中需且只能选一项；三项中需且只能选一项； B、D 两项中需且只能选一项；两项中需且只能选一项； 选选 C 必须先选必

8、须先选 D 。问题：如何选择投资决策，使总投资期望值最大？问题：如何选择投资决策，使总投资期望值最大？ 解解用用 xj 分别表示分别表示 A ，B ，C ，D ，E 的被选情况，则的被选情况，则于是投资总收益期望值：于是投资总收益期望值：54321967810 xxxxxz约束条件：约束条件： 资金总额限制：资金总额限制：155424654321xxxxx1,0,1, 2,3, 4,5jjxjj项目 被选中项目 未被选中 A，C，E 选且只选一项：选且只选一项：1531xxx项目项目所需资所需资金（万元）金（万元）收益期收益期望值（万元）望值（万元） A B C D E 6 4 2 4 5 1

9、0 8 7 6 9 选选 C 必须先选必须先选 D ：于是数学模型为以下于是数学模型为以下 01 规划：规划：31x ,41x ,40 x30 x或34xx5 , 4 , 3 , 2 , 110111554246967810max43425315432154321jxxxxxxxxxxxxxxxxxxzj，或 B，D 选且只选一项：选且只选一项：142 xx 例例 某人有一某人有一可以装可以装10公斤重、公斤重、0.025m3的物品。他准备的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表所示。用来装甲、乙两种物品，每件物品的重量、体积和价值如表所示。问两种物品各装多少件，所装

10、物品的总价值最大？问两种物品各装多少件，所装物品的总价值最大？ 解解 设甲、乙两种物品各装设甲、乙两种物品各装x1、x2件，则数学模型为：件，则数学模型为：且均取整数, 0,255 . 22108 . 02 . 134max21212121xxxxxxxxZ物品物品重量重量(公斤公斤/每件每件)体积体积(m3/每件每件)价值价值(元元/每件每件)甲甲乙乙1.20.80.0020.002543 例例 在上例中，假设此人在上例中，假设此人，最大载重量为，最大载重量为12公斤，其体积是公斤，其体积是0.02m3。背包和旅行箱只能选择其一背包和旅行箱只能选择其一，建立，建立下列几种情形的数学模型，使所

11、装物品价值最大。下列几种情形的数学模型，使所装物品价值最大。(1) 所装物品不变；所装物品不变；(2) 如果选择旅行箱，则如果选择旅行箱，则，价值分别，价值分别是是4和和3，载重量和体积的约束为，载重量和体积的约束为2025 . 1126 . 08 . 12121xxxx 解解 此问题可以建立两个整数规划模型，但用一个模型描此问题可以建立两个整数规划模型，但用一个模型描述述 更简单。引入更简单。引入01变量变量 yi，令，令2 , 10, 1iiiyi种方式装载时不采用第，种方式装载时采用第i=1,2 分别是采用背包及旅行箱装载。分别是采用背包及旅行箱装载。由于由于,上例上例约束左约束左边不变

12、边不变, 整数规划数学模型为整数规划数学模型为121212121212max431.20.8101222.5252010,011,2iiZxxxxyyxxyyyyxyi且取整数或(2) 不同载体所装物品不一样，数学模型不同载体所装物品不一样，数学模型为为121221211221211212max431.20.810( )1.80.612( )22.525( )1.5220( )1,0,01(1,2)iZxxxxMyaxxMybxxMycxxMydyyx xyi且均取整数或1212121.20.81022.525,0,xxxxxx且 均 取 整 数2025 .1126 .08 .12121xxx

13、x M为充分大的正为充分大的正数。可知，当使用背数。可知，当使用背包时包时(y1=1，y2=0)，式，式(b)和和(d)是多余的；当是多余的；当使用旅行箱时使用旅行箱时(y1=0，y2=1)，式，式(a)和和(c)是多是多余的。上式也可以令余的。上式也可以令yyyy1,21(1)右端常数是右端常数是k个值中的一个时，约束条件为个值中的一个时，约束条件为1111kiikiiinjjijyybxa，(2 2)对于对于m条件中有条件中有k（m）组起作用时，约束条件写成）组起作用时，约束条件写成11nmijjiiijia xbMyymk，这里这里yi=1表示第表示第i组约束不起作用，组约束不起作用，y

14、i=0表示第表示第i个约束起作用。个约束起作用。当约束条件是当约束条件是“”符号时右端常数项应为符号时右端常数项应为iibMy(3) 对于对于m条件中有条件中有k(m)个起作用时，约束条件写成个起作用时，约束条件写成11nmijjiiijia xbMyymk，一般地一般地: 同样可以讨论对于有同样可以讨论对于有m个条件个条件、有、有m(m、m)个条个条件起作用的情形。件起作用的情形。例例 试引入试引入01变量将下列各题分别表达为一般线性约束条件变量将下列各题分别表达为一般线性约束条件:(1) x1+x26或或4x1+6x210或或2x1+4x220 ;(2) 若若x15，则，则x20，否则，否

15、则x28;(3) x1取值取值0，1，3，5，7。 解解 (1) 3个约束只有个约束只有1个起作用个起作用1211221231236461024202011,2,3jxxy Mxxy Mxxy Myyyyj或 ，3 , 2 , 1101)1 (2042)1 (1064)1 (6321321221121jyyyyMyxxMyxxMyxxj，或或或(3) 右端常数是右端常数是5个值中的个值中的1个个4 , 3 , 2 , 1101753432143211jyyyyyyyyyxj，或10)1 (8)1 (552211或yMyxyMxMyxyMx(2) 两组约束只有一组起作用两组约束只有一组起作用(2

16、) 若若x15，则，则x20，否则，否则x28; (3) x1取值取值0，1，3，5，7。整数规划的数学模型整数规划的数学模型一般形式一般形式11max(min) (1.2)0 (1.2) njjjnijjijjZZc xa xbimxjn或且部分或全部为整数 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。整数规划。 纯整数规划：所有决策变量要求取非负整纯整数规划：所有决策变量要求取非负整数（这时数（这时）。）。 全整数规划：除了所有决策变量要求取非负全整数规

17、划：除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时也要求取整数（这时）。）。 混合整数规划：只有一部分的决策变量要混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。 01整数规划：所有决策变量只能取整数规划：所有决策变量只能取 0 或或 1 两个整数两个整数。整数规划与线性规划的关系整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍

18、入取整，寻求满足整数要求的解即可。满足整数要求的解即可。 但实际上两者却有很大的不同，通但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解最优解，有时甚至不能保证所得到的解是整数可行解。是整数可行解。例：设整数规划问题如下例：设整数规划问题如下 且为整数0,13651914max21212121xxxxxxxxZ 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。0,13651914max21212121xxxxxxxxZ用图解法求出最优解用图解法

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

20、此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。 如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。 目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有： 分支定界法和割平面法；分支定界法和割平面法； 对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。 分支定界法是一种隐枚举法或部分枚举法，是枚举分支定界法是一种隐枚举法或部分枚举法，是枚举法基础上的改进。分支定界法的关键是分支和定界。法基础上的改进。分支定界法的关键是分支和定界。

21、“ “分支分支”为整数规划最优解的出现创造了条件，为整数规划最优解的出现创造了条件，而而“定界定界”则可以提高搜索的效率则可以提高搜索的效率。 所谓所谓“”，是在分支过程中，若某个后继问，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个目标函数值就是一个“界限界限”，可作为衡量处理其它，可作为衡量处理其它分支的一个依据。分支的一个依据。 若整数规划的松驰问题的最优解不符合整数要求，若整数规划的松驰问题的最优解不符合整数要求，不妨假设不妨假设 不符合整数要求不符合整数要求, ,则可构造两个则可构造两个约束条

22、件约束条件 和和 如此不断继续，如此不断继续，直到获得整数规划的最优解。这就是所谓的直到获得整数规划的最优解。这就是所谓的“”iibx iibx 1iibx分支定界法分支定界法 基本思想：基本思想： 切割可行域，去掉非整数点。一次分枝变成两切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解个可行域，分别求最优解. 通过对松弛问题的分枝，通过对松弛问题的分枝，不断降低（不断降低（IP）最优值的上界，提高下界，当上界等）最优值的上界，提高下界，当上界等于下界时，得到最优解。于下界时，得到最优解。1 求解纯整数规划的分支定界法求解纯整数规划的分支定界法11max,1,2,0,1,2, ,

23、njjjnijjijjzc xa xbjmxjn且全为整数IPIP的松驰问题：的松驰问题：11max,1,2,0,1,2, ,njjjnijjijjzc xa xbimxjnLP,*:LPxzIPz设的最优解为最优值为 则 的最优值满足*zzz.zIP其中为在任何一个可行解处的目标值 检验与分支：检验与分支：,*.xIPxIPzz如果 满足的整数要求 则 为的最优解：否则,rx考虑一个不满足整数要求的将约束 1rrrrxxxx和)(的最大整数不超过形成两个子问题分别加入aaLP,;LPIP如果无最优解 则无最优解 求解求解LP LP : :1LP1maxnjjjzc x11,2,nijjija

24、 xbimrrxx njxj, 2 , 1, 02LP1maxnjjjzc x11,2,nijjija xbim1rrxxnjxj, 2 , 1, 0 求解求解LP1, LP2 ：设其解及最优值分别为设其解及最优值分别为.)(,(),(,(222111xzzxxzzx*,1zzz故对故对LP1剪支剪支.的最优值均满足：的最优值均满足：(i)如如则则LP1及由及由LP1分支的所有子问题分支的所有子问题,1zz 剪支及上下界改进分析剪支及上下界改进分析1()LP以为例,其他分支类似(ii)如如:1zz满足满足IP的要求时，则的要求时，则1x当当1x是是IP的可行解，故的可行解，故改进下界改进下界*

25、,1zz ,:1zz 同理，此时同理，此时LP1剪支剪支.*x注意到注意到IP的最优解的最优解必是必是LP1或或LP2的可行解的可行解, 于是于是),(*)(*11xzzxzz或或).(*)(*22xzzxzz,max*21zzz 改进上界：改进上界：,max:21zzz 对对21,xx中中. .zz直至产生或全分支被剪支例例 用分支定界法求解下列整数规划模型：用分支定界法求解下列整数规划模型：解解 先求对应的松弛问题先求对应的松弛问题(记为记为LP0)： 0,255 . 22108 . 02 . 1:034max21212121xxxxxxLPxxZ用图解法得到最优解用图解法得到最优解X（3

26、.57,7.14）,Z0=35.7,如下图所示如下图所示:且均取整数,0,255.22108.02.134max21212121xxxxxxxxZ8.3310108 . 02 . 121xx255 . 2221xx松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC10*035.7Z1010 x1x2oABC0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6), Z1=34.8LP2:X=(4,6.5),Z2=35.50,4255 . 22108 . 02 . 1:234ma

27、x211212121xxxxxxxLPxxZ得到两个线性规划及增加约束4311xx*035.5Z1010 x1x2oABCLP1LP334LP3:X=(4.33, 6), Z3=35.330,64255 . 22108 . 02 . 1:334max2121212121xxxxxxxxLPxxZ，2222677LPxxx选择目标值最大的分枝进行分支，增加约束及，显然不可行，得到线性规划6不可行72xLP1:X=(3, 7.6), Z1=34.8*035.33Z1010 x1x2oACLP134可行域是一条线段即，, 40,464255 . 22108 . 02 . 1:434max121121

28、212121xxxxxxxxxxLPxxZ：及，到线性规划及进行分枝，增加约束，选择由于545431113LPLPxxLPZZ60,65255 . 22108 . 02 . 1:534max2121212121xxxxxxxxLPxxZ，LP4:X=(4,6), Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6), Z1=34.8LP3LP5*3435.33Z*3535.33Z 尽管尽管LP1的解中的解中x1不为整数，但不为整数，但Z5Z1因此因此LP5的最优解的最优解就是原整数规划的最优解。就是原整数规划的最优解。上述分枝过程可用下图表示上述分枝过程可用下图表示LP0:

29、X=(3.57, 7.14), Z0=35.7LP1: X=(3, 7.6) Z1=34.8LP2: X=(4, 6.5) Z2=35.5x13x14LP3: X=(4.33, 6) Z3=35.33x26LP4: X=(4, 6) Z4=34LP5: X=(5, 5) Z5=35x14x15无可行解无可行解x27 例例 用分枝定界法求解整数规划问题（用图解法计算）用分枝定界法求解整数规划问题（用图解法计算）且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问

30、题0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（LP）用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64， 取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值取值x2 3 ，x2 4先将先将（LP）划分为（）划分为（LP1）和（）和（LP2）, ,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最小值的下最小值的下限。限。有下式：有下式：且且为为整整数数0,1 4 30 652 )

31、1(5min2111212121xxxxxxxxIPxxZ且且为为整整数数0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。x1x233(18/11,40/11) 先求先求（LP1）, ,如图所示。如图所示。此时此时B 在点取得最优解。在点取得最优解。x11, x2 =3, Z(1)16找到整数解，问题已探找到整数解，问题已探明，此枝停止计算。明，此枝停止计算。11同理求同理求（LP2） ,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即x12, x2 =10/

32、3, Z(2) 56/318.7 Z2 Z116 原问题有比原问题有比（16）更小的最优解，但）更小的最优解，但 x2 不是整数，故利用不是整数，故利用BAC加入条件：加入条件： x23, x24 有下式：有下式：且且为为整整数数0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且为为整整数数0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。x1x233(18/11,40/11)11BAC先求先求（LP3）, ,如图所示。如图所示

33、。此时此时D 在点取得最优解。在点取得最优解。即即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5) F 如对如对 Z(6) 继续分解，其最小值也不会低于继续分解，其最小值也不会低于15.5 ，问题探明问题探明, ,剪枝。剪枝。 至此，原问至此，原问题（题（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.5LP

34、3x1=12/5, x2=3Z(3) 17.4LP4无可无可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13 且全为整数且全为整数0,13651914max21212121xxxxxxxxZ用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题 LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP5x1=1, x2=2Z(5) 3LP6无可无可行解行解x22x23LP3x1=33/14, x2=2

35、Z(3) 61/14LP4无可无可行解行解x22x23LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x12x13LP1x1=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无可无可行解行解LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x11x12x22x23x12x13且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3

36、x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解。获得最优解。初始表初始表最终表最终表例例 用分枝定界法求解整数规划问题（单纯形法）用分枝定界法求解整数规划问题（单纯形法） x1=13/4 x2=5/2 Z(0) =59/414.75 选选 x2 进行分枝，即增加两个约束，进行分枝，即增加两个约束，2 x2 3 有下式：有下式：121212212max

37、322 92314(1) 2,0ZxxxxxxLPxx x且为整数121212212max322 92314(2) 3,0ZxxxxxxLPxx x且为整数 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将新加，将新加约束条件加入上表计算。即约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得得下表下表:32000CB 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-

38、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 4LP132000CB 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/403

39、x15/21001/23/22x230100-10 x31001-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，有下式：有下式：且且为为整整数数0,3 2 14329 2)3(23max2112212121xxxxxxxxIPxxZ且且为为整整数数0,4 2 14329 2)4(23max2112212121xxxxxxxxIPxxZ分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。CB XB

40、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-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP3CB XB b x1x2x3x4x5x83x

41、17/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/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP4树形图如下：树形图如下：LP1x1=7/2, x2=2Z(1)29/2

42、=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 且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （单纯形法）（单纯形法）cj-1-5000cBxBbx1x2x3x4x50 x32-111000 x4 30560100 x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-

43、5x240/11011/11 5/110-1x1 18/11101/11-6/1100 x526/1100-1/116/111-Z218/11006/1119/110LP1x1=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 先不考虑整数约束，按一般线性先不考虑整数约束，按一般线性规划问题求其最优解，线性规划问题

44、规划问题求其最优解，线性规划问题的最优基本可行解是解集的一个极点的最优基本可行解是解集的一个极点，这个极点的的坐标未必都是整数，这个极点的的坐标未必都是整数，若不是整数解，可增加一条约束，相若不是整数解，可增加一条约束，相当于增加一个平面将这个极点割掉，当于增加一个平面将这个极点割掉，称这种方法为割平面法。称这种方法为割平面法。割平面法的基本思想割平面法的基本思想例例 求解整数线性规划问题求解整数线性规划问题 C B sO A x1 x2整数, 0,104114. .max212121xxxxtsxxs解解 引入松驰变量将其化为标准形式引入松驰变量将其化为标准形式，利用单纯，利用单纯形法求其最

45、优解。形法求其最优解。最优单纯形表如下最优单纯形表如下4 , 3 , 2 , 1, 0104114. .max423121ixxxxxt sxxsi整数 从最优单纯形表中看出约束条件变成从最优单纯形表中看出约束条件变成 5 . 225. 075. 225. 04231xxxx 变形得变形得423125. 05 . 0225. 075. 02xxxx上式分别记为上式分别记为,1I2I 423125. 05 . 025. 075. 0 xIxI 都应小于等于都应小于等于0的整数。引进多余变量的整数。引进多余变量 21,II65,xx5 . 025. 075. 025. 06453xxxx4 , 3

46、 , 2 , 1, 0104114. .max423121ixxxxxt sxxsi整数jcjxBxBcib1x2x3x4x1x2xj 1 1 0 0 111 0 0.25 0 0 1 0 0.252.752.5 0 0 -0.25 -0.25 用对偶用对偶单纯形单纯形法求解法求解jcjxBxBcib1x2x3x4x5x6x1x2x5x6xj 1 1 0 0 0 0 11001 0 0.25 0 0 00 1 0 0.25 0 00 0 -0.25 0 1 00 0 0 -0.25 0 12.752.5-0.75-0.5 0 0 -0.25 -0.25 0 0 取取i=3为主元行为主元行,k=

47、3为主元列为主元列,进行换基迭代。再取进行换基迭代。再取i=4为主为主元行，元行，k=4为主元列，进行换基迭代得表。为主元列，进行换基迭代得表。5 . 025. 075. 025. 06453xxxx jcBcBxjxib1x2x3x4x5x6x1x2x5x6xj 1 1 0 0 0 0 11001 0 0 0 1 00 1 0 0 0 10 0 1 0 -4 00 0 0 1 0 -42232 0 0 0 0 -1 -1 最优基本可行解为：最优基本可行解为： 0, 2, 3, 2, 24321其余为xxxx设纯整数规划设纯整数规划njxbxaxcZjinjjijnjjj, 10max11且为

48、整数， 松弛问题松弛问题njxbxaxcZjinjjijnjjj, 10max11，的最优解的最优解TmTbbbbBbbBX),() 0 ,(21112 求解求解IP的割平面法的割平面法jcnmmcccc11BcBXbmcc 1mxx 11 mbbnmmxxxx 11im 11,11,11001mnm mmnaaaa 0 0jjiijcc aj单纯形法最终表单纯形法最终表设设xi不为整数，不为整数，,iikkiiiikkkkkxa xbxba xx即为非基变量将将 分离成一个分离成一个与一个与一个之和：之和：ikiab及 ,01,01iiiikikikiikbbfaafff则有则有kkikkk

49、ijiiixfxafbx iiijkiikkkkxba xff x上式两边都为上式两边都为并且有并且有1ikkikifxff加入松弛变量加入松弛变量si得得iikkiksf xf 此式称为以此式称为以xi行为源行行为源行(来源行来源行)的的，或，或，或，或R.E.Gomory。 将将Gomory约束方程加入到松弛问题的最优表中，约束方程加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。再继续切割，直到全部为整数解。0iikkkff x则则324313322354613651xxxxxx例如，例如，32

50、46536511)1(xxxx1行：行：移项：移项：46536532411xxxx令令046536532xx加入松弛变量加入松弛变量s1得得324653651xxs同理，对于同理，对于x2行有：行有：324313312xxs 例例 用割平面法求解下列用割平面法求解下列IP问题问题且为整数0,102304634max21212121xxxxxxxxZ解解 放宽变量约束，对应的松弛问题是放宽变量约束，对应的松弛问题是 0,102304634max21212121xxxxxxxxZ加入松弛变量加入松弛变量x3及及x4后，用单纯形法求解，得到最优表后，用单纯形法求解，得到最优表 最优解最优解X(0)(

51、5/2，15/4),不是不是IP的最优解。选择的最优解。选择表的第一行表的第一行(也可以选第二行也可以选第二行)为源行为源行252141431xxxCj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4分离系数后改写成分离系数后改写成212)211(41431xxx021412124341xxxx加入松弛变量加入松弛变量x5得到高莫雷约束方程得到高莫雷约束方程34522xxx 将上式作为约束条件添加到上表中，用对偶单将上式作为约束条件添加到上表中，用对偶单纯形法计算，如表所示纯形法计算，如表所示: Cj43000bCBXBx1x2x3

52、x4x5430 x1x2x51000101/41/811/23/42 0015/215/42j005/81/40430 x1x2x41000101/21/21/2001 1/43/81/2331j001/201/8最优解最优解X(1)(3，3)，最优值，最优值Z21。所有变量为整数，。所有变量为整数，X(1)就是就是IP的最优解。如果不是整数解，需要继续切割，的最优解。如果不是整数解，需要继续切割，重复上述计算过程。重复上述计算过程。 1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbbBcB11xnx2x1mxmx0111mabBcB1

53、01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmarna1 rb1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmrmaarnrnaa1 rrbbbBcB101xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs00001rmfrnf1rfbBcB100rf正则解正则解 1 求解求解01整数规划的隐枚举法（整数规划的隐枚举法（适合于变量个适合于变量个 数较少数较少的的0-1规划）规划）隐枚举法的步骤：隐枚举法的步骤： 1

54、.找出任意一可行解，目标函数值为找出任意一可行解，目标函数值为Z0 ； 2. 原问题原问题，则增加一个约束，则增加一个约束1 1220(*)nnc xc xc xZ当当，上式改为，上式改为约束；约束； 3. 列出所有可能解，对每个可能解先检验式列出所有可能解，对每个可能解先检验式(*)，若，若满足再检验其它约束，若不满足式满足再检验其它约束，若不满足式(*)，则认为不可行，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标若所有约束都满足，则认为此解是可行解，求出目标值值 ； 4. 目标函数值最大目标函数值最大(最小最小)的解就是最优解。的解就是最优解。 例例 用隐枚举法求解下列用隐

55、枚举法求解下列BIP问题问题4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或1153264321xxxx 解解 (1) 不难看出，当所有变量不难看出，当所有变量等于等于0或或1的任意组合时，第一个的任意组合时，第一个约束满足，说明第一个约束没有约束满足，说明第一个约束没有约束力，是多余的，从约束条件约束力，是多余的，从约束条件中去掉。中去掉。 还能通过观察得到还能通过观察得到X0(1，0，0，1)是一个可行解，目标是一个可行解，目标值值Z011是是BIP问题的下界，构问题的下

56、界，构造一个约束：造一个约束：原原BIP问题变为问题变为12341234123412341234max6235623511( )3564( )23 ( )( )24510011,2,3,4jZxxxxxxxxaxxxxbxxxxcdxxxxxj或 ，(2) 列出变量取值列出变量取值0和和1的组合，共的组合，共2416个，分个，分别代入约束条件判断是否可行。别代入约束条件判断是否可行。 首先判断式首先判断式(a)是否满足，如果满足，接下来是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见判断其它约束，否则认为不可行，计算过程见下表所示。下表所示。 3. 列出所有可能解，对每个可能

57、解先检验式列出所有可能解，对每个可能解先检验式(*)，若，若满足再检验其它约束，若不满足式满足再检验其它约束，若不满足式(*)，则认为不可行，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标若所有约束都满足，则认为此解是可行解，求出目标值值 ；jXjabcdZjjXjabcdZj1(0,0,0,0)9(1,0,0,0)2(0,0,0,1)10 (1,0,0,1)113(0,0,1,0)11(1,0,1,0)4(0,0,1,1)12 (1,0,1,1)145(0,1,0,0)13 (1,1,0,0)6(0,1,0,1)14 (1,1,0,1)137(0,1,1,0)15 (1,1,1

58、,0)8(0,1,1,1)16 (1,1,1,1) (3) 由上表知，由上表知，BIP问题的最优解：问题的最优解：X(1，0，1，1)，最优值，最优值Z14。 注：注： (1) 选择不同的初始可行解，计算量会不选择不同的初始可行解，计算量会不一样。一样。 一般地，当目标函数求最大值时，首先考虑目一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于标函数系数最大的变量等于1。 当目标函数求最小值时，先考虑目标函数系数当目标函数求最小值时，先考虑目标函数系数最大的变量等于最大的变量等于0；(2) 在上表的计算过程中，当目标值等于在上表的计算过程中，当目标值等于14时，将时，将其下界其下

59、界11改为改为14，可以减少计算量。，可以减少计算量。 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任项不同的任务，需要务，需要n 个人分别完成其中的一项，但由于任务的性质个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。（或花费的时间或费用）也就不同。 于是产生了一个问题，应指派哪个人去完成哪项任务，于是产生了一个问题，应指派哪个人去完成哪项任务，使完成使完成 n 项任务的总效率最高（或所需时间最少），这项任务的总效率最高（或所需时间最少），这

60、类问题称为类问题称为。 指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求解，规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。这就如同用单纯型法求解运输问题一样是不合算的。 利用指派问题的特点可有更简便的解法，这就是利用指派问题的特点可有更简便的解法，这就是，即，即。指派问题指派问题 例例 人事部门欲安排四人到四个不同的岗位工作，每个岗位人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如表所示，如一个人经考核四人在不同