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