管理学第3章整数规划课件

第3章整数规划ILP问题的概述1第3章整数规划ILP问题的概述1整数规划概述在线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或带有小数点的实数。但对于某些具体的问题，常要求最优解是整数的情形。例如，所求的解是机器台数，完成工作的人数或装货的车数等，这时，分数或小数的解答就不符合要求。为了满足整数解的要求，初看起来，似乎只要把已求得的解经过“舍入化整”就可以，但这常常是不可行的。（因为化整后不见得是可行解。或虽然是可行解，但不一定是最优解。）2整数规划概述在线性规划问题中，所有的解都假设为具有连续型的数整数规划概述求最优整数解的问题，称为整数规划(IntegerProgramming)，简称为IP。整数规划中，如果所有的变量都要求是非负整数，就称为纯整数规划(PureIntegerProgramming)或全整数规划(AllIntegerProgramming)。如果仅是其中一部分变量取值为整数，则称为混合整数规划(MixedIntegerProgramming)。如果变量只取0或1，则称为0-1规划。由于变量限制为整数实质上一个非线性约束，如0、1限制，因此：整数规划问题的求解要比一般的线性规划困难得多。3整数规划概述求最优整数解的问题，称为整数规划(Intege3.1整数线性规划问题整数规划是一类要求变量取整数值的数学规划。对于两个变量的整数规划，可以用图解法，但对于一般的整数规划问题，则需要专门的方法：割平面法、分枝定界法、(隐枚举法、匈牙利法)。本章的讲解将从图解法开始，引出若干个启示后，再学习专门的方法。43.1整数线性规划问题整数规划是一类要求变量取整数值的数3.1.1整数规划的典型问题举例投资决策问题某部门在今后五年中可用于投资的资金额为B万元，有n(n

2)个项目，假定每个最多投资一次，第j个项目需资金bj万元，将会获利cj万元，问如何投资使总利润最大。承建宿舍问题某建筑公司建两类宿舍，甲占地0.25

103(m2)，乙占地0.25

103(m2)，已购进地3

103(m2)。计划甲不超过8幢，乙不超过4幢，问如何建使获利最大？旅行售货员问题一推销员从v0出发，再遍访v1,v2,…,vn各一次，再返回v0。从vi到vj的差旅费为cij，如何使总费用最小。背包问题等53.1.1整数规划的典型问题举例投资决策问题5例1：某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备需要A、B两种材料的消耗以及资源的限制，如右表。问题：工厂应分别生产多少件甲、乙种仪器设备才能使工厂获利最多？解：目标函数：Maxz=x1+x2约束条件：s.t.3x1+2x2≤102x2≤5x1，x2≥0为整数不考虑整数约束得到最优解：x1=1.667，x2=2.5；z=4.167考虑整数约束得到最优解：x1=2，x2=2；z=4整数规划的最优目标值小于相应线性规划的最优目标值(相当于附加一个约束)3.1.2图解法求解及启示6例1：某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知例2：某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x2s.t.5x1+4x2≤242x1+5x2

≤13x1,x2

≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解整数规划图解法x11234567231BAx2B（4，1）才是IP的最优解7例2：某集装箱运输公司，箱型标准体积24m3，重量13T,现图解法的启示整数规划与一般线性规划之间有联系，一般我们称不加上整数约束的问题为对应整数规划问题的松弛问题。其解也有联系：两者之间的解不能简单的通过取整得到。如例2：A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解，因此纯整数规划的可行解就是可行域中的整数点；非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化整数规划的最优目标值小于相应对于求最大问题，整数规划的最优目标值小于相应线性规划的最优目标值，对于求最小问题，线性规划的最优目标值是对应整数规划的下界。如果一般线性规划无解，则对应的整数规划也无解8图解法的启示整数规划与一般线性规划之间有联系，一般我们称不加3.1.3：整数规划的模型例3：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。问该队员应如何选择？序号1234567物品食品氧气冰镐绳索帐篷相机通讯重量55261224重要系数20151814841093.1.3：整数规划的模型序号1234567物品食品氧气冰镐请大家试着建立该题的模型！10请大家试着建立该题的模型！10解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6

+4x7

25xi=1或xi=0i=1,2,….711解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队例4：背包问题(KnapsackProblem)一个旅行者，为了准备旅行的必须用品，要在背包内装一些最有用的东西，但有个限制，最多只能装b公斤的物品，而每件物品只能整个携带，这样旅行者给每件物品规定了一个“价值”以表示其有用的程度。如果共有n件物品，第j件物品aj公斤，其价值为cj。问题变成:在携带的物品总重量不超过b公斤条件下，携带哪些物品,可使总价值最大?12例4：背包问题(KnapsackProblem)12解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划：MaxZ=Σcjxjs.t.Σajxj

b

xj=0或1，j=1,…,n13解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，整数规划问题的数学模型整数规划(IP)的一般数学模型:max(min)Z=Σcjxjs.t.Σaijxj

bi(i=1,2,…m)xj

0且部分或全部是整数14整数规划问题的数学模型14整数规划问题的求解方法3.2Gomory割平面法3.3分枝定界法15整数规划问题的求解方法3.2Gomory割平面法15解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。16解法概述16设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。17设想计算机每秒能比较1000000个方式，那么要比较完20!先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。18先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入例求下列问题：MaxZ=3x1+13x2s.t.2x1+9x2

4011x1-8x2

82x1,x2

0,且取整数值19例求下列问题：19O1234567891054321x1x2I(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)都不是原规划最优解。20O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。EFGHIJ21O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五个互不相交的子问题P1P2P3P4P5之和,P3P5的定义域都是空集,而放弃整数要求后P1最优解I(2,4),Z1=58P2最优解(6,3),Z2=57

P4最优解(98/11,2),Z4=52(8/11)

P1P2P422O1234X1

2X1

6X2

3X2

2X1

3X1

7X2

4X2

3P1P5P4P2P3P23X12X16X23X22X13假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。如果求出的解不是整数，我们采取一定的方法将其割去，再继续求解，直至判定无解或求解出来；

以上描述了目前解整数规划问题的两种基本途径。24假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求3.2割平面法253.2割平面法253.2割平面法

（CuttingPlaceApproach）松驰问题：任何整数规划（P），凡放弃某些约束条件（如整数要求）后，所得到的问题（P0）都称为（P）的松驰问题。解法：若P0有最优，且为整数，则P达最优；若P0有最优，但不为整，增加一个割平面条件；若P0无最优，则P无最优。263.2割平面法

（CuttingPlaceAppro割平面条件割平面条件：将由（P0）得到的非整数解恰在被割掉，而原来ILP的可行解（均为整数）都没有被割掉。割平面条件的数学原理见P88。然后得到LP问题（P1），再判断它的解。如此循环，直到找到最优整数解。27割平面条件割平面条件：将由（P0）得到的非整数解恰在被割掉，例：maxx2s.t.3x1+2x2

6-3x1+2x2

0x1，x2

0，整数-3x1+2x2

=6x1x20-3x1+2x2

=011223图解法：x2

=1x1

=x228例：maxx2-3x1+2x2=6x1x20-3.3分枝定界法

（BranchandBoundMethod）293.3分枝定界法

（BranchandBoun分枝定界法思想一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。30分枝定界法思想30若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。对松驰问题分解：31若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数分枝定界法步骤分枝：从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl

[xl]或xl

[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。32分枝定界法步骤32定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。33定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用例用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。34例用分枝定界法求解：用单纯形法可解得相应的松驰问题的最012344321x1x2分枝：X1

1,x1

2P1P23501两个子问题：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4)36两个子问题：36（P2）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

2，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)37（P2）MaxZ=4x1+3x237012344321x1x2再对（P1）分枝：X1

