运筹学电子课件 第8章 整数规划.ppt

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

1、OPERATIONSRESEARCH运筹学——如何把事情做得最好OR31第八章整数规划本章要求理解整数规划的含义整数规划问题的计算机求解掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法整数规划的应用OR32８.１整数规划问题的提出决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整

2、数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。OR33问题举例例１：某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解OR34整数规划图解法x2x11234567231BAOR35图解法的启

3、示A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划的可行解就是可行域中的整数点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解OR36８.２分枝定界法思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解例２.maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解：先不考虑整数要求，解相应的LP问题（松弛问题），得：x1=4.8x2=0Z=9600不是可行解Z=9600是IP问题的上界，记为：Z

4、=9600OR37分枝定界法（续）X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1≤4和x1≥5原问题分解为两个maxZ=2000x1+1000x2maxZ=2000x1+1000x25x1+4x2≤245x1+4x2≤242x1+5x2≤13(IP1)2x1+5x2≤13(IP2)x1≤4x1≥5x1.x2≥0且为整数x1.x2≥0且为整数OR38分枝定界法（续）不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记为Z=9000٭由于目前的分枝末梢

5、最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000OR39分枝定界法一般步骤：(1)、(A),先解(A)的松弛问题(B)(2)、①(B)无可行解→(A)无可行解。②(B)最优解符合(A)要求，停。③(B)最优解不符合(A)要求，记目标函数值为Z1，转(3)。(3)、确定Z*的上下界：上界Z=Z1；估整数解Z，作下界(4)、选(B)解中最远离整数要求的分量Xj(Xj=bj)分枝，作(B)的后续问题(B1)、(B2)。(C)：(B）加约束Xj[bj](D)：(B)加约束Xj[bj]+1OR310(5)、解(B1)

6、、(B2)，修改Z*的上下界：取B1、B2最优目标函数值的最大值作为新的上界；用观察法取B1、B2中各一整数可行解，并选其中较大的目标函数值作为新的下界(6)、比较与剪枝，直至Z=Z剪枝条件：①(B1)，(B2)无可行解②(B1)，(B2)对应的目标值Z’Z③(B1)，(B2)对应的目标值Z’>ZOR311maxZ=40X1+90X29X1+7X2567X1+20X270X1,X20X1,X2为整数例３：OR312解：先解(1)的松弛问题X*=4.8091.817Z1*=355.890Z=355.890，Z=290选X1分枝问题(2)(1)X14问题(3)(1)X15O

7、R313选(2)继续分枝问题(4)(2)X22问题(5)(2)X23解为X1=4X2=2.1Z2=349.0解为X1=5X2=1.571Z3=341.39Z=349，Z=340OR314(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283327.12(6)5.4441307.76(7)无解X14X15X22X21X22X23OR315８.３0—1规划问题某些特殊问题，只做是非选