![整数规划及分支定界法课件_第1页](http://file4.renrendoc.com/view/7c807103ce0b54a217eee97f08afc4f6/7c807103ce0b54a217eee97f08afc4f61.gif)
![整数规划及分支定界法课件_第2页](http://file4.renrendoc.com/view/7c807103ce0b54a217eee97f08afc4f6/7c807103ce0b54a217eee97f08afc4f62.gif)
![整数规划及分支定界法课件_第3页](http://file4.renrendoc.com/view/7c807103ce0b54a217eee97f08afc4f6/7c807103ce0b54a217eee97f08afc4f63.gif)
![整数规划及分支定界法课件_第4页](http://file4.renrendoc.com/view/7c807103ce0b54a217eee97f08afc4f6/7c807103ce0b54a217eee97f08afc4f64.gif)
![整数规划及分支定界法课件_第5页](http://file4.renrendoc.com/view/7c807103ce0b54a217eee97f08afc4f6/7c807103ce0b54a217eee97f08afc4f65.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章整数规划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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 学校食堂工作人员管理方案
- 2023年美容师(初级)考试题库及答案
- 勤思考研2021年对外经贸大学汉语国际教育硕士考研真题分析-0109
- 载荷试验承载力取值与试验方法探讨
- 哈尔滨市重点中学2025届初三3月质量检测试题试化学试题试卷含解析
- 户外徒步活动策划方案(共5篇)
- 小学四年级全学期体育与健康《踩高跷》教学设计
- 棉麻女装品牌管微单月涨粉6万营销策略
- 《工厂消防安全自查报告》-企业管理
- 蕉下服装天猫专卖店运营规划
- 2023-2024年《智能化系统维保合同样本范本 》
- 充换电站相关行业投资方案范本
- 小学防汛抢险演练方案
- 五年级数学思维训练校本课程纲要
- 中医医疗质量分析和持续改进
- 2024年山东省生态环境监测专业技术人员大比武竞赛考试题库(含答案)
- 5G 基站运行与维护 课件 3-0 初始5G基站系统
- 《无人机飞行安全及法律法规》教学大纲
- 2024年中国国电龙源电力集团股份有限公司招聘笔试参考题库含答案解析
- 健康体重知识课件
- 内科医师晋升副主任高级职称(老年患者心衰合并肺部感染病例分析专题报告)
评论
0/150
提交评论