运筹学第五章--整数规划设计-胡运权.pptx

运筹学赵明霞山西大学经济与管理学院第五章 整数规划整数规划的数学模型割平面法分支定界法0-1整数规划指派问题应用求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数，则称为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规划问题。如果所有的变量都为0-1变量，则称之为0-1规划。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲运限制1365140?第一节 整数规划的数学模型例5.1 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大?解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 Max z = 2x1 +3 x2 s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2≥ 0为整数。如果去掉最后一个约束，就是一个线性规划问题。x2 2x1+3x2 =14.66322x1+3x2 =1413412x1 2x1+3x2 =6得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。第一次切割x1+x2≤54,1第二次切割第二节 割平面法13/4,5/2松弛问题设纯整数规划伴随LP的最优解若 全为整数，则为IP的最优解。否则，若不全为整数，设第r行基变量 非整。对应方程为将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有则加入松弛变量此式称为以r行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。 将Gomory约束加入到松弛问题(伴随LP)的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。割平面法，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是Gomory约束条件。Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。例5-5cj3-1000XBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/700-5/70-3/7选择较大小数的行构造割平面运筹学--线性规划cj3-10000XBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700x6-6/700-1/70-2/7100-5/70-3/70运筹学--线性规划cj3-10000XBbx1x2x3x4x5x631x25/4010-1/40-5/40x35/2001-1/20-11/20x57/40001/41-3/4000-1/40-17/4运筹学--线性规划第三节　分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。先求解整数规划的线性规划问题(伴随LP)。如果其最优解不符合整数条件，则求出整数规划的上下界。增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝）再求解这些子区域上的线性规划问题。不断缩小整数规划上下界的距离，最后得整数规划的最优解。 用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B： 第一步：求解问题B，可得以下情况之一： 1.B没有可行解，则A也没有可行解，求解过程停止。 2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。 3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。 第二步：确定A的最优目标函数值z*的上下界，其上界即为 ,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。 第三步：判断 是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。