?14/5 ?2/5
最优解为x1 =14，x2 =33，目标函数值为254。 2、用对偶单纯形法求解下列线性规划
min z=4x1+2x2+6x3
2x1 +4x2+8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0
解：将问题改写成如下形式
max（－z）=－4x1－2x2－6x3
－2x1－4x2－8x3 + x4 =－24 －4x1－x2－4x3 +x5 =－8 x1、x2，x3，x4，x5≥0
整个问题的计算过程列在表中。 Cj －4 －2 －6 CB XB x1 x2 x3 0 0 θ -2 0 θ -2 -6 x2 x3 －z x2 x5 －z x4 x5 －z -2 -4 -4 -4/-2 1/2 -7/2 -3 -3/(-7/2) -3 7/4 -1/2 [-4] -1 -2 -2/-4 1 0 0 0 1 0 0 -8 -4 -6 -6/-10 2 [-2] -2 -2/-2 0 1 0
zj - cj
0
0
0 x4 1 0 0 0 -1/4 -1/4 -1/2 (-1/2)/(-1/4) -1/2 1/8 -1/4 0 x5 0 1 0 0 0 1 0 0 1 -1/2 -1 b -24 -8 0 6 -2 -120 4 4 -32 得到问题的最优解为X*=（0，4，4）T 最优值为z*=32 3、用对偶单纯形法求解
min ??2x1?3x2?4x3?x1?2x2?x3?3?s..t?2x1?x2?3x3?4?x,x,x?0?123解：先将原问题改写为：
max z??2x1?3x2?4x3??x1?2x2?x3?x4 ??3 ?s..t??2x1?x2?3x3 ?x5??4?x?0,j?1,2,?,5?j建立单纯形表计算如下：
cj －2 －3 －4 0 0 CB 0 0 XB b －3 －4 x1 －1 [－2] －2 x2 －2 1 －3 [－5/2] －1/2 －4 1 0 0 x3 －1 －3 －4 1/2 3/2 －1 －1/5 7/5 －9/5 x4 1 0 0 1 0 0 －2/5 －1/5 －8/5 x5 0 1 0 －1/2 －1/2 －1 1/5 －2/5 －1/5 x4 x5 ?j 0 －2 x4 x1 －1 2 0 1 0 ?j －3 －2 x2 x1 2/5 11/5 0 1 0 ?j 故，原问题的最优解为X*?(11/5,2/5,0)T，z*?28/5。
灵敏度分析
1、设某线性规划问题的初始单纯形表和最优单纯形表分别为 Cj 5 4 3 0 0 CB XB x1 x2 x3 x4 x5 0 0 Cj CB 4 5 XB x2 x1 5 x1 0 1 4 x2 1 0 3 x3 -2 3 0 x4 2 -1 0 x5 -1 1 b 40 20 x4 x5 －z 1 2 5 1 1 4 1 4 3 1 0 0 0 1 0 b 60 80 0 －z 0 0 -4 -3 -1 -260 问：（1）c3在什么范围内变化，表中最优解不变？（2）c3从3变为8，求新的最优解
解：（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。
（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表中所示的新的最优解。 Cj 5 4 8 0 0 b CB XB x1 x2 x3 x4 x5 4 5 4 5 2、
max z=5x1+4x2
x1 +3x2≤90 2x1 + x2≤80 x1 + x2≤45 x1、x2，x3≥0
其初始单纯形表和最优单纯形表分别如表，试分析使最优基不变的b3的变化范围。（初始单纯形表） Cj 5 4 0 0 0 b CB XB x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 －z 1 2 1 5 5 x1 0 1 0 0 3 1 1 4 4 x2 0 0 1 0 1 0 0 0 0 x3 1 0 0 0 0 1 0 0 0 x4 2 1 -1 -1 0 0 1 0 0 x5 -5 -1 2 -3 90 80 45 0 x2 x1 －z x2 x3 －z 0 1 0 2/3 1/3 0 1 0 0 1 0 0 -2 [3] 1 0 1 -4 2 -1 -3 4/3 -1/3 -3 -1 1 -1 -1/3 1/3 -1 40 20 -260 160/3 20/3 -740/3 即新的最优解为X*=（0，160/3，20/3）T。 （最优单纯形表） Cj CB 0 5 4 XB x3 x1 x2 －z b 25 35 10 -215 解：由表可知，当B=（p3，p1，p2）时，有
?12?5??25?????B?1??01?1?B?1b??35?
?0?12??10?????当下式成立时，最优基不变。
?25??12?5??0??25?5?b3?????????B?1b?B?1?b??35???01?1??0???35??b3??0
?10??0?12???b??10??b?3??????3??即 25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0
解不等式有 －5≤Δb3≤5
此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb3，即
?10??3525?max?????b?min??,??
?2???1?5?同样可得－5≤Δb3≤5
因此，不影响最优基的b3的变化范围是[40，50]。
运输问题
1、用小元素法求下面运输问题（见表）的初始可行解，检验解的最优性，如
果不是最优解，改进成最优解。
B2 B3 B4 B5 销地 B1 产量 产地 A1 6 9 4 8 5 20 A2 10 6 12 8 7 30 A3 6 5 9 20 9 40 A4 2 13 6 14 3 60 25 15 35 45 30 销量 解：最小元素法 20 x14 30 15 10 15 25 5 30 OBJ＝955 ? 运费表 (检验数zij |wij ) 0 6 0 9 4 (15) 8 1 5 4 -7 10 -7 6 -3 12 -6 7 ?3 8 5 6 5 6 9 9 9 20 6 2 2 13 6 17 14 3 0 11 ?4 ?4 ?3
迭代后的分配表{xij } 5 15 30 15 25 25 5 OBJ＝850 30 运费表 (检验数zij |wij ) 0 6 0 9 1 5 4 4 8 0 10 0 6 4 12 1 7 4 8 5 6 5 9 13 20 6 9 9
2 13 6 10 14 3 6 2 0 4 ?4 ?4 ?3 答：x13=5, x14=15, x24=30, x32=15, x33=25,
x41=25, x43=5, x45=30, OBJ=850。
2、运输问题的产销平衡表如下。用最小元素法给出运输问题的初始可行解，检验解的最优性，如果不是最优解，改进成最优解。 销地 B1 B2 B3 B4 产量 产地 A1 A2 A3 销量 解：第一部，最小元素法 销地 产地 A1 A2 A3 销量 B1 3 3 1 7 3 B2 11 9 6 4 6 0 B3 4 3 1 2 10 54 0 B4 3 10 8 3 5 6 3 产量 73 0 41 0 9 3 3 1 7 3 11 9 4 6 3 2 10 5 10 8 5 6 7 4 9 ② ⑤ ① ④ ③初始基可行解，x13 = 4, x14 = 3, x21 = 3, x23 = 1, ⑥ x 32 = 6, x34 = 5。
运输费用为：Z=3×4+10×3 +1×3 +2×1+4×6+5×3=12+30+3+2+24+15=86 第二步，解的最优性检验 销地 B1 B2 B3 B4 产地 3 11 3 10 4 3 1 9 2 8 A2 3 1 A3 7 4 10 5 6 3 令自由变量u1 = 0 ，得：u1 = 0，v3 = 3，v4 = 10，u3 = -5，v2 = 9，u2 = -1，v1 = 2，则：
σ11=C11 - (u1 + v1) = 3 – ( 0 + 2 ) = 1 σ12=C12 - (u1 + v2) = 11 – ( 0 + 9 ) = 2 σ22=C22 - (u2 + v2) = 9 – ( -1 + 9 ) = 1 σ24=C24 - (u2 + v4) = 8 – ( -1 + 10 ) = -1 σ31=C31 - (u3 + v1) = 7 – ( -5 + 2 ) = 10 σ33=C33 - (u3 + v3) = 10 – ( -5 + 3 ) = 12 第三步，解的改进
A1