Cj → 0 3 10 0
0
段↓基 b
P1 P2 P3
P4
Qi 注
1
0
x3 24 3
4
1
0
6
0 x4 15 -1 (5) 0
1
3 调出
Cj-Zj →
3 10 0
0
2
0
x3 12 (19/5) 0
10 x2 3 -1/5 1
P4
θi 注
1
cj-zj →
例
cj → 0 3 10 0 段 ↓ 基 b P1 P2 P3
0 P4
θi 注
1 0 x3 24 3 4 1 0 0 x4 15 -1 5 0 1
cj-zj →
步骤4.1
c j z j c j cB p j
▪ 计算检验数Ｃｊ－Ｚｊ：其中Ｚｊ等于Ｐｊ中各分 量与相应的左边各Ｃｊ的乘积之和，Ｃｊ－Ｚｊ等 于Ｐｊ上面对应的Ｃｊ减去Ｚｊ；
步骤1
▪ 引入松弛变量等，将问题化成标准形式；
max F 3x1 10x2 0x3 0x4 s.t. 3x1 4x2 x3 24 x1 5x2 x4 15 x j 0, j 1,2,3,4
步骤2
▪ 具体写出各系数矩阵Ａ，B，Ｐj和Ｃ; ▪ 特别注意：A矩阵中有否完全单位向量组。
第三章 单纯形法
▪ 单纯形法适用于任何线性规划问题的求解。
▪ 单纯形法的一般解法 ▪ 大M法和两阶段法 ▪ 修正单纯形法 ▪ 单纯形法的数学原理
第一节 单纯形法的一般解法
▪ 例：
max F 3x1 10x2 s.t. 3x1 4x2 24 x1 5x2 15 x1 0, x2 0
pi* j*
将原主元行上的元素，分别除以主元素，使主元素
为“1”。即：
Cj → 0
3 10 0
0
段↓基
b
P1
P2
P3
P4
θi 注
1
0
x3 24
3
Байду номын сангаас
4
1
0
6
0
x4 15
-1 (5)
0
1
3 调出
Cj-Zj →
3 10 0
0
2
0
x3
10 x2
Cj-Zj →
例：
Cj → 0 3 10 0
0
段↓基
b
P1 P2
cj → 0 3 10 0
0
段 ↓ 基 b P1 P2 P3
P4
θi 注
1
0 x3 24 3
4
1
0
0 x4 15 -1 5 0
1
cj-zj
→
cj → 0 3 10 0
0
段 ↓ 基 b P1 P2 P3
P4
θi 注
1
0 x3 24 3
4
1
0
0 x4 15 -1 5 0
1
cj-zj
→
3 10 0 0
步骤4.2：判断
其余均为0。
Cj
→
0
3
10
0
0
段
↓基
b
P1
P2
P3
P4
θi
注
1
0
x3
24
3
4
1
0
6
0
x4
15
-1
(5)
0
1
3 调出
Cj-Zj
→
3
10
0
0
2
0
x3
0
10
x2
3 -1/5 1
0
1/5
Cj-Zj
→
则：A=-4
Cj → 0 3 10 0
0
段↓基
b
P1
P2
P3
P4
θi 注
1
0 x3 24 3
4
1
0
6
0 x4 15 -1 (5) 0
▪ 5.1决定主元素 ▪ 5.2换基迭代 ▪ 5.3计算新元素
5.1 决定主元素：
▪ 当表中出现正检验数时，找出其中绝对值最大的一个所在的列作为主元 列，记为Pj*，然后用主元列中各正分量去除b列中相应的分量，得到θ i，接 着取θ i中最小的分量所在的行为主元行，记为Pi*；主元行与主元列相交处 的元素即主元素，记为Pi*j*；找到主元素后，打上一个圈以示区别。
主元素
6 主元行
3
5.2：换基
▪ 把主元行对应的变量（出基变量/调出变量）从基底调出，
用主元列对应的变量（入基变量/调入变量）代替之，进入
下一段。
例中：x4调出，x2调入。
Cj → 0 3 10 0 0
段 ↓基 b
P1 P2 P3
P4
θi 注
1
0 x3 24 3
4
1
0
6
0 x4 15 -1 (5) 0
P3
P4
θi 注
1
0
x3 24 3
4
1
0
6
0 x4 15 -1 (5) 0
1
3 调出
Cj-Zj →
3 10 0
0
2
0
x3
10 x2 3 -1/5 1 0 1/5
Cj-Zj →
5.3 计算新元素
▪ 5.3.2 原非主元行上元素的计算：
先将原主元行上的新元素乘以某一数A后，分别加上原非主
元行上的元素，使原主元列上各元素除了原主元素为“1”外，
计算检验数，判断检验数
Cj → 0 3 10 0
0
段↓基 b
P1 P2 P3
P4
Qi 注
1
0
x3 24 3
4
1
0
6
0 x4 15 -1 (5) 0
1
3 调出
Cj-Zj →
3 10 0
0
2
0
x3 12 19/5 0
10 x2 3 -1/5 1
Cj-Zj →
1 -4/5 0 1/5
计算检验数，判断检验数
1
3 调出
Cj-Zj →
3 10 0
0
2
0
x3 12 19/5 0
1
-4/5
10 x2 3 -1/5 1 0 1/5
Cj-Zj →
步骤6：回到第4步
▪ 步骤4：计算检验数、判断检验数
➢ 计算检验数Ｃｊ-Ｚｊ：
（１）若所有检验数均≤０时，即得到最优解和最优值； （２）若检验数存在正值，继续下一步。
▪ （１）若所有检验数均≤０时，即得到最优解和 最优值；
▪ （２）若检验数存在正值，继续下一步。
Cj → 0 3 10 0
0
段↓基 b
P1 P2 P3
P4
θi 注
1
0 x3 24 3
4
1
0
0 x4 15 -1 5 0
1
cj-zj
→
3 10 0 0
▪ 本例中：c1-z1>0，c2-z2>0
步骤5：换基迭代
1
3
Cj-Zj →
3 10 0 0
换基后
Cj → 0 3 10 0
0
段
↓基 b
P1 P2 P3
P4
1
0 x3 24 3
4
1
0
0 x4 15 -1 (5) 0
1
Cj-Zj →
3 10 0
0
2
0 x3
10 x2
Cj-Zj →
θi 注
6 3
5.3：计算新元素
5.3.1 原主元行上元素的计算：
pi*t p i*t '
A
3 1
4 5
1 0
0 1
B 1254
3
4
1
0
P1 1 P2 5 P3 0 P4 1
C 3 10 0 0
步骤3
▪ 形成初始表如下，表中基变量为Ａ矩阵中完 全单位向量组对应的变量。
段 cj → ↓基
C
b
p1 p2 … pn
θi
注
基变 基 1 量对 变
应的 量
cj
例
cj → 段 ↓ 基 b P1 P2 P3
Cj → 0 3 10 0 0
段↓基
b
P1 P2 P3
P4
θi 注
1
0 x3 24 3
4
1
0
0 x4 15 -1 5 0
1
Cj-Zj →
3 10 0 0
例： 主元列
Cj → 0 3 10 0
0
段↓基
b
P1
P2
P3
P4
θi 注
0 1
0 Cj-Zj
x3 24 3 4
x4 15 -1 (5)
→
3 10
10 01 00