运筹学第5章整数规划ppt课件.ppt

《运筹学第5章整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter5整数规划(IntegerProgramming)整数规划问题的提出分支定界法割平面法0-1整数规划指派问题本章主要内容：1第一节.整数规划问题的提出一、整数规划的一般形式1、实例：例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：货物体积每箱（米3）重量每箱（百斤）利润每箱（百元）甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？2A(4.8,0)0X1X2B(4,1)①②③④⑤设x1、x2为甲乙两种货物托运的箱数。(非负整数)不考虑x1、x2取整数的

2、约束，线性规划的可行域如图中的阴影部分，最优解为3若将（x1=4.8，x2=0）凑整为（x1=5，x2=0），显然已不满足约束条件，②>25。若将（x1=4.8，x2=0）凑整为（x1=4，x2=0），是可行解，但是否最优呢？当（x1=4，x2=0），Z＝80。向原点平行移动目标函数的等值线，第一次遇到“＋”的B点，即为最优解。(“＋”的点表示可行的整数解。)当（x1=4，x2=1），Z＝90，更优。42、整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。5纯整数规划

3、(全整数规划)：所有变量要求取非负整数。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。63、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。7例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。8用解法求出最优解x1＝3/2,x2

4、=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图9因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法割平面法对于特别的0－1规划问题采用隐枚举法和匈牙利

5、法。10基本思想:第二节分枝定界解法首先，不考虑变量的整数约束，求解相应的线性规划，得到线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。如果线性规划的最优解中至少有一个变量不是整数，选择其中一个将线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，叫做“分枝”。分枝过程得到的整数解中，目标函数值最大的一个叫做整数规划目标函数值的“下界”。分枝过程中非整数的线性规划的最优解，如果目标函数值小于或等于这个“下界”，就停止继

6、续分枝。这个过程，叫做“定界”。11步骤1：用单纯形法求解线性规划问题，得到最优解及最优值。步骤2：分枝。例2解整数规划问题41/9>10/3,优先选择B1分枝。12无可行解61/14(B12)>10/3(B2),优先选择B12分枝。134>10/3，所以B2无需分枝。14(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分

7、枝标明求解的结果。分支定界法的步骤(1)用观察法求整数规划原问题的一个可行解，其目标值便是R的最优目标值z*的一个下界z。(2)求解与R对应的线性规划问题R0，若R0无可行解，则R也无可行解，结束；若得到R0的最优解x0和最优值z0。若x0符合R的整数条件，则显然x0也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是R的最优目标值的一上界。15(4)定界。在各分枝中找出目标函数值最大者作为新的上界；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。(5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则

8、剪掉这一枝（用打×表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。16解求相应的线性规划B例2求解A17线性规划B的最优解X*=(4.81,1.82)