第一章 线性规划线性规划的建模线性规划的模型线性规划的图解法线性规划的标准化线性规划的基本概念线性规划的求解
2
1、线性规划的建模一例（例 1）
例 1：在工厂计划期内要安排生产 A,B两种产品，已知生产单位产品所需的设备台时及 a,b两种原材料的消耗如下表。
又该工厂每生产一件 A产品可获利 2元，
每生产一件 B产品可获例 3元。问：如何安排计划使该工厂获利最大？
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
3
解 设 A,B两种的产量分别为 （ 决策变量 ）,该问题的数学模型为：
目标函数约束函数
（ Subject To,s.t.）
12,xx
12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
4
2、线性规划模型
12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
12,2,3C c c1
2
xX
x
1 1 1 2
2 1 2 2
3 1 3 2
12
40
04
aa
A a a
aa
1
2
3
8
16
12
b
bb
b
5
线性规划模型解析式标准形式
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x
0,1,,.
nn
nn
nn
m m m n n m
j
z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
6
模型形式简记
1
1
m a x
( 1,2,,)
..
0 ( 1,2,,)
n
jj
j
n
i j j i
j
j
Z c x
a x b i m
st
x j n
11 12 1
21 22 2
12
n
n
m m m n
a a a
a a a
A
a a a
12(,,,)nC c c c?
1
2
m
b
b
b
b
1
2
n
x
x
X
x
1
2
,1,2,,
j
j
j
mj
a
a
P j n
a
7
线性规划模型矩阵标准形式线性规划模型的结构目标函数,max,min
约束条件,≥,=,≤
变量符号：,≥0,unr,≤0
线性规划的标准形式目标函数,max
约束条件,=
变量符号,≥0
m a x ( m in )
.,(,)
( ) 0,
z C X
s t A X b
X u n r
m a x
..
0
z CX
s t A X b
X
8
线性规划模型 练习 1
三种产品要经过三种不同的工序加工。各种产品每一件所需时间（分钟），每天各道工序的加工能力（每天多少分钟）和销售每一种产品的单位利润如下。试建立使总利润达到最大的线性规划模型。
工序 每件时间（分钟）
第 1种产品 第 2种产品 第 3种产品工序加工能力
（分钟 /天）
1
2
3
1 2 1
3 1 2
1 4 1
430
460
420
利润 /件
（元） 3 2 5
9
线性规划模型 练习 2
某厂为进行生产需采购 A,B两种原材料，
单价分别为 70元 /公斤和 50元 /公斤。现要求购买资金不超过 5000元，总购买量不少于 80公斤，而 A原材料不少于 20公斤。问如何确定最好的采购方案（即花掉的资金最少并且购买的总量最大）？
10
3、线性规划的图解
解决只有两个决策变量的线性规划问题
方法：在直角坐标系中画出所有约束方程的图象，从而得到 可行域（满足所有约束方程的解的集合）； 然后画出经过原点的目标函数图象的平行线 —— 目标函数等值线； 寻找经过可行域的使 Z达到最大的目标函数等值线，该直线与可行域的交集即为 最优解 集 。
图解法例 1
max z=x1+3x2
s.t,x1+ x2≤6
-x1+2x2≤8
x1 ≥0,x2≥0
6
4
-8
6
0
x1
x2
目标函数等值线最优解可行域
12
图解法例 2
max z=2x1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
x2
0 4 8
4
3
x1
最优解（ 4,2）
目标函数等值线可行域 0
13
四种可能的解的情况唯一最优解无穷多最优解无界解（无穷可行解，但无最优解）
无解（无可行解）
14
唯一最优解max z=2x
1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
0 4 8
4
3
x1
x2
最优解（ 4,2）
目标函数等值线可行域
15
线性规划的图解
无穷多最优解在例 2中,max z=2x1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
目标函数改为,max z=2x1+4x2
0 4 8
4
3
x1
最优解（ 4，
2）
目标函数等值线可行域目标函数等值线与第一条约束直线平行，
可以移至重合，与可行域交集为一线段。
16
无界解目标函数等值线
17
无解
18
4、模型的标准化一般形式：
1
1
m a x ( m i n )
(,) 1,2,,
..
0 1,2,,
n
jj
i
n
ij j i
j
j
Z f c x
a x b i m
st
x j n
标准形式,1
1
m a x
1,2,,
..
0 1,2,,
n
jj
i
n
ij j i
j
j
Z c x
a x b i m
st
x j n
19
模型的标准化
11
0
11
0
11
m in m a x ( )
,0,0
0
ni
ni
nn
fz
j j j j
jj
nn
x
ij j i ij j n i i
jj
nn
x
ij j i ij j n i i
jj
k k k k k k
j j j j
z c x f c x
a x b a x x b
a x b a x x b
x x x x x x
a x b x x a x
松 弛 变 量剩 余 变 量无 约 束,令令 则 0
j
bx
20
模型的标准化例题将
12
12
1
2
12
m a x 2 3
2 8
4 1 6
4 12
,0
z x x
xx
x
x
xx
标准化
21
例题答案
12
12
1
2
m a x 2 3
2 3 8
4 4 16
4 5 12
0,1,,5.
j
z x x
x x x
xx
xx
xj
标准化形式
12
12
1
2
12
m a x 2 3
2 8
4 1 6
4 12
,0
z x x
xx
x
x
xx
原型
22
模型的标准化练习
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 2 3
7
2
..
3 2 5
,0,
z x x x
x x x
x x x
st
x x x
x x x
无约束将下列模型标准化
23
练习答案
1 2 4 5 6 7
1 2 4 5 6
1 2 4 5 7
1 2 4 5
1 2 4 5 6 7
m a x 2 3 ( ) 0 0
( ) 7
( ) 2
..
3 2 ( ) 5
,,,,,0
z x x x x x x
x x x x x
x x x x x
st
x x x x
x x x x x x
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 2 3
7
2
..
3 2 5
,0,
z x x x
x x x
x x x
st
x x x
x x x
无约束原型标准化形式
24
5、线性规划的基本概念几何概念 代数概念约束直线 满足一个等式约束的解约束半平面 满足一个不等式约束的解约束半平面的交集：
凸多边形满足一组不等式约束的解约束直线的交点 基解可行域的极点 基可行解目标函数等值线：
一组平行线目标函数值等于一个常数的解
26
可行解与最优解可行解：满足约束条件的解，记为 X
X=（ x1,x2,…,xn） T
最优解：使目标函数值达到最优的可行解。
基矩阵约束方程系数矩阵 A的 m× m子矩阵 B,若 B
的行列式 ≠0,则称 B为 A的一个基（矩阵）。
=
=
目标函数约束条件行列式 ≠0
基矩阵右边常数
28
基变量、基向量基 B对应的 m个变量为基变量，其他 n-
m个变量为非基变量。假定
1
1 1 1 2 1 m
22 1 2 2 2 m
12
12
a
a a a
,
( 1,2,)
,,
j
j
j
m m m m mj
jj
m
aaa
a
Bp
a a a a
p x j m
B p p p
设为基变量 的系数向量——基向量。
则
29
mnmmmmmmmm
nmmm
nmmm
aaaaaa
aaaaaa
aaaaaa
A
2121
2221222221
1211111211
mmmm
m
m
aaa
aaa
aaa
B
21
22221
11211
mnmmmm
nmm
nmm
aaa
aaa
aaa
N
21
22212
12111基阵 非基阵
TmB xxxX?21TnmN xxxX?21
基向量非基向量基变量 非基变量
30
基解、基可行解基解,令所有非基变量为 0，根据约束方程求得的解（不包括非负约束）为对应基的基解。表示为
X=（ x1,x2,…,xm,0,…,0） T
基可行解,满足非负约束的基解。
基的个数最多为,故基解的个数最多为 。 mnc
m
nc
31
总结几个概念
基矩阵、非基矩阵
基变量、非基变量
基向量、非基向量
基解、可行解、基可行解、最优解
32
几种解的关系可行域的性质
● 线性规划的可行域是凸集
● 线性规划的最优解在极点上凸集 凸集 不是凸集极点
m a x z= 2x 1 + 3 x 2 +x 3
s,t,x 1 + 3 x 2 +x 3? 15
2x 1 + 3 x 2 - x 3? 18
x 1 - x 2 +x 3? 3
x 1,x 2,x 3? 0
1 2 3
1 2 3 4
1 2 3 5
1 2 3 6
m a x 2 3
3 15
2 3 18
..
3
0,1,2,,6.
j
z x x x
x x x x
x x x x
st
x x x x
xj
基解例 1
x 1 + 3 x 2 +x 3 = 1 5
2x 1 + 3 x 2 -x 3 = 1 8
x 1 -x 2 +x 3 =3
x 1 + 3x 2 +x 3 +x 4 = 15
2x 1 + 3x 2 - x 3 +x 5 = 18
x 1 - x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 5,3,1,0,0,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=20
x 1 + 3 x 2 +x 4 = 1 5
2x 1 + 3 x 2 = 1 8
x 1 -x 2 =3
基变量 x1,x2,x4,非基变量 x3,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 27/5,12/5,0,2/5,0,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
x 1 + 3 x 2 = 1 5
2x 1 + 3 x 2 +x 5 = 1 8
x 1 -x 2 =3
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x5,非基变量 x3,x4,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 6,3,0,0,-3,0） T
是基解，但不是可行解，不是一个极点。
x 1 + 3 x 2 = 1 5
2x 1 + 3 x 2 = 1 8
x 1 -x 2 +x 6 =3
基变量 x1,x2,x6,非基变量 x3,x4,x5
基解为（ x1,x2,x3,x4,x5,x6） T=（ 3,4,0,0,0,4） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 +x 4 = 1 5
3x 2 -x 3 = 1 8
-x 2 +x 3 =3
基变量 x2,x3,x4,非基变量 x1,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 0,21/2,27/2,-30,0,0） T
是基解，但不是可行解。
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 = 1 5
3x 2 -x 3 +x 5 = 1 8
-x 2 +x 3 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 0,3,6,0,15,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=15
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 = 1 5
3x 2 -x 3 = 1 8
-x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 0,11/2,-3/2,0,0,10） T
是基解但不是可行解。
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
基解例 2
max z=x1+3x2 D
s.t,x1+ x2+x3 =6 B
-x1+2x2 +x4=8 x4=0 C x3=0
x1,x2,x3,x4≥0 x1=0
E O x2=0 A
O A B C D E
基变量 x 3 x 4 x 1 x 4 x 1 x 2 x 2 x 3 x 2 x 4 x 1 x 3
非基变量 x 1 x 2 x 2 x 3 x 3 x 4 x 1 x 4 x 1 x 3 x 2 x 4
x j < 0 -- -- -- -- x 4 x 1
基可行解 是 是 是 是 否 否
43
基解课堂练习
max z=3x1+x2
s.t,3x1+ 5x2+x3 =15
5x1+2x2 +x4=10
x1,x2,x3,x4≥0
试求其所有的基解,并判断哪些基解为基可行解,
44
练习答案
11
22
33
44
55
66
35 2 0 4 5
,,,0,0
52 1 9 1 9
31
,2,0,9,0
50
30
,5,0,0,1 5
51
51
,0,5,1 0,0
20
50
,0,3,0,4
21
10
,0,0,1 5,1 0
01
T
T
T
T
T
T
BX
BX
BX
BX
BX
BX
是是是是
45
解题过程
A= 3 5 1 0 B1= 3 5 ∣ B∣ ≠0为 A的一个基
5 2 0 1 5 2
B1对应的基变量为 x1,x2,令非基变量 x3=x4=0,则求得基变量
x1=20/19,x2=45/19，从而 X1=（ 20/19,45/19,0,0） T为基解，满足非负，也为基可行解。
同理求得 B2= 3 1,X2=(2,0,9,0)T
5 0
B3= 3 0,X3=(5,0,0,-15)T
5 1
B4= 5 1,X4=(0,5,-10,0)T
2 0
B5= 5 0,X5=(0,3,0,4)T
2 1
B6= 1 0,X6=(0,0,15,10)T
0 1
显然 X3,X4是基解，但不是基可行解,X1,X2,X3,X4是基可行解。
maxz=3x1+x2
s.t,3x1+ 5x2+x3 =15
5x1+2x2 +x4=10
x1,x2,x3,x4≥0
46
基解课后练习
在下列线性规划问题中，找出所有基解、
基可行解和最优解。
maxZ=10x1+5x2
s,t 3x1+4x2≤9
5x1+2x2≤8
x1,x2≥0
47
6、线性规划的求解寻找最优解的过程进基变量、离基变量、基变换单纯形法
48
寻找最优解的过程根据问题的标准，从可行域中某个基可行解
（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。
49
以例 1为例
MaxZ=2x1+3x2
x1+2x2 ≤ 8
4x1 ≤ 16
4x2≤ 12
x1,x2≥ 0
50
第一步 化标准型
MaxZ=2x1+3x2+0x3+0x4+0x5
x1+2x2+x3 =8
4x1 +x4 =16
4x2+ +x5=12
x1,x2,x3≥ 0
51
第二步 寻找第一个基，求第一个基可行解
A=(P1,P2,P3,P4,P5)
B=(P3,P4,P5)= 1 0 0
0 1 0
0 0 1
令 x1=x2=0,得第一个基可行解
x(1)=(0,0,8,16,12)T
此时 z=0,由于 z=2x1+3x2有正系数的非基变量 x1和 x2,选择将 x2换入 。
52
第三步 将 x2换入，选择一个基变量换出
x1依然为非基变量，令 x1=0,则
x3=8-2x2≥ 0
x4=16≥ 0
x5=12-4x2≥ 0
因而 x2=min(8/2,-,12/4)=3
当 x2=3时,x5=0,,由此选择 x2替换 x5。
53
经过替换得
x3=2-x1+1/2x5
x4=16-4x1
x2=3-1/4x5
z=9+2x1-3/4x5
令 x1=x5=0,
得 z=9和另一个基可行解 x(2)=(0,3,2,16,0)T
此时有正系数的非基变量 x1,因而选择 x1换入，用相同的方法选择换出的基变量
54
同理可得其他的基可行解
x(3)=(2,3,0,8,0)T
x(4)=(4,2,0,0,4)T
当解为 x(4)时,z=14-1.5x3-0.125x4
此时再无正系数的非基变量，所以
max=14,唯一最优解为 x(4)
=
目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换
=
基变量
=
进基变量离基变量目标函数约束条件右边常数=
=
目标函数约束条件新的基矩阵右边常数=
=
进基变量离基变量目标函数约束条件基矩阵
=
=
目标函数约束条件新的基矩阵右边常数=
60
单纯形法
61
单纯形法的基本思想根据问题的标准，从可行域中某个基可行解
（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。
线性规划的矩阵表示
=
=
=
=
=
典则形式（典式）
64
11 00
N B BC C B N C C B A
可以证明：
检验数
典则形式（典式）
65
证明
1100N B BC C B N C C B A
1100N B BC C B N C C B A
1
1
1
1
(,),
(,) (,)
( 0,) 0
B
B N B
B N B B
TT
NB
C C B A
C C C B B N
C C C C B N
C C B N
检验数 --所有变量的系数?非基变量的系数注意 1：基变量检验数为
0
注意 2：所有检验数
<=0时得到最优解
66
由上面证明得检验数?
① 令 xN =0,得 xB=B-1b,此即为基解
x*=(xB,xN)T=(B-1b,0)
② 当所有 δ≤0时，
基解 x*=(B-1b,0)为最优基解
③ 当所有 B-1b≥ 0
时，最优基解
x*=(B-1b,0)为最优基可行解，
即为最优的极点，即为最优解。
67
NBA
N
B
X
XX
bAX b
X
XNB
N
B?
bNXBX
NB
NB NXbBX NB NXBbBX 11
N
B
X
XX
N
N
X
NXBbBX 11
令 0?NX
则
0
1bB
X
定义 在约束方程组 (2) 中，对于一个选定的基 B，令所有的非基变量为零得到的解，称为相应于基 B
的 基本解 。
再看一次整个过程
68
基本定理 1
对于一个线性规划问题，若存在基 B,使则对应于基 B的基可行解就是最优解,B为最优基。
1 0Bb
1,0
BNX B b X
1 0BC C B A
可行性 最优性
69
基本定理 2
线性规划问题如果存在最优解，
则一定存在一个基本可行解是最优解。
70
矩阵与单纯形表的对应关系
X b
CB XB A b
-Z
XB XN b
CB XB B N b
-Z
XB XN b
CB XB I B-1N B-1b
-Z CT-CBB-1A -CBTB-1b
模型矩阵形式 单纯形表
72
单纯形表的基本格式（ 1）
C b
X
CB XB B-1A B-1b
-Z C-CBB-1A -CBB-1b
X b
CB XB A b
-Z
73
单纯形表的基本格式（ 2）
11
11
m a x ( )
.,
0,0
B N B
BN
BN
Z C B b C C B A X
X B NX B b
st
XX
典式：
CB CN b
XB XN
CB XB I B-1N B-1b
-Z C-CBB-1A -CBB-1b
单纯形法基本格式：
74
单纯形表的基本格式（ 3）
BX
X sX b
sX
A I b
Z? C 00
(右端项 )（松弛变量）（原始决策变量）
BX
X
sX
b
BX
1BA? 1B? 1Bb?
Z? 1
BC C B A 1BCB 1BC B b?
(右端项 )（松弛变量）（原始决策变量）
①对于迭代过程中的任意可行基 B所形成的单纯形表，初始表中单位子矩阵的位置（即松弛变量对应的系数）必为 B-1
② 留意松弛变量 xs的检验数 -CBB-1，在下一章有用。
75
单纯形表的基本格式（ 3）
BX
X sX b
sX
A I b
Z? C 00
(右端项 )（松弛变量）（原始决策变量）
BX
X
sX
b
BX
1BA? 1B? 1Bb?
Z? 1
BC C B A 1BCB 1BC B b?
(右端项 )（松弛变量）（原始决策变量）
③研究此时的系数矩阵
11
12
1 1 1
12
(,,,)
(,,,)
n
n
B A B P P P
B P B P B P
由此可见，此时 xj 的系数为 B-1Pj 。
76
单纯形法例 1 23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
2
0,1,5,
j
z x x
x x x
x x x
st
x x x
xj
77
初始可行基初始基可行解
1 4 5
1 0 0
0 1 0,,
0 0 1
B p p p
( 0 ) ( 2,0,0,1,2 ) TX?
23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
= 2
0,1,5.
j
z x x
x x x
x x x
st
x x x
xj
78
000-210-Z
2210-110x50
1101-310x40
—2001-21x10
x5x4x3x2x1XBCB
θB-1b
00-210C
23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
2
0,1,5,
j
z x x
x x x
x x x
st
x x x
xj
初始单纯形表
79
-10-1100-Z
1/211-1200x50
—101-310x21
—402-501x10
000-210-Z
2210-110x50
1101-310x40
—2001-21x10
x5x4x3x2x1XBCB θB
-1b
00-210C
表 1
表 2
80
-3/2-1/2-1/2000-Z
1/21/2-1/2100x3-2
5/23/2-1/2010x21
13/25/2-1/2001x10
-10-1100-Z
1/211-1200x50
—101-310x21
—402-501x10
x5x4x3x2x1XBCB θB-1b
00-210C
表 2
表 3
最优解
**13 5 1 3(,,,0,0),.
2 2 2 2
TXZ
81
例 2
m ax z= 2x 1 +3 x 2 +x 3
st x 1 +3 x 2 +x 3? 15
2x 1 +3 x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m i n z’ = - 2x 1 - 3x 2 - x 3
st x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 - x 3 +x 5 = 1 8
x 1 - x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 3 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
m in z’= -2 x 1 -3 x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 [3 ] 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 1 0 0 -1 0 0 -15
x 2 0 1/3 1 1/3 1/3 0 0 5 5/1/3
x 5 0 [1] 0 -2 -1 1 0 3 3/1
x 6 0 4/3 0 4/3 1/3 0 1 8 8/4/3
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
x 3 进基,x 6 离基
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 0 0 0 -5 /6 -1 /3 -1 /2 -2 0
x 2 0 0 1 0 1 /4 0 -1 /4 3
x 1 0 1 0 0 -1 /6 1 /3 1 /2 5
x 3 0 0 0 1 5 /1 2 -1 /3 1 /4 1
最优解,( x 1,x 2,x 3,x 4,x 5 x 6 )= (5,3,1,0,0,0),m ax z=2 0
86
单纯形法的求解步骤
1、标准化
2、求出初始基可行解
3、列出单纯形表，并求出检验数的值
4、对检验数进行判断,
（ 1）若所有检验数 <=0,则已求出最优解；
（ 2）若至少有一个检验数为正,则选取绝对值最大的那个，对应的非基变量为入基变量。计算 θ 的值：
① 若对应非基变量 xk 的系数 B-1pk ≤ 0
（ 即 θ <0或 ∞),则不存在最优解；
② 若至少有一个 θ >0,则选择最小的，其对应的变量为出基变量。进行初等变换。转 3
87
人工变量法
1、两阶段法
2、大 M法
88
对于约束条件为 >=或 =的情形
11
11
nn
ij j n i i ij j n i n i i
jj
nn
ij j i ij j j i
jj
a x x b a x x x b
a x b a x x b
89
假定已经标准化的原问题为
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x
0,1,,.
nn
nn
nn
m m m n n m
j
z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
90
对于已经标准化的形式，每个约束等式加上一个人工变量
1 1 1 1 2 2 1 1 1
2 1 1 2 2 2 2 2 2
1 1 2 2
12
0,1,,.
,,,
n n n
n n n
m m m n n n m m
j
n n n m
a x a x a x x b
a x a x a x x b
a x a x a x x b
x j n m
x x x
为 人 工 变 量,
91
两阶段法,将求解过程分成两个阶段第一阶段,构造辅助线性规划问题求解，若求得辅助线性规划问题的目标函数值为 0，则原问题存在可行解，进入第二阶段，否则原问题无解。
第二阶段,以第一阶段求得的最优解为初始可行解，求解原问题。
92
所加入的人工变量只有满足全为 0时才能保证原等式成立。建立新目标。所有人工变量全为 0
时，新目标函数达到最优值 0。
12
12
m a x
m i n
n n n m
n n n m
z x x x
z x x x
或
93
第一阶段 求解辅助线性规划问题
12
12
1 1 1 1 2 2 1 1 1
2 1 1 2 2 2 2 2 2
1 1 2 2
m a x
m in
0,
n n n m
n n n m
n n n
n n n
m m m n n n m m
j
z x x x
z x x x
a x a x a x x b
a x a x a x x b
a x a x a x x b
xj
或
1,,.nm
94
若第一阶段求得的最优解使目标函数值达到最大值 0，
则进入第二阶段。假定求得的最优解为 X=( )。
95
第二阶段、以 X为初始可行解求解原问题
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x ( m in )
0,1,,.
nn
nn
nn
m m m n n m
j
z z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
或
96
两阶段法例 11 2 3 4
1 2 3
1 2 3
1 2 3 4
m a x 2 3
2 3 15
2 5 20
..
2 10
0( 1,4)
j
z x x x x
x x x
x x x
st
x x x x
xj
97
第一阶段，构造辅助线性规划问题
5 6 7
1 2 3
1 2 3
1 2 3 4
m a x
2 3 5 1 5
2 5 6 2 0
..
2 7 1 0
0 ( 1,,7 )
j
W x x x
x x x x
x x x x
st
x x x x x
xj
1 2 3 4
1 2 3
1 2 3
1 2 3 4
m a x 2 3
2 3 15
2 5 20
..
2 10
0( 1,4)
j
z x x x x
x x x
x x x
st
x x x x
xj
原问题辅助规划问题人工变量
98
对辅助规划问题的求解
0
0
0
1
0
0
0
1
x5
-1
-9/5
-1/5
1/5
-3/5
0
0
1
0
x6
-1
-901016/52/5-W
10/361109/53/5x7-1
2040011/52/5x30
15/730007/5-1/5x5-1
-4501954-W
101011121x7-1
42000512x6-1
51500321x5-1
x7x4x3x2x1XBCB θB-1b
-10000C
表
1
表
2
99
-1
-9/7
-1/7
5/7
-16/7
-9/7
-1/7
5/7
x5
-1
-1
7/4
2/7
-3/7
-3/7
7/4
2/7
-3/7
x6
-1
0-10000-W
15/711006/7x40
25/700103/7x30
15/70001-1/7x20
-15/701006/7-W
15/715/711006/7x7-1
—25/700103/7x30
—15/70001-1/7x20
x7x4x3x2x1XBCB θB-1b
-10000C
表
3
表
4
**1 5 2 5 1 5( 0,,,,0,0,0 ),0,
777
TXW
最优解
100
第二阶段，求解原问题
15-1000-Z
5/27/6001x11
5/2-1/2100x33
5/21/6010x22
0006/7-Z
5/215/71006/7x4-1
25/325/70103/7x33
—15/7001-1/7x22
x4x3x2x1XBCB θB-1b
-1321C
* 15 25 15( 0,,,)
777
TX?以 为初始基可行解求解原问题表
1
表
2
**( 5 / 2,5 / 2,5 / 2,0 ),1 5TXz
最优解为
101
两阶段法例 2
1 2 3 1 2 3
1 2 3 1 2 3 4
1 2 3 1 2 3 5
1 2 3 1 2 3
1 2 3 1 2 3 4 5
6 7 8
m a x 2 3 m a x 2 3
3 5 3 48 3 5 3 48
5 8 8 32 5 8 8 32
.,,,
2 4 18 2 4 18
,,0,,,0
m a x
z x x x z x x x
x x x x x x x
x x x x x x x
s t s t
x x x x x x
x x x x x x x x
W x x x
标准化
，
辅助规划问题
1 2 3 4 6
1 2 3 5 7
1 2 3 8
1 2 3 4 5
3 5 3 48
5 8 8 32
,,
2 4 18
,,,0
x x x x x
x x x x x
st
x x x x
x x x x x
，
102
求解辅助规划问题
-7/8
-1/4
1/8
-5/8
1
0
1
0
x5
0
0
0
0
1
0
0
0
1
x6
-1
-15/8
-1/4
1/8
-5/8
0
0
1
0
x7
-1
380-1-140-3/8-Z
1010-60-1/4x8-1
400115/8x20
280-1-80-1/8x6-1
-980-11159-Z
91810-421x8-1
43200885x7-1
48/5480-1-353x6-1
x8x4x3x2x1XBCB θB-1b
-10000C
表 1
表 2
由于辅助线性规划问题最优解为 -38，不为 0，
所以原问题不存在可行解（无解）。
103
大 M法原理,在进行迭代时，只有所有的人工变量均迭代为非基变量（即为 0）时，
才能消除大 M对目标函数的影响，使目标函数达到最优。
例,P64 例 3
12m a x n n n mz x x x
104
添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数 δj
所有 δj<=0
对任一 δj>0
有 aik<=0
令 ak =max{δj}
对所有 aik >0计算
θi=bi/ aik
令 θi =min{θi}
xi为换出变量
aik为主元素基变量中有非零的人工变量某非基变量检验数为零唯一最优解无可行解无界解无穷多最优解迭代运算是 否 否否是是 是单纯形法一般步骤
105
无穷多个最优解若存在一个非基变量的检验数为 0，则最优解不止一个且为无穷多个。
106
无穷多最优解例题
141-1/204x4-1
60-100-Z
31/43/810x2-1
60-100-Z
11/4-1/801x1-3
—201/21-1x2-1
10002-2-Z
661013x4-1
24012-2x3-1
x4x3x2x1XBCB θB-1b
-1-1-1-3C
表 1
表 2
表 3
107
由表 2得最优解由表 3得最优解所以，最优解为
( 1 ) *( 0,2,0,4 ),6TXZ
( 2 ) *( 1,3,0,0 ),6TXZ
* ( 1 ) ( 2 )( 1 )
0 1
X X X
108
x1
x2
(1)X
(2)X
109
无穷多个最优解练习
12
12
12
12
m a x
0
.,1
,0
z x x
xx
s t x x
xx
110
练习答案
12
1 2 3
1 2 4
1 2 3 4
m a x
0
.,1
,,,0
z x x
x x x
s t x x x
x x x x
111
111011x11
1/211120x30
-1-1000-Z
-1-1000-Z
1/21/2-1/201x11
1/21/21/210x21
00011-Z
111011x40
—0011-1x30
X4x3x2x1XBCB θB-1b
0011C
表 1
表 2
表 3
12
1 2 3
1 2 4
1 2 3 4
m a x
0
.,1
,,,0
z x x
x x x
s t x x x
x x x x
112
( 1 ) *( 1,0,1,0 ),1TXZ
( 2 ) *( 1 / 2,1 / 2,0,0 ),1TXZ
* ( 1 ) ( 2 )( 1 )
0 1
X X X
由表 2得最优解由表 3得最优解所以，最优解为
113
无界解例题
23
1 4 5
2 4 5
3 4 5
m a x 2
1 5 13
2 2 2
1 3 5
.,2 2 2
1 1 1
2 2 2
0,1,,5
j
z x x
x x x
x x x
st
x x x
xj
114
23
1 4 5
2 4 5
3 4 5
m a x 2
1 5 13
2 2 2
1 3 5
.,2 2 2
1 1 1
2 2 2
0,1,,5
j
z x x
x x x
x x x
st
x x x
xj
作出其初始单纯形表如下
0 0 0 3/2 -5/2 7/2
1 0 0 -1/2 5/2 13/2
0 1 0 -1/2 3/2 5/2
0 0 1 -1/2 1/2 1/2
x1 x2 x3 x4 x5 RHS(右端向量 )
z
x1
x2
x3
x4进基无离基变量
x4可无限增大，
目标函数值随之无限增大，所以为无界解
115
单纯形法的进一步讨论
—— 退化对于基可行解 XB=B-1b,XN=0,若存在基变量的值为 0，则称该 可行解是退化的,
否则为 非退化的,即 XB=B-1b>0。
若某线性规划问题的所以基可行解都是非退化的，则该问题为非退化的，否则该问题为退化的。
116
退化引起死循环从某个基开始，经过若干次迭代以后又回到原来的基，也就是单纯形法出现了死循环。
出现死循环的原因主要是因为退化的问题中，基变量取值可以为 0，即经过迭代以后，目标函数值可能不会增加。
117
死循环的避免一种有效的方法是 Bland方法
P67
118
单纯形法的进一步讨论
—— 最小化目标函数最小化目标函数问题只须在判断检验数时取相反符号即可。
即迭代终止条件为：
1 0BC C B A
119
最小化目标函数例题
1 2 3 4
1 2 3
1 2 4
m in 3
2 2 4
.,3 6
0( 1,,4)
j
z x x x x
x x x
s t x x x
xj
120
以 MIN求解
-60100-Z
41-1/204x41
201/21-1x21
-1000-22-Z
661013x41
24012-2x31
x4x3x2x1XBCB θB-1b
1113C
表 1
表 2
121
以 MAX求解
60-100-Z’
141-1/204x4-1
—20?1-1x2-1
10002-2-Z’
661013x4-1
24012-2x3-1
X4x3x2X1XBCB θB-1b
-1-1-1-3C
表 1
表 2
122
本章结束！
2
1、线性规划的建模一例（例 1）
例 1：在工厂计划期内要安排生产 A,B两种产品，已知生产单位产品所需的设备台时及 a,b两种原材料的消耗如下表。
又该工厂每生产一件 A产品可获利 2元，
每生产一件 B产品可获例 3元。问：如何安排计划使该工厂获利最大？
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
3
解 设 A,B两种的产量分别为 （ 决策变量 ）,该问题的数学模型为：
目标函数约束函数
（ Subject To,s.t.）
12,xx
12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
4
2、线性规划模型
12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
12,2,3C c c1
2
xX
x
1 1 1 2
2 1 2 2
3 1 3 2
12
40
04
aa
A a a
aa
1
2
3
8
16
12
b
bb
b
5
线性规划模型解析式标准形式
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x
0,1,,.
nn
nn
nn
m m m n n m
j
z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
6
模型形式简记
1
1
m a x
( 1,2,,)
..
0 ( 1,2,,)
n
jj
j
n
i j j i
j
j
Z c x
a x b i m
st
x j n
11 12 1
21 22 2
12
n
n
m m m n
a a a
a a a
A
a a a
12(,,,)nC c c c?
1
2
m
b
b
b
b
1
2
n
x
x
X
x
1
2
,1,2,,
j
j
j
mj
a
a
P j n
a
7
线性规划模型矩阵标准形式线性规划模型的结构目标函数,max,min
约束条件,≥,=,≤
变量符号：,≥0,unr,≤0
线性规划的标准形式目标函数,max
约束条件,=
变量符号,≥0
m a x ( m in )
.,(,)
( ) 0,
z C X
s t A X b
X u n r
m a x
..
0
z CX
s t A X b
X
8
线性规划模型 练习 1
三种产品要经过三种不同的工序加工。各种产品每一件所需时间（分钟），每天各道工序的加工能力（每天多少分钟）和销售每一种产品的单位利润如下。试建立使总利润达到最大的线性规划模型。
工序 每件时间（分钟）
第 1种产品 第 2种产品 第 3种产品工序加工能力
（分钟 /天）
1
2
3
1 2 1
3 1 2
1 4 1
430
460
420
利润 /件
（元） 3 2 5
9
线性规划模型 练习 2
某厂为进行生产需采购 A,B两种原材料，
单价分别为 70元 /公斤和 50元 /公斤。现要求购买资金不超过 5000元，总购买量不少于 80公斤，而 A原材料不少于 20公斤。问如何确定最好的采购方案（即花掉的资金最少并且购买的总量最大）？
10
3、线性规划的图解
解决只有两个决策变量的线性规划问题
方法：在直角坐标系中画出所有约束方程的图象，从而得到 可行域（满足所有约束方程的解的集合）； 然后画出经过原点的目标函数图象的平行线 —— 目标函数等值线； 寻找经过可行域的使 Z达到最大的目标函数等值线，该直线与可行域的交集即为 最优解 集 。
图解法例 1
max z=x1+3x2
s.t,x1+ x2≤6
-x1+2x2≤8
x1 ≥0,x2≥0
6
4
-8
6
0
x1
x2
目标函数等值线最优解可行域
12
图解法例 2
max z=2x1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
x2
0 4 8
4
3
x1
最优解（ 4,2）
目标函数等值线可行域 0
13
四种可能的解的情况唯一最优解无穷多最优解无界解（无穷可行解，但无最优解）
无解（无可行解）
14
唯一最优解max z=2x
1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
0 4 8
4
3
x1
x2
最优解（ 4,2）
目标函数等值线可行域
15
线性规划的图解
无穷多最优解在例 2中,max z=2x1+3x2
s.t,x1+ 2x2≤8
4 x1 ≤16
4x2 ≤12
x1 ≥0,x2≥0
目标函数改为,max z=2x1+4x2
0 4 8
4
3
x1
最优解（ 4，
2）
目标函数等值线可行域目标函数等值线与第一条约束直线平行，
可以移至重合，与可行域交集为一线段。
16
无界解目标函数等值线
17
无解
18
4、模型的标准化一般形式：
1
1
m a x ( m i n )
(,) 1,2,,
..
0 1,2,,
n
jj
i
n
ij j i
j
j
Z f c x
a x b i m
st
x j n
标准形式,1
1
m a x
1,2,,
..
0 1,2,,
n
jj
i
n
ij j i
j
j
Z c x
a x b i m
st
x j n
19
模型的标准化
11
0
11
0
11
m in m a x ( )
,0,0
0
ni
ni
nn
fz
j j j j
jj
nn
x
ij j i ij j n i i
jj
nn
x
ij j i ij j n i i
jj
k k k k k k
j j j j
z c x f c x
a x b a x x b
a x b a x x b
x x x x x x
a x b x x a x
松 弛 变 量剩 余 变 量无 约 束,令令 则 0
j
bx
20
模型的标准化例题将
12
12
1
2
12
m a x 2 3
2 8
4 1 6
4 12
,0
z x x
xx
x
x
xx
标准化
21
例题答案
12
12
1
2
m a x 2 3
2 3 8
4 4 16
4 5 12
0,1,,5.
j
z x x
x x x
xx
xx
xj
标准化形式
12
12
1
2
12
m a x 2 3
2 8
4 1 6
4 12
,0
z x x
xx
x
x
xx
原型
22
模型的标准化练习
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 2 3
7
2
..
3 2 5
,0,
z x x x
x x x
x x x
st
x x x
x x x
无约束将下列模型标准化
23
练习答案
1 2 4 5 6 7
1 2 4 5 6
1 2 4 5 7
1 2 4 5
1 2 4 5 6 7
m a x 2 3 ( ) 0 0
( ) 7
( ) 2
..
3 2 ( ) 5
,,,,,0
z x x x x x x
x x x x x
x x x x x
st
x x x x
x x x x x x
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 2 3
7
2
..
3 2 5
,0,
z x x x
x x x
x x x
st
x x x
x x x
无约束原型标准化形式
24
5、线性规划的基本概念几何概念 代数概念约束直线 满足一个等式约束的解约束半平面 满足一个不等式约束的解约束半平面的交集：
凸多边形满足一组不等式约束的解约束直线的交点 基解可行域的极点 基可行解目标函数等值线：
一组平行线目标函数值等于一个常数的解
26
可行解与最优解可行解：满足约束条件的解，记为 X
X=（ x1,x2,…,xn） T
最优解：使目标函数值达到最优的可行解。
基矩阵约束方程系数矩阵 A的 m× m子矩阵 B,若 B
的行列式 ≠0,则称 B为 A的一个基（矩阵）。
=
=
目标函数约束条件行列式 ≠0
基矩阵右边常数
28
基变量、基向量基 B对应的 m个变量为基变量，其他 n-
m个变量为非基变量。假定
1
1 1 1 2 1 m
22 1 2 2 2 m
12
12
a
a a a
,
( 1,2,)
,,
j
j
j
m m m m mj
jj
m
aaa
a
Bp
a a a a
p x j m
B p p p
设为基变量 的系数向量——基向量。
则
29
mnmmmmmmmm
nmmm
nmmm
aaaaaa
aaaaaa
aaaaaa
A
2121
2221222221
1211111211
mmmm
m
m
aaa
aaa
aaa
B
21
22221
11211
mnmmmm
nmm
nmm
aaa
aaa
aaa
N
21
22212
12111基阵 非基阵
TmB xxxX?21TnmN xxxX?21
基向量非基向量基变量 非基变量
30
基解、基可行解基解,令所有非基变量为 0，根据约束方程求得的解（不包括非负约束）为对应基的基解。表示为
X=（ x1,x2,…,xm,0,…,0） T
基可行解,满足非负约束的基解。
基的个数最多为,故基解的个数最多为 。 mnc
m
nc
31
总结几个概念
基矩阵、非基矩阵
基变量、非基变量
基向量、非基向量
基解、可行解、基可行解、最优解
32
几种解的关系可行域的性质
● 线性规划的可行域是凸集
● 线性规划的最优解在极点上凸集 凸集 不是凸集极点
m a x z= 2x 1 + 3 x 2 +x 3
s,t,x 1 + 3 x 2 +x 3? 15
2x 1 + 3 x 2 - x 3? 18
x 1 - x 2 +x 3? 3
x 1,x 2,x 3? 0
1 2 3
1 2 3 4
1 2 3 5
1 2 3 6
m a x 2 3
3 15
2 3 18
..
3
0,1,2,,6.
j
z x x x
x x x x
x x x x
st
x x x x
xj
基解例 1
x 1 + 3 x 2 +x 3 = 1 5
2x 1 + 3 x 2 -x 3 = 1 8
x 1 -x 2 +x 3 =3
x 1 + 3x 2 +x 3 +x 4 = 15
2x 1 + 3x 2 - x 3 +x 5 = 18
x 1 - x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 5,3,1,0,0,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=20
x 1 + 3 x 2 +x 4 = 1 5
2x 1 + 3 x 2 = 1 8
x 1 -x 2 =3
基变量 x1,x2,x4,非基变量 x3,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 27/5,12/5,0,2/5,0,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
x 1 + 3 x 2 = 1 5
2x 1 + 3 x 2 +x 5 = 1 8
x 1 -x 2 =3
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x5,非基变量 x3,x4,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 6,3,0,0,-3,0） T
是基解，但不是可行解，不是一个极点。
x 1 + 3 x 2 = 1 5
2x 1 + 3 x 2 = 1 8
x 1 -x 2 +x 6 =3
基变量 x1,x2,x6,非基变量 x3,x4,x5
基解为（ x1,x2,x3,x4,x5,x6） T=（ 3,4,0,0,0,4） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 +x 4 = 1 5
3x 2 -x 3 = 1 8
-x 2 +x 3 =3
基变量 x2,x3,x4,非基变量 x1,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 0,21/2,27/2,-30,0,0） T
是基解，但不是可行解。
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 = 1 5
3x 2 -x 3 +x 5 = 1 8
-x 2 +x 3 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为（ x1,x2,x3,x4,x5,x6） T=（ 0,3,6,0,15,0） T
是基可行解，表示可行域的一个极点。
目标函数值为,z=15
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 = 1 5
3x 2 -x 3 = 1 8
-x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基解为
（ x1,x2,x3,x4,x5,x6） T=（ 0,11/2,-3/2,0,0,10） T
是基解但不是可行解。
x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 -x 3 +x 5 = 1 8
x 1 -x 2 +x 3 +x 6 =3
基解例 2
max z=x1+3x2 D
s.t,x1+ x2+x3 =6 B
-x1+2x2 +x4=8 x4=0 C x3=0
x1,x2,x3,x4≥0 x1=0
E O x2=0 A
O A B C D E
基变量 x 3 x 4 x 1 x 4 x 1 x 2 x 2 x 3 x 2 x 4 x 1 x 3
非基变量 x 1 x 2 x 2 x 3 x 3 x 4 x 1 x 4 x 1 x 3 x 2 x 4
x j < 0 -- -- -- -- x 4 x 1
基可行解 是 是 是 是 否 否
43
基解课堂练习
max z=3x1+x2
s.t,3x1+ 5x2+x3 =15
5x1+2x2 +x4=10
x1,x2,x3,x4≥0
试求其所有的基解,并判断哪些基解为基可行解,
44
练习答案
11
22
33
44
55
66
35 2 0 4 5
,,,0,0
52 1 9 1 9
31
,2,0,9,0
50
30
,5,0,0,1 5
51
51
,0,5,1 0,0
20
50
,0,3,0,4
21
10
,0,0,1 5,1 0
01
T
T
T
T
T
T
BX
BX
BX
BX
BX
BX
是是是是
45
解题过程
A= 3 5 1 0 B1= 3 5 ∣ B∣ ≠0为 A的一个基
5 2 0 1 5 2
B1对应的基变量为 x1,x2,令非基变量 x3=x4=0,则求得基变量
x1=20/19,x2=45/19，从而 X1=（ 20/19,45/19,0,0） T为基解，满足非负，也为基可行解。
同理求得 B2= 3 1,X2=(2,0,9,0)T
5 0
B3= 3 0,X3=(5,0,0,-15)T
5 1
B4= 5 1,X4=(0,5,-10,0)T
2 0
B5= 5 0,X5=(0,3,0,4)T
2 1
B6= 1 0,X6=(0,0,15,10)T
0 1
显然 X3,X4是基解，但不是基可行解,X1,X2,X3,X4是基可行解。
maxz=3x1+x2
s.t,3x1+ 5x2+x3 =15
5x1+2x2 +x4=10
x1,x2,x3,x4≥0
46
基解课后练习
在下列线性规划问题中，找出所有基解、
基可行解和最优解。
maxZ=10x1+5x2
s,t 3x1+4x2≤9
5x1+2x2≤8
x1,x2≥0
47
6、线性规划的求解寻找最优解的过程进基变量、离基变量、基变换单纯形法
48
寻找最优解的过程根据问题的标准，从可行域中某个基可行解
（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。
49
以例 1为例
MaxZ=2x1+3x2
x1+2x2 ≤ 8
4x1 ≤ 16
4x2≤ 12
x1,x2≥ 0
50
第一步 化标准型
MaxZ=2x1+3x2+0x3+0x4+0x5
x1+2x2+x3 =8
4x1 +x4 =16
4x2+ +x5=12
x1,x2,x3≥ 0
51
第二步 寻找第一个基，求第一个基可行解
A=(P1,P2,P3,P4,P5)
B=(P3,P4,P5)= 1 0 0
0 1 0
0 0 1
令 x1=x2=0,得第一个基可行解
x(1)=(0,0,8,16,12)T
此时 z=0,由于 z=2x1+3x2有正系数的非基变量 x1和 x2,选择将 x2换入 。
52
第三步 将 x2换入，选择一个基变量换出
x1依然为非基变量，令 x1=0,则
x3=8-2x2≥ 0
x4=16≥ 0
x5=12-4x2≥ 0
因而 x2=min(8/2,-,12/4)=3
当 x2=3时,x5=0,,由此选择 x2替换 x5。
53
经过替换得
x3=2-x1+1/2x5
x4=16-4x1
x2=3-1/4x5
z=9+2x1-3/4x5
令 x1=x5=0,
得 z=9和另一个基可行解 x(2)=(0,3,2,16,0)T
此时有正系数的非基变量 x1,因而选择 x1换入，用相同的方法选择换出的基变量
54
同理可得其他的基可行解
x(3)=(2,3,0,8,0)T
x(4)=(4,2,0,0,4)T
当解为 x(4)时,z=14-1.5x3-0.125x4
此时再无正系数的非基变量，所以
max=14,唯一最优解为 x(4)
=
目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换
=
基变量
=
进基变量离基变量目标函数约束条件右边常数=
=
目标函数约束条件新的基矩阵右边常数=
=
进基变量离基变量目标函数约束条件基矩阵
=
=
目标函数约束条件新的基矩阵右边常数=
60
单纯形法
61
单纯形法的基本思想根据问题的标准，从可行域中某个基可行解
（一个极点）开始，转换到另一个更优的基可行解（另一个极点），直到使目标函数达到最大、得到最优解为止。
线性规划的矩阵表示
=
=
=
=
=
典则形式（典式）
64
11 00
N B BC C B N C C B A
可以证明：
检验数
典则形式（典式）
65
证明
1100N B BC C B N C C B A
1100N B BC C B N C C B A
1
1
1
1
(,),
(,) (,)
( 0,) 0
B
B N B
B N B B
TT
NB
C C B A
C C C B B N
C C C C B N
C C B N
检验数 --所有变量的系数?非基变量的系数注意 1：基变量检验数为
0
注意 2：所有检验数
<=0时得到最优解
66
由上面证明得检验数?
① 令 xN =0,得 xB=B-1b,此即为基解
x*=(xB,xN)T=(B-1b,0)
② 当所有 δ≤0时，
基解 x*=(B-1b,0)为最优基解
③ 当所有 B-1b≥ 0
时，最优基解
x*=(B-1b,0)为最优基可行解，
即为最优的极点，即为最优解。
67
NBA
N
B
X
XX
bAX b
X
XNB
N
B?
bNXBX
NB
NB NXbBX NB NXBbBX 11
N
B
X
XX
N
N
X
NXBbBX 11
令 0?NX
则
0
1bB
X
定义 在约束方程组 (2) 中，对于一个选定的基 B，令所有的非基变量为零得到的解，称为相应于基 B
的 基本解 。
再看一次整个过程
68
基本定理 1
对于一个线性规划问题，若存在基 B,使则对应于基 B的基可行解就是最优解,B为最优基。
1 0Bb
1,0
BNX B b X
1 0BC C B A
可行性 最优性
69
基本定理 2
线性规划问题如果存在最优解，
则一定存在一个基本可行解是最优解。
70
矩阵与单纯形表的对应关系
X b
CB XB A b
-Z
XB XN b
CB XB B N b
-Z
XB XN b
CB XB I B-1N B-1b
-Z CT-CBB-1A -CBTB-1b
模型矩阵形式 单纯形表
72
单纯形表的基本格式（ 1）
C b
X
CB XB B-1A B-1b
-Z C-CBB-1A -CBB-1b
X b
CB XB A b
-Z
73
单纯形表的基本格式（ 2）
11
11
m a x ( )
.,
0,0
B N B
BN
BN
Z C B b C C B A X
X B NX B b
st
XX
典式：
CB CN b
XB XN
CB XB I B-1N B-1b
-Z C-CBB-1A -CBB-1b
单纯形法基本格式：
74
单纯形表的基本格式（ 3）
BX
X sX b
sX
A I b
Z? C 00
(右端项 )（松弛变量）（原始决策变量）
BX
X
sX
b
BX
1BA? 1B? 1Bb?
Z? 1
BC C B A 1BCB 1BC B b?
(右端项 )（松弛变量）（原始决策变量）
①对于迭代过程中的任意可行基 B所形成的单纯形表，初始表中单位子矩阵的位置（即松弛变量对应的系数）必为 B-1
② 留意松弛变量 xs的检验数 -CBB-1，在下一章有用。
75
单纯形表的基本格式（ 3）
BX
X sX b
sX
A I b
Z? C 00
(右端项 )（松弛变量）（原始决策变量）
BX
X
sX
b
BX
1BA? 1B? 1Bb?
Z? 1
BC C B A 1BCB 1BC B b?
(右端项 )（松弛变量）（原始决策变量）
③研究此时的系数矩阵
11
12
1 1 1
12
(,,,)
(,,,)
n
n
B A B P P P
B P B P B P
由此可见，此时 xj 的系数为 B-1Pj 。
76
单纯形法例 1 23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
2
0,1,5,
j
z x x
x x x
x x x
st
x x x
xj
77
初始可行基初始基可行解
1 4 5
1 0 0
0 1 0,,
0 0 1
B p p p
( 0 ) ( 2,0,0,1,2 ) TX?
23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
= 2
0,1,5.
j
z x x
x x x
x x x
st
x x x
xj
78
000-210-Z
2210-110x50
1101-310x40
—2001-21x10
x5x4x3x2x1XBCB
θB-1b
00-210C
23
1 2 3
2 3 4
2 3 5
m a x 2
2 2
3 1
..
2
0,1,5,
j
z x x
x x x
x x x
st
x x x
xj
初始单纯形表
79
-10-1100-Z
1/211-1200x50
—101-310x21
—402-501x10
000-210-Z
2210-110x50
1101-310x40
—2001-21x10
x5x4x3x2x1XBCB θB
-1b
00-210C
表 1
表 2
80
-3/2-1/2-1/2000-Z
1/21/2-1/2100x3-2
5/23/2-1/2010x21
13/25/2-1/2001x10
-10-1100-Z
1/211-1200x50
—101-310x21
—402-501x10
x5x4x3x2x1XBCB θB-1b
00-210C
表 2
表 3
最优解
**13 5 1 3(,,,0,0),.
2 2 2 2
TXZ
81
例 2
m ax z= 2x 1 +3 x 2 +x 3
st x 1 +3 x 2 +x 3? 15
2x 1 +3 x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m i n z’ = - 2x 1 - 3x 2 - x 3
st x 1 + 3 x 2 +x 3 +x 4 = 1 5
2x 1 + 3 x 2 - x 3 +x 5 = 1 8
x 1 - x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 3 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
m in z’= -2 x 1 -3 x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 [3 ] 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 1 0 0 -1 0 0 -15
x 2 0 1/3 1 1/3 1/3 0 0 5 5/1/3
x 5 0 [1] 0 -2 -1 1 0 3 3/1
x 6 0 4/3 0 4/3 1/3 0 1 8 8/4/3
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
x 3 进基,x 6 离基
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 0 0 0 -5 /6 -1 /3 -1 /2 -2 0
x 2 0 0 1 0 1 /4 0 -1 /4 3
x 1 0 1 0 0 -1 /6 1 /3 1 /2 5
x 3 0 0 0 1 5 /1 2 -1 /3 1 /4 1
最优解,( x 1,x 2,x 3,x 4,x 5 x 6 )= (5,3,1,0,0,0),m ax z=2 0
86
单纯形法的求解步骤
1、标准化
2、求出初始基可行解
3、列出单纯形表，并求出检验数的值
4、对检验数进行判断,
（ 1）若所有检验数 <=0,则已求出最优解；
（ 2）若至少有一个检验数为正,则选取绝对值最大的那个，对应的非基变量为入基变量。计算 θ 的值：
① 若对应非基变量 xk 的系数 B-1pk ≤ 0
（ 即 θ <0或 ∞),则不存在最优解；
② 若至少有一个 θ >0,则选择最小的，其对应的变量为出基变量。进行初等变换。转 3
87
人工变量法
1、两阶段法
2、大 M法
88
对于约束条件为 >=或 =的情形
11
11
nn
ij j n i i ij j n i n i i
jj
nn
ij j i ij j j i
jj
a x x b a x x x b
a x b a x x b
89
假定已经标准化的原问题为
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x
0,1,,.
nn
nn
nn
m m m n n m
j
z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
90
对于已经标准化的形式，每个约束等式加上一个人工变量
1 1 1 1 2 2 1 1 1
2 1 1 2 2 2 2 2 2
1 1 2 2
12
0,1,,.
,,,
n n n
n n n
m m m n n n m m
j
n n n m
a x a x a x x b
a x a x a x x b
a x a x a x x b
x j n m
x x x
为 人 工 变 量,
91
两阶段法,将求解过程分成两个阶段第一阶段,构造辅助线性规划问题求解，若求得辅助线性规划问题的目标函数值为 0，则原问题存在可行解，进入第二阶段，否则原问题无解。
第二阶段,以第一阶段求得的最优解为初始可行解，求解原问题。
92
所加入的人工变量只有满足全为 0时才能保证原等式成立。建立新目标。所有人工变量全为 0
时，新目标函数达到最优值 0。
12
12
m a x
m i n
n n n m
n n n m
z x x x
z x x x
或
93
第一阶段 求解辅助线性规划问题
12
12
1 1 1 1 2 2 1 1 1
2 1 1 2 2 2 2 2 2
1 1 2 2
m a x
m in
0,
n n n m
n n n m
n n n
n n n
m m m n n n m m
j
z x x x
z x x x
a x a x a x x b
a x a x a x x b
a x a x a x x b
xj
或
1,,.nm
94
若第一阶段求得的最优解使目标函数值达到最大值 0，
则进入第二阶段。假定求得的最优解为 X=( )。
95
第二阶段、以 X为初始可行解求解原问题
1 1 2 2
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
m a x ( m in )
0,1,,.
nn
nn
nn
m m m n n m
j
z z c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x j n
或
96
两阶段法例 11 2 3 4
1 2 3
1 2 3
1 2 3 4
m a x 2 3
2 3 15
2 5 20
..
2 10
0( 1,4)
j
z x x x x
x x x
x x x
st
x x x x
xj
97
第一阶段，构造辅助线性规划问题
5 6 7
1 2 3
1 2 3
1 2 3 4
m a x
2 3 5 1 5
2 5 6 2 0
..
2 7 1 0
0 ( 1,,7 )
j
W x x x
x x x x
x x x x
st
x x x x x
xj
1 2 3 4
1 2 3
1 2 3
1 2 3 4
m a x 2 3
2 3 15
2 5 20
..
2 10
0( 1,4)
j
z x x x x
x x x
x x x
st
x x x x
xj
原问题辅助规划问题人工变量
98
对辅助规划问题的求解
0
0
0
1
0
0
0
1
x5
-1
-9/5
-1/5
1/5
-3/5
0
0
1
0
x6
-1
-901016/52/5-W
10/361109/53/5x7-1
2040011/52/5x30
15/730007/5-1/5x5-1
-4501954-W
101011121x7-1
42000512x6-1
51500321x5-1
x7x4x3x2x1XBCB θB-1b
-10000C
表
1
表
2
99
-1
-9/7
-1/7
5/7
-16/7
-9/7
-1/7
5/7
x5
-1
-1
7/4
2/7
-3/7
-3/7
7/4
2/7
-3/7
x6
-1
0-10000-W
15/711006/7x40
25/700103/7x30
15/70001-1/7x20
-15/701006/7-W
15/715/711006/7x7-1
—25/700103/7x30
—15/70001-1/7x20
x7x4x3x2x1XBCB θB-1b
-10000C
表
3
表
4
**1 5 2 5 1 5( 0,,,,0,0,0 ),0,
777
TXW
最优解
100
第二阶段，求解原问题
15-1000-Z
5/27/6001x11
5/2-1/2100x33
5/21/6010x22
0006/7-Z
5/215/71006/7x4-1
25/325/70103/7x33
—15/7001-1/7x22
x4x3x2x1XBCB θB-1b
-1321C
* 15 25 15( 0,,,)
777
TX?以 为初始基可行解求解原问题表
1
表
2
**( 5 / 2,5 / 2,5 / 2,0 ),1 5TXz
最优解为
101
两阶段法例 2
1 2 3 1 2 3
1 2 3 1 2 3 4
1 2 3 1 2 3 5
1 2 3 1 2 3
1 2 3 1 2 3 4 5
6 7 8
m a x 2 3 m a x 2 3
3 5 3 48 3 5 3 48
5 8 8 32 5 8 8 32
.,,,
2 4 18 2 4 18
,,0,,,0
m a x
z x x x z x x x
x x x x x x x
x x x x x x x
s t s t
x x x x x x
x x x x x x x x
W x x x
标准化
，
辅助规划问题
1 2 3 4 6
1 2 3 5 7
1 2 3 8
1 2 3 4 5
3 5 3 48
5 8 8 32
,,
2 4 18
,,,0
x x x x x
x x x x x
st
x x x x
x x x x x
，
102
求解辅助规划问题
-7/8
-1/4
1/8
-5/8
1
0
1
0
x5
0
0
0
0
1
0
0
0
1
x6
-1
-15/8
-1/4
1/8
-5/8
0
0
1
0
x7
-1
380-1-140-3/8-Z
1010-60-1/4x8-1
400115/8x20
280-1-80-1/8x6-1
-980-11159-Z
91810-421x8-1
43200885x7-1
48/5480-1-353x6-1
x8x4x3x2x1XBCB θB-1b
-10000C
表 1
表 2
由于辅助线性规划问题最优解为 -38，不为 0，
所以原问题不存在可行解（无解）。
103
大 M法原理,在进行迭代时，只有所有的人工变量均迭代为非基变量（即为 0）时，
才能消除大 M对目标函数的影响，使目标函数达到最优。
例,P64 例 3
12m a x n n n mz x x x
104
添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数 δj
所有 δj<=0
对任一 δj>0
有 aik<=0
令 ak =max{δj}
对所有 aik >0计算
θi=bi/ aik
令 θi =min{θi}
xi为换出变量
aik为主元素基变量中有非零的人工变量某非基变量检验数为零唯一最优解无可行解无界解无穷多最优解迭代运算是 否 否否是是 是单纯形法一般步骤
105
无穷多个最优解若存在一个非基变量的检验数为 0，则最优解不止一个且为无穷多个。
106
无穷多最优解例题
141-1/204x4-1
60-100-Z
31/43/810x2-1
60-100-Z
11/4-1/801x1-3
—201/21-1x2-1
10002-2-Z
661013x4-1
24012-2x3-1
x4x3x2x1XBCB θB-1b
-1-1-1-3C
表 1
表 2
表 3
107
由表 2得最优解由表 3得最优解所以，最优解为
( 1 ) *( 0,2,0,4 ),6TXZ
( 2 ) *( 1,3,0,0 ),6TXZ
* ( 1 ) ( 2 )( 1 )
0 1
X X X
108
x1
x2
(1)X
(2)X
109
无穷多个最优解练习
12
12
12
12
m a x
0
.,1
,0
z x x
xx
s t x x
xx
110
练习答案
12
1 2 3
1 2 4
1 2 3 4
m a x
0
.,1
,,,0
z x x
x x x
s t x x x
x x x x
111
111011x11
1/211120x30
-1-1000-Z
-1-1000-Z
1/21/2-1/201x11
1/21/21/210x21
00011-Z
111011x40
—0011-1x30
X4x3x2x1XBCB θB-1b
0011C
表 1
表 2
表 3
12
1 2 3
1 2 4
1 2 3 4
m a x
0
.,1
,,,0
z x x
x x x
s t x x x
x x x x
112
( 1 ) *( 1,0,1,0 ),1TXZ
( 2 ) *( 1 / 2,1 / 2,0,0 ),1TXZ
* ( 1 ) ( 2 )( 1 )
0 1
X X X
由表 2得最优解由表 3得最优解所以，最优解为
113
无界解例题
23
1 4 5
2 4 5
3 4 5
m a x 2
1 5 13
2 2 2
1 3 5
.,2 2 2
1 1 1
2 2 2
0,1,,5
j
z x x
x x x
x x x
st
x x x
xj
114
23
1 4 5
2 4 5
3 4 5
m a x 2
1 5 13
2 2 2
1 3 5
.,2 2 2
1 1 1
2 2 2
0,1,,5
j
z x x
x x x
x x x
st
x x x
xj
作出其初始单纯形表如下
0 0 0 3/2 -5/2 7/2
1 0 0 -1/2 5/2 13/2
0 1 0 -1/2 3/2 5/2
0 0 1 -1/2 1/2 1/2
x1 x2 x3 x4 x5 RHS(右端向量 )
z
x1
x2
x3
x4进基无离基变量
x4可无限增大，
目标函数值随之无限增大，所以为无界解
115
单纯形法的进一步讨论
—— 退化对于基可行解 XB=B-1b,XN=0,若存在基变量的值为 0，则称该 可行解是退化的,
否则为 非退化的,即 XB=B-1b>0。
若某线性规划问题的所以基可行解都是非退化的，则该问题为非退化的，否则该问题为退化的。
116
退化引起死循环从某个基开始，经过若干次迭代以后又回到原来的基，也就是单纯形法出现了死循环。
出现死循环的原因主要是因为退化的问题中，基变量取值可以为 0，即经过迭代以后，目标函数值可能不会增加。
117
死循环的避免一种有效的方法是 Bland方法
P67
118
单纯形法的进一步讨论
—— 最小化目标函数最小化目标函数问题只须在判断检验数时取相反符号即可。
即迭代终止条件为：
1 0BC C B A
119
最小化目标函数例题
1 2 3 4
1 2 3
1 2 4
m in 3
2 2 4
.,3 6
0( 1,,4)
j
z x x x x
x x x
s t x x x
xj
120
以 MIN求解
-60100-Z
41-1/204x41
201/21-1x21
-1000-22-Z
661013x41
24012-2x31
x4x3x2x1XBCB θB-1b
1113C
表 1
表 2
121
以 MAX求解
60-100-Z’
141-1/204x4-1
—20?1-1x2-1
10002-2-Z’
661013x4-1
24012-2x3-1
X4x3x2X1XBCB θB-1b
-1-1-1-3C
表 1
表 2
122
本章结束！
