《管理运筹学》演示整数规划

1、管理运筹学演示,制作 & 讲授： 施应玲,1999年12月1日宅) ,华北电力大学,目录,线性规划图解法,单纯形表结构,线性规划单纯形法(1),最小元素法,伏格尔法,闭回路法,位势法,闭回路调整法,目标规划图解法(1),目标规划图解法(2),整数规划(分枝定界法),和,和,线性规划单纯形法(2),图解法与单纯形法的联系,指派问题(匈牙利法)(1),使用计算机软件包求解,指派问题(匈牙利法)(2),0-1规划(隐枚举法),整数规划(割平面法),典型应用案例,线性规划单纯形法(3),目标规划单纯形法,线性规划求解几种结果,几种常用规划数学软件比较,动态规划(1),动态规

2、划(2),最小树问题(破圈法/避圈法),最短路问题(迪克斯拉法)(1),最大流问题(福克逊法),最小费用最大流问题,(2),对偶单纯形法,改进单纯形法,动态规划(逆推法),(顺推法),(3),. 定界。设整数规划的目标最优值为z*，则 ，其中， 和 为整数规划目标值的上、下界； . 分枝。在非整数最优解中，任选一个不符合整数条件的变量，构造两个约束条件： . 修改上下界。方法如下： 在各分枝中，找出目标值最大者作为新的上界； 从已符合整数条件的分枝中，找出目标值最大者作为新的下界。 . 比较和剪枝。比较各个分枝的目标值，如果有小于 者，则剪掉这个分枝；否则，继续分枝。反复进行，当 ，得到整数最

3、优解 。,例1：用分枝定界法求整数规划,分枝定界法的求解步骤:,. 先不考虑整数约束条件，求解相应的线性规划，有以下几种情况： 如果线性规划没有可行解，则整数规划也没有可行解，停止计算； 如果线性规划有最优解，且为整数最优解，则这个解为整数规划的整数最优解； 如果线性规划有最优解，但为非整数最优解，则转入下一步；,B,C,0,x1,x2,整数规划(分枝定界法) (例1),B,z = 40 x1+90 x2,0 Z* 356,x1=4,x1=5,B,C,0,x1,x2,B1,B2,整数规划(分枝定界法) (例2),0 Z* 356,0 Z* 356,0 Z* 349,z = 40 x1+90 x

4、2,x2=3,x1=4,x1=5,B,C,0,x1,x2,B3,x2=1,B2,B5,整数最优解: x1=4.0 ,x2=2.0,整数规划(分枝定界法) (例1),0 Z* 356,0 Z* 356,0 Z* 349,0 Z* 349,Z下界= Z*=Z上界,z = 40 x1+90 x2,例：求解下列整数规划：,整数,例3：用割平面法求解整数规划,整数,1,1,0,0,解：先不考虑整数约束，求相应的线性规划的最优解，用单纯形法求解，标准型和初始单纯形表如下：,0,0,-1/2,-1/2,-5/2,经过若干步迭代后，得到如下最优表及最优解：,最优解：x1=3/4 , x2=7/4 , x3=

5、x4=0 , max z =5/2 ,显然不符合整数条件。,构造切割方程：首先，从最优表中任意选一非整数分量，写出其相应的约束条件，如：,再将上式中的系数和常数都分解成整数和非负真分数之和，并移项(整数移到左边，分数移到右边)，如：,从约束条件可以看出，由于x1和 x2为非负整数,所以x3和 x4也必然为非负整数，这样，在上式括号内的数值则为正数，而且等式右边必定是负数，即有，,化简后，即得到一切割方程：,再将其作为新的约束条件，加到最优表中(添加松弛变量 x5 )；,显然，需要按照对偶单纯形法继续迭代，x5为换出变量， x3为换入变量，迭代结果如下：,整数最优解： x1=1 , x2=1 ,

6、 x3=1 , x4= x5=0 , max z =2,例：用隐枚举法求01规划,解：先找出一个可行解，显然， 满足约束条件，是一个可行解，目标值z为3。由于 目标函数是求最大化，所以，增加一个过滤条件为：,计算过程可列表进行，为减少计算工作量，在表中可将目标函数中的系数 按递增顺序排列，并结合新的目标值改进过滤条件。,( 0 ),( 1 ),( 2 ),( 3 ),( 4 ),0,5,-1,1,0,1,计算过程如下表:,( 1 ),( 2 ),( 3 ),( 4 ),3,8,0,2,1,1,改进过滤条件,用 代替,( 1 ),( 2 ),( 3 ),( 4 ),-2,6,3,1,再改进过滤条件,用 代替,最优解:,最优值:,例1.设有四项工作A、B、C、D，需分配甲、乙、丙、丁四个人去完成，每个人只能完成一件工作，每件工作只能由一个人去完成，这四个人完成各项工作所需的费用如下表所示，问如何分配工作才能使总费用最省？,0,0,最优解:,6,0,3,0,2,0,1,6,2,3,2,0,2,4,指派问题(匈牙利法)(例1)