资源描述：
《运筹学第五章整数规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第五章整数规划主要内容：1、分枝定界法；2、割平面法;3、0—1型整数规划：4、指派问题。重点与难点：分枝定界法和割平而法的原理、求解方法，0—1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。要求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。§1问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP）O如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变暈要求为整数，称为混合整数规划。例1求解下列整数规划问题maxz=20%!+10x25x{+4兀2<242“+5x2<13xpx2>0、兀
2、］宀为整数如果不考虑整数约朿，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：—4.89%2=°9maxz=96o用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（兀1=4,兀2=1）吋得最优解为坷=4,尤2=1，最优值为z=90o市上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下而介绍几种常用解法。§2分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A,1JZ相应的线性*—规划问题B,
3、从解B开始，若其最优解不符合A的整数条件，那么B的最优值必是A的最优值Z的上界，记为Z；*7而A的任意可行解的11标函数值是Z的一个下界d,采取将B的可行域分枝的方法，逐步减少z和增人&，最终求得现举例说明:例2求解Amaxz=40xj+90兀2①9%)+7兀2556②7兀]+20兀2<70③%],Eno坷,兀2为整数⑤解：先不考虑条件⑤，即解相应的线性规划B（①-④），得最优解兀1=4.81,X2=1-82,—356（见下显然，它不符合整数条件⑤。这时，勺为问题A的最优值/的上界，记Z=Z（），而%,=0,勺=0显然是问题A的一个整数可行解，这时z=0,是/的一个下界，记&=o,
4、即05/5256。分枝定界法的解法，首先注意其屮一个非整数变量的解，如州，在B小西=4.81,于是对原问题增加两个约束条件:x,<4>x,>5,可将原问题分解为两个子问题Q、B2（即两枝），给每枝增加一个约束条件,如图。76543不考虑整数条件解问题d、得到最优解:2问题d问题场知=349乙=341X]=4X]=5x2=2.1=1.57—昭然未得到全部变量是整数解，T>乙2,/.将Z改为349（*349）,0?2，/•先分解为两枝，增加条件兀2-2的问题称为“3；增加条件兀2>3的问题称为B4。在上图中再去掉兀2>2与兀2V3之间
5、的可行域，再求解问题'B,其结果列在下图中，可见问题$3的解已都是整数，它的口标函数值乙3=340,取&=340,*而它大于z4=327,所以再分解B4已无必要，而问题B2的z2=341，所以Z可能在3402问题禺问题垓x}=5.44—1Z5=308无可行解z-340-I-山以上解题过程可得到分枝定界法的求解步骤:1.给定原问题的初始上界z解与原问题A相应的线性规划问
6、题B,可能出现以下情况之一:①B没有可行解，这时A也没有可行解，则停止；②B有最优解，并符合A的整数条件，B的最优解即为A的最优解，则停止;③B有最优解，但不符合A的整数条件，记它的目标函数值勺为壬。2.给定原问题的初始下界&用观察法找出问题A的一整数可行解，一般取=0,7=1,2,---,/1o求得其目标函数值，记作这样，就有3.分枝在B的最优解屮任选一个不符合整数条件的变量厂，其值为巧，以［巧］表示小于巧•的最大整数，构造两个约束条件：Xjs［巧］和厂n［巧］+1并将其分别加入问题B,求两个后继规划问题d'B?,不考虑整数条件，解这两个后继问题。4.定界(修改上、下界)以每个后
7、继问题为一•分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界Z，从己符合幣数条件的各分支中，找出目标函数值的最大者作为新的下界2。5・比较与剪枝各分枝的最优目标函数值中若有小于莖者，则剪掉这枝，以后不再考虑了，若大于Z，口不符合整数条件，则继续分枝直到得到/=&为止，求得最优整数解兀;(j=l,2,---,/t)o§3割平面法这个方法的基础仍是用解线性规划的方法去解整数规划问题，首先不考虑变量x,•是整数这个条件，但增加线性约束条件（用
