对偶单纯形法的基本思路：
对 max z CX s.t AX b
X 0
取 B P 基 1 P 2 P m
m Z a C B B x 1 b (C N C B B 1 N )X N
XBB1bB1NN X
XB0,XN0
得 令XN 基 0 得 X1 X本 B B B1 b 解 1b,0
对问题maxz CX s.t AX b
X 0
取可行基
BP1 P2 Pm
令XN 0 得 XBB1b0
得基本X 可 1行 B1b,解 0
m Z a C B B x 1 b ( C N C B B 1 N )X N
XBB1bB1NN X
XB0,XN0
初始单纯形表：
XB XN
常数项
? 0 检验行 0 CN- CBB-1N
X1 检0
X3 0 X2 0 X1 1
X2 X3 X4 X5 0 0 -3/5 -2/5 Z+12/5 0 1 -1 -1 0
1 0 1/5 4/5 6/5 0 0 -2/5 -3/5 3/5
1、确定出基变量：
设br =min{bi | bi <0} 则取br所在行的基变量 为出基变量
即取X4为出基变量
x4 x5
6 3
引进人工变量x6，x7
x 1 , x 2 , x 3 , x 4 , x 5 0
max Z 2x1 x2 Mx6 Mx7
3x1 x2 x3 x6 3
s.t 4 x1x1
3x2 2x2
x4 x5
x7 3
6
用单纯形 法求解
x1, x2 , x3 , x4 , x5 0
6 3
x 1 , x 2 , x 3 , x 4 , x 5 0
即 mZ a x 2 x 1 x 2
3x1 x2 x3
3
s.tx41x1
3x2 2x2
x4 6 x5 3
x1,x2,x3,x4,x5 0
取 B 基 P 3 ,P 4 ,P 5 基X 本 0 ， 0 ， 解 3 ， 6 ， 3
X3 -3 -1 1 0 0 -3 X4 -4 -3 0 1 0 -6 X5 1 2 0 0 1 3
1 21 3
X1 X2 X3 X4 X5 检 -2/3 0 0 -1/3 0 Z+2
X3 -5/3 0 1 -1/3 0 -1 X2 4/3 1 0 -1/3 0 2 X5 -5/3 0 0 2/3 1 -1
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
分析： 若X3或X4所在的行的aij均 非负，
则问题一定无可行解
否则，做换基迭代
X1 X2 X3 X4 X5 检 -2 -1 0 0 0 Z
单纯形法（原始单纯形法）的两个条件：
1、问题为标准型
2、有初始基本可行解
求 min Z 2 x 1 x 2
3x1 x2 3
s
.t
4 x1 x1
3x2 2x2
6 3
x 1 , x 2 0
标准型为
max Z 2 x 1 x 2
3 x1 x2 x3 3
s
.t
4 x1 3 x2 x1 2 x2
于A是 X b
B
N
XB XN
b
BX BNN Xb
B 可逆
XBB1bB1NN X
且ZCB CNXXNB CBXBCNXN
C B (B 1 b B 1 NN )X C N X N
C B B 1 b (C N C B B 1 N )X N
对问题maxz CX
m Z a C B B x 1 b ( C N C B B 1 N ) X N
最优对偶单纯形表的充 要条件：B1b0
例：求 min Z 2 x1 x 2
3x1 x2 3
s
.t
4 x1 x1
3x2 2x2
6 3
x1 , x 2 0
解：标准型为
检验行 ≤0
max Z 2 x 1 x 2
3 x1 x 2 x3 3
s
.t
4xx1基1 B2的3xx典22 则 x形x54 式
对偶单纯形法的优点：
1、不需要人工变量；
2、当变量多于约束时，用对偶单 纯形法可减少迭代次数；
3、在灵敏度分析中，有时需要用对 偶单纯形法处理简化。
原始单纯形法的基本思路：
对标准型 maxz CX s.t AXb X 0,b 0
AB,N
CCB CN
X
X X
B N
A P 1P 2 P m P m 1 P n 设 BP 1 P 2 P m是可
s.t AX b X 0
XBB1bB1NN X
取可行基
BP1 P2
XB0,XN0
Pm关于可行基B的典则形式
检验数
令XN 0 得 XBB1b0得基本X 可 1行 B1b,解 0
1、若所有的C 检N 验 B数 1N0 ,则X1为最优解
2、检C 验 NC 数 BB1N中存在一 0个 ,且分 该量 分量对 向量中所有 0,则 的目 分标 量函数域 值内 在无 可上 行界
Z- CBB-1b
XB
E B-1N
B-1b 0
0 X B (C N C B B 1 N )X N Z C B B 1 b
XBB1NN X B1b
若CNB1N0，X 1为最优解 否则，选定入基、出基 变量 对该单纯形表做行变换 直C 至 NB1N0， 得最优单纯形表
最优单纯形表的充要条 件：CN B1N0，
3、若检C验 N C 数 BB1N中至少有一0个 ,且分 该量 分量对 的列向量中至分少量 有 0,则 一存 个在更好的解基本
做换基:迭 在代 迭代过程中 持， 对始 应终 的保 基本解 即 XBB1b0
并使检C 验 N 数 CBB1N中0的分量 个数越来越少 CN， CB最 B1终 N0
原始单纯ቤተ መጻሕፍቲ ባይዱ法的迭代过程：
2、确定入基变量：
原则：
保持检验行系数≤0
设mi narii
|
ari
0 i0
ar0i
则取xi0 为入基变量
最优X解 （3， 6， 0， 0， 0）
若 C NC BB 1N0:
作对偶单纯形表：
若B1b0
,
X
为最优解
1
否则，换基迭代
选定入基、出基变量
对该单纯形表做行变换
XB XN
常数项
检验行 0 CN- CBB-1N 0 Z- CBB-1b
XB
E B-1N
? B-1b 0
(始终CN 保 B 持 1N0） 直至 B1b0， 得最优对偶单纯形表