《管理运筹学》演示(整数规划).ppt

010-62374836(宅)华北电力大学华北电力大学线性规划图解法单纯形表结构线性规划单纯形法(1)最小元素法伏格尔法闭回路法位势法闭回路调整法目标规划图解法(1)目标规划图解法(2)整数规划(分枝定界法)和和线性规划单纯形法(2)图解法与单纯形法的联系指派问题(匈牙利法)(1)使用计算机软件包求解指派问题(匈牙利法)(2)0-1规划(隐枚举法)整数规划(割平面法)典型应用案例线性规划单纯形法(3)目标规划单纯形法线性规划求解几种结果几种常用规划数学软件比较动态规划(1)动 态 规 划(2)最小树问题(破圈法/避圈法)最短路问题(迪克斯拉法)(1)最大流问题(福克逊法)最小费用最大流问题(2)对偶单纯形法改进单纯形法动态规划(逆推法)(顺推法)(3)对对于于整整数数规规划划问问题题,先先不不考考虑虑整整数数约约束束,求求相相应应的的线线性性规规划划问问题题的的最最优优解解,如如果果最最优优解解是是一一个个非非整整数数最最优优解解,构构造造约约束束条条件件,缩缩小小线线性性规规划划问问题题的的可可行行域域,丢丢弃弃不不含含整整数数解解的的区区域域，然然后后在在缩缩小小后后的的子子可可行行域域中中继继续续求求解解,直直止止求求出出相相应的线性规划的最优解为整数解。应的线性规划的最优解为整数解。分枝：如果求出的最优解是一个非整数解，则以这个解任一分量相邻的两个整数点为边缘将线性规划的可行域分成两个子区域，每个子区域就是一个分枝（或子问题）；定界：在分枝过程中，通过分枝找到更好的最优值和整数解不断地修改上下界，和减小上下界之间的范围，当上下界相同时，即得到整数最优解。分枝定界法的基本思想分枝定界法的基本思想:2.定界。设整数规划的目标最优值为z*，则 ，其中，和 为整数规划目标值的上、下界；3.分枝。在非整数最优解中，任选一个不符合整数条件的变量，构造两个约束条件：4.修改上下界。方法如下：q 在各分枝中，找出目标值最大者作为新的上界；q 从已符合整数条件的分枝中，找出目标值最大者作为新的下界。5.比较和剪枝。比较各个分枝的目标值，如果有小于 者，则剪掉这个分枝；否则，继续分枝。反复进行，当 ，得到整数最优解 。例例1 1：用分枝定界法求整数规划：用分枝定界法求整数规划分枝定界法的求解步骤分枝定界法的求解步骤:1.先不考虑整数约束条件，求解相应的线性规划，有以下几种情况：如果线性规划没有可行解，则整数规划也没有可行解，停止计算；如果线性规划有最优解，且为整数最优解，则这个解为整数规划的整数最优解；如果线性规划有最优解，但为非整数最优解，则转入下一步；9x1+7x2=56BC0 0 x x1 1x21 12 25 53 34 46 67 78 89 91 12 25 53 34 46 67 78 87x1+20 x2=70整数规划整数规划(分枝定界法分枝定界法)()(例例1)1)B Bz=40 x1+90 x2x x1 1=4.81=4.81x x2 2=1.82=1.82 z=z=356356B B0 Z*3569x1+7x2=56x x1 1=4 4x x1 1=5=5BC0 0 x x1 1x21 12 25 53 34 46 67 78 89 91 12 25 53 34 46 67 78 87x1+20 x2=70B B1 1B B2 2x x1 1=4.81=4.81x x2 2=1.82=1.82 z=z=356356B BB B2 2x x1 1=4.00=4.00 x x2 2=2.10=2.10 z=z=349349x x1 1=5.00=5.00 x x2 2=1.57=1.57 z=z=341341B B1 1整数规划整数规划(分枝定界法分枝定界法)()(例例2)2)0 Z*3560 Z*3560 Z*349z=40 x1+90 x29x1+7x2=56x x2 2=3=3x x1 1=4 4x x1 1=5=5BC0 0 x x1 1x21 12 25 53 34 46 67 78 89 91 12 25 53 34 46 67 78 87x1+20 x2=70B B3 3B B4 4x x2 2=1=1x x2 2=2=2x x2 2=2=2B B2 2B B5 5B B4 4B B3 3x x1 1=4.00=4.00 x x2 2=2.00=2.00 z=z=340340 x x1 1=1.42=1.42x x2 2=3.00=3.00 z=z=327327x x1 1=4.81=4.81x x2 2=1.82=1.82 z=z=356356B BB B2 2x x1 1=4.00=4.00 x x2 2=2.10=2.10 z=z=349349x x1 1=5.00=5.00 x x2 2=1.57=1.57 z=z=341341B B1 1B B5 5x x1 1=5.44=5.44x x2 2=1.00=1.00 z=z=308308无无可可行行解解B B6 6整数最优解整数最优解:x x1 1=4.0=4.0,x,x2 2=2.0=2.0整数规划整数规划(分枝定界法分枝定界法)()(例例1)1)0 Z*3560 Z*3560 Z*3490 Z*349Z下界=Z*=Z上界z=40 x1+90 x2对于整数规划问题,首先不考虑整数约束,求解相应的线性规划问题的解,如果最优解是一个非整数解,就增增加加一一个个约约束束条条件件,缩小线性规划问题的可行域,继续求解,直到求出相应的线性规划问题的最优解为整数解。割平面法的基本思想割平面法的基本思想:例：求解下列整数规划：整数整数最优解整数最优解:例3：用割平面法求解整数规划整数11001400-111031011100解：先不考虑整数约束，求相应的线性规划的最优解，用单纯形法求解，标准型和初始单纯形表如下：11003/47/41110-1/41/4013/41/400-1/2-1/2-5/2经过若干步迭代后，得到如下最优表及最优解：最优解：x1=3/4,x2=7/4,x3=x4=0,max z=5/2,显然不符合整数条件。构造切割方程：首先，从最优表中任意选一非整数分量，写出其相应的约束条件，如：再将上式中的系数和常数都分解成整数和非负真分数之和，并移项(整数移到左边，分数移到右边)，如：从约束条件可以看出，由于x1和 x2为非负整数,所以x3和 x4也必然为非负整数，这样，在上式括号内的数值则为正数，而且等式右边必定是负数，即有，化简后，即得到一切割方程：再将其作为新的约束条件，加到最优表中(添加松弛变量 x5)；1100000-1/2-1/2-5/203/47/4-311010-1/41/4013/41/400-3-1001显然，需要按照对偶单纯形法继续迭代，x5为换出变量，x3为换入变量，迭代结果如下：11000000-1/3-2-1/61111101001/30100001-11/120-1/3111整数最优解：x1=1,x2=1,x3=1,x4=x5=0,max z=2 例：用隐枚举法求例：用隐枚举法求0 01 1规划规划解：先找出一个可行解，显然，满足约束条件，是一个可行解，目标值z为3。由于 目标函数是求最大化，所以，增加一个过滤条件为：计算过程可列表进行，为减少计算工作量，在表中可将目标函数中的系数 按递增顺序排列，并结合新的目标值改进过滤条件。(0)(1)(2)(3)(4)05-1101 满足条件是 ,否约束条件 计算过程如下表:(1)(2)(3)(4)约束条件满足条件是 ,否 3 80211 改进过滤条件,用 代替(1)(2)(3)(4)-2 63 1 约束条件满足条件是 ,否 再改进过滤条件,用 代替最优解:最优值:例1.设有四项工作A、B、C、D，需分配甲、乙、丙、丁四个人去完成，每个人只能完成一件工作，每件工作只能由一个人去完成，这四个人完成各项工作所需的费用如下表所示，问如何分配工作才能使总费用最省？人工作A AB BC CDD甲甲乙乙丙丙丁丁4679610835711884960 0最优解:60302016232024w修改指派矩阵:w试求最优解:00 00 00 0400修改指派矩阵方法:从每一行元素中减去该行的最小元素；再从所得矩阵的各列元素中减去该列的最小元素。v试求最优解方法：从第一行开始，给只有一个0元素的行的0元素加圈，记为，表示代表这一行的人承担了某一项任务；然后划去0元素所在列的其它0元素，并记为，表示这一列所代表的任务已有人承担了，不需要其他人再来承担。给只有一个0元素的列的0元素加圈，记为，然后划去0元素所在行的其它0元素，并记为；反复进行，直到所有的0元素加圈和划去为止。例2:求下列表所示效率矩阵的指派问题的最优解:任务人员甲乙丙丁戊1287154ABCDE791714109612677614610969109指派问题指派问题(匈牙利法匈牙利法)()(例例2)2)-2-2+205384440080003202001104713修改指派矩阵修改指派矩阵试找最优解试找最优解作最少直线覆盖所有作最少直线覆盖所有0 0元素元素增加增加0 0元素元素0538444008000320200110471305384440080003202001104713再试找最优解再试找最优解最优解最优解