第五章整数规划

《第五章整数规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案第五章整数规划主要内容：1、分枝定界法；2、割平面法；3、0－1型整数规划；4、指派问题。重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。要求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。§1问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。例1求解下列整数规划问题如果不考虑整数约束，就是一个线性规划问题（称这样的问题为

2、原问题相应的线性规划问题），很容易求得最优解为：。精彩文档实用标准文案用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（）时得最优解为x2３２+１++++０１２３４５６７x，最优值为z=90。由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。§2分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A，与之相应的线性规划问题B，从解B开始，若其最优解不符合A的整数条件，那么B的最优值必是A的最优

3、值的上界，记为；而A的任意可行解的目标函数值是的一个下界，采取将B的可行域分枝的方法，逐步减少和增大，最终求得。现举例说明：①②③④⑤例2求解A精彩文档实用标准文案解：先不考虑条件⑤，即解相应的线性规划B（①--④），得最优解4.81,1.82,356（见下图）。87654321012345678910显然，它不符合整数条件⑤。这时，为问题A的最优值的上界，记，而0,0显然是问题A的一个整数可行解，这时z=0，是的一个下界，记，即。分枝定界法的解法，首先注意其中一个非整数变量的解，如，在B中=4.81，于是对原问题增加两个约束条件：，可将原问题分解为两个子问题（即两枝

4、），给每枝增加一个约束条件，如图。8765问题B14问题B2321012345678910不考虑整数条件解问题得到最优解：问题问题34943415精彩文档实用标准文案2.11.57显然未得到全部变量是整数解，，将改为349（=349），。继续对问题进行分解，，先分解为两枝，增加条件的问题称为；增加条件的问题称为。在上图中再去掉与之间的可行域，再求解问题，其结果列在下图中，可见问题的解已都是整数，它的目标函数值，取=340，而它大于，所以再分解已无必要，而问题的，所以可能在之间有整数解，于是再对分解，得问题，为非整数解，且，问题为无可行解，于是可断定：，为最优整数解。问

5、题4.811.82356问题问题精彩文档实用标准文案42.134951.57341问题问题423401.423327问题问题5.441308无可行解由以上解题过程可得到分枝定界法的求解步骤：1.给定原问题的初始上界解与原问题A相应的线性规划问题B，可能出现以下情况之一：①B没有可行解，这时A也没有可行解，则停止；②B有最优解，并符合A的整数条件，B的最优解即为A的最优解，则停止；③B有最优解，但不符合A的整数条件，记它的目标函数值为。2.给定原问题的初始下界用观察法找出问题A的一整数可行解，一般取。求得其目标函数值，记作。这样，就有。3.分枝在B的最优解中任选一个不符

6、合整数条件的变量，其值为，以[]表示小于的最大整数，构造两个约束条件:和并将其分别加入问题B，求两个后继规划问题，不考虑整数条件，解这两个后继问题。4.定界（修改上、下界）精彩文档实用标准文案以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值的最大者作为新的下界。5.比较与剪枝各分枝的最优目标函数值中若有小于者，则剪掉这枝，以后不再考虑了，若大于，且不符合整数条件，则继续分枝直到得到为止，求得最优整数解。§3割平面法这个方法的基础仍是用解线性规划的方法去解整数规划问题，首先不考

7、虑变量是整数这个条件，但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。例3求解①②③④⑤如不考虑条件⑤，求得相应的线性规划的最优解：就是图中可行域R的极点A，不符合整数条件。x2A1C(1,1)R01x1x2AD1C(1,1)R/01x1将原问题化为标准型精彩文档实用标准文案不考虑整数条件，用单纯形法求解相应线性规划的最优解。初始表1100CBX