运筹学期末考试复习资料.doc

《运筹学期末考试复习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)

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

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

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

5、/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/60Cj11000CBXBbx1x2x3x4s11 x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/60得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。4.分支定界法例：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的

6、最优解，如图所示。x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。对于x1＝18/11≈1.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在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。同理求（LP2）,如图所示。在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝－56

7、/3≈－18.7∵Z2

8、如图所示。此时E在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解