对偶单纯形法是求解对偶规划的一种方法 ×
对偶单纯形法,利用对偶理论得到的一个求解线性规划问题的方法单纯形法（原始单纯形法）的 两个条件,
1、问题为标准型
2、有初始基本可行解
0,
32
634
33
.
2m in
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
标准型为
0,,,,
32
634
33
.
2m a x
54321
521
7421
6321
7621
76
xxxxx
xxx
xxxx
xxxx
ts
MxMxxxZ
xx,引进人工变量用单纯形法求解对偶单纯形法的优点：
1、不需要人工变量；
2、当变量多于约束时，用对偶单纯形法可减少迭代次数；
3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。
bAX?于是 b
X
XNB
N
B
bNXBX NB
B 可逆
NB NXBbBX 11
N
B
NB X
XCCZ且 NNBB XCXC
NNNB XCNXBbBC )( 11
NBNB XNBCCbBC )( 11
0,0
.
m a x
bX
bAXts
CXz对标准型
nmm PPPPPA 121是可行基设 mPPPB?21?
NBA,?
N
B
X
XX
原始单纯形法的基本思路：
NB CCC?
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
关于可行基 B的典则形式检验数
0?NX令 01 bBX B得 0,11 bBX得基本可行解
01 1 NBC N、若所有的检验数 为最优解则 1,X
解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数
,0
,03 1
NBCC BN
域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数
,0
,02 1
NBCC BN
持对应的基本解可行在迭代过程中，始终保做换基迭代,
01 bBX B即
0
0
1
1
NBCC
NBCC
BN
BN
个数越来越少，最终的分量中并使检验数
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
bBCZXNBCCX BNBNB 11 )(0
bBNXBX NB 11
0?NX令 01 bBX B得
，若 01 NBC N 为最优解1XX
B XN 常数项检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
初始单纯形表：
0?
原始单纯形法的迭代过程：
0,11 bBX得基本可行解
0
变量否则，选定入基、出基对该单纯形表做行变换
，直至 01 NBC N
得最优单纯形表件：最优单纯形表的充要条,01 NBC N
0
.
m a x
X
bAXts
CXz对
mPPPB?21?取基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
对偶单纯形法的基本思路：
0?NX令 bBX B 1得
0,11 bBX得基本解
:01 NBCC BN若
XB XN 常数项检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
作对偶单纯形表,
0?
0
为最优解1,X
否则，换基迭代对该单纯形表做行变换
，直至 01 bB
得最优对偶单纯形表
01 bB若
）始终保持 0( 1 NBC N
选定入基、出基变量要条件：最优对偶单纯形表的充 01 bB
0,
32
634
33
.
2m i n
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ例：求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
解：标准型为
0,,,,
32
634
33
.
54321
521
421
321
xxxxx
xxx
xxx
xxx
ts
212m a x xxZ即
543,,PPPB?取基
36300,，，，基本解X
基 B的典则形式
X1 X2 X3 X4 X5
检 -2 -1 0 0 0 Z
X3 -3 -1 1 0 0 -3
X4 -4 -3 0 1 0 -6
X5 1 2 0 0 1 3
不可行检验行
≤ 0
分析：
若 X3或 X4所在的行的 aij均非负，
则问题一定无可行解否则，做换基迭代
X1 X2 X3 X4 X5
检 -2 -1 0 0 0 Z
X3 -3 -1 1 0 0 -3
X4 -4 -3 0 1 0 -6
X5 1 2 0 0 1 3
1、确定出基变量：
设 br =min{bi | bi <0}
则取 br所在行的基变量为出基变量即取 X4为出基变量
2、确定入基变量：
原则：
保持检验行系数 ≤0
0
00|m i n
ri
i
ri
ri
i
aaa
设为入基变量则取 0ix
31
X1 X2 X3 X4 X5
检
X3
X2
X5
21
X1 X2 X3 X4 X5
检
X3
X2
X1
），，，，（最优解 0005653?X
512Z最优值
-2/3 0 0 -1/3 0 Z+2
-5/3 0 1 -1/3 0 -1
4/3 1 0 -1/3 0 2
-5/3 0 0 2/3 1 -1
0 0 0 -3/5 -2/5 Z+12/5
0 0 1 -1 -1 0
0 1 0 1/5 4/5 6/5
1 0 0 -2/5 -3/5 3/5
），（
所求问题的最优解
5
6
5
3?X
5
12?Z最优值
0,
32
634
33
.
2m i n
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ例：求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
解：标准型为
），，，，（最优解 0005653?X
512Z最优值对偶单纯形法步骤,
1、找出一个初始对偶可行解。
把原问题写成该基的典则形式时,目标函数的系数均 ≤0
2、判断,（ 1）若 B-1b≥0，则得到最优解 0,1
0 bBX
结束
（ 2）若 B-1b≥0,
mbbbbB,,,211?记
0|m i n iir bbb设
njab rjj?,2,10,0 且若存在某个则问题无可行解。
3、换基迭代：
（ 1）确定出基变量：
（ 2）确定入基变量
0
00|m i n
ri
i
ri
ri
i
aaa
设即找出一个基 B，
为入基变量则取 0,ix
24 0 转，得一新的单纯形表，为主元素进行换基迭代、以 ria
否则转下一步所在行的基变量出基则取 rb?
0,,
964
52
5
.
2m a x
321
32
32
321
21
xxx
xx
xx
xxx
ts
xxZ
求解下列问题例：用对偶单纯形法
0,,
964
52
5
.
2m a x
54321
532
432
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
，，
解：问题化为标准型
964 532 xxx
），，（初始基 541 PPPB?
不是典则形式
X1 X2 X3 X4 X5
检 2 1 0 0 0 Z
X1 1 1 1 0 0 5
X4 0 2 1 1 0 5
X5 0 -4 -6 0 1 -9
0 -1 -2 -10
3141
X1 X2 X3 X4 X5
检
X1
X4
X2 0 1 3/2 0 -1/4 9/4
0 0 -2 1 1/2 1/2
1 0 -1/2 0 1/4 11/4
0 0 -1/2 0 -1/4 Z-31/4
），，，，（最优解 021049411?X
4
31?Z最优值
），（最优解 49411?X
4
31?Z最优值注意,对偶单纯形法仅限于初始基 B对应的典则形式中目标函数的系数（检验数）均 ≤0的情形。
nn xcxcxcz2211m i n
:形如
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
nn xcxcxcz2211m a x
:标准型
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
2211
222222121
111212111
.
),,2,1(0 njc j若可用对偶单纯形法
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
2211
222222121
111212111
.
）（基 mnnn PPPB,,,21?
），，，，（
基本解
mbbbX,,,000 21
B的典则形式
ABCC B 1由于NBBCCC BNB,1 ），（
NBCBBCCC BBNB 11, ），（
NBCCCC BBNB 1, ），（
），（ NBCCO BN 1
AB 1?且 ),(1 NBB ),( 11 NBBB ),( 1 NBE
X 解检验行 Z- CBB-1b
XB B-1b
ABCC B 1
AB 1?
0,0
.
m a x
bX
bAXts
CXz对标准型设 B为可行基
XB XN 解检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
NBA,,?
N
B
X
XX
NB CCC?
01 NBCC BN最优
0?
01 ABCC B最优原始单纯形法的基本思路：
X 解检验行 Z- CBB-1b
XB B-1b
ABCC B 1
AB 1?
0,0
.
m a x
bX
bAXts
CXz
对标准型设 B为可行基
01 ABCC B
10 BCY B
最优
00 AYC
CAY?0
YbSD?m i n）：（
其偶规划为无符号限制Y
CYAts?.
）的可行解是（ DY 0原始单纯形法的迭代过程,
）（ P
010,）得到最优解为（ bBXP
01 bB当 时且 01 ABCC B
）的最优解为（且由对偶理论知,DBCY B 10
的前提下，）的解是基本可行解在保证（ 01 bBP
）的可行解的方向迭代是（即向 DBCY B 10
的方向迭代向 01 ABCC B
）同时得到可行解）和（即（ DP
010,）得到最优解为（ bBXP
时且 01 bB，当 01 ABCC B
）的最优解为（且由对偶理论知,DBCY B 10
的方向迭代，向 01 bB
）的可行解的前提下，是（即 DBCY B 10
01 ABCC B在保证
）同时得到可行解时）和（即（ DP
对偶单纯形法的基本思路,
）的可行解方向迭代即向（ P
对偶单纯形法单纯形法解线性规划问题的方法如何用？
求解线性规划问题的 方法与步骤,
1,把原问题化为标准型
0
.
m a x
X
bAXts
CXz
2、找初始基
找不到基找到一个基 B
，转第 3步
，转第 4步
3、把问题写成关于基 B的典则形式
01 bB即若对应的基本解可行，
若对应的基解不可行，
，用单纯形法
0
0
存在检验数检验数均
，对偶单纯形法
，转第 4步
4、增加人工变量，用大 M法或两阶段法求解
01 bB即
0
52
2
.
834m in
321
32
31
321
xxx
xx
xx
ts
xxxZ
，，
例求
0,,
52
2
.
834m a x
54321
532
431
321
xxxxx
xxx
xxx
ts
xxxZ
，，
标准型为
541 PPB,若取初始基?
的典则形式为则关于 1B
0,,
52
2
.
834m a x
54321
532
431
321
xxxxx
xxx
xxx
ts
xxxZ
，，
对应 B1的基本解：
520001,，，，X
可用对偶单纯形法求解检验数全部 ≤0
不 可行
212 PPB,若取初始基?
的典则形式为则关于 2B
0,,
52
2
.
3418m a x
54321
532
431
543
xxxxx
xxx
xxx
ts
xxxZ
，，
对应 B2的基本解
000522,，，，X
用单纯形法求解可行
0,,,
0289
5
15223
12
.
m in
654321
64321
31
4321
5432
6
xxxxxx
xxxxx
xx
xxxx
xxxx
ts
xZ
，，
例：求
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
5432
6
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xZ
，，
化标准型
8765,PPPPB,，取初始基?
0,,,
0289
5
15223
12
.
289m a x
654321
64321
831
74321
5432
4321
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xxxxZ
B
，，
的典则形式关于对应 B的基本解：
5,150,1,0000,，，，X
存在检验数 >0
不可行单纯形法 ×
对偶单纯形法？ ×
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
5432
6
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xZ
，，
对
9x增加人工变量大 M法：
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
95432
96
xxxxxx
xxxxx
xxx
xxxxx
xxxxx
ts
MxxZ
，，
求两阶段法
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
95432
9
xxxxxx
xxxxx
xxx
xxxxx
xxxxx
ts
xZ
，，
求单纯形法单纯形法作业：
0,
77
42
.
m a x
21
21
21
21
xx
xx
xx
ts
xxZ
求解下列问题用对偶单纯形法
13
31
*
13
10
13
21
*
Z
X
最优值：
），，（最优解：
对偶单纯形法,利用对偶理论得到的一个求解线性规划问题的方法单纯形法（原始单纯形法）的 两个条件,
1、问题为标准型
2、有初始基本可行解
0,
32
634
33
.
2m in
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
标准型为
0,,,,
32
634
33
.
2m a x
54321
521
7421
6321
7621
76
xxxxx
xxx
xxxx
xxxx
ts
MxMxxxZ
xx,引进人工变量用单纯形法求解对偶单纯形法的优点：
1、不需要人工变量；
2、当变量多于约束时，用对偶单纯形法可减少迭代次数；
3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。
bAX?于是 b
X
XNB
N
B
bNXBX NB
B 可逆
NB NXBbBX 11
N
B
NB X
XCCZ且 NNBB XCXC
NNNB XCNXBbBC )( 11
NBNB XNBCCbBC )( 11
0,0
.
m a x
bX
bAXts
CXz对标准型
nmm PPPPPA 121是可行基设 mPPPB?21?
NBA,?
N
B
X
XX
原始单纯形法的基本思路：
NB CCC?
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
关于可行基 B的典则形式检验数
0?NX令 01 bBX B得 0,11 bBX得基本可行解
01 1 NBC N、若所有的检验数 为最优解则 1,X
解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数
,0
,03 1
NBCC BN
域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数
,0
,02 1
NBCC BN
持对应的基本解可行在迭代过程中，始终保做换基迭代,
01 bBX B即
0
0
1
1
NBCC
NBCC
BN
BN
个数越来越少，最终的分量中并使检验数
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
bBCZXNBCCX BNBNB 11 )(0
bBNXBX NB 11
0?NX令 01 bBX B得
，若 01 NBC N 为最优解1XX
B XN 常数项检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
初始单纯形表：
0?
原始单纯形法的迭代过程：
0,11 bBX得基本可行解
0
变量否则，选定入基、出基对该单纯形表做行变换
，直至 01 NBC N
得最优单纯形表件：最优单纯形表的充要条,01 NBC N
0
.
m a x
X
bAXts
CXz对
mPPPB?21?取基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
对偶单纯形法的基本思路：
0?NX令 bBX B 1得
0,11 bBX得基本解
:01 NBCC BN若
XB XN 常数项检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
作对偶单纯形表,
0?
0
为最优解1,X
否则，换基迭代对该单纯形表做行变换
，直至 01 bB
得最优对偶单纯形表
01 bB若
）始终保持 0( 1 NBC N
选定入基、出基变量要条件：最优对偶单纯形表的充 01 bB
0,
32
634
33
.
2m i n
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ例：求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
解：标准型为
0,,,,
32
634
33
.
54321
521
421
321
xxxxx
xxx
xxx
xxx
ts
212m a x xxZ即
543,,PPPB?取基
36300,，，，基本解X
基 B的典则形式
X1 X2 X3 X4 X5
检 -2 -1 0 0 0 Z
X3 -3 -1 1 0 0 -3
X4 -4 -3 0 1 0 -6
X5 1 2 0 0 1 3
不可行检验行
≤ 0
分析：
若 X3或 X4所在的行的 aij均非负，
则问题一定无可行解否则，做换基迭代
X1 X2 X3 X4 X5
检 -2 -1 0 0 0 Z
X3 -3 -1 1 0 0 -3
X4 -4 -3 0 1 0 -6
X5 1 2 0 0 1 3
1、确定出基变量：
设 br =min{bi | bi <0}
则取 br所在行的基变量为出基变量即取 X4为出基变量
2、确定入基变量：
原则：
保持检验行系数 ≤0
0
00|m i n
ri
i
ri
ri
i
aaa
设为入基变量则取 0ix
31
X1 X2 X3 X4 X5
检
X3
X2
X5
21
X1 X2 X3 X4 X5
检
X3
X2
X1
），，，，（最优解 0005653?X
512Z最优值
-2/3 0 0 -1/3 0 Z+2
-5/3 0 1 -1/3 0 -1
4/3 1 0 -1/3 0 2
-5/3 0 0 2/3 1 -1
0 0 0 -3/5 -2/5 Z+12/5
0 0 1 -1 -1 0
0 1 0 1/5 4/5 6/5
1 0 0 -2/5 -3/5 3/5
），（
所求问题的最优解
5
6
5
3?X
5
12?Z最优值
0,
32
634
33
.
2m i n
21
21
21
21
21
xx
xx
xx
xx
ts
xxZ例：求
0,,,,
32
634
33
.
2m a x
54321
521
421
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
解：标准型为
），，，，（最优解 0005653?X
512Z最优值对偶单纯形法步骤,
1、找出一个初始对偶可行解。
把原问题写成该基的典则形式时,目标函数的系数均 ≤0
2、判断,（ 1）若 B-1b≥0，则得到最优解 0,1
0 bBX
结束
（ 2）若 B-1b≥0,
mbbbbB,,,211?记
0|m i n iir bbb设
njab rjj?,2,10,0 且若存在某个则问题无可行解。
3、换基迭代：
（ 1）确定出基变量：
（ 2）确定入基变量
0
00|m i n
ri
i
ri
ri
i
aaa
设即找出一个基 B，
为入基变量则取 0,ix
24 0 转，得一新的单纯形表，为主元素进行换基迭代、以 ria
否则转下一步所在行的基变量出基则取 rb?
0,,
964
52
5
.
2m a x
321
32
32
321
21
xxx
xx
xx
xxx
ts
xxZ
求解下列问题例：用对偶单纯形法
0,,
964
52
5
.
2m a x
54321
532
432
321
21
xxxxx
xxx
xxx
xxx
ts
xxZ
，，
解：问题化为标准型
964 532 xxx
），，（初始基 541 PPPB?
不是典则形式
X1 X2 X3 X4 X5
检 2 1 0 0 0 Z
X1 1 1 1 0 0 5
X4 0 2 1 1 0 5
X5 0 -4 -6 0 1 -9
0 -1 -2 -10
3141
X1 X2 X3 X4 X5
检
X1
X4
X2 0 1 3/2 0 -1/4 9/4
0 0 -2 1 1/2 1/2
1 0 -1/2 0 1/4 11/4
0 0 -1/2 0 -1/4 Z-31/4
），，，，（最优解 021049411?X
4
31?Z最优值
），（最优解 49411?X
4
31?Z最优值注意,对偶单纯形法仅限于初始基 B对应的典则形式中目标函数的系数（检验数）均 ≤0的情形。
nn xcxcxcz2211m i n
:形如
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
nn xcxcxcz2211m a x
:标准型
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
2211
222222121
111212111
.
),,2,1(0 njc j若可用对偶单纯形法
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
2211
222222121
111212111
.
）（基 mnnn PPPB,,,21?
），，，，（
基本解
mbbbX,,,000 21
B的典则形式
ABCC B 1由于NBBCCC BNB,1 ），（
NBCBBCCC BBNB 11, ），（
NBCCCC BBNB 1, ），（
），（ NBCCO BN 1
AB 1?且 ),(1 NBB ),( 11 NBBB ),( 1 NBE
X 解检验行 Z- CBB-1b
XB B-1b
ABCC B 1
AB 1?
0,0
.
m a x
bX
bAXts
CXz对标准型设 B为可行基
XB XN 解检验行 0 CN- CBB-1N Z- CBB-1b
XB E B-1N B-1b
NBA,,?
N
B
X
XX
NB CCC?
01 NBCC BN最优
0?
01 ABCC B最优原始单纯形法的基本思路：
X 解检验行 Z- CBB-1b
XB B-1b
ABCC B 1
AB 1?
0,0
.
m a x
bX
bAXts
CXz
对标准型设 B为可行基
01 ABCC B
10 BCY B
最优
00 AYC
CAY?0
YbSD?m i n）：（
其偶规划为无符号限制Y
CYAts?.
）的可行解是（ DY 0原始单纯形法的迭代过程,
）（ P
010,）得到最优解为（ bBXP
01 bB当 时且 01 ABCC B
）的最优解为（且由对偶理论知,DBCY B 10
的前提下，）的解是基本可行解在保证（ 01 bBP
）的可行解的方向迭代是（即向 DBCY B 10
的方向迭代向 01 ABCC B
）同时得到可行解）和（即（ DP
010,）得到最优解为（ bBXP
时且 01 bB，当 01 ABCC B
）的最优解为（且由对偶理论知,DBCY B 10
的方向迭代，向 01 bB
）的可行解的前提下，是（即 DBCY B 10
01 ABCC B在保证
）同时得到可行解时）和（即（ DP
对偶单纯形法的基本思路,
）的可行解方向迭代即向（ P
对偶单纯形法单纯形法解线性规划问题的方法如何用？
求解线性规划问题的 方法与步骤,
1,把原问题化为标准型
0
.
m a x
X
bAXts
CXz
2、找初始基
找不到基找到一个基 B
，转第 3步
，转第 4步
3、把问题写成关于基 B的典则形式
01 bB即若对应的基本解可行，
若对应的基解不可行，
，用单纯形法
0
0
存在检验数检验数均
，对偶单纯形法
，转第 4步
4、增加人工变量，用大 M法或两阶段法求解
01 bB即
0
52
2
.
834m in
321
32
31
321
xxx
xx
xx
ts
xxxZ
，，
例求
0,,
52
2
.
834m a x
54321
532
431
321
xxxxx
xxx
xxx
ts
xxxZ
，，
标准型为
541 PPB,若取初始基?
的典则形式为则关于 1B
0,,
52
2
.
834m a x
54321
532
431
321
xxxxx
xxx
xxx
ts
xxxZ
，，
对应 B1的基本解：
520001,，，，X
可用对偶单纯形法求解检验数全部 ≤0
不 可行
212 PPB,若取初始基?
的典则形式为则关于 2B
0,,
52
2
.
3418m a x
54321
532
431
543
xxxxx
xxx
xxx
ts
xxxZ
，，
对应 B2的基本解
000522,，，，X
用单纯形法求解可行
0,,,
0289
5
15223
12
.
m in
654321
64321
31
4321
5432
6
xxxxxx
xxxxx
xx
xxxx
xxxx
ts
xZ
，，
例：求
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
5432
6
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xZ
，，
化标准型
8765,PPPPB,，取初始基?
0,,,
0289
5
15223
12
.
289m a x
654321
64321
831
74321
5432
4321
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xxxxZ
B
，，
的典则形式关于对应 B的基本解：
5,150,1,0000,，，，X
存在检验数 >0
不可行单纯形法 ×
对偶单纯形法？ ×
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
5432
6
xxxxxx
xxxxx
xxx
xxxxx
xxxx
ts
xZ
，，
对
9x增加人工变量大 M法：
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
95432
96
xxxxxx
xxxxx
xxx
xxxxx
xxxxx
ts
MxxZ
，，
求两阶段法
0,,,
0289
5
15223
12
.
m a x
654321
64321
831
74321
95432
9
xxxxxx
xxxxx
xxx
xxxxx
xxxxx
ts
xZ
，，
求单纯形法单纯形法作业：
0,
77
42
.
m a x
21
21
21
21
xx
xx
xx
ts
xxZ
求解下列问题用对偶单纯形法
13
31
*
13
10
13
21
*
Z
X
最优值：
），，（最优解：
