Lecture 7 整数规划

《Lecture 7 整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整数规划华南理工大学模具研究室mesjzhang@scut.edu.cn在线性规划问题的讨论中，有些最优解是小数，但某些常要求最优解是整数（即整数解）,如决策变量是：机器的台数、人数、车辆数等等整数规划模型线性规划和整数规划的关系对IP问题，可能会认为，只要求出不受整数约束的解，然后“舍入化整”，就可得到整数最优解？对吗？上例得到的启示１：（１）化整后未必是可行解（２）即使是可行解，也未必是最优解（３）即使该方法结果可以得到最优解，但如果有n个决策变量，则取舍方案有２n种。当n=60时，260约等于1018，

2、这使计算机也难以实现。所以，有必要讨论整数规划的求解方法。启示２：（１）是否能在LP的约束区域中切去几块不含整数解的可行域，使整数解作为顶点，这样求LP问题的最优解，即为整数解。如前例，增加约束x2≤3，则LP问题的最优解，即为x1=5,x2=3,Zmax=17，就是IP问题的解。（２）在LP的可行域中，整数点不多时（12个），是否可以用穷举法。割平面法1959年，R.E.Gomory首先提出，从此使IP逐渐形成为一个独立的运筹学分支。其实质是用解LP问题的方法来解IP问题。基本思想是：通过对LP问题的求解，如果最

3、优解X*是整数解，则就是IP的解。不是整数解，设法对LP问题增加约束（割平面），把LP的可行域中去掉不含整数解的一部分，再求LP问题。反复进行，直到求得最优解割平面法的关键在于如何寻找适当的切割约束条件（即构造一个割平面），且保证切掉的部分不含有整数解。但由于用割平面法求解IP问题常常会遇到收敛很慢的情况。所以用它来求解IP问题的仍然不多，但在理论上是重要的。序号bcBxBx1x2x3x4(a)0x3211050x4-4*101-2检验数-1-1000(b)0x111/21/205/21x403218检验数0-1/

4、21/205/2(c)1X1101/6-1/67/61x2012/31/38/3检验数005/61/623/6序号bcBxBx1x2x3x4x5(a)1x2012/31/308/31x1101/6-1/607/60x500-2/3-1/3*1-2/3检验数005/61/6023/6(b)1x20100121x1101/20-1/23/20x40021-32检验数001/201/27/2注意：此处需要用对偶单纯形法求解分枝定界法（BranchandBoundmethod）如果通过对全体可行的整数解，逐个比较优劣，得

5、到最优解的方法，称为完全枚举法（穷举法）。但在解的个数很多时，这往往是不可能的。如果能通过仅对部分可行整数解的讨论，就得到原问题的最优解，称为部分枚举法或隐枚举法。分枝定界法就是一种隐枚举法，这是一种应用很广的求解方法。分枝定界法是求解整数规划的一种常用的有效方法，它不仅能针对纯整数规划问题求解，也能对混合整数规划问题求解.先给出它的一般思想：松弛问题的提出考察这样的问题其中S是有限集设A,B是两个有限集，且f(x)是定义在B上的函数，优化模型：称问题(2)是问题(1)的松弛问题。显然(2)的最优值小于等于问题(1

6、)的最优值。问题(2)的搜索范围大，所以(2)的求解更难一些？看一个生活中的例子：B—全国100m跑运动员全体A—全国18岁的百米运动员全体问题(2)很易解决，只需查一下全国记录就知道了。但问题(1)确难多了。先假设对某个最优化问题（1）(min)已找到一个容易解决的松弛问题(2),设x0是(2)的最优解，其最优解z0=f(x0).１、如果　　　　则问题(1)也解决了２、否则，至少可知问题(1)的最优值z1一定≥z0.即给出了问题(1)的一个下界所以解决问题(2)总是有好处的。求解过程0-1规划如果线性规划中的所有

7、变量的取值只能取0、1，则这类线性规划问题是一种特殊的整数规划问题，我们把它称为0-1规划，把只能取0或1值的变量称为0-1变量。主要求解方法：（过滤性隐枚举法）过滤性隐举法基本思想是：首先将全部变量取0或1的所有组合列出，然后再逐个检查这些组合（解）是否可行的过程中，利用增加并不断修改过滤条件的办法，减少计算量，达到求出最优解的目的。