简写形式为：
njmi
j
x
i
b
n
j
j
x
ij
a
tS
n
j
j
x
j
cz
,,2,1;,2,1
0
1.
1
m a x
向量和矩阵表示
max z=CX
X=
其中,C=(c1,c2,…,cn )
向量 Pj对应的决策变量是 xj,
njjx
b
n
j
jxjP
,,2,1,0
1
nx
x
x
2
1
m
b
b
b
b
mj
a
j
a
j
a
j
P
2
1
,2
1
矩阵形式为：
max z=CX
s.t
0X
BAX;,
2
,
1
21
22221
11211
m
PPP
mn
a
m
a
m
a
n
aaa
n
aaa
A?
0
0
0
0
称 A为约束条件的 m× n维系数矩阵,
一般 m<n;m,n>0;
b为资源向量；
C为价值向量；
X为决策变量向量 。
实际遇到的各种线性规划问题的数学模型都应变换为标准形式后求解 。
以下讨论如何化标准型的问题：
若要求目标函数实现最小化,即 min z=CX.这时只需将目标函数最小化变换为最大化，即令 z`=-z,于是得到 max z`=-CX,这就和标准型的目标函数的形式一致了。
（ 2） 约束方程为不等式 。 这里有两种情况：一种是约束方程为 ‘ ≤’ 不等式,则可在 ‘ ≤’ 不等式的左边加上非负松弛变量,
把原 ‘ ≤’ 不等式变为等式；另一种是约束方程 ‘ ≥’ 不等式,则可在 ‘ ≥’ 不等式的左端减去一个非负剩余变量 （ 也可称松弛变量 ）,
把不等式约束条件变为等式约束条件 。
(3)若存在取值无 （ 符号 ）
约束的变量 xk,可令 xk=xk`-
xk``,其中 xk`,xk``≥0。
下面举例说明例 3 将下面的数学模型化为标准型 。
Max z=2x1+3x2
x1+2x2≤8
4x1≤16
4x2≤12
x1,x2≥0
解将各不等式加上松弛变量即得
Max z=2x1+3x2
x1+2x2+x3=8
4x1+x4=16
4x2+x512
x1,x2,x3,x4,x5≥0
例 3 将下述线性规划问题化为标准型
min z=-x1+2x2-3x3
x1+x2+x3≤7
x1-x2+x3≥2
-3x1+x2+2x3=5
x1,x2≥0,x3为无约束解步骤为
1,令 x3=x4-x5,其中 x4,x5≥0;
2,在第一个不等式 ≤的左边加上松弛变量 x6;
3,在第二个不等式 ≥的左边减去剩余变量 x7;
4,令 z`=-z,把求 min z 改为求 max z`; 即可得该问题的标准型
max z`=x1-2x2+3(x4-x5)
x1+x2+(x4-x5)+x6 =7
x1-x2+(x4-x5) -x7=2
-3x1+x2+2(x4-x5)=5
x1,x2,x4,x5,x6,x7≥0
1.4 线性规划问题的解概念可行解满足约束条件和非负约束的解称为可行解，而使目标函数达到最大值的可行解叫最优解。
不失一般性，可设称 PJ（ J=1,2,…,m）为基向量，
与基向量 Pj相应的
xj(j==1,2,…,m)为基变量。否则称为非基变量。
m
PPP
mm
a
m
a
m
a
m
aaa
B?
,
2
,
1
21
11211
为了进一步讨论线性规划问题的解，下面研究约束方程
（ 1.5）的求解问题。假设该方程组系数矩阵 A的秩为 m,
因 m<n,故它有无穷多个解。
假设前 m个变量的系数列向量是线性独立的。
这时（ 1.5）可写成
n
x
mn
a
n
a
n
a
m
x
mm
a
m
a
m
a
m
b
b
b
m
x
mm
a
m
a
m
a
x
m
a
a
a
x
m
a
a
a
2
1
1
1
12
11
2
1
2
1
2
2
22
21
1
1
12
11
方程组 （ 1.7） 的一个基是
m
PPP
mm
a
m
a
m
a
m
aaa
B?
,
2
,
1
21
11211
设 XB是对应于这个基的基变量
XB=(x1,x2,…,xm)T
现若令 （ 1.7 ） 的 非 基 变 量
xm+1=xm+2=… =xn=0,并用高斯消去法,可以求出一个解
X=(x1,x2,…,xm,0,…,0)T
这个解的非零分量的数目不大于方程的个数 m,称为基解。于是，
由一个基可以求出一个基解。
基可行解满足非负条件（ 1.6）的基解，称为基可行解。于是基可行解的非零分量的数目也不大于 m,并且都是非负的。
可行基对应于基可行解的基，称为可行基。
可见，约束方程祖（ 1.5）具有的基解的数目最多是个。
基解中非零分量的个数小于
m时（或基变量有零时），这基解（或基可行解）称为退化解（或退化基可行解）。
§ 2 线性规划问题的几何意义
2.1 基本概念凸集 设 K是 n维欧氏空间的一点集,
若任意两点 X(1)∈ K,X(2)∈ K的连线上的点 αX(1)+ （ 1-α ） ∈ K,
（ 0≤α≤1）,则称 K为凸集 。
一般的实心圆，实心多边形、实心多面体等都是凸集，而圆周和有洞的圆盘等都不是凸集。
凸组合 设 X(1),X(2),…,X(k)是 n维欧氏空间 En中的 k个点,若存在 μ1,μ2,…,
μk,且 0≤μi≤1,i=1,2,…,k; =1,使
X=μ1X(1)+μ2X(2)+… +μkX(k)
则称 X为 X(1),X(2),…,X(k)的凸组合。
1
1
k
i
i?
顶点 设 K是凸集,X∈ K,若 X不能用不同的两点 X(1)∈ K和 X(2)∈ K的线性组合表示为
X=αX(1)+（ 1-α） X(2),（ 0<α<1）
则称 X为 K的一个顶点（或极点）。
2.2 基本定理定理 1 若线性规划问题存在可行域,则其可行域是凸集 。
n
j
jjj xbxPXD
1
0,|
引理 1 线 性 规 划 问 题 的 可 行 解
X=(x1,x2,?,xn)T为基可行解的充分必要条件是 X的正分量是线性独立的 。
定理 2 线性规划问题的基可行解 X对应于可行域的顶点 。
引理 2 若 K是有界凸集,则任意一点
x∈ K可表示为 K的顶点的凸组合 。
定理 3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优 。
有时目标函数可能在多个顶点达到最大值。这时这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优值。
§ 3 单纯形法
3.1 单纯形法举例例 6 试以例 1来讨论它的求解。
例 1的标准型为
max z=2x1+3x2+0x3+0x4+0x5
x1+2x2+x3 =8
4x1 +x4 =16
4x2 +x5=12
xj ≥0,j=1,2,?,5
解 约束方程的系数矩阵
10040
01004
00121
),,,,(
54321
PPPPPA
从（ 1.12）中可以看到
x3,x4,x5的系数列向量是线性独立的，
1
0
0
,
0
1
0
,
0
0
1
543 PPP
这些向量构成一个基
100
010
001
),,(
543
PPPB
对应于 B的变量 x3,x4,x5 为 基 变 量,从
（ 1.12） 中可以得到
x3 =8-x1-2x2
x4 =16-4x1 （ 1.13）
x5=12- 4x2
将 （ 1.13） 代入目标函数 (1.11)得到
z=0+2x1+3x2
当令非基变量 x1=x2=0,便得到 z=0.这时得到一个基可行解 X(0)
X(0)=(0,0,8,16.12)T
现分析（ 1.13），由于 x2的系数为正，
显然当将 x2越大则目标函数 z的值也越大。当将 x2 定为换入变量后，必须从 x3,x4,x5中换出一个，并保证其余的变量都是非负，即 x3,x4,x5≥0。
当 x1=0,由 （ 1.13） 式得到
x3 =8 -2x2≥0
x4 =16≥0 （ 1.15）
x5=12-4x2≥0
从 （ 1.15） 中可以看出,x2的最大值只有选择
x2=min(8/2,-,12/4)=3
时，才能使（ 1.15）成立。
因当 x2=3时，基变量 x5=0，
这就决定用 x2去替换 x5。以上数学描述说明了每生产一件产品 Ⅱ,需要用掉各种资源的数量为 2,0,4。由这些资源中的薄弱环节，就确定了产品 Ⅱ 的产量，这里就是由原材料 B的数量确定了产品 Ⅱ 的产量 x2=12/4=3件。
为了求得以 x3,x4,x2为基变量的一个基可行解和进一步分析问题,需将 （ 1.13）
中 x2 与 x5的位置对换 。 得到
x3+2x2 =8- x1 (1)
x4 =16-4x1 (2) （ 1.16）
4x2=12- x5 (3)
用高斯消去法,将 （ 1.16） 式中的系数列向量变换为单位列向量 。 其运算步骤,
（ 3） ‘ =（ 3） /4； （ 1） ‘ =（ 1） -2×
（ 3） ‘ ； （ 2） ’ =（ 2）,并将结果仍按原顺序有：
x3 =2- x1 +1/2x5 (1)‘
x4 =16-4x1 (2)‘ （ 1.17）
x2=3-1/4 x5 (3)`
再将 （ 1.17） 代入目标函数 （ 1.11）
得到
z=9+2+2x1-3/4+2x5(1.18)
令非基变量 x1=x5 =0,得到 z=9,并得到另一个基可行解 X(1)
X(1)=(0,3,2,16,0)T
从目标函数的表达式 （ 1.18） 中可以看到,非基变量 x1的系数是正的,说明目标函数值还可以增大,X(1)不一定是最优解 。 于是再用上述方法,确定换入,换出变量,继续跌代,再得到另一个新的基可行解 X(2)，
X(2)=（ 2,3,0,8,0） T
再经过一次迭代,再得到一个基可行解 X(3)
X(3)=（ 4,2,0,0,4） T
而这时得到目标函数的表达式是：
z=14-1.5x3-0.125x4 (1.19)
再分析（ 1.19），可见到所有非基变量 x3,x4的系数都是负数。
这说明若要用剩余资源 x3,x4，就必须支付附加费用。所以当
x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以 X(3)是最优解。即应当产品 Ⅰ
生产 4件，产品 Ⅱ 生产 2件，工厂才能得到最大利润。
3.2初始基可行解的确定为了确定初始基可行解,要首先找出初始可行基,其方法如下：
1,若线性规划问题
0
m a x
1
1
j
n
j
jj
n
j
jj
x
bxP
xcz
从 Pj(j=1,2,…,n)中一般能直接观察到存在一个初始可行基
1000
0100
0010
0001
),,,(
21 m
PPPB?
2,对所有约束条件是,≤”
形式的不等式,可以利用化标准型的方法,在每个约束条件的左端加上一个松驰变量 。 经整理,
重新对 xj 及
aij(i=1,2,…,m;j=1,2,…,n) 进行编号,则可得下列方程组
x1 +a1,m+1xm+1+… +a1nxn=b1
x2 +a2,m+1xm+1+… +a2nxn=b2
………………………
xm
+am,m+1xm+1+… +amnxn=bm
xj≥0,j=1,2,… n
显然得到一个 m× m单位矩阵
1000
0100
0010
0001
),,,(
21 m
PPPB?
以 B作为可行基 。 移项得
x1=b1-a1,m+1xm+1-… -a1nxn
x2=b2-a2,m+1xm+1-… -a2nxn
………………………
xm=bm -am,m+1xm+1-… -amnxn
令 xm+1=xm+2=… =xn=0,由 （ 1.23） 可得
xi=bi (I=1,2,…,m)
又因 bj≥0,所以得到一个初始基可行解
X=(x1,x2,…,xm,0,…,0)T
=(b1,b2,…,bm,0,…,0)T
3.对所有约束条件是,≥” 形式的不等式及等式约束情况,若不存在单位矩阵时,就采取人造基的方法 。 即对不等式约束减去一个非负的剩余变量后,再加上一个非负的人工变量 。 对于等式约束加上一个非负的人工变量,总能得到一个单位矩阵 。
3,3 最优性检验与解的判别线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、
无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后（ 1.23）
式变为
(i=1,2,…,m) (1.24 )
j
n
mj
ijii xabx?
1
将 （ 1.24 ） 式 代 入 目 标 函 数
（ 1.20）,整理后得
j
m
i
iji
n
mj
j
m
i
ii xaccbcz )(
111
令,
（ j=m+1,…,n）
于是再令
（ j=m+1,…,n）
则 （ 1.27）
m
i
ii bcz
1
0?
m
i
ijij acz
1
jj
n
mj
j xzczz )(
1
0
jjj zc
j
n
mj
j xzz?
1
0?
1,最优解的判别定理：
若 X(0)=( 0,…,0)T为对应与基 B的一个基可行解,
且 对 于 一 切 j=m+1,…,n 有
σj≤0,则 X(0)为最优解,称 σj
为检验数 。
,,,21 mbbb
2,无穷多最优解判别定理：
若 X(0)=(,0,…,0)T为一个基可行解,对于一切
j=m+1,…,n有 σj≤0,又存在某 个 非 基 变 量 的 检 验 数
σm+k=0,则线性规划问题有无穷多最优解 。
,,,21 mbbb
3,无界解判别定理,
若 X(0)=( 0,…,0)T
为一个基可行解,有一个
σm+k>0,并且对
i=1,2,…,m有 ai,m+k≤0,那么该线性规划问题具有无界解 （ 或称无最优解 ）
,,,21 mbbb
3.4 基变换
1,换入变量的确定：由 （ 1.27）
式看到,当某些 σj>0时,xj增加则目标函数还可以增大,这时要将某个非基变量 xj换到基变量中去 （ 称为换入变量 ） 。 若有两个以上的
σj>0,那么选哪个非基变量作为换入变量呢？
为了使目标函数值增加最快,从直观上一般选 σj>0种的大者 （ 可以任意选或按最小下标选 ） 即
max(σj>0)=σk
则对应的 xk为换入变量 。 （ 实际上换一次基将使目标函数值改进
σkθ） 。
1,换出变量的确定按最小比值确定换出变量。
3.5 迭代（旋转运算）
将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或 Gauss变换变为单位矩阵 。
例 7 试用上述方法计算例 6的两个基变换。
解 约束条件的增广矩阵为
x1 x2 x3 x4 x5 b
1210040
1601004
800121
当以 x3,x4,x5为基变量,x1，
x2为非基变量,令 x1 =x2=0，
可得到一个基可行解
X(0)=(0,0,8,16,12)
现用 x2去替换 x5,于是将 x3，
x4,x2的系数矩阵变换为单位矩阵经变换后为
x1 x2 x3 x4 x5 b
令非基变量 x1,x5=0,得到新的基可行解
X(1)=(0,3,2,16,0)T
34/10010
1601004
22/10101
§ 4 单纯形法的计算步骤为了便于迭代运算,可将上述方程组写成增广矩阵
-z x1 x2 … xm xm+1 … xn b
01
1000
0100
0010
121
1,
222,2
111,1
nmm
mmnmm
nm
nm
ccccc
baa
baa
baa
若将 z看成不参与基变换的基变量，它与 x1,x2,…,xm的系数构成一个基，这时可采用行初等变换将 c1,c2,…,c m变换为零，使其对应的系数矩阵为单位矩阵，
得到
-z x1 x2 … xm xm+1 … xn
b
m
i
ii
m
i
inin
m
i
miim
mmnmm
nm
nm
bcaccacc
baa
baa
baa
111
1,1
1,
222,2
111,1
0001
1000
0100
0010
可根据上述增广矩阵设计计算表如下：
cj c
1
… cm cm+1 … cn θ
CB xB b x
1
… xm xm+1 … xn
c1
C2
…
cm
x1
x2
…
x
m
b1
b2
…
bm
1
0
…
0
…
…
…
0
0
…
1
a1,m+1
a2,m+1
…
am,m+1
…
…
…
a1n
a2n
…
amn
θ1
θ2
…
θm
-z 0 … 0 …?
m
i
iibc
1
m
i
miim acc
1
1,1
m
i
inin acc
1
4.2 计算步骤
（ 1） 找出初始可行基,确定初始基可行解,建立初始单纯形表 。
（ 2） 检验各非基变量 xj的检验数是则已得到最优解 。 可停止计算 。 否则,转入下一步 。
（ 3 ） 在 中,若有某个对应项
xk的系数列向量 Pk≤0,则此问题是无界,停止计算 。 否则,转入下一步 。
nmjacc j
m
i
ijijj,,1,0
1
若
nmjj,,1,0
（ 4） 根据 max(σj>0)=σk,确定 xk为换入变量,按 θ规则计算可确定 xl为换入变量 。 转入下一步 。
（ 5） 以 alk为主元素进行迭代 （ 即用高斯消去法或称为旋转运算 ）,把 xk所对应的列向量将 xB列中的 xl换为 xk,得到新的单纯形表。重复（ 2） —（ 5），直到终止。
lk
l
ik
ik
i
a
ba
a
b )0|m in (?
0
1
0
0
2
1
mk
lk
k
k
k
a
a
a
a
P
将 xB列中的 xl换为 xk,得到新的单纯形表 。 重复 （ 2） —（ 5）,直到终止 。 现用例 1的标准型来说明上述计算步骤 。
（ 1） 根据例 1的标准型,去松弛变量 x3,x4,x5为基变量,它对应的单位矩阵为基 。 这就得到初始即可行解
X(0)=(0,0,8,16,12)T
将有关数值填入表中，得到初始单纯形表。
表 1-3
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
0 x3
0 x4
0 x5
8
16
12
1
4
0
2
0
4
1
0
0
0
1
0
0
0
1
4
-
3
-z 0 2 3 0 0 0
各非基变量的检验数为
σ1=c1-z1=2-
(0× 2+0× 1+0× 4+0× 0)=2
σ2=c2-z2=3-
(0× 2+0× 2+0× 0+0× 4)=3
(2)因检验数都大于 0,且 P1,P2有正分量存在,转入下一步
（ 3） max(σ1,σ2)=max(2,3)=3;对应的变量 x2 为换入变量 。 计算 θ
θ=
它所在行对应的 x 为换出变量,x 所在
3)4/12,,2/8m i n ()0|(m i n 2
2
i
i
i
i
aab
以 [4]为主元素进行旋转运算,即初等变换,
使 P2变为 （ 0,0,1）
T,在 xB列中将 x2替换 x5,
于是得到新表 1-4
cj
cB xB b 2x1 3x2 0x3 0x4 0x5 θ
0 x3
0 x4
3 x2
2
16
3
1
4
0
0
0
1
1
0
0
0
1
0
-1/2
0
1/4
2
4
-
-z 9 2 0 0 0 -3/4
由于检验数有正数,还没有得到最优解,max(σ1,
σ5)=max(2,-3/4)=2=σ1,则 x1 为换入变量,
θ=
则 x3为换出变量。以 1为主元数进行旋转运算，得
2),4/16,1/2m i n ()0|(m i n 1
1
i
i
i
i
a
a
b
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
2 x1
0 x4
3 x2
2
8
3
1
0
0
0
0
1
1
-4
0
0
1
0
-1/2
2
1/4
-
4
12
-z -13 0 0 -2 0 1/4
由于检验数有正数,还没有得到最优解,max(σ3,σ5)=max(-
2,1/4)=1/4=σ5,则 x5为换入变量,
θ=
则 x4为换出变量。以 2 为主元数进行旋转运算，得
4))4/1/(3,2/8,m i n ()0|(m i n 5
5
i
i
i
i
a
a
b
表 1-6,
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
-2
1/2
1/4
1/2
-1/8
0
1
0
-z -13 0 0 -2 0 1/4
得到最优解 X=(4,2,0,0,4),最优值 z=14,
§ 5 单纯形法的进一步讨论
5.1 人工变量法
5.1 人工变量法设线性规划问题的约束条件是分别给每一个约束方程加入人工变量 xn+1,xn+2,…,xn+m,得到
n
j
jj bxP
1
a11x1+a12x2+… +a1nxn+xn+1
=b1
a21x1+a22x2+… +a2nxn +xn+2
=b2
……………………… ……………
am1x1+am2x2+… +amnxn
+ xn+m =bm
x1,x2,…,xn≥0,xn+1,xn+2,…,xn+m≥0
以 xn+1,xn+2,…,xn+m为基变量,则可得到 m× m一个单位矩阵,l令非基变量 x1,x2,…,xn为零,得到一个初始基可行解
X(0)=(0,0,…,0,b1,b2,…,bm)T
若经过基变换后，得到的最终单纯形表中当所有的 cj-zj≤0，基变量中不包含人工变量，就得到原问题的一个基可行解，否则，原问题无可行解。
1、大 M法在一个线性规划问题的约束条件中加入人工变量后,要求人工变量对目标函数的取值无影响,为此可取人工变量在目标函数中的系数为 -
M(M为非常大的正数 ),这样目标函数要实现最大化,人工变量只能取零,因此必须把人工变量从基变量中换出,否则目标函数就不可能实现最大化 。
例 7 用大 M法求解线性规划问题
min z=-3x1+x2+x3
x1-2x2+x3≤11
-4x1+x2+2x3≥3
-2x1 +x3=1
x1,x2,x3≥0
解在上述问题的约束条件中加入松弛变量,剩余变量和人工变量,得到
min z=-3x1+x2+x3+0x4+0x5+Mx6+Mx7
x1-2x2+x3+x4=11
-4x1+x2+2x3-x5+x6=3
-2x1 +x3+x7=1
x1,x2,x3,x4,x5,x6,x7≥0
用单纯形表进行计算,得到最优解是
x1=4,x2=1,x3=9,x4=x5=x6=x7=0,最优值 z=-2
cj
cB xB
b -3
X1
1
x2
1
x3
0
x4
0
x5
M
x6
M
x7
Θ
0 x4
M x6
Mx7
11
3
1
1
-4
-2
-2
1
0
1
2
1
1
0
0
0
-1
0
0
1
0
0
0
1
11
3/2
1
cj-zj -3+6M 1-M 1-3M 0 M 0 0
0 x4
M x6
1x3
10
1
1
3
0
-2
-2
1
0
0
0
1
1
0
0
0
-1
0
0
1
0
-1
-2
1
1
cj-zj -1 1-M 0 0 M 0 3M-1
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
2
1
0
-5
-2
1
4
cj-zj -1 0 0 0 1 M-1 M+1
-3 x1
1 x2
1x3
4
1
9
1
0
0
0
1
0
0
0
1
1/3
0
2/3
-2/3
-1
-4/3
2/3
1
4/3
-5/3
-2
-7/3
2 0 0 0 1/3 1/3 M-1/3 M-2/3
2,两阶段法由于大 M法在使用电子计算机求解时，只能用很大的数代替 M，这就可能造成计算上的出错。
故下面介绍两阶段法。
第一阶段不考虑原问题是否存在基可行解,给原线性规划问题加上人工变量,构造仅含人工变量的目标函数和要求实现最小化 。 即求解如下问题：
minω=0x1+… +0xn + xn+1+… +xn+m
a11x1+a12x2+… +a1nxn+ xn+1 =b1
a21x1+a22x2+… +a2nxn + xn+2 =b2
……………………………………
am1x1+am2x2+… +amnxn + xn+m =bm
x1,x2,…,xn≥0,xn+1,xn+2,…,xn+m≥0
若得到 ω=0，这说明原问题存在基可行解，可以进行第二阶段的计算否则，原问题无可行解。
第二阶段：将第一阶段得到的最优单纯形表，除去人工变量，将原目标函数的系数换掉该表的目标函数的系数行，作为第二阶段计算的初始表。
例 9 用两阶段法求解下面的线性规划问题：
min z=-3x1+x2+x3
x1-2x2+x3≤11
-4x1+x2+2x3≥3
-2x1 +x3=1
x1,x2,x3≥0
解将上面的问题的约束方程加上人工变量得到第一阶段的问题：
min z=x6+x7
x1-2x2+x3+x4=11
-4x1+x2+2x3-x5+x6=3
-2x1 +x3+x7=1
x1,x2,x3,x4,x5,x6,x7≥0
第一阶段
cj
cB xB
b 0
X1
0
x2
0
x3
0
x4
0
x5
1
x6
1
x7
Θ
0 x4
1 x6
1x7
11
3
1
1
-4
-2
-2
1
0
1
2
1
1
0
0
0
-1
0
0
1
0
0
0
1
11
3/
2
1
cj-zj 6 -1 -3 0 1 0 0
0 x4
1 x6
1x3
10
1
1
3
0
-2
-2
1
0
0
0
1
1
0
0
0
-1
0
0
1
0
-1
-2
1
1
cj-zj 0 -1 0 0 1 0 3
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
2
1
0
-5
-2
1
4
-
-
cj-zj 0 0 0 0 0 1 1
第二阶段
cj
cB xB
b -3
x1
1
x2
1
x3
0
x4
0
x5
Θ
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
4
-
-
cj-zj -1 0 0 0 1
-3 x1
1 x2
1x3
4
1
9
1
0
0
0
1
0
0
0
1
1/3
0
2/3
-2/3
-1
-4/3
cj-zj 2 0 0 0 1/3 1/3
最优解为,x1=4,x2=1,x3=9,
最优值 z=-2
第二章 对偶理论与灵敏度分析
§ 1 单纯形法的矩阵描述设线性规划问题
Max z=CX
AX≤b
X≥0
给这个线性规划问题的约束条件加入松弛变量
Xs=( xn+1,xn+2,…,xn+m)T得到标准型：
Max z=CX+0X (2.1)
AX+IXs=b (2.2)
X,Xs≥0 (2.3)
设 B是一个可行基,即基矩阵 。 若将系数矩阵
(A,I)分为 （ B,N） 两块,这里 N是非基变量的系数矩阵 。 对应于 B的基变量,用向量
XB=(xB1,xB2,…,xBm)T表示,则同时 C=(CB,CN)于是
（ B,N） =b
(CB,CN) =CBXB+CNXN
S
B
X
XX
S
B
X
X
S
B
X
X
将 （ 2.1）,（ 2.2）,（ 2.3） 改写为
Max z=CBXB+CNXN (2.4)
BXB+NXN=b (2.5)
XB,XN≥0
将 （ 2.5） 移项后得到
BXB =b-NXN （ 2.6）
对 （ 2.6） 左乘 B-1后得
XB = B-1b- B-1NXN （ 2.7）
将 （ 2.7） 代入 （ 2.4） 得
z=CB B-1b+(CN- CBB-1N)XN (2.8)
令非基变量 XN=0,得到一个基可行解目标函数值
z= CB B-1b
0
1
)1( bBX
从 92.7),(2.8)可以看出
（ 1） 目标函数中非基变量得系数 CN- CBB-1N就是第一章的检验数 。 因为 XB在 （ 2.8） 中的系数是 0,即
CB-CBB-1B=0
又因 CN中对应于 Xs的系数为 0，在（ 2.8）式中
Xs的系数实质上是 0-CBB-1,因此所有检验数都可用 C-CBB-1A与 -CBB-1表示。
（ 2） 用矩阵描述时 θ规则的表达式是 2
lj
l
ij
ij
i
i PB
bB
PB
PB
bB
)(
)(
0)(|
)(
)(
m i n
1
1
1
1
1
(3)单纯形表为了便于在表中找出 B-1所在的位置,将 （ 2.4）,
（ 2.5） 改写为
-z+CBXB+CN1XN1+0Xs=0
BXB+NXN+IXs=b
当确定 XB为基变量时,经过基变换后可得到 XB与
z得表达式 （ 2.7）,（ 2.8） 并将他们改写为
XB+B-1N1XN+B-1Xs=B-1b
-z+（ CN-CBB-1N1） XN1- CBB-1Xs=- CBB-1b
上述两式用矩阵表示为
b
bB
X
X
X
z
I
s
N
B
1-
B
1
1-
B1
1-
BN
1-
1
1-
BC-BC-NBC-C01
BNB0
设 B是一个可行基,即基矩阵 。 若将系数矩阵
(A,I)分为 （ B,N） 两块,这里 N是非基变量的系数矩阵 。 对应于 B的基变量,用向量
XB=(xB1,xB2,…,xBm)T表示，则同时 C=(CB,CN)于是
（ B,N） =b
(CB,CN) =CBXB+CNXN
S
B
X
X
X
S
B
X
X
S
B
X
X
用表格表示为表 2-1
基变量 非基变量 RHS
XN1 Xs
I
0
B-1N1
CN-CBB-1N1
B-1
- CBB-1
B-1b
- CBB-1b
§ 3对偶问题的提出第一章的例 1讨论了利用有限的资源如何安排生产才能获得最大的利润的问题。现在从另一角度来讨论这个问题。假设该工厂的决策者决定这些资源不用来生产而是考虑将其出租或出售。这时决策者就要考虑给每种资源如何定价的问题。
设用 y1,y3,y3分别表示出租单位设备台时的租金和出让单位原材料 A,B得附加值 。 于是
y1+4y2≥2
2y1+4y3≥3
则所有资源出租和出让,其所得收入为
ω=8y1+16y2+12y3
则得到下面的线性规划问题
minω=8y1+16y2+12y3
y1+4y2≥2
2y1+4y3≥3
y1,y2,y3≥0
称这个线性规划问题为原问题的对偶问题。
下面在从另一角度来讨论。
从 § 1得到检验数的另一表达式是
CN-CBB-1N与 - CBB-1
由第一章知,当检验数
CN-CBB-1N≤0
CBB-1≤0
则线性规划问题已得到最优解。可见（ 2.9），
（ 2.10）是作为得到最优解的条件。
1,（ 2.9）,（ 2.10） 中都有乘子 CBB-1,称为单纯形乘子并用符号 Y=CBB-1表示 。 由于 （ 2.10）
的条件,可得 Y≥0
2.对应基变量 XB的检验数是 0。 它是 CB-CBB-1B=0.
包括基变量在内的所有检验数可用 C-CBB-1A≤0表示 。 即 C-CBB-1A=C-YA≤0,移项得到 YA≥C
3.由条件 （ 2.10） 得到 -Y=- CBB-1
即 Yb= CBB-1b=z因 Y的上界为无限大，所以只存在最小值。
4,在这里可以得到另一个线性规划问题
Min ω=Yb
YA≥C
Y≥0
称它为原线性规划问题 {Max z=CX|AX≤b,X≥0}
的对偶规划问题。
从这两个规划问题的表达式可看出：根据原线性规划问题的系数矩阵 A,C,b就可以写出它的对偶问题。如第一章的例 1，原问题的系数矩阵是；
40
04
21
A );3,2(?C
12
16
8
b
那麽它的对偶问题是
Min ω=Y（ 8,16,12） T
Y ≥（ 2,3）
Y≥0
这里 Y=( y1,y2,y3)
即
minω=8y1+16y2+12y3
y1+4y2≥2
2y1+4y3≥3
y1,y2,y3≥0
40
04
21
§ 4 线性规划的对偶理论
4.1 原问题和对偶问题的关系表 2-2
x
y
x1 x2 c xn 原关系 minω
y1
Y2
…
ym
a11 a12 …
a1n
a21 a22 … a2n
……………
am1 am2…
amn
≤
≤
…
≤
b1
B2
…
bm
对偶关系 ≥≥ … ≥ Max z=
minω
Max z c1 c2 … cn
例 1 试求下述线性规划问题的对偶问题
min z=2x1+3x2-5x3+x4
x1+x2-3x3+x4≥5
2x1 +2x3-x4≤4
x2+x3+x4=6
x1≤0,x2,x3≥0;x4无约束解设对应于三个约束条件的对偶变量分别为 y1,y2,y3;
由于目标函数是求极小值,由上表知其对偶问题为
max z’=5y1+4y2+6y3
y1+2y2≥2
y1+y3≤3
-3y1+2y2+y3≤-5
y1-y2+y3=1
y1≥0,y2≤0,y3无约束
4.2 对偶问题的基本性质
1,对称性 对偶问题的对偶是原问题 。
2,弱对偶性 若 X*是原问题的可行解,Y*是对偶问题的可行解 。 则存在
CX*≤Y*b
3,无界性 若原问题 （ 对偶问题 ） 为无界解,则其对偶问题 （ 原问题 ） 无可行解 。
4、可行解是最优解时的性质 设 X^是原问题的可行解,Y^是对偶问题的可行解，当 CX^=Y^b时，
X^,Y^是最优解。
5,对偶定理 若原问题有最优解,
那么对偶问题也有最优解且最优值相同 。
6、互补松驰性 若 X^,Y^分别是对偶问题和原问题的可行解。那么
Y^Xs=0和 YsX^=0,当且仅当 X^,Y^
为最优解。
7,设原问题是
max z=CX;AX+Xs=b,X,Xs≥0
它的对偶问题是
min ω=Yb;YA-Ys=C;Y,Ys≥0
则原问题单纯形表的检验数行对应其对偶问题的一个基解,其对应关系如下表：
其中 Ys1对应于原问题中基变量 XB的剩余变量,Ys2对应于原问题中非基变量 XN的剩余变量。
XB XN XS
0
-Ys2
Ys1
-CBB-1
CN-CBB-1N
-Y
例 4
已知线性规划问题
max z=x1+x2
-x1+x2+x3≤2
-2x1+x2-x3≤1
x1,x2,x3≥0
试用对偶理论证明该线性规划问题无优解。
证首先看到该问题存在可行解 X=(0,0,0);而对偶问题为
min ω=2y1+y2
-y1-2y2≥1
y1+y2≥1
y1-y2≥0
y1,y2≥0
由于该问题无可行解，故原问题无最优解。
例 5
已知线性规划问题
min ω=2x1+3x2+5x3+2x4+3x5
x1+x2+2x3+x4+3x5≥4
2x1-x2+3x3+x4+x5≥3
x1,x2,x3,x4,x5≥0
已知其对偶问题的最优解为 y1*=4/5，
y2*=3/5;z=5.用对偶理论求出原问题的最优解。
解先写出它的对偶问题
max z=4y1+3y2
y1+2y2≤2 （ 1）
y1-y2≤3 （ 2）
2y1+3y2≤5 （ 3）
y1+y2≤2 （ 4）
3y1+y2≤3 （ 5）
y1,y2≥0 （ 6）
将 y1*,y2*的值代入约束条件，得
（ 2），（ 3），（ 4）为严格不等式；
由互补松弛性得 x2*=x3*=x4*=0,因
y1,y2≥0;原问题的两个约束条件应取等式，即
3x1*+x5*=4
2x1*+x5*=3
求解得 x1*=1,x2*=1,故原问题的最优解为
X*=(1,0,0,0,1); ω*=5.
§ 6 对偶单纯形法前面讲到原问题与对偶问题的解之间的关系时指出：在单纯形表中进行迭代时，在 b列中得到的时原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代。当在检验数行得到对偶问题的解也是基可行解时，则已得到最优解，即原问题和对偶问题都是最优解。
根据对偶问题的对称性，若保持对偶问题的解是基可行解，
即 cj-CBB-1Pj≤0而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解，其优点是原问题的初始解不一定要是基可行解，可从非基可行解开始迭代，
方法如下：
设原问题为
max z=CX
AX=b
X≥0
又设 B是一个基。不失一般性，令 B=
（ P1,P2,…,Pm）,它对应的变量为
XB=(x1,x2,…,xm)
当非基变量都为 0时，可以得到 XB=B-1b.若 B-1b
中至少有一个负分量，设（ B-1b） I<0,并且在单纯形表的检验数行中得检验数都为非正，即对偶问题保持可行解，
它的个分量是
1,对应基变量 x1,x2,…,xm的检验数是
σi=ci-zi=ci- CBB-1Pi=0,i=1,2,…,m
2,对应非基变量 xm+1,…,xn的检验数是
σj=cj-zj=cj- CBB-1Pj≤0,j=m+1,…,n
每次迭代是将基变量中的负分量 xl取出，取替换非基变量中的 xk,经基变换，所有检验数仍保持非正，从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。
对偶单纯形法的计算步骤：
根据线性规划问题，列出初始单纯形表。检查 b
列的数字，若都为非负，检验数都为非正，则得到了最优解。停止计算。若检查 b列的数字时，
至少还有一个负分量，检验数保持非正，那么进行一下计算。
（ 2） 确定换出变量按对应的基变量 xl为换出变量。
（ 3） 确定换出变量在单纯形表中检查 xl所在行的各系数
alj≥0,则无可行解。停止计算。
若存在 alj<0(j=1,2,…,n),计算按 θ规则所对应的列的非基变量 xk为换入变量，这样才能保持得到的对偶问题解仍然为可行解。
liii bBbBbB 111 0|m in
lk
kk
lj
lj
jj
j a
zca
a
zc?
0|m i n?
4、以 alk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复（ 1） -（ 4）的步骤。
下面来举例说明具体的算法。
例 6 用对偶单纯形法求解
min ω=2x1+3x2+4x3
x1+2x2+x3≥3
2x1-x2+3x3≥4
x1,x2,x3≥0
解现将问题化为下面的形式，以便得到对偶问题的初始可行基
max z=-2x1-3x2-4x3
-x1-2x2-x3+x4=-3
-2x1+x2-3x3+x5=-4
x1,x2,x3,x4,x5≥0
建立该问题的初始单纯形表 2-6如下
cj
cB xB b
-2
x1
-3
x2
-4
x3
0
x4
0
x5
0 x4
0 x5
-
3
-
4
-1
[-2]
-2
1
-1
-3
1
0
0
1
cj-zj -2 -3 -4 0 0
表 2-7
cj
cB xB
b -2
x1
-3
x2
-4
x3
0
x4
0
x5
0 x4
-2 x1
-1
2
0
1
[-5/2]
-1/2
1/2
3/2
1
0
-1/2
-1/2
cj-zj 0 -4 -1 0 -1
表 2-8
cj
cB xB
b -2
x1
-3
x2
-4
x3
0
x4
0
x5
-3 x2
-2 x1
2/5
11/5
0
1
1
0
-1/5
7/5
-2/5
-1/5
1/5
-2/5
cj-zj 0 0 -3/5 -8/5 -1/5
最优解为 y*=(y1*,y2*)=(8/5,1/5)
从以上求解过程可以看到，对偶单纯形法有以下优点：
（ 1） 初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。
（ 2） 当变量多余约束条件，对这样的线性规划问题，用对偶单纯形法可以减少计算的工作量。
因此对变量较少而约束条件很多的线性规划问题，
可以先将它变为对偶问题，然后用对偶单纯形法求解。
在灵敏度分析中,有时需要用对偶单纯形法，可是问题的处理简化。对偶单纯形法的局限性主要是对大多数线性规划问题，痕难找到一个初始可行基，因而这方法很少单独使用。
§ 7 灵敏度分析当线性规划问题的系数发生变化时，最优解一般要发生变化，主要有以下几种情况：
原问题 对偶问题 结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解表中的解仍然为最优解用单纯形法继续迭代求最优解用对偶单纯形法迭代求最优解引进人工变量，编制新的单纯形表，
求最优解下面就各种情况分别进行讨论。
7.1 资源数量变化的分析资源数量变化是指系数 br发生变化，即
br’=br+Δbr.并假设问题的其它系数都不变。这样使原问题的解变为
XB’=B-1(b+Δb)
这里 Δb=（ 0,…,Δbr,0,…,0） T.只要 XB’
≥0，最终表的检验数不变，则最优基不变，但最优解的值发生了变化，所以 XB’为新的最优解。
新的最优解的值可允许变化的范围用以下方法确定。
B-1(b+Δb)= B-1b+ B-1Δb
= B-1b+ B-1,B-1=
0
0
r
b
mr
ir
r
r
rmr
rir
rr
r
a
a
a
b
ba
ba
ba
b
11
0
0
这时在最终表中求得的 b列的所有元素
，
由此得当
mibab riri,,2,1,0
mibba irir,,2,1,
于是得到时,;/0 iririr abba;/0 iririr abba 时，
}0|/{m i n}0|/{m a x iririiririri
i
aabbaab
例如求第一章例 1中第二个约束条件 b2
的变化范围 Δb2时，可计算
B-1b+ B-1
可得的变化范围是 [-8,16];显然 b2的变换范围是 [8,32]。
0
0
0
1 2 5.0
5.0
25.0
2
4
4
0
0
rr bb
,85.0/4,1625.0/4 22 bb
22,16125.0/2 bb 所以例 1
从表 1-5得知第一章例 1中，每设备台时的影子价格为 1.5元，若该厂又从别处抽出 4台时用于生产，求这时该厂生产产品的最优方案。
解 先计算 B-1Δb
B-1Δb=
将上述结果反映到最终表中得
2
8
0
0
0
4
0125.05.0
15.02
025.00
表 2-10。
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3 x2
4+0
4-8
2+2
1
0
0
0
0
1
0
-2
0.5
0.25
0.5
-
0.125
0
1
0
cj-zj 0 0 -1.5 -
0.125
0
由于 b列中有负数，故用对偶单纯形法求新的最优解。计算结果如下表表 2-11
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
2 x1
0 x3
3 x2
4
2
3
1
0
0
0
0
1
0
1
0
0.25
-0.25
0
0
-0.5
0.25
cj-zj 0 0 0 -0.5 -0.75
即该厂最优生产方案应改为 Ⅰ 4件,Ⅱ 3件，获利
z*=17元从表中看出 x3=2,即设备有两小时未被利用。
7.2 目标函数中价值系数 cj的变化分析可以分别就 cj时对应的非基变量和基变量两种情况来讨论。
（ 1） 若 cj是非基变量 xj的系数，这时他在计算表中所对应的检验数是
σj =cj- CBB-1Pj
或 σj=
当 cj变化 Δcj时，要保证最终表中这个检验数仍然小雨或等于零，即
σj’=cj+Δcj- CBB-1Pj≤0
那么 cj+Δcj≤YPj,即 Δcj的值必需小于或等于 YPj-cj,才可以满足原最优解条件，这可以确定 Δcj的变化范围了。
m
i
iijj yac
1
(2)若 cr是基变量 xr的系数。因 cr∈ CB,
当 cr变化 Δcr时，就引起 CB的变化，这时
(CB+ΔCB)B-1A=CB B-1A+(0,…,
Δcr,…,0) B-1A
= CB B-1A+Δcr(ar1,ar2,…,arn)
可见当 cr变化 Δcr时，最终表中的检验数是
σj’=cj - CBB-1A-Δcjarj’,j=1,2,…,n
若要求原最优解不变，即必需满足
σj’≤0。于是得到当 arj’<0,Δcr≤σj/a rj’
arj’>0,Δcr≥σj/a rj’ j=1,2,…,n
Δcr可变化的范围是
}0|/{m i n}0|/{m a x rjrjjjrrjrjjj aacaa
例 1 试以第一章例 1的最终表 1-5为例，设基变量 x2的系数 c2
变化 Δc2，在原最优解不变的条件下，确定 Δc2的变化范围。
解 这时表 1-5最终计算表变成为表 2-12：
cj
cB xB
b 2
x1
3+Δc2
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
4
0.5
0.25
0.5
-
0.125
0
1
0
cj-zj 0 Δc2 -1.5 -
0.125
0
为了保持原最优解不变，则 x2的检验数应当为零，于是得表 2-13a
cj
cB xB
b 2
x1
3+Δc2
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3+Δc2 x2
4
4
2
1
0
0
0
0
1
0
-4
0.5
0.25
0.5
-0.125
0
1
0
cj-zj 0 0 -1.5
-Δc2/2
Δc2/8
-0.125
0
从上表可见有：
-1.5-Δc2/2≤0和 Δc2/8-0.125≤0，由此可得
Δc2≥-1.5/0.5； Δc2≤1。 Δc2的变化范围为,-
3≤Δc2≤1。即 c2可以在 [0,4]内变化而不影响原最优解。
7.3 技术系数 aij的变化分两种情况来讨论技术系数 aij的变化，下面一具体的例 ]子来说明：
例 9
分析在原计划中是否应该安排一种新产品 。
以第一章例 1的最终表 1-5为例,设该厂除了生产产品 Ⅰ,Ⅱ 外,还生产新产品 Ⅲ,已知生产产品 Ⅲ,每件需消耗原材料 A,B各为 6㎏,3㎏,
是用设备 2台时 。 每件可获利 5元,问该厂是否应生产新产品和生产多少？
解 分析这问题的步骤是：
（ 1） 设生产产品 Ⅲ x3’台，其技术向量
P3’=(2,6,3)T,然后计算最终表中对应于 x3’的检验数
σ3‘=c3’-CBB-1P3’=5-(1.5,0.125,0)(2,6,3)T=1.25>0
说明安排生产产品 Ⅲ 是有利可图的 。
（ 2） 计算 Ⅲ 在最终表中对应 x3’的列向量
B-1P3’=
25.0
2
5.1
3
6
2
0125.05.0
15.02
025.00
并将（ 1），（ 2）中的计算结果填入最终计算表 1-5得表 2-
13b：
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
5
x3’
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
-2
0.5
0.25
0.5
-
0.125
0
1
0
1.5
[2]
0.25
cj-zj 0 0 -1.5 -
0.125
0 1.25
可行解，但检验数还有正数，说明目标寒暑值还可以改善。
（ 3）进行迭代得最优单纯形表 2-13c:
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
5
x3’
2 x1
0 x3’
3 x2
1
2
1.5
1
0
0
0
0
1
1,5
–1
0.75
-0.125
0.25
-0.1875
-0.75
0,5
-0.125
0
1
0
cj-zj 0 0 -0.25 -0.4375 -0.625 0
例 10
分析原计划生产产品的工艺结构发生变化 。
以第一章例 1为例 。 若 P1’=(2,5,2)T,每件利润为 4元,试分析原最优计划有什么影响？
B-1P1’=
x1’的检验数为
σ1‘=c1’-CBB-1P1’=4-
(1.5,0.125,0)(2,5,2)T=0.375
375.0
5.0
25.1
2
5
2
0125.05.0
15.02
025.00
将以上结果填入最终表 x1的列向量位置，得表 2-14
cj
cB xB b
2
x1
4
x1’
3
x2
0
x3
0
x4
0
x5
4 x1
0 x5
3 x2
4
4
2
1
0
0
1.25
50.5
0.375
0
0
1
0
-2
0.5
0.25
0.5
0.125
0
1
0
cj-zj 0 0.375 0 -1.5 -
0.125
0
经迭代得最优表 2-15：
cj
cB xB b
4
x1‘
3
x2
0
x3
0
x4
0
x5
4 x1‘
0 x5
3 x2
3.2
2.4
0.8
1
0
0
0
0
1
0
-2
0.5
0.2
0.4
-0.2
0
1
0
cj-zj 0 0 -1.5 -0.2 0
上表表明原问题和对偶问题得解都是可行解所以表中的结果已是最优解 。 即应当生产
Ⅰ ‘3.2单位；生产产品 Ⅱ 0.8单位 。 可获利
15.2元 。
注意,若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解。
例 11
设例 10中 Ⅰ ‘的技术系数向量为 P1’=(4,5,2)T，
而每件获利仍然为 4元 。 试问应如何安排最优生产方案？
解 方法与例 10相同,以 x1’代替 x1,计算
B-1P1’=
x1’的检验数为
σ1‘=c1’-CBB-1P1’=4-(1.5,0.125,0)(4,5,2)T=-2.625
3 7 5.1
5.3
25.1
2
5
4
01 2 5.05.0
15.02
025.00
将以上结果填入最终表 x1的列向量位置，
得表 2-16
cB xB b x1’ x2 x3 x4 x5
4 x1
0 x5
3 x2
4
4
2
1.25
-3.5
1.357
0
0
1
0
-2
0.5
0.25
0.5
0.125
0
1
0
cj-zj -
2.625
0 -1.5 -
0.125
0
将表 2-16的 x1’替换基变量中的 x1，得表 2-17
cB xB b x1’ x2 x3 x4 x5
4 x1‘
0 x5
3 x2
3.2
15.3
-2.4
1
0
0
0
0
1
0
-2
0.5
0.2
1.2
-0.4
0
1
0
cj-zj 0 0 -1.5 0.4 0
由于原问题与对偶问题都是非可行解 。
于是引入人工变量 x6因在表 2-17中 x2
所在行,用方程表示时为
0x1’+x2+0.5x3-0.4x4+0x5=-2.4
引入人工变量 x6后,便为
-x2-0.5x3+0.4x4+x6=2.4
将 x6作为基变量代替 x2,填入表
2-17的表 2-18
cB xB b x1’ x2 x3 x4 x5 x6
4 x`1
0 x5
-M x6
3.2
15.2
2.4
1
0
0
0
0
-1
0
-2
-0.5
0.2
1.2
[0.4]
0
1
0
0
0
1
cj-zj 0 3-M -0.5M -0.8
+0.4M
0 0
用单纯形法求解得表 2-19
cj
cB xB b
4
x1‘
3
x2
0
x3
0
x4
0
x5
-M
x6
4 x1‘
0 x5
0 x4
2
8
6
1
0
0
0.5
3
-2.5
1.25
–0.5
–1.25
0
0
1
0
1
0
0.5
-3
2.5
cj-zj 0 1 -1 0 0 -M+2
4 x1‘
3 x2
0 x4
0.667
2.667
12.667
1
0
0
0
1
0
0.33
-
0.167
1.667
0
0
1
-0.33
0.33
0.83
0
-1
0
cj-zj 0 0 -0.83 0 -0.33 -M+2
除以上介绍的几项分析外，还可以作增减约束条件的分析。
njmi
j
x
i
b
n
j
j
x
ij
a
tS
n
j
j
x
j
cz
,,2,1;,2,1
0
1.
1
m a x
向量和矩阵表示
max z=CX
X=
其中,C=(c1,c2,…,cn )
向量 Pj对应的决策变量是 xj,
njjx
b
n
j
jxjP
,,2,1,0
1
nx
x
x
2
1
m
b
b
b
b
mj
a
j
a
j
a
j
P
2
1
,2
1
矩阵形式为：
max z=CX
s.t
0X
BAX;,
2
,
1
21
22221
11211
m
PPP
mn
a
m
a
m
a
n
aaa
n
aaa
A?
0
0
0
0
称 A为约束条件的 m× n维系数矩阵,
一般 m<n;m,n>0;
b为资源向量；
C为价值向量；
X为决策变量向量 。
实际遇到的各种线性规划问题的数学模型都应变换为标准形式后求解 。
以下讨论如何化标准型的问题：
若要求目标函数实现最小化,即 min z=CX.这时只需将目标函数最小化变换为最大化，即令 z`=-z,于是得到 max z`=-CX,这就和标准型的目标函数的形式一致了。
（ 2） 约束方程为不等式 。 这里有两种情况：一种是约束方程为 ‘ ≤’ 不等式,则可在 ‘ ≤’ 不等式的左边加上非负松弛变量,
把原 ‘ ≤’ 不等式变为等式；另一种是约束方程 ‘ ≥’ 不等式,则可在 ‘ ≥’ 不等式的左端减去一个非负剩余变量 （ 也可称松弛变量 ）,
把不等式约束条件变为等式约束条件 。
(3)若存在取值无 （ 符号 ）
约束的变量 xk,可令 xk=xk`-
xk``,其中 xk`,xk``≥0。
下面举例说明例 3 将下面的数学模型化为标准型 。
Max z=2x1+3x2
x1+2x2≤8
4x1≤16
4x2≤12
x1,x2≥0
解将各不等式加上松弛变量即得
Max z=2x1+3x2
x1+2x2+x3=8
4x1+x4=16
4x2+x512
x1,x2,x3,x4,x5≥0
例 3 将下述线性规划问题化为标准型
min z=-x1+2x2-3x3
x1+x2+x3≤7
x1-x2+x3≥2
-3x1+x2+2x3=5
x1,x2≥0,x3为无约束解步骤为
1,令 x3=x4-x5,其中 x4,x5≥0;
2,在第一个不等式 ≤的左边加上松弛变量 x6;
3,在第二个不等式 ≥的左边减去剩余变量 x7;
4,令 z`=-z,把求 min z 改为求 max z`; 即可得该问题的标准型
max z`=x1-2x2+3(x4-x5)
x1+x2+(x4-x5)+x6 =7
x1-x2+(x4-x5) -x7=2
-3x1+x2+2(x4-x5)=5
x1,x2,x4,x5,x6,x7≥0
1.4 线性规划问题的解概念可行解满足约束条件和非负约束的解称为可行解，而使目标函数达到最大值的可行解叫最优解。
不失一般性，可设称 PJ（ J=1,2,…,m）为基向量，
与基向量 Pj相应的
xj(j==1,2,…,m)为基变量。否则称为非基变量。
m
PPP
mm
a
m
a
m
a
m
aaa
B?
,
2
,
1
21
11211
为了进一步讨论线性规划问题的解，下面研究约束方程
（ 1.5）的求解问题。假设该方程组系数矩阵 A的秩为 m,
因 m<n,故它有无穷多个解。
假设前 m个变量的系数列向量是线性独立的。
这时（ 1.5）可写成
n
x
mn
a
n
a
n
a
m
x
mm
a
m
a
m
a
m
b
b
b
m
x
mm
a
m
a
m
a
x
m
a
a
a
x
m
a
a
a
2
1
1
1
12
11
2
1
2
1
2
2
22
21
1
1
12
11
方程组 （ 1.7） 的一个基是
m
PPP
mm
a
m
a
m
a
m
aaa
B?
,
2
,
1
21
11211
设 XB是对应于这个基的基变量
XB=(x1,x2,…,xm)T
现若令 （ 1.7 ） 的 非 基 变 量
xm+1=xm+2=… =xn=0,并用高斯消去法,可以求出一个解
X=(x1,x2,…,xm,0,…,0)T
这个解的非零分量的数目不大于方程的个数 m,称为基解。于是，
由一个基可以求出一个基解。
基可行解满足非负条件（ 1.6）的基解，称为基可行解。于是基可行解的非零分量的数目也不大于 m,并且都是非负的。
可行基对应于基可行解的基，称为可行基。
可见，约束方程祖（ 1.5）具有的基解的数目最多是个。
基解中非零分量的个数小于
m时（或基变量有零时），这基解（或基可行解）称为退化解（或退化基可行解）。
§ 2 线性规划问题的几何意义
2.1 基本概念凸集 设 K是 n维欧氏空间的一点集,
若任意两点 X(1)∈ K,X(2)∈ K的连线上的点 αX(1)+ （ 1-α ） ∈ K,
（ 0≤α≤1）,则称 K为凸集 。
一般的实心圆，实心多边形、实心多面体等都是凸集，而圆周和有洞的圆盘等都不是凸集。
凸组合 设 X(1),X(2),…,X(k)是 n维欧氏空间 En中的 k个点,若存在 μ1,μ2,…,
μk,且 0≤μi≤1,i=1,2,…,k; =1,使
X=μ1X(1)+μ2X(2)+… +μkX(k)
则称 X为 X(1),X(2),…,X(k)的凸组合。
1
1
k
i
i?
顶点 设 K是凸集,X∈ K,若 X不能用不同的两点 X(1)∈ K和 X(2)∈ K的线性组合表示为
X=αX(1)+（ 1-α） X(2),（ 0<α<1）
则称 X为 K的一个顶点（或极点）。
2.2 基本定理定理 1 若线性规划问题存在可行域,则其可行域是凸集 。
n
j
jjj xbxPXD
1
0,|
引理 1 线 性 规 划 问 题 的 可 行 解
X=(x1,x2,?,xn)T为基可行解的充分必要条件是 X的正分量是线性独立的 。
定理 2 线性规划问题的基可行解 X对应于可行域的顶点 。
引理 2 若 K是有界凸集,则任意一点
x∈ K可表示为 K的顶点的凸组合 。
定理 3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优 。
有时目标函数可能在多个顶点达到最大值。这时这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优值。
§ 3 单纯形法
3.1 单纯形法举例例 6 试以例 1来讨论它的求解。
例 1的标准型为
max z=2x1+3x2+0x3+0x4+0x5
x1+2x2+x3 =8
4x1 +x4 =16
4x2 +x5=12
xj ≥0,j=1,2,?,5
解 约束方程的系数矩阵
10040
01004
00121
),,,,(
54321
PPPPPA
从（ 1.12）中可以看到
x3,x4,x5的系数列向量是线性独立的，
1
0
0
,
0
1
0
,
0
0
1
543 PPP
这些向量构成一个基
100
010
001
),,(
543
PPPB
对应于 B的变量 x3,x4,x5 为 基 变 量,从
（ 1.12） 中可以得到
x3 =8-x1-2x2
x4 =16-4x1 （ 1.13）
x5=12- 4x2
将 （ 1.13） 代入目标函数 (1.11)得到
z=0+2x1+3x2
当令非基变量 x1=x2=0,便得到 z=0.这时得到一个基可行解 X(0)
X(0)=(0,0,8,16.12)T
现分析（ 1.13），由于 x2的系数为正，
显然当将 x2越大则目标函数 z的值也越大。当将 x2 定为换入变量后，必须从 x3,x4,x5中换出一个，并保证其余的变量都是非负，即 x3,x4,x5≥0。
当 x1=0,由 （ 1.13） 式得到
x3 =8 -2x2≥0
x4 =16≥0 （ 1.15）
x5=12-4x2≥0
从 （ 1.15） 中可以看出,x2的最大值只有选择
x2=min(8/2,-,12/4)=3
时，才能使（ 1.15）成立。
因当 x2=3时，基变量 x5=0，
这就决定用 x2去替换 x5。以上数学描述说明了每生产一件产品 Ⅱ,需要用掉各种资源的数量为 2,0,4。由这些资源中的薄弱环节，就确定了产品 Ⅱ 的产量，这里就是由原材料 B的数量确定了产品 Ⅱ 的产量 x2=12/4=3件。
为了求得以 x3,x4,x2为基变量的一个基可行解和进一步分析问题,需将 （ 1.13）
中 x2 与 x5的位置对换 。 得到
x3+2x2 =8- x1 (1)
x4 =16-4x1 (2) （ 1.16）
4x2=12- x5 (3)
用高斯消去法,将 （ 1.16） 式中的系数列向量变换为单位列向量 。 其运算步骤,
（ 3） ‘ =（ 3） /4； （ 1） ‘ =（ 1） -2×
（ 3） ‘ ； （ 2） ’ =（ 2）,并将结果仍按原顺序有：
x3 =2- x1 +1/2x5 (1)‘
x4 =16-4x1 (2)‘ （ 1.17）
x2=3-1/4 x5 (3)`
再将 （ 1.17） 代入目标函数 （ 1.11）
得到
z=9+2+2x1-3/4+2x5(1.18)
令非基变量 x1=x5 =0,得到 z=9,并得到另一个基可行解 X(1)
X(1)=(0,3,2,16,0)T
从目标函数的表达式 （ 1.18） 中可以看到,非基变量 x1的系数是正的,说明目标函数值还可以增大,X(1)不一定是最优解 。 于是再用上述方法,确定换入,换出变量,继续跌代,再得到另一个新的基可行解 X(2)，
X(2)=（ 2,3,0,8,0） T
再经过一次迭代,再得到一个基可行解 X(3)
X(3)=（ 4,2,0,0,4） T
而这时得到目标函数的表达式是：
z=14-1.5x3-0.125x4 (1.19)
再分析（ 1.19），可见到所有非基变量 x3,x4的系数都是负数。
这说明若要用剩余资源 x3,x4，就必须支付附加费用。所以当
x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以 X(3)是最优解。即应当产品 Ⅰ
生产 4件，产品 Ⅱ 生产 2件，工厂才能得到最大利润。
3.2初始基可行解的确定为了确定初始基可行解,要首先找出初始可行基,其方法如下：
1,若线性规划问题
0
m a x
1
1
j
n
j
jj
n
j
jj
x
bxP
xcz
从 Pj(j=1,2,…,n)中一般能直接观察到存在一个初始可行基
1000
0100
0010
0001
),,,(
21 m
PPPB?
2,对所有约束条件是,≤”
形式的不等式,可以利用化标准型的方法,在每个约束条件的左端加上一个松驰变量 。 经整理,
重新对 xj 及
aij(i=1,2,…,m;j=1,2,…,n) 进行编号,则可得下列方程组
x1 +a1,m+1xm+1+… +a1nxn=b1
x2 +a2,m+1xm+1+… +a2nxn=b2
………………………
xm
+am,m+1xm+1+… +amnxn=bm
xj≥0,j=1,2,… n
显然得到一个 m× m单位矩阵
1000
0100
0010
0001
),,,(
21 m
PPPB?
以 B作为可行基 。 移项得
x1=b1-a1,m+1xm+1-… -a1nxn
x2=b2-a2,m+1xm+1-… -a2nxn
………………………
xm=bm -am,m+1xm+1-… -amnxn
令 xm+1=xm+2=… =xn=0,由 （ 1.23） 可得
xi=bi (I=1,2,…,m)
又因 bj≥0,所以得到一个初始基可行解
X=(x1,x2,…,xm,0,…,0)T
=(b1,b2,…,bm,0,…,0)T
3.对所有约束条件是,≥” 形式的不等式及等式约束情况,若不存在单位矩阵时,就采取人造基的方法 。 即对不等式约束减去一个非负的剩余变量后,再加上一个非负的人工变量 。 对于等式约束加上一个非负的人工变量,总能得到一个单位矩阵 。
3,3 最优性检验与解的判别线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、
无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后（ 1.23）
式变为
(i=1,2,…,m) (1.24 )
j
n
mj
ijii xabx?
1
将 （ 1.24 ） 式 代 入 目 标 函 数
（ 1.20）,整理后得
j
m
i
iji
n
mj
j
m
i
ii xaccbcz )(
111
令,
（ j=m+1,…,n）
于是再令
（ j=m+1,…,n）
则 （ 1.27）
m
i
ii bcz
1
0?
m
i
ijij acz
1
jj
n
mj
j xzczz )(
1
0
jjj zc
j
n
mj
j xzz?
1
0?
1,最优解的判别定理：
若 X(0)=( 0,…,0)T为对应与基 B的一个基可行解,
且 对 于 一 切 j=m+1,…,n 有
σj≤0,则 X(0)为最优解,称 σj
为检验数 。
,,,21 mbbb
2,无穷多最优解判别定理：
若 X(0)=(,0,…,0)T为一个基可行解,对于一切
j=m+1,…,n有 σj≤0,又存在某 个 非 基 变 量 的 检 验 数
σm+k=0,则线性规划问题有无穷多最优解 。
,,,21 mbbb
3,无界解判别定理,
若 X(0)=( 0,…,0)T
为一个基可行解,有一个
σm+k>0,并且对
i=1,2,…,m有 ai,m+k≤0,那么该线性规划问题具有无界解 （ 或称无最优解 ）
,,,21 mbbb
3.4 基变换
1,换入变量的确定：由 （ 1.27）
式看到,当某些 σj>0时,xj增加则目标函数还可以增大,这时要将某个非基变量 xj换到基变量中去 （ 称为换入变量 ） 。 若有两个以上的
σj>0,那么选哪个非基变量作为换入变量呢？
为了使目标函数值增加最快,从直观上一般选 σj>0种的大者 （ 可以任意选或按最小下标选 ） 即
max(σj>0)=σk
则对应的 xk为换入变量 。 （ 实际上换一次基将使目标函数值改进
σkθ） 。
1,换出变量的确定按最小比值确定换出变量。
3.5 迭代（旋转运算）
将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或 Gauss变换变为单位矩阵 。
例 7 试用上述方法计算例 6的两个基变换。
解 约束条件的增广矩阵为
x1 x2 x3 x4 x5 b
1210040
1601004
800121
当以 x3,x4,x5为基变量,x1，
x2为非基变量,令 x1 =x2=0，
可得到一个基可行解
X(0)=(0,0,8,16,12)
现用 x2去替换 x5,于是将 x3，
x4,x2的系数矩阵变换为单位矩阵经变换后为
x1 x2 x3 x4 x5 b
令非基变量 x1,x5=0,得到新的基可行解
X(1)=(0,3,2,16,0)T
34/10010
1601004
22/10101
§ 4 单纯形法的计算步骤为了便于迭代运算,可将上述方程组写成增广矩阵
-z x1 x2 … xm xm+1 … xn b
01
1000
0100
0010
121
1,
222,2
111,1
nmm
mmnmm
nm
nm
ccccc
baa
baa
baa
若将 z看成不参与基变换的基变量，它与 x1,x2,…,xm的系数构成一个基，这时可采用行初等变换将 c1,c2,…,c m变换为零，使其对应的系数矩阵为单位矩阵，
得到
-z x1 x2 … xm xm+1 … xn
b
m
i
ii
m
i
inin
m
i
miim
mmnmm
nm
nm
bcaccacc
baa
baa
baa
111
1,1
1,
222,2
111,1
0001
1000
0100
0010
可根据上述增广矩阵设计计算表如下：
cj c
1
… cm cm+1 … cn θ
CB xB b x
1
… xm xm+1 … xn
c1
C2
…
cm
x1
x2
…
x
m
b1
b2
…
bm
1
0
…
0
…
…
…
0
0
…
1
a1,m+1
a2,m+1
…
am,m+1
…
…
…
a1n
a2n
…
amn
θ1
θ2
…
θm
-z 0 … 0 …?
m
i
iibc
1
m
i
miim acc
1
1,1
m
i
inin acc
1
4.2 计算步骤
（ 1） 找出初始可行基,确定初始基可行解,建立初始单纯形表 。
（ 2） 检验各非基变量 xj的检验数是则已得到最优解 。 可停止计算 。 否则,转入下一步 。
（ 3 ） 在 中,若有某个对应项
xk的系数列向量 Pk≤0,则此问题是无界,停止计算 。 否则,转入下一步 。
nmjacc j
m
i
ijijj,,1,0
1
若
nmjj,,1,0
（ 4） 根据 max(σj>0)=σk,确定 xk为换入变量,按 θ规则计算可确定 xl为换入变量 。 转入下一步 。
（ 5） 以 alk为主元素进行迭代 （ 即用高斯消去法或称为旋转运算 ）,把 xk所对应的列向量将 xB列中的 xl换为 xk,得到新的单纯形表。重复（ 2） —（ 5），直到终止。
lk
l
ik
ik
i
a
ba
a
b )0|m in (?
0
1
0
0
2
1
mk
lk
k
k
k
a
a
a
a
P
将 xB列中的 xl换为 xk,得到新的单纯形表 。 重复 （ 2） —（ 5）,直到终止 。 现用例 1的标准型来说明上述计算步骤 。
（ 1） 根据例 1的标准型,去松弛变量 x3,x4,x5为基变量,它对应的单位矩阵为基 。 这就得到初始即可行解
X(0)=(0,0,8,16,12)T
将有关数值填入表中，得到初始单纯形表。
表 1-3
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
0 x3
0 x4
0 x5
8
16
12
1
4
0
2
0
4
1
0
0
0
1
0
0
0
1
4
-
3
-z 0 2 3 0 0 0
各非基变量的检验数为
σ1=c1-z1=2-
(0× 2+0× 1+0× 4+0× 0)=2
σ2=c2-z2=3-
(0× 2+0× 2+0× 0+0× 4)=3
(2)因检验数都大于 0,且 P1,P2有正分量存在,转入下一步
（ 3） max(σ1,σ2)=max(2,3)=3;对应的变量 x2 为换入变量 。 计算 θ
θ=
它所在行对应的 x 为换出变量,x 所在
3)4/12,,2/8m i n ()0|(m i n 2
2
i
i
i
i
aab
以 [4]为主元素进行旋转运算,即初等变换,
使 P2变为 （ 0,0,1）
T,在 xB列中将 x2替换 x5,
于是得到新表 1-4
cj
cB xB b 2x1 3x2 0x3 0x4 0x5 θ
0 x3
0 x4
3 x2
2
16
3
1
4
0
0
0
1
1
0
0
0
1
0
-1/2
0
1/4
2
4
-
-z 9 2 0 0 0 -3/4
由于检验数有正数,还没有得到最优解,max(σ1,
σ5)=max(2,-3/4)=2=σ1,则 x1 为换入变量,
θ=
则 x3为换出变量。以 1为主元数进行旋转运算，得
2),4/16,1/2m i n ()0|(m i n 1
1
i
i
i
i
a
a
b
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
2 x1
0 x4
3 x2
2
8
3
1
0
0
0
0
1
1
-4
0
0
1
0
-1/2
2
1/4
-
4
12
-z -13 0 0 -2 0 1/4
由于检验数有正数,还没有得到最优解,max(σ3,σ5)=max(-
2,1/4)=1/4=σ5,则 x5为换入变量,
θ=
则 x4为换出变量。以 2 为主元数进行旋转运算，得
4))4/1/(3,2/8,m i n ()0|(m i n 5
5
i
i
i
i
a
a
b
表 1-6,
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
θ
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
-2
1/2
1/4
1/2
-1/8
0
1
0
-z -13 0 0 -2 0 1/4
得到最优解 X=(4,2,0,0,4),最优值 z=14,
§ 5 单纯形法的进一步讨论
5.1 人工变量法
5.1 人工变量法设线性规划问题的约束条件是分别给每一个约束方程加入人工变量 xn+1,xn+2,…,xn+m,得到
n
j
jj bxP
1
a11x1+a12x2+… +a1nxn+xn+1
=b1
a21x1+a22x2+… +a2nxn +xn+2
=b2
……………………… ……………
am1x1+am2x2+… +amnxn
+ xn+m =bm
x1,x2,…,xn≥0,xn+1,xn+2,…,xn+m≥0
以 xn+1,xn+2,…,xn+m为基变量,则可得到 m× m一个单位矩阵,l令非基变量 x1,x2,…,xn为零,得到一个初始基可行解
X(0)=(0,0,…,0,b1,b2,…,bm)T
若经过基变换后，得到的最终单纯形表中当所有的 cj-zj≤0，基变量中不包含人工变量，就得到原问题的一个基可行解，否则，原问题无可行解。
1、大 M法在一个线性规划问题的约束条件中加入人工变量后,要求人工变量对目标函数的取值无影响,为此可取人工变量在目标函数中的系数为 -
M(M为非常大的正数 ),这样目标函数要实现最大化,人工变量只能取零,因此必须把人工变量从基变量中换出,否则目标函数就不可能实现最大化 。
例 7 用大 M法求解线性规划问题
min z=-3x1+x2+x3
x1-2x2+x3≤11
-4x1+x2+2x3≥3
-2x1 +x3=1
x1,x2,x3≥0
解在上述问题的约束条件中加入松弛变量,剩余变量和人工变量,得到
min z=-3x1+x2+x3+0x4+0x5+Mx6+Mx7
x1-2x2+x3+x4=11
-4x1+x2+2x3-x5+x6=3
-2x1 +x3+x7=1
x1,x2,x3,x4,x5,x6,x7≥0
用单纯形表进行计算,得到最优解是
x1=4,x2=1,x3=9,x4=x5=x6=x7=0,最优值 z=-2
cj
cB xB
b -3
X1
1
x2
1
x3
0
x4
0
x5
M
x6
M
x7
Θ
0 x4
M x6
Mx7
11
3
1
1
-4
-2
-2
1
0
1
2
1
1
0
0
0
-1
0
0
1
0
0
0
1
11
3/2
1
cj-zj -3+6M 1-M 1-3M 0 M 0 0
0 x4
M x6
1x3
10
1
1
3
0
-2
-2
1
0
0
0
1
1
0
0
0
-1
0
0
1
0
-1
-2
1
1
cj-zj -1 1-M 0 0 M 0 3M-1
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
2
1
0
-5
-2
1
4
cj-zj -1 0 0 0 1 M-1 M+1
-3 x1
1 x2
1x3
4
1
9
1
0
0
0
1
0
0
0
1
1/3
0
2/3
-2/3
-1
-4/3
2/3
1
4/3
-5/3
-2
-7/3
2 0 0 0 1/3 1/3 M-1/3 M-2/3
2,两阶段法由于大 M法在使用电子计算机求解时，只能用很大的数代替 M，这就可能造成计算上的出错。
故下面介绍两阶段法。
第一阶段不考虑原问题是否存在基可行解,给原线性规划问题加上人工变量,构造仅含人工变量的目标函数和要求实现最小化 。 即求解如下问题：
minω=0x1+… +0xn + xn+1+… +xn+m
a11x1+a12x2+… +a1nxn+ xn+1 =b1
a21x1+a22x2+… +a2nxn + xn+2 =b2
……………………………………
am1x1+am2x2+… +amnxn + xn+m =bm
x1,x2,…,xn≥0,xn+1,xn+2,…,xn+m≥0
若得到 ω=0，这说明原问题存在基可行解，可以进行第二阶段的计算否则，原问题无可行解。
第二阶段：将第一阶段得到的最优单纯形表，除去人工变量，将原目标函数的系数换掉该表的目标函数的系数行，作为第二阶段计算的初始表。
例 9 用两阶段法求解下面的线性规划问题：
min z=-3x1+x2+x3
x1-2x2+x3≤11
-4x1+x2+2x3≥3
-2x1 +x3=1
x1,x2,x3≥0
解将上面的问题的约束方程加上人工变量得到第一阶段的问题：
min z=x6+x7
x1-2x2+x3+x4=11
-4x1+x2+2x3-x5+x6=3
-2x1 +x3+x7=1
x1,x2,x3,x4,x5,x6,x7≥0
第一阶段
cj
cB xB
b 0
X1
0
x2
0
x3
0
x4
0
x5
1
x6
1
x7
Θ
0 x4
1 x6
1x7
11
3
1
1
-4
-2
-2
1
0
1
2
1
1
0
0
0
-1
0
0
1
0
0
0
1
11
3/
2
1
cj-zj 6 -1 -3 0 1 0 0
0 x4
1 x6
1x3
10
1
1
3
0
-2
-2
1
0
0
0
1
1
0
0
0
-1
0
0
1
0
-1
-2
1
1
cj-zj 0 -1 0 0 1 0 3
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
2
1
0
-5
-2
1
4
-
-
cj-zj 0 0 0 0 0 1 1
第二阶段
cj
cB xB
b -3
x1
1
x2
1
x3
0
x4
0
x5
Θ
0 x4
1 x2
1x3
12
1
1
3
0
-2
0
1
0
0
0
1
1
0
0
-2
-1
0
4
-
-
cj-zj -1 0 0 0 1
-3 x1
1 x2
1x3
4
1
9
1
0
0
0
1
0
0
0
1
1/3
0
2/3
-2/3
-1
-4/3
cj-zj 2 0 0 0 1/3 1/3
最优解为,x1=4,x2=1,x3=9,
最优值 z=-2
第二章 对偶理论与灵敏度分析
§ 1 单纯形法的矩阵描述设线性规划问题
Max z=CX
AX≤b
X≥0
给这个线性规划问题的约束条件加入松弛变量
Xs=( xn+1,xn+2,…,xn+m)T得到标准型：
Max z=CX+0X (2.1)
AX+IXs=b (2.2)
X,Xs≥0 (2.3)
设 B是一个可行基,即基矩阵 。 若将系数矩阵
(A,I)分为 （ B,N） 两块,这里 N是非基变量的系数矩阵 。 对应于 B的基变量,用向量
XB=(xB1,xB2,…,xBm)T表示,则同时 C=(CB,CN)于是
（ B,N） =b
(CB,CN) =CBXB+CNXN
S
B
X
XX
S
B
X
X
S
B
X
X
将 （ 2.1）,（ 2.2）,（ 2.3） 改写为
Max z=CBXB+CNXN (2.4)
BXB+NXN=b (2.5)
XB,XN≥0
将 （ 2.5） 移项后得到
BXB =b-NXN （ 2.6）
对 （ 2.6） 左乘 B-1后得
XB = B-1b- B-1NXN （ 2.7）
将 （ 2.7） 代入 （ 2.4） 得
z=CB B-1b+(CN- CBB-1N)XN (2.8)
令非基变量 XN=0,得到一个基可行解目标函数值
z= CB B-1b
0
1
)1( bBX
从 92.7),(2.8)可以看出
（ 1） 目标函数中非基变量得系数 CN- CBB-1N就是第一章的检验数 。 因为 XB在 （ 2.8） 中的系数是 0,即
CB-CBB-1B=0
又因 CN中对应于 Xs的系数为 0，在（ 2.8）式中
Xs的系数实质上是 0-CBB-1,因此所有检验数都可用 C-CBB-1A与 -CBB-1表示。
（ 2） 用矩阵描述时 θ规则的表达式是 2
lj
l
ij
ij
i
i PB
bB
PB
PB
bB
)(
)(
0)(|
)(
)(
m i n
1
1
1
1
1
(3)单纯形表为了便于在表中找出 B-1所在的位置,将 （ 2.4）,
（ 2.5） 改写为
-z+CBXB+CN1XN1+0Xs=0
BXB+NXN+IXs=b
当确定 XB为基变量时,经过基变换后可得到 XB与
z得表达式 （ 2.7）,（ 2.8） 并将他们改写为
XB+B-1N1XN+B-1Xs=B-1b
-z+（ CN-CBB-1N1） XN1- CBB-1Xs=- CBB-1b
上述两式用矩阵表示为
b
bB
X
X
X
z
I
s
N
B
1-
B
1
1-
B1
1-
BN
1-
1
1-
BC-BC-NBC-C01
BNB0
设 B是一个可行基,即基矩阵 。 若将系数矩阵
(A,I)分为 （ B,N） 两块,这里 N是非基变量的系数矩阵 。 对应于 B的基变量,用向量
XB=(xB1,xB2,…,xBm)T表示，则同时 C=(CB,CN)于是
（ B,N） =b
(CB,CN) =CBXB+CNXN
S
B
X
X
X
S
B
X
X
S
B
X
X
用表格表示为表 2-1
基变量 非基变量 RHS
XN1 Xs
I
0
B-1N1
CN-CBB-1N1
B-1
- CBB-1
B-1b
- CBB-1b
§ 3对偶问题的提出第一章的例 1讨论了利用有限的资源如何安排生产才能获得最大的利润的问题。现在从另一角度来讨论这个问题。假设该工厂的决策者决定这些资源不用来生产而是考虑将其出租或出售。这时决策者就要考虑给每种资源如何定价的问题。
设用 y1,y3,y3分别表示出租单位设备台时的租金和出让单位原材料 A,B得附加值 。 于是
y1+4y2≥2
2y1+4y3≥3
则所有资源出租和出让,其所得收入为
ω=8y1+16y2+12y3
则得到下面的线性规划问题
minω=8y1+16y2+12y3
y1+4y2≥2
2y1+4y3≥3
y1,y2,y3≥0
称这个线性规划问题为原问题的对偶问题。
下面在从另一角度来讨论。
从 § 1得到检验数的另一表达式是
CN-CBB-1N与 - CBB-1
由第一章知,当检验数
CN-CBB-1N≤0
CBB-1≤0
则线性规划问题已得到最优解。可见（ 2.9），
（ 2.10）是作为得到最优解的条件。
1,（ 2.9）,（ 2.10） 中都有乘子 CBB-1,称为单纯形乘子并用符号 Y=CBB-1表示 。 由于 （ 2.10）
的条件,可得 Y≥0
2.对应基变量 XB的检验数是 0。 它是 CB-CBB-1B=0.
包括基变量在内的所有检验数可用 C-CBB-1A≤0表示 。 即 C-CBB-1A=C-YA≤0,移项得到 YA≥C
3.由条件 （ 2.10） 得到 -Y=- CBB-1
即 Yb= CBB-1b=z因 Y的上界为无限大，所以只存在最小值。
4,在这里可以得到另一个线性规划问题
Min ω=Yb
YA≥C
Y≥0
称它为原线性规划问题 {Max z=CX|AX≤b,X≥0}
的对偶规划问题。
从这两个规划问题的表达式可看出：根据原线性规划问题的系数矩阵 A,C,b就可以写出它的对偶问题。如第一章的例 1，原问题的系数矩阵是；
40
04
21
A );3,2(?C
12
16
8
b
那麽它的对偶问题是
Min ω=Y（ 8,16,12） T
Y ≥（ 2,3）
Y≥0
这里 Y=( y1,y2,y3)
即
minω=8y1+16y2+12y3
y1+4y2≥2
2y1+4y3≥3
y1,y2,y3≥0
40
04
21
§ 4 线性规划的对偶理论
4.1 原问题和对偶问题的关系表 2-2
x
y
x1 x2 c xn 原关系 minω
y1
Y2
…
ym
a11 a12 …
a1n
a21 a22 … a2n
……………
am1 am2…
amn
≤
≤
…
≤
b1
B2
…
bm
对偶关系 ≥≥ … ≥ Max z=
minω
Max z c1 c2 … cn
例 1 试求下述线性规划问题的对偶问题
min z=2x1+3x2-5x3+x4
x1+x2-3x3+x4≥5
2x1 +2x3-x4≤4
x2+x3+x4=6
x1≤0,x2,x3≥0;x4无约束解设对应于三个约束条件的对偶变量分别为 y1,y2,y3;
由于目标函数是求极小值,由上表知其对偶问题为
max z’=5y1+4y2+6y3
y1+2y2≥2
y1+y3≤3
-3y1+2y2+y3≤-5
y1-y2+y3=1
y1≥0,y2≤0,y3无约束
4.2 对偶问题的基本性质
1,对称性 对偶问题的对偶是原问题 。
2,弱对偶性 若 X*是原问题的可行解,Y*是对偶问题的可行解 。 则存在
CX*≤Y*b
3,无界性 若原问题 （ 对偶问题 ） 为无界解,则其对偶问题 （ 原问题 ） 无可行解 。
4、可行解是最优解时的性质 设 X^是原问题的可行解,Y^是对偶问题的可行解，当 CX^=Y^b时，
X^,Y^是最优解。
5,对偶定理 若原问题有最优解,
那么对偶问题也有最优解且最优值相同 。
6、互补松驰性 若 X^,Y^分别是对偶问题和原问题的可行解。那么
Y^Xs=0和 YsX^=0,当且仅当 X^,Y^
为最优解。
7,设原问题是
max z=CX;AX+Xs=b,X,Xs≥0
它的对偶问题是
min ω=Yb;YA-Ys=C;Y,Ys≥0
则原问题单纯形表的检验数行对应其对偶问题的一个基解,其对应关系如下表：
其中 Ys1对应于原问题中基变量 XB的剩余变量,Ys2对应于原问题中非基变量 XN的剩余变量。
XB XN XS
0
-Ys2
Ys1
-CBB-1
CN-CBB-1N
-Y
例 4
已知线性规划问题
max z=x1+x2
-x1+x2+x3≤2
-2x1+x2-x3≤1
x1,x2,x3≥0
试用对偶理论证明该线性规划问题无优解。
证首先看到该问题存在可行解 X=(0,0,0);而对偶问题为
min ω=2y1+y2
-y1-2y2≥1
y1+y2≥1
y1-y2≥0
y1,y2≥0
由于该问题无可行解，故原问题无最优解。
例 5
已知线性规划问题
min ω=2x1+3x2+5x3+2x4+3x5
x1+x2+2x3+x4+3x5≥4
2x1-x2+3x3+x4+x5≥3
x1,x2,x3,x4,x5≥0
已知其对偶问题的最优解为 y1*=4/5，
y2*=3/5;z=5.用对偶理论求出原问题的最优解。
解先写出它的对偶问题
max z=4y1+3y2
y1+2y2≤2 （ 1）
y1-y2≤3 （ 2）
2y1+3y2≤5 （ 3）
y1+y2≤2 （ 4）
3y1+y2≤3 （ 5）
y1,y2≥0 （ 6）
将 y1*,y2*的值代入约束条件，得
（ 2），（ 3），（ 4）为严格不等式；
由互补松弛性得 x2*=x3*=x4*=0,因
y1,y2≥0;原问题的两个约束条件应取等式，即
3x1*+x5*=4
2x1*+x5*=3
求解得 x1*=1,x2*=1,故原问题的最优解为
X*=(1,0,0,0,1); ω*=5.
§ 6 对偶单纯形法前面讲到原问题与对偶问题的解之间的关系时指出：在单纯形表中进行迭代时，在 b列中得到的时原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代。当在检验数行得到对偶问题的解也是基可行解时，则已得到最优解，即原问题和对偶问题都是最优解。
根据对偶问题的对称性，若保持对偶问题的解是基可行解，
即 cj-CBB-1Pj≤0而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解，其优点是原问题的初始解不一定要是基可行解，可从非基可行解开始迭代，
方法如下：
设原问题为
max z=CX
AX=b
X≥0
又设 B是一个基。不失一般性，令 B=
（ P1,P2,…,Pm）,它对应的变量为
XB=(x1,x2,…,xm)
当非基变量都为 0时，可以得到 XB=B-1b.若 B-1b
中至少有一个负分量，设（ B-1b） I<0,并且在单纯形表的检验数行中得检验数都为非正，即对偶问题保持可行解，
它的个分量是
1,对应基变量 x1,x2,…,xm的检验数是
σi=ci-zi=ci- CBB-1Pi=0,i=1,2,…,m
2,对应非基变量 xm+1,…,xn的检验数是
σj=cj-zj=cj- CBB-1Pj≤0,j=m+1,…,n
每次迭代是将基变量中的负分量 xl取出，取替换非基变量中的 xk,经基变换，所有检验数仍保持非正，从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。
对偶单纯形法的计算步骤：
根据线性规划问题，列出初始单纯形表。检查 b
列的数字，若都为非负，检验数都为非正，则得到了最优解。停止计算。若检查 b列的数字时，
至少还有一个负分量，检验数保持非正，那么进行一下计算。
（ 2） 确定换出变量按对应的基变量 xl为换出变量。
（ 3） 确定换出变量在单纯形表中检查 xl所在行的各系数
alj≥0,则无可行解。停止计算。
若存在 alj<0(j=1,2,…,n),计算按 θ规则所对应的列的非基变量 xk为换入变量，这样才能保持得到的对偶问题解仍然为可行解。
liii bBbBbB 111 0|m in
lk
kk
lj
lj
jj
j a
zca
a
zc?
0|m i n?
4、以 alk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复（ 1） -（ 4）的步骤。
下面来举例说明具体的算法。
例 6 用对偶单纯形法求解
min ω=2x1+3x2+4x3
x1+2x2+x3≥3
2x1-x2+3x3≥4
x1,x2,x3≥0
解现将问题化为下面的形式，以便得到对偶问题的初始可行基
max z=-2x1-3x2-4x3
-x1-2x2-x3+x4=-3
-2x1+x2-3x3+x5=-4
x1,x2,x3,x4,x5≥0
建立该问题的初始单纯形表 2-6如下
cj
cB xB b
-2
x1
-3
x2
-4
x3
0
x4
0
x5
0 x4
0 x5
-
3
-
4
-1
[-2]
-2
1
-1
-3
1
0
0
1
cj-zj -2 -3 -4 0 0
表 2-7
cj
cB xB
b -2
x1
-3
x2
-4
x3
0
x4
0
x5
0 x4
-2 x1
-1
2
0
1
[-5/2]
-1/2
1/2
3/2
1
0
-1/2
-1/2
cj-zj 0 -4 -1 0 -1
表 2-8
cj
cB xB
b -2
x1
-3
x2
-4
x3
0
x4
0
x5
-3 x2
-2 x1
2/5
11/5
0
1
1
0
-1/5
7/5
-2/5
-1/5
1/5
-2/5
cj-zj 0 0 -3/5 -8/5 -1/5
最优解为 y*=(y1*,y2*)=(8/5,1/5)
从以上求解过程可以看到，对偶单纯形法有以下优点：
（ 1） 初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。
（ 2） 当变量多余约束条件，对这样的线性规划问题，用对偶单纯形法可以减少计算的工作量。
因此对变量较少而约束条件很多的线性规划问题，
可以先将它变为对偶问题，然后用对偶单纯形法求解。
在灵敏度分析中,有时需要用对偶单纯形法，可是问题的处理简化。对偶单纯形法的局限性主要是对大多数线性规划问题，痕难找到一个初始可行基，因而这方法很少单独使用。
§ 7 灵敏度分析当线性规划问题的系数发生变化时，最优解一般要发生变化，主要有以下几种情况：
原问题 对偶问题 结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解表中的解仍然为最优解用单纯形法继续迭代求最优解用对偶单纯形法迭代求最优解引进人工变量，编制新的单纯形表，
求最优解下面就各种情况分别进行讨论。
7.1 资源数量变化的分析资源数量变化是指系数 br发生变化，即
br’=br+Δbr.并假设问题的其它系数都不变。这样使原问题的解变为
XB’=B-1(b+Δb)
这里 Δb=（ 0,…,Δbr,0,…,0） T.只要 XB’
≥0，最终表的检验数不变，则最优基不变，但最优解的值发生了变化，所以 XB’为新的最优解。
新的最优解的值可允许变化的范围用以下方法确定。
B-1(b+Δb)= B-1b+ B-1Δb
= B-1b+ B-1,B-1=
0
0
r
b
mr
ir
r
r
rmr
rir
rr
r
a
a
a
b
ba
ba
ba
b
11
0
0
这时在最终表中求得的 b列的所有元素
，
由此得当
mibab riri,,2,1,0
mibba irir,,2,1,
于是得到时,;/0 iririr abba;/0 iririr abba 时，
}0|/{m i n}0|/{m a x iririiririri
i
aabbaab
例如求第一章例 1中第二个约束条件 b2
的变化范围 Δb2时，可计算
B-1b+ B-1
可得的变化范围是 [-8,16];显然 b2的变换范围是 [8,32]。
0
0
0
1 2 5.0
5.0
25.0
2
4
4
0
0
rr bb
,85.0/4,1625.0/4 22 bb
22,16125.0/2 bb 所以例 1
从表 1-5得知第一章例 1中，每设备台时的影子价格为 1.5元，若该厂又从别处抽出 4台时用于生产，求这时该厂生产产品的最优方案。
解 先计算 B-1Δb
B-1Δb=
将上述结果反映到最终表中得
2
8
0
0
0
4
0125.05.0
15.02
025.00
表 2-10。
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3 x2
4+0
4-8
2+2
1
0
0
0
0
1
0
-2
0.5
0.25
0.5
-
0.125
0
1
0
cj-zj 0 0 -1.5 -
0.125
0
由于 b列中有负数，故用对偶单纯形法求新的最优解。计算结果如下表表 2-11
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
2 x1
0 x3
3 x2
4
2
3
1
0
0
0
0
1
0
1
0
0.25
-0.25
0
0
-0.5
0.25
cj-zj 0 0 0 -0.5 -0.75
即该厂最优生产方案应改为 Ⅰ 4件,Ⅱ 3件，获利
z*=17元从表中看出 x3=2,即设备有两小时未被利用。
7.2 目标函数中价值系数 cj的变化分析可以分别就 cj时对应的非基变量和基变量两种情况来讨论。
（ 1） 若 cj是非基变量 xj的系数，这时他在计算表中所对应的检验数是
σj =cj- CBB-1Pj
或 σj=
当 cj变化 Δcj时，要保证最终表中这个检验数仍然小雨或等于零，即
σj’=cj+Δcj- CBB-1Pj≤0
那么 cj+Δcj≤YPj,即 Δcj的值必需小于或等于 YPj-cj,才可以满足原最优解条件，这可以确定 Δcj的变化范围了。
m
i
iijj yac
1
(2)若 cr是基变量 xr的系数。因 cr∈ CB,
当 cr变化 Δcr时，就引起 CB的变化，这时
(CB+ΔCB)B-1A=CB B-1A+(0,…,
Δcr,…,0) B-1A
= CB B-1A+Δcr(ar1,ar2,…,arn)
可见当 cr变化 Δcr时，最终表中的检验数是
σj’=cj - CBB-1A-Δcjarj’,j=1,2,…,n
若要求原最优解不变，即必需满足
σj’≤0。于是得到当 arj’<0,Δcr≤σj/a rj’
arj’>0,Δcr≥σj/a rj’ j=1,2,…,n
Δcr可变化的范围是
}0|/{m i n}0|/{m a x rjrjjjrrjrjjj aacaa
例 1 试以第一章例 1的最终表 1-5为例，设基变量 x2的系数 c2
变化 Δc2，在原最优解不变的条件下，确定 Δc2的变化范围。
解 这时表 1-5最终计算表变成为表 2-12：
cj
cB xB
b 2
x1
3+Δc2
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
4
0.5
0.25
0.5
-
0.125
0
1
0
cj-zj 0 Δc2 -1.5 -
0.125
0
为了保持原最优解不变，则 x2的检验数应当为零，于是得表 2-13a
cj
cB xB
b 2
x1
3+Δc2
x2
0
x3
0
x4
0
x5
2 x1
0 x5
3+Δc2 x2
4
4
2
1
0
0
0
0
1
0
-4
0.5
0.25
0.5
-0.125
0
1
0
cj-zj 0 0 -1.5
-Δc2/2
Δc2/8
-0.125
0
从上表可见有：
-1.5-Δc2/2≤0和 Δc2/8-0.125≤0，由此可得
Δc2≥-1.5/0.5； Δc2≤1。 Δc2的变化范围为,-
3≤Δc2≤1。即 c2可以在 [0,4]内变化而不影响原最优解。
7.3 技术系数 aij的变化分两种情况来讨论技术系数 aij的变化，下面一具体的例 ]子来说明：
例 9
分析在原计划中是否应该安排一种新产品 。
以第一章例 1的最终表 1-5为例,设该厂除了生产产品 Ⅰ,Ⅱ 外,还生产新产品 Ⅲ,已知生产产品 Ⅲ,每件需消耗原材料 A,B各为 6㎏,3㎏,
是用设备 2台时 。 每件可获利 5元,问该厂是否应生产新产品和生产多少？
解 分析这问题的步骤是：
（ 1） 设生产产品 Ⅲ x3’台，其技术向量
P3’=(2,6,3)T,然后计算最终表中对应于 x3’的检验数
σ3‘=c3’-CBB-1P3’=5-(1.5,0.125,0)(2,6,3)T=1.25>0
说明安排生产产品 Ⅲ 是有利可图的 。
（ 2） 计算 Ⅲ 在最终表中对应 x3’的列向量
B-1P3’=
25.0
2
5.1
3
6
2
0125.05.0
15.02
025.00
并将（ 1），（ 2）中的计算结果填入最终计算表 1-5得表 2-
13b：
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
5
x3’
2 x1
0 x5
3 x2
4
4
2
1
0
0
0
0
1
0
-2
0.5
0.25
0.5
-
0.125
0
1
0
1.5
[2]
0.25
cj-zj 0 0 -1.5 -
0.125
0 1.25
可行解，但检验数还有正数，说明目标寒暑值还可以改善。
（ 3）进行迭代得最优单纯形表 2-13c:
cj
cB xB
b 2
x1
3
x2
0
x3
0
x4
0
x5
5
x3’
2 x1
0 x3’
3 x2
1
2
1.5
1
0
0
0
0
1
1,5
–1
0.75
-0.125
0.25
-0.1875
-0.75
0,5
-0.125
0
1
0
cj-zj 0 0 -0.25 -0.4375 -0.625 0
例 10
分析原计划生产产品的工艺结构发生变化 。
以第一章例 1为例 。 若 P1’=(2,5,2)T,每件利润为 4元,试分析原最优计划有什么影响？
B-1P1’=
x1’的检验数为
σ1‘=c1’-CBB-1P1’=4-
(1.5,0.125,0)(2,5,2)T=0.375
375.0
5.0
25.1
2
5
2
0125.05.0
15.02
025.00
将以上结果填入最终表 x1的列向量位置，得表 2-14
cj
cB xB b
2
x1
4
x1’
3
x2
0
x3
0
x4
0
x5
4 x1
0 x5
3 x2
4
4
2
1
0
0
1.25
50.5
0.375
0
0
1
0
-2
0.5
0.25
0.5
0.125
0
1
0
cj-zj 0 0.375 0 -1.5 -
0.125
0
经迭代得最优表 2-15：
cj
cB xB b
4
x1‘
3
x2
0
x3
0
x4
0
x5
4 x1‘
0 x5
3 x2
3.2
2.4
0.8
1
0
0
0
0
1
0
-2
0.5
0.2
0.4
-0.2
0
1
0
cj-zj 0 0 -1.5 -0.2 0
上表表明原问题和对偶问题得解都是可行解所以表中的结果已是最优解 。 即应当生产
Ⅰ ‘3.2单位；生产产品 Ⅱ 0.8单位 。 可获利
15.2元 。
注意,若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解。
例 11
设例 10中 Ⅰ ‘的技术系数向量为 P1’=(4,5,2)T，
而每件获利仍然为 4元 。 试问应如何安排最优生产方案？
解 方法与例 10相同,以 x1’代替 x1,计算
B-1P1’=
x1’的检验数为
σ1‘=c1’-CBB-1P1’=4-(1.5,0.125,0)(4,5,2)T=-2.625
3 7 5.1
5.3
25.1
2
5
4
01 2 5.05.0
15.02
025.00
将以上结果填入最终表 x1的列向量位置，
得表 2-16
cB xB b x1’ x2 x3 x4 x5
4 x1
0 x5
3 x2
4
4
2
1.25
-3.5
1.357
0
0
1
0
-2
0.5
0.25
0.5
0.125
0
1
0
cj-zj -
2.625
0 -1.5 -
0.125
0
将表 2-16的 x1’替换基变量中的 x1，得表 2-17
cB xB b x1’ x2 x3 x4 x5
4 x1‘
0 x5
3 x2
3.2
15.3
-2.4
1
0
0
0
0
1
0
-2
0.5
0.2
1.2
-0.4
0
1
0
cj-zj 0 0 -1.5 0.4 0
由于原问题与对偶问题都是非可行解 。
于是引入人工变量 x6因在表 2-17中 x2
所在行,用方程表示时为
0x1’+x2+0.5x3-0.4x4+0x5=-2.4
引入人工变量 x6后,便为
-x2-0.5x3+0.4x4+x6=2.4
将 x6作为基变量代替 x2,填入表
2-17的表 2-18
cB xB b x1’ x2 x3 x4 x5 x6
4 x`1
0 x5
-M x6
3.2
15.2
2.4
1
0
0
0
0
-1
0
-2
-0.5
0.2
1.2
[0.4]
0
1
0
0
0
1
cj-zj 0 3-M -0.5M -0.8
+0.4M
0 0
用单纯形法求解得表 2-19
cj
cB xB b
4
x1‘
3
x2
0
x3
0
x4
0
x5
-M
x6
4 x1‘
0 x5
0 x4
2
8
6
1
0
0
0.5
3
-2.5
1.25
–0.5
–1.25
0
0
1
0
1
0
0.5
-3
2.5
cj-zj 0 1 -1 0 0 -M+2
4 x1‘
3 x2
0 x4
0.667
2.667
12.667
1
0
0
0
1
0
0.33
-
0.167
1.667
0
0
1
-0.33
0.33
0.83
0
-1
0
cj-zj 0 0 -0.83 0 -0.33 -M+2
除以上介绍的几项分析外，还可以作增减约束条件的分析。
