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

《管理运筹学》演示1999年12月1宅)sylpy@263.net2021/6/271目录线性规划图解法单纯形表结构线性规划单纯形法(1)最小元素法伏格尔法闭回路法位势法闭回路调整法目标规划图解法(1)目标规划图解法(2)整数规划(分枝定界法)和和线性规划单纯形法(2)图解法与单纯形法的联系指派问题(匈牙利法)(1)使用计算机软件包求解指派问题(匈牙利法)(2)0-1规划(隐枚举法)整数规划(割平面法)典型应用案例线性规划单纯形法(3)目标规划单纯形法线性规划求解几种结果几种常用规划数学软件比较动态规划(1)动态规划(2)最小树问题(破圈法/避圈法)最短路问题(迪克斯拉法)(1)最大流问题(福克逊法)最小费用最大流问题(2)对偶单纯形法改进单纯形法动态规划(逆推法)(顺推法)(3)2021/6/272对于整数规划问题,先不考虑整数约束,求相应的线性规划问题的最优解,如果最优解是一个非整数最优解,构造约束条件,缩小线性规划问题的可行域,丢弃不含整数解的区域，然后在缩小后的子可行域中继续求解,直止求出相应的线性规划的最优解为整数解。分枝：如果求出的最优解是一个非整数解，则以这个解任一分量相邻的两个整数点为边缘将线性规划的可行域分成两个子区域，每个子区域就是一个分枝（或子问题）；定界：在分枝过程中，通过分枝找到更好的最优值和整数解不断地修改上下界，和减小上下界之间的范围，当上下界相同时，即得到整数最优解。分枝定界法的基本思想:2021/6/273.定界。设整数规划的目标最优值为z*，则，其中，和为整数规划目标值的上、下界；.分枝。在非整数最优解中，任选一个不符合整数条件的变量，构造两个约束条件：

.修改上下界。方法如下：在各分枝中，找出目标值最大者作为新的上界；从已符合整数条件的分枝中，找出目标值最大者作为新的下界。.比较和剪枝。比较各个分枝的目标值，如果有小于者，则剪掉这个分枝；否则，继续分枝。反复进行，当，得到整数最优解。例1：用分枝定界法求整数规划分枝定界法的求解步骤:.先不考虑整数约束条件，求解相应的线性规划，有以下几种情况：如果线性规划没有可行解，则整数规划也没有可行解，停止计算；如果线性规划有最优解，且为整数最优解，则这个解为整数规划的整数最优解；如果线性规划有最优解，但为非整数最优解，则转入下一步；2021/6/2749x1+7x2=56BC0x1x2125346789125346787x1+20x2=70整数规划(分枝定界法)(例1)Bz=40x1+90x2x1=4.81x2=1.82z=356B0

Z*

3562021/6/2759x1+7x2=56x1=4x1=5BC0x1x2125346789125346787x1+20x2=70B1B2x1=4.81x2=1.82z=356BB2x1=4.00x2=2.10z=349x1=5.00x2=1.57z=341B1整数规划(分枝定界法)(例2)0

Z*

3560

Z*

3560

Z*

349z=40x1+90x22021/6/2769x1+7x2=56x2=3x1=4x1=5BC0x1x2125346789125346787x1+20x2=70B3B4x2=1x2=2x2=2B2B5B4B3x1=4.00x2=2.00z=340x1=1.42x2=3.00z=327x1=4.81x2=1.82z=356BB2x1=4.00x2=2.10z=349x1=5.00x2=1.57z=341B1B5x1=5.44x2=1.00z=308无可行解B6整数最优解:x1=4.0,x2=2.0整数规划(分枝定界法)(例1)0

Z*

3560

Z*

3560

Z*

3490

Z*

349Z下界=Z*=Z上界z=40x1+90x22021/6/277对于整数规划问题,首先不考虑整数约束,求解相应的线性规划问题的解,如果最优解是一个非整数解,就增加一个约束条件,缩小线性规划问题的可行域,继续求解,直到求出相应的线性规划问题的最优解为整数解。割平面法的基本思想:例：求解下列整数规划：整数整数最优解:2021/6/278例3：用割平面法求解整数规划整数11001400-111031011100解：先不考虑整数约束，求相应的线性规划的最优解，用单纯形法求解，标准型和初始单纯形表如下：2021/6/27911003/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,显然不符合整数条件。构造切割方程：首先，从最优表中任意选一非整数分量，写出其相应的约束条件，如：再将上式中的系数和常数都分解成整数和非负真分数之和，并移项(整数移到左边，分数移到右边)，如：2021/6/2710从约束条件可以看出，由于x1和x2为非负整数,所以x3和x4也必然为非负整数，这样，在上式括号内的数值则为正数，而且等式右边必定是负数，即有，化简后，即得到一切割方程：再将其作为新的约束条件，加到最优表中(添加松弛变量x5

)；1100000-1/2-1/2-5/203/47/4-311010-1/41/4013/41/400-3-1001显然，需要按照对偶单纯形法继续迭代，x5为换出变量，x3为换入变量，迭代结果如下：2021/6/271111000000-1/3-2-1/61111101001/30100001-11/120-1/3111整数最优解：x1=1,x2=1,x3=1,x4=x5=0,max

z

=22021/6/2712例：用隐枚举法求0－1规划解：先找出一个可行解，显然，满足约束条件，是一个可行解，目标值z为3。由于目标函数是求最大化，所以，增加一个过滤条件为：计算过程可列表进行，为减少计算工作量，在表中可将目标函数中的系数按递增顺序排列，并结合新的目标值改进过滤条件。2021/6/2713(0)(1)(2)(3)(4)05-1101

满足条件是,否约束条件

××计算过程如下表:(1)(2)(3)(4)约束条件满足条件是,否×

3×80211

改进过滤条件,用代替2021/6/2714(1)(2)(3)(4)-2×63×1×约束条件满足条件是,否×

×再改进过滤条件,用代替最优解:最优值:2021/6/2715例1.设有四项工作A、B、C、D，需分配甲、乙、丙、丁四个人去完成，每个人只能完成一件工作，每件工作只能由一个人去完成，这四个人完成各项工作所需的费用如下表所示，问如何分配工作才能使总费用最省？人工作ABCD甲乙丙丁4679610835711884962021/6/271600最优解:60302016232024指派问题(匈牙利法)(例1)修改指派矩阵:试求最优解:00000004002021/6/2717修改指派矩阵方法:从每一行元素中减去该行的最小元素；再从所得矩阵的各列元素中减去该列的最小元素。试求最优解方法：从第一行开始，给只有一个0元素的行的0元素加圈，记为◎，表示代表这一行的人承担了某一项任务；然后划去0元素所在列的其它0元素，并记为

，表示这一列所代表的任务已有人承担了，不需要其他人再来承担。给只有一个0元素的列的0元素加圈，记为◎，然后划去0元素所在行的其它0元素，并记为

；反复进行，直到所有的0元素加圈和划去为止。2021/6/2718例2:求下列表所示效率矩阵的指派问题的最优解:任务人员甲乙丙丁戊1287154ABCDE791714109612677614610969109指派问题(匈牙利法)(例2)2021/6/2719

-2