整数规划及分支定界法课件

第三章整数规划1ppt精选版第三章整数规划1ppt精选版3-1整数规划问题

整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。

根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。

2ppt精选版3-1整数规划问题2ppt精选版

整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。3ppt精选版整数规划是数学规划中一个较弱的分支，目前只能解中等规例3-1：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。4ppt精选版例3-1：一登山队员做登山准备，他需要携带的物品有：食品，氧5ppt精选版5ppt精选版解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4

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

xj=0或18ppt精选版解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，数学模型整数规划(IP)的一般数学模型:Max(min)Z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整数9ppt精选版数学模型9ppt精选版解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。10ppt精选版解法概述10ppt精选版设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。11ppt精选版设想计算机每秒能比较1000000个方式，那么要比较完20!先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。12ppt精选版先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入例3-3求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值13ppt精选版例3-3求下列问题：13ppt精选版O1234567891054321x1x2I(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)都不是原规划最优解。14ppt精选版O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。EFGHIJ15ppt精选版O1234O1234567891054321x1x2I(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)

P1P2P416ppt精选版O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P17ppt精选版X12X16X23X22X13假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。以上描述了目前解整数规划问题的两种基本途径。18ppt精选版假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求分枝定界解法（BranchandBoundMethod)原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。19ppt精选版分枝定界解法19ppt精选版最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。20ppt精选版最通常的松驰问题是放弃变量的整数性要求后，（P）为线分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。21ppt精选版分枝定界法步骤21ppt精选版若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl

[xl]或xl

[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。22ppt精选版若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数定界：把满足整数条件各分枝的最优目标函数值作为上（max）（下(min)）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。23ppt精选版定界：把满足整数条件各分枝的最优目标函数值作为上（max）（例5-6用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20且为整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10），Z=111/10为各分枝的上界。24ppt精选版例5-6用分枝定界法求解：24ppt精选版012344321x1x2分枝：X11,x12P1P225ppt精选版01两个子问题：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

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

3x1+4x2124x1+2x29x1,x20，x1

2，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)27ppt精选版（P2）MaxZ=4x1+3x227ppt精选版012344321x1x2再对（P1）分枝：X11（P3）x22（P4）x23P1P2P3P428ppt精选版01（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=1029ppt精选版（P1）两个子问题：29ppt精选版（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=930ppt精选版（P1）两个子问题：30ppt精选版X12X2

2X11X23P1:(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=1031ppt精选版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20且取整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3），Z=26/3为各分枝的下界。32ppt精选版例5-7用分枝定界法求解：32ppt精选版

0123456

87654321x1x2p33ppt精选版012

0123456

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

3(P2)

x14为空集P134ppt精选版012（P1）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13整数用单纯形法可解得（P1）的最优解（3，3/2）Z=935ppt精选版（P1）35ppt精选版（P2）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20x14整数无可行解。36ppt精选版（P2）36ppt精选版

0123456

87654321x1x2p对(P1)x13选x2进行分枝：(P3)x21无可行解(P4)

x22P437ppt精选版012（P3）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13，x21整数无可行解。38ppt精选版（P3）38ppt精选版（P4）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13，x22整数用单纯形法可解得（P4）的最优解（2，2）Z=1039ppt精选版（P4）39ppt精选版X14X21X13X22P1:(3,3/2)Z=9P4:(2,2)Z=10P2:无可行解P3:无可行解P:(10/3,4/3)Z=26/3原问题的最优解（2，2）Z=1040ppt精选版X14X21X13X22P1:(3,3第三章整数规划41ppt精选版第三章整数规划1ppt精选版3-1整数规划问题

整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。

根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。

42ppt精选版3-1整数规划问题2ppt精选版

整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。43ppt精选版整数规划是数学规划中一个较弱的分支，目前只能解中等规例3-1：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。44ppt精选版例3-1：一登山队员做登山准备，他需要携带的物品有：食品，氧45ppt精选版5ppt精选版解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4

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

xj=0或148ppt精选版解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，数学模型整数规划(IP)的一般数学模型:Max(min)Z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整数49ppt精选版数学模型9ppt精选版解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。50ppt精选版解法概述10ppt精选版设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。51ppt精选版设想计算机每秒能比较1000000个方式，那么要比较完20!先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。52ppt精选版先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入例3-3求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值53ppt精选版例3-3求下列问题：13ppt精选版O1234567891054321x1x2I(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)都不是原规划最优解。54ppt精选版O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。EFGHIJ55ppt精选版O1234O1234567891054321x1x2I(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)

P1P2P456ppt精选版O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P57ppt精选版X12X16X23X22X13假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。以上描述了目前解整数规划问题的两种基本途径。58ppt精选版假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求分枝定界解法（BranchandBoundMethod)原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。59ppt精选版分枝定界解法19ppt精选版最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。60ppt精选版最通常的松驰问题是放弃变量的整数性要求后，（P）为线分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。61ppt精选版分枝定界法步骤21ppt精选版若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl

[xl]或xl

[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。62ppt精选版若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数定界：把满足整数条件各分枝的最优目标函数值作为上（max）（下(min)）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。63ppt精选版定界：把满足整数条件各分枝的最优目标函数值作为上（max）（例5-6用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20且为整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10），Z=111/10为各分枝的上界。64ppt精选版例5-6用分枝定界法求解：24ppt精选版012344321x1x2分枝：X11,x12P1P265ppt精选版01两个子问题：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

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

3x1+4x2124x1+2x29x1,x20，x1

2，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)67ppt精选版（P2）MaxZ=4x1+3x227ppt精选版012344321x1x2再对（P1）分枝：X11（P3）x22（P4）x23P1P2P3P468ppt精选版01（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=1069ppt精选版（P1）两个子问题：29ppt精选版（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=970ppt精选版（P1）两个子问题：30ppt精选版X12X2

2X11X23P1:(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=1071ppt精选版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20且取整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3），Z=26/3为各分枝的下界。72ppt精选版例5-7用分枝定界法求解：32ppt精选版

0123456

87