运筹学期末考试复习资料

1、1. 最小费用最大流例1 求下图所示网络中的最小费用最大流，弧旁的权是（bij,cij）.解：（1）取初始可行流为零流f(0)=0,构造赋权有向图M(f(0),求出从vs到vt的最短路(vs,v2,v1,vt),如下图中双箭头所示。（2）在原网络D中，与这条最短路相对应的增广链为=（vs,v2,v1,vt）。（3）在上对f(0)=0进行调整，取=5，得到新可行流f(1)，如下图所示。按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图 M(f(1),(Mf(2),(Mf(3),(Mf(4) 由于在Mf(4)中已经

2、不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1)=11是最小费用最大流。 2. 灵敏度分析（1）资源数量br变化的分析 最优单纯形表如下 这里B=求b2的增量Dbr变化范围：所以b2的增量Dbr变化范围是-8，16，显然b2的变化范围是8，32。（2）目标函数中价值系数cj的变化分析1）非基变量对应的价值系数的灵敏度分析例 Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0 求C3的变化范围？解：最优单纯形表从表中看到可得到c3 9/5 时，c3 -

3、4+9/5=-11/5原最优解不变。2） 基变量对应的价值系数的灵敏度分析例 Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0解：下表为最优单纯形表,考虑基变量系数c2发生变化j=cj-(c1×a1j+c5 × a5j+(c2+c2)×a2j)j=3,4可得到 -3c21时，原最优解不变。（3） 增加一个约束3.割平面法例：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621

4、100x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6在松弛问题最优解中，x1, x2 均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得： 引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。 Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x

5、28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60 得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。4. 分支定界法例：用分枝定界法求解整数规划问题（用图解法计算）记为（IP） 解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的最优解，如图所示。 x118/11, x2 =

6、40/11 Z(0) =218/11(19.8)即Z 也是（IP）最小值的下限。对于x118/111.64，取值x1 1， x1 2对于x2 =40/11 3.64，取值x2 3 ，x2 4先将（LP）划分为（LP1）和（LP2）,取x1 1, x1 2有下式： 现在只要求出（LP1）和（LP2）的最优解即可。先求（LP1）,如图所示。此时B 在点取得最优解。 x11, x2 =3, Z(1)16找到整数解，问题已探明，此枝停止计算。同理求（LP2） ,如图所示。在C 点取得最优解。即x12, x2 =10/3, Z(2) 56/318.7 Z2 < Z116 原问题有比（16）更小的最

7、优解，但 x2 不是整数，故利用3 10/34 加入条件。 加入条件： x23, x24 有下式： 只要求出（LP3）和（LP4）的最优解即可。先求（LP3）,如图所示。此时D 在点取得最优解。即 x112/52.4, x2 =3, Z(3)-87/5-17.4<Z-19.8但x112/5不是整数，可继续分枝。即 x12, x13 。求（LP4），如图所示。无可行解，不再分枝。 在（LP3）的基础上继续分枝。加入条件x12, x13有下式： 只要求出（LP5）和（LP6）的最优解即可。先求（LP5）,如图所示。此时E 在点取得最优解。即 x12, x2 =3, Z(5)17找到整数解，问

8、题已探明，此枝停止计算。求（LP6），如图所示。此时 F在点取得最优解。x13, x2 =2.5, Z(6)31/215.5 > Z(5) 如对 Z(6) 继续分解，其最小值也不会低于15.5 ，问题探明,剪枝。 至此，原问题（IP）的最优解为：x1=2，x2 =3, Z* = Z(5) =-17以上的求解过程可以用一个树形图表示如右： 5. 贝叶斯例：某石油钻探队准备在一远景区勘探石油，根据预测估计钻井出油的概率为0.3，可以自己钻探或是出租。 自己钻探的费用为1000万元，出油可收入4000万元； 如果出租，租金为200万元，若有油租金再增加100万元。为获更多情报，可以先做地震试验

9、，再行决策。地震试验将有油区勘测为封闭构造的概率为0.8；将无油区勘测为开放构造的概率为0.6。地震试验费为100万元。试用决策树法进行决策。由题意知，有油事件q1的概率P(1)=0.3，无油事件q2的概率P(2)=0.7，这是先验概率；后验概率则是封闭构造而有油的概率P(1|I1)=0.8，开放构造而无油的概率 P(2|I2)=0.4。6. 大M法例： 标准化 单纯形表cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x711311-4-2-2101211000-10010001j3-6M-1+M-1+3M0-M000-M-1x4x6x3101130-2-21

10、00011000-10010-1-21j1-1+M00-M0-3M+10-1-1x4x2x3121130-2010001100-2-10210-5-21j1000-10-3M+13-1-1x1x2x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3j000-1/3-1/3-M+1/3-M+2/3最优值和最优解 X*=（4，1，9，0，0）T，x6*=x7*=0； z*=2。7. 互补松弛性定理例：原问题 的最优解为X*=（0，0，4，4）T。试利用互补松弛定理求对偶问题最优解。解：先写出对偶问题求解，Y*=（6/5，1/5，0），z*=w*=28。8

11、. 根据原问题最优表写出对偶问题的最优解和最优值例：原问题 已知它的最优表，求对偶最优解。Cj1018000CBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7解：写出对偶问题 计算步骤 原问题的初始单纯形表中的基变量的技术系数-最终单纯形表中的检验数即 y1*=0-0=0, y2*=0-(-32/7)=32/7, y3*=0-(-6/7)=6/7 则Y*=（0 ，32/7，6/7），W=4100/79. 目标规划某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500