《整数规划(第4章)》由会员分享，可在线阅读，更多相关《整数规划(第4章)（39页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章第四章第四章 整数规划整数规划整数规划整数规划 1 引引 言言 整整数数规规划划是是一一类类要要求求变变量量取取整整数数值值的的数数学学规规划划，可可分分成成线线性性和非线性两类。和非线性两类。 根根据据变变量量的的取取值值性性质质，又又可可以以分分为为全全整整数数规规划划，混混合合整整数数规规划，划，0-1整数规划等。整数规划等。 整数规划是数学规划中一整数规划是数学规划中一个较弱的分支，目前只能解中个较弱的分支，目前只能解中等规模的线性整数规划问题，等规模的线性整数规划问题，而非线性整数规划问题，还没而非线性整数规划问题，还没有好的办法。有好的办法。例例1：一一登登山山队队员员
2、做做登登山山准准备备，他他需需要要携携带带的的物物品品有有：食食品品，氧氧气气，冰冰镐镐，绳绳索索，帐帐篷篷，照照相相机机和和通通讯讯设设备备，每每种种物物品品的的重重要要性性系系数数和和重重量量如如下下：假假定定登登山山队队员员可可携携带带最最大大重重量量为为25公公斤斤。问问如如何何携携带他能够受益最大？带他能够受益最大？序号序号序号序号1 12 23 34 45 56 67 7物品物品物品物品 食品食品食品食品 氧气氧气氧气氧气 冰镐冰镐冰镐冰镐 绳索绳索绳索绳索 帐篷帐篷帐篷帐篷 相机相机相机相机 设备设备设备设备重量重量重量重量5 55 52 26 612122 24 4重要重要重要
3、重要系数系数系数系数20201515181814148 84 41010解：解：如果令如果令xi=1表示登山队员携带表示登山队员携带物品物品i，xi=0表示登山队员不携带表示登山队员不携带物品物品i，则，则问题表示成问题表示成0-1规划规划:Max Z= 20x1+15x2 +18x3 +14x4 +8x5 +4x6 +10x7s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1或或xi=0 i=1,2,.7数学模型数学模型整数规划整数规划(IP)的一般数学模型的一般数学模型:Max (min) Z = cjxjs.t. aijxj bi(i=1,2
4、,m) xj 0 且部分或全部是整数且部分或全部是整数求解误区求解误区：先放弃变量的：先放弃变量的整数性要求，解一个线性规整数性要求，解一个线性规划问题，然后用划问题，然后用“四舍五入四舍五入”法取整数解，这种方法，法取整数解，这种方法，只有在变量的取值很大时，只有在变量的取值很大时，才有成功的可能性，而当变才有成功的可能性，而当变量的取值较小时，特别是量的取值较小时，特别是0-1规划时，往往不能成功。规划时，往往不能成功。例例2 求下列问题：求下列问题：Max Z=3x1+13x2s.t.2x1+9x2 40 11x1-8x2 82x1,x2 0,且取整数值且取整数值O 1 2 3 4 5
5、6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)AD可行域可行域OABD内整数点，放弃整数要求内整数点，放弃整数要求后，最优解后，最优解B(9.2,2.4) Z0=58.8，而原而原整数规划最优解整数规划最优解I(2,4) Z0=58，实际上实际上B附近四个整点附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规都不是原规划最优解。划最优解。O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)ADv假如能求出可行域的假如能求出可行域的“整点凸包整点凸包”（包含所有整点的
6、最小多边形（包含所有整点的最小多边形OEFGHIJ），），则可在此凸包上求线性则可在此凸包上求线性规划的解，即为原问题的解。但求规划的解，即为原问题的解。但求“整点凸包整点凸包”十分困难。十分困难。E EF FGGHHI IJ J2 分枝定界解法分枝定界解法（Branch and Bound Method)原问题的松驰问题：任何整数规原问题的松驰问题：任何整数规划（划（IP），），凡放弃某些约束条件凡放弃某些约束条件（如整数要求）后，所得到的问（如整数要求）后，所得到的问题（题（P） 都称为（都称为（IP）的松驰问题。的松驰问题。 最通常的松驰问题是放弃变最通常的松驰问题是放弃变量的整数性要求
7、后，（量的整数性要求后，（P）为线性为线性规划问题。规划问题。 分枝定界法步骤分枝定界法步骤一般求解对应的松驰问题，可能一般求解对应的松驰问题，可能会出现下面几种情况：会出现下面几种情况：若所得的最优解的各分量恰好是若所得的最优解的各分量恰好是整数，则这个解也是原整数规划整数，则这个解也是原整数规划的最优解，计算结束。的最优解，计算结束。 分枝定界法步骤分枝定界法步骤一般求解对应的松驰问题，可能一般求解对应的松驰问题，可能会出现下面几种情况：会出现下面几种情况：若所得的最优解的各分量恰好是若所得的最优解的各分量恰好是整数，则这个解也是原整数规划整数，则这个解也是原整数规划的最优解，计算结束。的
8、最优解，计算结束。若松驰问题无可行解，则原整数若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分若松驰问题有最优解，但其各分量不全是整数，则这个解不是原量不全是整数，则这个解不是原整数规划的最优解，转下一步。整数规划的最优解，转下一步。若松驰问题有最优解，但其各分若松驰问题有最优解，但其各分量不全是整数，则这个解不是原量不全是整数，则这个解不是原整数规划的最优解，转下一步。整数规划的最优解，转下一步。从不满足整数条件的基变量中任从不满足整数条件的基变量中任选选 一个一个xl进行分枝，它必须满足进行分枝，它必须满足xl xl 或或
9、xl xl +1中的一个，把这中的一个，把这两个约束条件加进原问题中，形两个约束条件加进原问题中，形成两个互不相容的子问题（两分成两个互不相容的子问题（两分法）法）。定界：把满足整数条件各分枝的定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。用它来判断分枝是保留还是剪枝。定界：把满足整数条件各分枝的定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优
10、的界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查分枝全剪掉，直到每个分枝都查清为止。清为止。例例3用分枝定界法求解：用分枝定界法求解：Max Z=4x1+3x2s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数整数用单纯形法可解得相应的松驰问题用单纯形法可解得相应的松驰问题的最优解（的最优解（6/5，21/10）Z=111/10为各分枝的上界。为各分枝的上界。0 1 2 3 44 3 2 1x1x2分分分分枝：枝：枝：枝：X X1 1 1,x 1,x1 1 2 2P P1 1P P2 2两个子问题：两个子问题：（P1）Max Z=4x1+3x2 s.t. 3x1
11、+4x2 12 4x1+2x2 9 x1,x2 0 ， x1 1 ，整数整数用单纯形法可解得相应的用单纯形法可解得相应的（P1）的的最优解（最优解（1，9/4） Z=10(3/4)（P2）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ， x1 2 ，整数整数用单纯形法可解得相应的用单纯形法可解得相应的（P2）的的最优解（最优解（2，1/2） Z=9(1/2)0 1 2 3 44 3 2 1x1x2再对（再对（再对（再对（P P1 1）分枝：分枝：分枝：分枝：X X1 1 1 1（P P3 3） x x2 2 2 2 （P P4 4） x x2
12、2 3 3P P1 1P P2 2P P3 3P P4 4（P1）两个子问题：两个子问题：（P3）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x x2 2 2 2整数整数用单纯形法可解得相应的用单纯形法可解得相应的（P3）的的最优解（最优解（1，2） Z=10（P1）两个子问题：两个子问题：（P4）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x x2 2 3 3整数整数用单纯形法可解得相应的用单纯形法可解得相应的（P4）的的最优解（最优解（0，3） Z=9X1 2
13、X2 2X1 1X2 3P1:(1,9/4)Z=10(3/4)P4: (0,3) Z=9P2:(2,1/2) Z=9(1/2)P3: (1,2) Z=10P:(6/5,21/10) Z=111/10原问题的最优解原问题的最优解（1，2） Z=10例例4用分枝定界法求解：用分枝定界法求解：Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数整数用单纯形法可解得相应的松驰问题用单纯形法可解得相应的松驰问题的最优解（的最优解（10/3，4/3）Z=26/3为各为各分枝的下界。分枝的下界。 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p
14、0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p选选选选 x x1 1进行分枝：进行分枝：进行分枝：进行分枝： (P(P1 1) x) x1 1 3 3(P(P2 2) ) x x1 1 4 4 为空集为空集为空集为空集P1（P1）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数整数用单纯形法可解得用单纯形法可解得（P1）的最优解的最优解（3，3/2）Z=9（P2）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数整数无可行解。无可行解。 0 1 2 3 4 5 6
15、 8 7 6 5 4 3 2 1x1x2p对对对对(P(P1 1) x) x1 1 3 3 选选选选 x x2 2进行分枝：进行分枝：进行分枝：进行分枝： (P(P3 3) x) x2 2 1 1无可行解无可行解无可行解无可行解 (P(P4 4) ) x x2 2 2 2P4（P3）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数整数无可行解。无可行解。（P4）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数整数用单纯形法可解得用单纯形法可解得（P4）的最优解
16、的最优解（2，2）Z=10X1 4X2 1X1 3X2 2P1:(3,3/2)Z=9P4:(2,2) Z=10P2:无可行解无可行解P3:无可行解无可行解P:(10/3,4/3) Z=26/3原问题的最优解原问题的最优解（2，2） Z=10v3、0-1型整数规划 0-1型整数规划是整数规划中的特殊情形，它的变量仅取值0或1。在本节我们先介绍引入0-1变量的实际问题，再研究其解法隐枚举法。一、引入0-1变量的实际问题 1、相互排斥的变量 2、相互排斥的约束条件 3、关于固定费用的问题二、0-1型整数规划的解法-隐枚举法指指 派派 问问 题题w在生活中经常遇到这样的问题，某单位需完成n项任务,恰好有n个人可承担这些任务。由于每人的专长不同，个人完成任务不同，效率（或所费时间）也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最少）。这类问题称为指派问题或分派问题，它是0-1规划的特例例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种德说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少？ 任务人员 EJGR甲 2 15 13 4乙 10 4 14 15丙 9 14 16 13丁 7 8 11 9