1（P3）x2

2（P4）x2

3P1P2P3P43801（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

2整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=1039（P1）两个子问题：39（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

3整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=940（P1）两个子问题：40X1

2X2

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=1041X12X22X11X23P1:(1,例用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。42例用分枝定界法求解：42

0123456

87654321x1x2p43012

0123456

87654321x1x2p选x1进行分枝：(P1)x1

3(P2)

x1

4为空集P144012（P1）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

3整数用单纯形法可解得（P1）的最优解（3，3/2）Z=945（P1）45（P2）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

4整数无可行解。46（P2）46

0123456

87654321x1x2p对(P1)x1

3选x2进行分枝：(P3)x2

1无可行解(P4)

x2

2P447012（P3）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

1整数无可行解。48（P3）48（P4）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

2整数用单纯形法可解得（P4）的最优解（2，2）Z=1049（P4）49X1

4X2

1X13X2

2P1:(3,3/2)Z=9P4:(2,2)Z=10P2:无可行解P3:无可行解P:(10/3,4/3)Z=26/3原问题的最优解（2，2）Z=1050X14X21X13X22P1:(3,3分枝定界法是求整数规划的一种常用的有效的方法，既能解决纯整数规划的问题，也能解决混合整数规划的问题。练习：Minf=-5x1-4x