北京交通大学经济管理学院SchoolicsandManagomentBoijingJiaotongUniversity整数规划的上界 乙：松弛问题的最优值整数规划的下界2：可行解的目标值求解一系列的线性规划问题，不断减小上界,增大下界，直至二者相等ZZ北京交通大学
整数规划的上界 ：松弛问题的最优值 整数规划的下界 ：可行解的目标值 求解一系列的线性规划问题, 不断减小 上界,增大下界, 直至二者相等
北京交通大学经济管理学院School of Econnics and ManagomentBojing Jiaotong UniversityMax z = a cjxj原问题A：j=1na aijx,=b;(i=1,L m)j=103(j=1,L ,n)x;(j=1,L ,n)Cn0Maxz= :a.cjX;j-1松弛问题B：na(i=1,L m)bajX;jl30x(i=lL .n)北京交通大学
原问题A： 松弛问题B：
北京交通大学经济管理学院本节内容提要nicsandManagomentshastonuny整数规划问题的提出分支定界解法重点小结北京交通大学
本节内容提要 整数规划问题的提出 分支定界解法 小结 重点
北京交通大学(枝)分支定界解法经济管理学院SchoolanagemenBojingJiaotongUniv(BranchandBoundMethod)设有最大化的IP问题A，与它相应的LP问题(也称松弛问题)记为Bo.从解问题B.开始若其最优解不符合A的整数条件，那么B.的最优目标函数必是A的最优目标函数的上界同时,A的任意可行解的目标函数值将是最优目标函数的一个下界(定界)分支定界法就是将B.的可行域分成子区域的方法,逐步减小上界和增大下界,最终求到最优值（分支）北京交通大学
分支（枝）定界解法 ( Branch and Bound Method ) 设有最大化的IP问题A, 与它相应的LP问题 (也称松弛问题)记为B0 . 从解问题B0开始, 若其最优解不符合A的整数条件, 那么B0的 最优目标函数必是A的最优目标函数的上界. 同时,A的任意可行解的目标函数值将是最 优目标函数的一个下界.(定界) 分支定界法就是将B0的可行域分成子区域 的方法,逐步减小上界和增大下界,最终求 到最优值.(分支)
BX2Max z = 40x +90x2z=0=1.82x,=4.81i9x + 7x256Zo=35617 xi + 20x2 ± 70A例 2Xx,41B,Bx301xi=5.00 x,=1.57x,=4.00 x2=2.10ixi x,整数Z=0Z,=341171=349解：Xi=0，X2=0 是A的一个可行解，z= 0.,=569x,+7xMaxz40x,90x240x,+90x9x7x56(4.81,1.87x20x707x,+20x,=70X， X 0B.的最优解为x,=4.81,x,=1.82.zo=356,不是A的可行解
(4.81,1.8 2) 9x1+7x2 =56 7x1+20x2 =70 z=40x1+90x 2 B0的最优解为x1 =4.81, x2 =1.82, z 0 =356, 不是A的可行解. x1 =5.00 x2 =1.57 B1 x1 =4.00 x2 =2.10 z1=349 x14 x15 z2=341 B2 z =0 B x1 =4.81 x2 =1.82 z0=356 z =0