运筹学第五章 整数规划 胡运权.ppt

《运筹学第五章 整数规划 胡运权.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学赵明霞山西大学经济与管理学院第五章整数规划整数规划的数学模型割平面法分支定界法0-1整数规划指派问题应用2021/7/2523求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数，则称为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规划问题。如果所有的变量都为0-1变量，则称之为0-1规划。2021/7/2534例5.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问

2、两种货物各托运多少件，可使获得利润最大?货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140第一节整数规划的数学模型2021/7/2545解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型Maxz=2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1，x2≥0为整数。如果去掉最后一个约束，就是一个线性规划问题。2021/7/2556得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值

3、为14。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=62021/7/2567性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。2021/7/25713/4,5/2松弛问题第一次切割4,1第二次切割x1+x2≤5第二节割平面法2021/7/258设纯整数规划伴随LP的最优解若全为整数，则为IP的最优解。否则，若不全为整数，设第r行基变量非整。对应方程为2021/7/2

4、59将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有2021/7/2510加入松弛变量此式称为以r行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题(伴随LP)的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则2021/7/2511割平面法，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整

5、数解，这个条件就是Gomory约束条件。Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。2021/7/2512例5-52021/7/2513cj3-1000XBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/700-5/70-3/7选择较大小数的行构造割平面2021/7/2514运筹学--线性规划--线性规划--线性规划cj3-10000XBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700

6、x6-6/700-1/70-2/7100-5/70-3/702021/7/2515运筹学--线性规划--线性规划--线性规划3x11100001-1x25/4010-1/40-5/40x35/2001-1/20-11/20x57/40001/41-3/4000-1/40-17/4cj3-10000XBbx1x2x3x4x5x62021/7/2516运筹学--线性规划--线性规划--线性规划分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。先求解整数规划的线

7、性规划问题(伴随LP)。如果其最优解不符合整数条件，则求出整数规划的上下界。增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝）再求解这些子区域上的线性规划问题。不断缩小整数规划上下界的距离，最后得整数规划的最优解。第三节　分枝定界法2021/7/251718用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：第一步：求解问题B，可得以下情况之一：1.B没有可行解，则A也没有可行解，求解过程停止。2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。3.B有最