Page:1
QSC华东理工大学 工商经济学院 生产与运作管理
Page:2
QSC华东理工大学 工商经济学院 生产与运作管理线性规划经典问题生产计划问题某工厂拥有 A,B,C三种类型的设备,生产甲,乙,丙,
丁四种产品 。 每件产品在生产中需要占用的设备机时数,
每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
每件产品占用的机时数（小时 /件）
产品甲产品乙产品丙产品丁设备能力
（小时）
设备 A 1.5 1.0 2.4 1.0 2000
设备 B 1.0 5.0 1.0 3.5 8000
设备 C 1.5 3.0 3.5 1.0 5000
利润（元 /件） 5.24 7.30 8.34 4.18
Page:3
QSC华东理工大学 工商经济学院 生产与运作管理
max z= 5.24x1 +7.30x2 +8.34x3 +4.18x4
s.t,1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000
1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000
1.0x1 +3.0x2 +3.5x3 +1.0x4 ≤5000
x1,x2,x3,x4 ≥0
Page:4
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示一般形式
m a x ( m i n ) z c x c x c xn n1 1 2 2?
s t a x a x a x b
a x a x a x b
a x a x a x b
n
n n
m m mn n m
.,(,)
(,)
(,)
11 1 12 2 1n 1
21 1 22 2 2 2
1 1 2 2
x x x n1 1 0,,
Page:5
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示 -矩阵形式
nc
c
c
C
2
1
nx
x
x
X
2
1
nb
b
b
b
2
1
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
max (min) z＝ CTX
s.t,AX≤(＝,≥)b
X≥0
Page:6
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示 -标准形式
max z＝ CTX
s.t,AX＝ b
X≥0
Page:7
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的几何特征
max z= x1 +3x2
s.t,x1 +x2 ≤6
-x1+2x2 ≤8
x1,x2 ≥0
1
2
3
4
5
6
x
z = 0
z = 3
z = 6
z = 9
z = 1 2
z = 1 5,3
0 1 3 4 5 6
约束条件（ 1 ） 约束条件（ 2 ）
C
-1-8 -2-3-4-5-6-7
x
2
1
Page:8
QSC华东理工大学 工商经济学院 生产与运作管理
(d)可行域无界 (e)可行域无界 (f)可行域为空集多个最优解 目标函数无界 无可行解
(a)可行域有界 (b)可行域有界 (c)可行域无界唯一最优解 多个最优解 唯一最优解
Page:9
QSC华东理工大学 工商经济学院 生产与运作管理线性规划解的基本概念
max z= x1 +2x2
s.t,x1 +x2 ≤3
x2 ≤1
x1,x2 ≥0
max z= x1 +2x2
s.t,x1 +x2 +x3 =3
x2 +x4 =1
x1,x2,x3,x4 ≥0
Page:10
QSC华东理工大学 工商经济学院 生产与运作管理
O
1
2
3
1 2 3
x
x
2
1
A
BC
D
x
3
=0
x
4
=0
x
2
=0
x
1
=0 可行域
(可行解全体 )
基本可行解
(可行域顶点,极点 )
基本解
Page:11
QSC华东理工大学 工商经济学院 生产与运作管理求解一般线性规划问题策略
寻找初始基本可行解
给出基本可行解为最优解的判别准则
给出从目前基本可行解转移到新基本可行解的方法
Page:12
QSC华东理工大学 工商经济学院 生产与运作管理求解流程确定初始基本可行解最优解？
否转移到新的基本可行解给出最优解是
Page:13
QSC华东理工大学 工商经济学院 生产与运作管理基的定义定义 线性规划的基 (Basis)
对于线性规划的约束条件
AX=b
X≥0
设 B是 A矩阵中的一个非奇异的 m× m子矩阵,则称 B为线性规划的一个基 。
Page:14
QSC华东理工大学 工商经济学院 生产与运作管理设 B是线性规划的一个基,则 A可以表示为
A=[ B,N ]
X X
X
B
N
X也可相应地分成其中 XB为 m× 1向量，称为基变量
XN为 (n-m)× 1向量，称为非基变量约束方程 AX=b 的分块矩阵表示
B N XX b,,B
N
AX=b可表示为或 BXB+NXN=b
Page:15
QSC华东理工大学 工商经济学院 生产与运作管理若 XN取确定的值,则 XB有唯一的值与之对应
XB=B-1b-B-1NXN
特别,取 XN=0,这时有 XB=B-1b
Page:16
QSC华东理工大学 工商经济学院 生产与运作管理定义 线性规划的解称为线性规划与基 B对应的基本解 。
若其中 B-1b?0,则称以上的基本解为一基本可行解,相应的基 B称为可行基 。
X XX B b
0
B
N
1
基本解与基本可行解的定义
Page:17
QSC华东理工大学 工商经济学院 生产与运作管理定理 线性规划的基本可行解就是可行域的极点
Page:18
QSC华东理工大学 工商经济学院 生产与运作管理单纯形原理的矩阵描述设标准的线性规划问题为
min z= CTX
s.t,AX=b
X?0
矩阵 A可以分块记为 A=[B,N]
相应地,向量 X和 C可以记为
X XX C CC
B
N
B
N
,
Page:19
QSC华东理工大学 工商经济学院 生产与运作管理
AX=b可以写成
BXB+NXN=b
即
XB=B-1b-B-1NXN
对于一个确定的基 B,目标函数 z可以写成
z T BT NT B
N
B
T
B N
T
N
C X C C X
X
C X C X,.
目标函数 z用非基变量表出的形式
z BT N NT N
B
T
B
T
N
T
N
C B b B NX C X
C B b C B N C X
( )
( )
1 1
1 1
Page:20
QSC华东理工大学 工商经济学院 生产与运作管理单纯形表的结构
C
B
C
N
X
B
X
N
C
B
X
B
I B -1 N B -1 b
检验数 0 C
N
-C
B
B
-1
N
Page:21
QSC华东理工大学 工商经济学院 生产与运作管理求解方法 — 单纯形方法
max z= 50x1 +40x2
s.t,3x1 +5x2 ≤150
x2 ≤ 20
8x1 +5x2 ≤300
x1,x2 ≥ 0
Page:22
QSC华东理工大学 工商经济学院 生产与运作管理
1 0
3 0
2 0
6 0
5 0
4 0
X
2
1 0 2 0 3 0 4 0 5 0
A B
C
DE
( 1 )
( 2 )
( 3 )
X
1
X
4
= 0
X
5
= 0
X
2
= 0
X
3
= 0
X
1
= 0
Page:23
QSC华东理工大学 工商经济学院 生产与运作管理标准化
max z= 50x1 +40x2
s.t,3x1 +5x2 ＋ x3 =150 (1)
x2 +x4 = 20 (2)
8x1 +5x2 +x5 =300 (3)
x1,x2,x3,x4,x5 ≥ 0
Page:24
QSC华东理工大学 工商经济学院 生产与运作管理信息表 (单纯形表 )
当前基本可行解,(0,0,150,20,300),Z=0
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
0 3 5 1 0 0 150 150 / 3
0 0 1 0 1 0 20 -
0 8 5 0 0 1 300 300 / 8
50 40 0 0 0
x 5
检验数
x 3
x 4
Page:25
QSC华东理工大学 工商经济学院 生产与运作管理当前基本可行解,(75/2,0,75/2,20,0),Z=1875
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
0 0 25 / 8 1 0 - 3/ 8 75 / 2 12
0 0 1 0 1 0 20 20
50 1 5/ 8 0 0 1/ 8 75 / 2 60
0 35 / 4 0 0 - 25 / 4
x 3
x 4
x 1
检验数
Page:26
QSC华东理工大学 工商经济学院 生产与运作管理
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
40 0 1 8/ 25 0 - 3/ 25 12
0 0 0 - 8/ 25 1 3/ 25 8
50 1 0 - 5/ 25 0 5/ 25 30
0 0 - 14 / 5 0 - 26 / 5
x 1
检验数
x 2
x 4
当前基本可行解,(30,12,0,8,0),Z=1980
Page:27
QSC华东理工大学 工商经济学院 生产与运作管理一般问题的初始基本可行解
max z= 4x1 +2x2 -3x3 +5x4
s.t,2x1 -x2 + x3 +2x4 ≥50 (1)
3x1 -x3 +2x4?80 (2)
x1 +x2 +x4 = 60 (3)
x1,x2,x3,x4 ≥ 0
Page:28
QSC华东理工大学 工商经济学院 生产与运作管理标准化
max z= 4x1 +2x2 -3x3 +5x4
s.t,2x1 -x2 + x3 +2x4 － x5 =50 (1)
3x1 -x3 +2x4 +x6 = 80 (2)
x1 +x2 +x4 = 60 (3)
x1,x2,x3,x4,x5,x6 ≥ 0
Page:29
QSC华东理工大学 工商经济学院 生产与运作管理添加人工变量
max z= 4x1 +2x2 -3x3 +5x4 -Mx7 -Mx8
s.t,2x1 -x2 + x3 +2x4 － x5 +x7 =50 (1)
3x1 -x3 +2x4 +x6 = 80 (2)
x1 +x2 +x4 ＋ x8 = 60 (3)
x1,x2,x3,x4,x5,x6,x7,x8 ≥ 0
Page:30
QSC华东理工大学 工商经济学院 生产与运作管理几种特殊情况 -无可行解
max z= x1 -x2
s.t,0.5x1 +x2 ≥4 (1)
x1 +x2 ≤3 (2)
x1,x2 ≥0
Page:31
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M
x
1
x
2
x
3
x
4
x
5
RH
S
比值
-M 1/2 1 -1 0 1 4
4/ 1
0 1 1 0 1 0 3
3/ 1
M / 2+ 1 M -1 -M 0 0
x
5
x
4
检验数当前基本可行解,(0,0,0,3,4),Z=-4M
Page:32
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M
x 1 x 2 x 3 x 4 x 5 R HS
-M - 1/2 0 -1 -1 1 1
-1 1 1 0 1 0 3
-M / 2 +1 0 -M -M 0
x 5
x 2
检验数当前基本可行解,(0,3,0,0,1),Z=-M-3
Page:33
QSC华东理工大学 工商经济学院 生产与运作管理无可行解的判别准则最优解时，人工变量仍为基变量
Page:34
QSC华东理工大学 工商经济学院 生产与运作管理可行域无界
max z= x1 -x2
s.t,0.5x1 +x2 ≥4 (1)
x1 +x2 ≥3 (2)
x1,x2 ≥0
Page:35
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
-M 1/2 1 -1 0 1 0 4
4/ 1
-M 1 1 0 -1 0 1 3
3/ 1
3M / 2+ 1 2M -1 -M -M 0
检验数
x 5
x 6
当前基本可行解,(0,0,0,0,4,3),Z=-7M
Page:36
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
-M - 1/2 0 -1 1 1 -1 1 1/ 1
-1 1 1 0 -1 0 1 3 -
-M / 2 +2 0 -M M -1 0 -
2M + 1
x 2
检验数
x 5
当前基本可行解,(0,3,0,0,1),Z=-M-3
Page:37
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
0 - 1/2 0 -1 1 1 -1 1
-
-1 1/2 1 -1 0 1 0 4
8
3/ 2 0 1 0 -
M + 1
-M
x 4
x 2
检验数当前基本可行解,(0,4,0,1,0),Z= -4
Page:38
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
0 0 1 -2 1 2 -1 5
1 1 2 -2 0 2 0 8
0 -3 2 0 -M -2 -M
x 4
x 1
检验数当前基本可行解,(8,0,0,5,0),Z= 8
Page:39
QSC华东理工大学 工商经济学院 生产与运作管理可行域无界的判别准则存在非基变量，检验数 >0，
技术系数均?0
Page:40
QSC华东理工大学 工商经济学院 生产与运作管理无穷多最优解
max z= 8x1 +5x2
s.t,3x1 +5x2 ≤150 (1)
x2 ≤ 20 (2)
8x1 +5x2 ≤300 (3)
x1,x2 ≥ 0
Page:41
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x
1
x
2
x
3
x
4
x
5
R HS
比值
0 3 5 1 0 0 150
150/ 3
0 0 1 0 1 0 20
-
0 8 5 0 0 1 300
300/ 8
8 5 0 0 0
x
5
检验数
x
3
x
4
当前基本可行解,(0,0,150,20,300),Z=0
Page:42
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x 1 x 2 x 3 x 4 x 5 R HS
比值
0 0 25/8 1 0 - 3/8 75/2
0 0 1 0 1 0 20
8 1 5/8 0 0 1/8 75/2
0 0 0 0 -1
x 3
x 4
x 1
检验数当前基本可行解,(75/2,0,75/2,20,0),Z=300
Page:43
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x 1 x 2 x 3 x 4 x 5 R HS
比值
5 0 1 8/25 0 - 3/25 12
0 0 0 - 8/25 1 3/25 8
8 1 0 - 5/25 0 5/25 30
0 0 0 0 -1
x 1
检验数
x 2
x 4
当前基本可行解,(30,12,0,8,0),Z=300
Page:44
QSC华东理工大学 工商经济学院 生产与运作管理无穷多解的判别准则存在非基变量，检验数 =0
Page:45
QSC华东理工大学 工商经济学院 生产与运作管理对偶线性规划
Page:46
QSC华东理工大学 工商经济学院 生产与运作管理产品 1 产品 2
资源限量
（ 吨 ）
资源 1 1,0 3,0 200
资源 2 2,0 2,0 350
资源 3 4,0 1,0 220
资源 4 3,0 2,0 400
利润
（万元 / 件）
3,0 5,0
如何合理使用资源，使总利润最大？
有限资源下的利润最大化问题
Page:47
QSC华东理工大学 工商经济学院 生产与运作管理
max z = 3x
1
+5 x
2
s.t,x
1
+3 x
2 ≤ 200
2x
1
+2 x
2 ≤ 350
4x
1
+x
2 ≤ 220
3x
1
+2 x
2 ≤ 400
x
1
,x
2 ≥ 0
线性规划模型
Page:48
QSC华东理工大学 工商经济学院 生产与运作管理最优生产计划为：
x1= 41.82 (件 )，
x2= 52.73 (件 )
最大利润 z=389.09（ 万元 ）
资源的剩余量：
资源 1,200-(x1+3x2)= 0 （ 吨 ）
资源 2,350-(2x1+2x2)= 160.9 （ 吨 ）
资源 3,220-(4x1+2x2)= 0 （ 吨 ）
资源 4,400-(3x1+2x2)= 169.09 （ 吨 ）
最优解
Page:49
QSC华东理工大学 工商经济学院 生产与运作管理问题：
每种资源的价值如何？
应如何定价？
与市场采购价关系如何？
影子价格的引入
Page:50
QSC华东理工大学 工商经济学院 生产与运作管理影子价格满足的条件：
m i n y = 200w 1 + 3 5 0 w 2 + 2 2 0 w 3 + 4 0 0 w 4
s,t,
w 1 + 2 w 2 + 4 w 3 + 3 w 4 ≥ 3
3w 1 + 2 w 2 +w 3 + 2 w 4 ≥ 5
w 1,w 2,w 3,w 4 ≥ 0
最优解 (四种资源的影子价格：万元 /吨 ),
w1=1.55,w2= 0,w3= 0.36,w4= 0
目标函数值 y=389.09（ 万元 ）
Page:51
QSC华东理工大学 工商经济学院 生产与运作管理产品 2 产品 3
资源限量
（吨）
资源剩余
（吨）
影子价格
（万元 / 吨）
资源 1 1,0 3,0 200 0? 1,5 5
资源 2 2,0 2,0 350 1 6 0,9 0? 0
资源 3 4,0 1,0 220 0? 0,3 6
资源 4 3,0 2,0 400 1 6 9,0 9? 0
利润率
( 万元 / 件 )
3,0 5,0
机会成本
( 万元 / 件 )
3,0 5,0
机会成本－利润率
( 万元 / 件 )
0
0
产品产量
( 件 )
4 1,8 5 2,7
影子价格的经济意义
Page:52
QSC华东理工大学 工商经济学院 生产与运作管理利润最大化问题影子价格的经济解释每一种资源的影子价格
=
当该资源增加一个单位时，
总利润 Z的增加量
Page:53
QSC华东理工大学 工商经济学院 生产与运作管理成本最小化问题影子价格的经济解释每一种需求的影子价格
=
当该需求增加一个单位时，
总成本 Z的增加量
Page:54
QSC华东理工大学 工商经济学院 生产与运作管理对偶的定义定义 设以下线性规划问题
Max z=CTX
s.t,AX ≤ b (P)
X≥0
为原始问题,则称以下问题
Min z=bTW
s.t,ATW ≥ C (D)
W≥0
为原始问题的对偶问题。
Page:55
QSC华东理工大学 工商经济学院 生产与运作管理例
max Z= 4x1 +7x2
s.t,3x1 +5x2 ≤6
x1 +2x2 ≤8
x1,x2 ≥0
(P)
min W= 6w1 +8w2
s.t,3w1 +w2 ≥4
5w1 +2w2 ≥7
w1,w2 ≥0
(D)
Page:56
QSC华东理工大学 工商经济学院 生产与运作管理对偶的对偶设原始问题 (P)为：
max z=CTX
s.t,AX ≤ b
X≥0
(P)的对偶 (D)为,
min w=bTY
s.t,ATY ≥ C
W≥0
(D)的等价问题为,
max w’=-bTY
s.t,-ATY≤ -C
Y≥0
(D) 的对偶 为,
minz’=-CTX
s.t,-AX ≥- b
X≥0
Page:57
QSC华东理工大学 工商经济学院 生产与运作管理定理 对偶问题的对偶就是原始问题
Page:58
QSC华东理工大学 工商经济学院 生产与运作管理一般问题的对偶 -处理方法
m i n z= 8x1 +5 x2 m ax z ' = - 8x 1 - 5x 2
s,t,-x
1
+2 x
2
≤ 4 s,t,-x
1
+2 x
2
≤ 4
3x
1
-x
2
=7 3x
1
-x
2
≤ 7
2x
1
+4 x
2
≥ 8 - 3x
1
+x
2
≤ -7
x
1
≥ 0,x
2
≤ 0 - 2x
1
- 4x
2
≤ - 8
x
1
≥ 0,x
2
≤ 0
Page:59
QSC华东理工大学 工商经济学院 生产与运作管理极小化问题
（ m i n ）
极大化问题
（ m ax ）
变
x
j
≥ 0? ——?
a
ij
w
j
≤ b
i 约量
x
j
,u n r? ——?
a
ij
w
j
=b
i 束
x
j
≤ 0? ——?
a
ij
w
j
≥ b
i
约? a ij
x
j
≥ b
i
——? w
j
≥ 0
变束? a ij
x
j
=b
i
——? w
j
,u n r
量
a
ij
x
j
≤ b
i
——? w
j
≤ 0
Page:60
QSC华东理工大学 工商经济学院 生产与运作管理例
max z= 8x1 +5x2
s.t,-x1 +2x2 ≤4
3x1 -x2 =7
2x1 +4x2 ≥8
x1≥0,x2≤0
min w= 4y1 +7y2 +8y3
s.t,-y1 +3y2 +2y3 ≥8
2y1 -y2 +4y3 ≤5
y1≥0,y2:unr y3≤0
Page:61
QSC华东理工大学 工商经济学院 生产与运作管理与对偶有关的定理
Page:62
QSC华东理工大学 工商经济学院 生产与运作管理弱对偶定理若 X,Y分别是原问题
LP与其对偶问题 DP的可行解，且
z=CTX,w=bTY,
则
w≥z
bAX?
TTT bAX?
YbYAX TTT?
YbCX TT?
wy?
Page:63
QSC华东理工大学 工商经济学院 生产与运作管理强对偶定理若 X,Y分别是原问题 LP
与其对偶问题 DP的可行解，且
CTX=bTY,
则 X,Y分别是原问题 LP
与其对偶问题 DP的最优解。
Page:64
QSC华东理工大学 工商经济学院 生产与运作管理最优解定理若原问题 LP有最优解 X*，
则其对偶问题 DP也有最优解 Y*，且
z*=CTX * =bTY *=w*
Page:65
QSC华东理工大学 工商经济学院 生产与运作管理对偶解定理若用单纯形法解原问题 LP，
得有最优解 X*，相应的最优基为 B，则
Y*=CBB-1
为其对偶问题 DP的最优解
Page:66
QSC华东理工大学 工商经济学院 生产与运作管理互补松弛定理量。
的松弛变量与剩余变与分别是和其中件是：
是最优解的充分必要条与的可行解与
DP
LPYX
XY
XY
YXDPLP
SS
S
S
0
0
Page:67
QSC华东理工大学 工商经济学院 生产与运作管理互补松弛定理的应用
min z= 6x1 +8x2 +3x3
s.t,x1 +x2 ≥1
x1 +2x2 +x3 ≥-1
x1,x2,x3 ≥0
求解以下线性规划问题 LP,
Page:68
QSC华东理工大学 工商经济学院 生产与运作管理
max w= y1 -y2
s.t,y1 +y2 ≤6
y1 +2y2 ≤8
y2 ≤3
y1,y2 ≥0
写出对偶问题 DP：
利用图解法,可以求得 DP的最优解为
(y1,y2)T=(6,0)T
Page:69
QSC华东理工大学 工商经济学院 生产与运作管理得到对偶问题各松弛变量的值
y3=0,y4=2,y5=3
即对偶问题的最优解和最优目标函数值为
YT=(y1,y2,y3,y4,y5)T=(6,0,0,2,3)T
w=6
根据互补松弛定理,以下的互补松弛关系成立由 y1>0 得到 x4=0
由 y4>0 得到 x2=0
由 y5>0 得到 x3=0
Page:70
QSC华东理工大学 工商经济学院 生产与运作管理因此原始问题的约束条件
x1 +x2 -x4 =1
x1 +2x2 +x3 -x5 =-1
成为
x1 =1
x1 -x5 =-1
由此得到
x1=1,x5=2
即原始问题的最优解为
X=(x1,x2,x3,x4,x5)T=(1,0,0,0,2)T
z=6
Page:71
QSC华东理工大学 工商经济学院 生产与运作管理对偶单纯形法
C
B
C
N
X
B
X
N
C
B
X
B
I B -1 N B -1 b
检验数 C
B
-C
B
B
-1
B C
N
-C
B
B
-1
N
ABCC B 1
0?
0?
LP可行解
DP可行解
Page:72
QSC华东理工大学 工商经济学院 生产与运作管理当 LP与 DP均为可行时，
LP与 DP均得到最优解单纯形方法：
保持 LP可行的同时，
逐步将 DP变可行对偶单纯形方法：
保持 DP可行的同时，
逐步将 LP变可行
Page:73
QSC华东理工大学 工商经济学院 生产与运作管理
max z= -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
Page:74
QSC华东理工大学 工商经济学院 生产与运作管理
max z= -2x1 -3x2 -4x3
-x1 -2x2 -x3 +x4 =-3
-2x1 +x2 -3x3 +x5 =-4
x1,x2,x3,x4,x5 ≥0
Page:75
QSC华东理工大学 工商经济学院 生产与运作管理
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 -1 -2 -1 1 0 -3
0 x 5 -2 1 -3 0 1 -4
-2 -3 -4 0 0-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 0 - 5 / 2 1 / 2 1 - 1 / 2 -1
-2 x 1 1 - 1 / 2 3 / 2 0 - 1 / 2 2
0 -4 -1 0 -1
m i n |z cy y z cyj j
rj
rj
k k
rk
0
m i n |z cy y z cyj j
rj
rj
k k
rk
0
Page:76
QSC华东理工大学 工商经济学院 生产与运作管理
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 0 - 5 / 2 1 / 2 1 - 1 / 2 -1
-2 x 1 1 - 1 / 2 3 / 2 0 - 1 / 2 2
0 -4 -1 0 -1
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
-3 x 2 0 1 - 1 / 5 - 2 / 5 1 / 5 2 / 5
-2 x 1 1 0 7 / 5 - 1 / 5 - 2 / 5 1 1 / 5
0 0 - 9 / 5 - 8 / 5 - 1 / 5
Page:77
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析
Page:78
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析目的灵敏度分析所要解决的问题：
系数在什么范围内变化,不会影响已获得的最优基 。
如果系数的变化超过以上范围,如何在原来最优解的基础上求得新的最优解
当线性规划问题增加一个新的变量或新的约束,如何在原来最优解的基础上获得新的最优解 。
Page:79
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析内容
※ 目标函数系数 cj的改变
※ 常数项 bi的改变
※ 技术系数 aij的改变
Page:80
QSC华东理工大学 工商经济学院 生产与运作管理目标函数系数 cj的改变
C B C N
X B X N
C B X B I B -1 N B -1 b
检验数 0 C
N -C B B
-1
N
非基变量在目标函数中系数的灵敏度分析基变量在目标函数中系数的灵敏度分析
Page:81
QSC华东理工大学 工商经济学院 生产与运作管理非基变量在目标函数中系数的灵敏度分析
-例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 c2进行灵敏度分析 。
Page:82
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
得到以上问题的最优单纯形表：
Page:83
QSC华东理工大学 工商经济学院 生产与运作管理当 c2’=c2+?时，相应的单纯形表为：
-1 - 1+δ 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0
0 -1 0
-2
Page:84
QSC华东理工大学 工商经济学院 生产与运作管理
0
12
47
要使原来的解仍保持最优解，就要 zj-cj≤ 0（ j=1,2,3,4,5），即
12
47
由此得到，,即当 c2?35/12时，最优解保持不变
12
47
Page:85
QSC华东理工大学 工商经济学院 生产与运作管理基变量在目标函数中系数的灵敏度分析
-例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 c1进行灵敏度分析 。
Page:86
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
4 7 / 1 2
0 -1 0 -2
得到以上问题的最优单纯形表：
Page:87
QSC华东理工大学 工商经济学院 生产与运作管理
- 1+δ -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
- 1+δ x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0
-47/12-1/4? 0 -1+1/3? 0 - 2- 2/ 3?
当 c1’=c1+?时，相应的单纯形表为：
Page:88
QSC华东理工大学 工商经济学院 生产与运作管理
03/22
03/11
01 / 3 -4-
要使原来的基仍保持最优基，就要 zj-cj≤ 0（ j=1,2,3,4,5），即
3
3
12
δ
δ
δ
由此得到,-33，即当 -2?c1?4时，最优基保持不变
Page:89
QSC华东理工大学 工商经济学院 生产与运作管理右边常数的灵敏度分析
C B C N
X B X N
C B X B I B -1 N B -1 b
检验数 0 C
N -C B B
-1
N
右边常数的灵敏度分析
Page:90
QSC华东理工大学 工商经济学院 生产与运作管理例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 b1进行灵敏度分析 。
Page:91
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
0 x
4
1 1 2 1 0 0 9
0 x
5
1 1 -1 0 1 0 2
0 x
6
-1 1 1 0 0 1 4
-1 -1 4 0 0 0
最优单纯形表
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
初始单纯形表
Page:92
QSC华东理工大学 工商经济学院 生产与运作管理对于上述最优解，最优基为：
B
1
1 3 0 2 3
0 1 1
1 3 0 1 3
/ /
/ /
b B b
1
1 3 0 2 3
0 1 1
1 3 0 1 3
9
2
4
1 3
6
13 3
/ /
/ /
/
/
101
111
201
B
Page:93
QSC华东理工大学 工商经济学院 生产与运作管理当 b1’=b1+?=9+?时，最后一张单纯形表中的右边常数将成为
3/3/13
6
3/3/1
4
2
9
3/103/1
110
3/203/1
1
bBb
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3+δ / 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3+δ / 3
0 -
47/ 12
0 -1 0 -2
最后一张单纯形表中的右边常数将成为：
Page:94
QSC华东理工大学 工商经济学院 生产与运作管理原始可行条件 为：
1 3 1 3 0
13 3 1 3 0
/ /
/ /
1
13
-1,b1’=b1+8时，原来的最优基仍为原始可行基
Page:95
QSC华东理工大学 工商经济学院 生产与运作管理增加一个新的变量 -例增加一个新的变量 x7，它在目标函数中的系数 c7=1，在约束条件中的系数向量为,
1
1
1
7a
求新的最优基和最优解。
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
Page:96
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
0 x
4
1 1 2 1 0 0 9
0 x
5
1 1 -1 0 1 0 2
0 x
6
-1 1 1 0 0 1 4
-1 -1 4 0 0 0
最优单纯形表
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
初始单纯形表
Page:97
QSC华东理工大学 工商经济学院 生产与运作管理对于上述最优解，最优基为：
B
1
1 3 0 2 3
0 1 1
1 3 0 1 3
/ /
/ /?
101
111
201
B
单纯形表中 x7对应的系数：
0
2
3/1
1
1
1
3/103/1
110
3/203/1
7
1
aB
Page:98
QSC华东理工大学 工商经济学院 生产与运作管理加入 x7后的单纯形表为：
-1 -1 4 0 0 0 1
x 1 x 2 x 3 x 4 x 5 x 6 x 7 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 - 1/ 3 1/ 3
0 x
5
0 2 0 0 1 1 2 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 -
47/ 12
0 -1 0 -2 2/ 3
……
Page:99
QSC华东理工大学 工商经济学院 生产与运作管理增加一个新的约束 -例增加一个新的约束,-x1+2x2≥ 2，求新的最优基和最优解。
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
-x1+2x2≥ 2 -x1+2x2-x7=2 x1-2x2+x7=-2
Page:100
QSC华东理工大学 工商经济学院 生产与运作管理在原最优单纯形表中加入新方程信息：
-1 -1 4 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 0 1/ 3
0 x
5
0 2 0 0 1 1 0 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 x
7
1 -2 0 0 0 0 1 -2
Page:101
QSC华东理工大学 工商经济学院 生产与运作管理变成单纯形表：
-1 -1 4 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 0 1/ 3
0 x
5
0 2 0 0 1 1 0 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 x
7
0 - 7/ 4 0 - 1/ 3 0 2/ 3 1 - 7/ 3
0 - 47 / 12 0 -1 0 -2 0
……
QSC华东理工大学 工商经济学院 生产与运作管理
Page:2
QSC华东理工大学 工商经济学院 生产与运作管理线性规划经典问题生产计划问题某工厂拥有 A,B,C三种类型的设备,生产甲,乙,丙,
丁四种产品 。 每件产品在生产中需要占用的设备机时数,
每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
每件产品占用的机时数（小时 /件）
产品甲产品乙产品丙产品丁设备能力
（小时）
设备 A 1.5 1.0 2.4 1.0 2000
设备 B 1.0 5.0 1.0 3.5 8000
设备 C 1.5 3.0 3.5 1.0 5000
利润（元 /件） 5.24 7.30 8.34 4.18
Page:3
QSC华东理工大学 工商经济学院 生产与运作管理
max z= 5.24x1 +7.30x2 +8.34x3 +4.18x4
s.t,1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000
1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000
1.0x1 +3.0x2 +3.5x3 +1.0x4 ≤5000
x1,x2,x3,x4 ≥0
Page:4
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示一般形式
m a x ( m i n ) z c x c x c xn n1 1 2 2?
s t a x a x a x b
a x a x a x b
a x a x a x b
n
n n
m m mn n m
.,(,)
(,)
(,)
11 1 12 2 1n 1
21 1 22 2 2 2
1 1 2 2
x x x n1 1 0,,
Page:5
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示 -矩阵形式
nc
c
c
C
2
1
nx
x
x
X
2
1
nb
b
b
b
2
1
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
max (min) z＝ CTX
s.t,AX≤(＝,≥)b
X≥0
Page:6
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的表示 -标准形式
max z＝ CTX
s.t,AX＝ b
X≥0
Page:7
QSC华东理工大学 工商经济学院 生产与运作管理线性规划问题的几何特征
max z= x1 +3x2
s.t,x1 +x2 ≤6
-x1+2x2 ≤8
x1,x2 ≥0
1
2
3
4
5
6
x
z = 0
z = 3
z = 6
z = 9
z = 1 2
z = 1 5,3
0 1 3 4 5 6
约束条件（ 1 ） 约束条件（ 2 ）
C
-1-8 -2-3-4-5-6-7
x
2
1
Page:8
QSC华东理工大学 工商经济学院 生产与运作管理
(d)可行域无界 (e)可行域无界 (f)可行域为空集多个最优解 目标函数无界 无可行解
(a)可行域有界 (b)可行域有界 (c)可行域无界唯一最优解 多个最优解 唯一最优解
Page:9
QSC华东理工大学 工商经济学院 生产与运作管理线性规划解的基本概念
max z= x1 +2x2
s.t,x1 +x2 ≤3
x2 ≤1
x1,x2 ≥0
max z= x1 +2x2
s.t,x1 +x2 +x3 =3
x2 +x4 =1
x1,x2,x3,x4 ≥0
Page:10
QSC华东理工大学 工商经济学院 生产与运作管理
O
1
2
3
1 2 3
x
x
2
1
A
BC
D
x
3
=0
x
4
=0
x
2
=0
x
1
=0 可行域
(可行解全体 )
基本可行解
(可行域顶点,极点 )
基本解
Page:11
QSC华东理工大学 工商经济学院 生产与运作管理求解一般线性规划问题策略
寻找初始基本可行解
给出基本可行解为最优解的判别准则
给出从目前基本可行解转移到新基本可行解的方法
Page:12
QSC华东理工大学 工商经济学院 生产与运作管理求解流程确定初始基本可行解最优解？
否转移到新的基本可行解给出最优解是
Page:13
QSC华东理工大学 工商经济学院 生产与运作管理基的定义定义 线性规划的基 (Basis)
对于线性规划的约束条件
AX=b
X≥0
设 B是 A矩阵中的一个非奇异的 m× m子矩阵,则称 B为线性规划的一个基 。
Page:14
QSC华东理工大学 工商经济学院 生产与运作管理设 B是线性规划的一个基,则 A可以表示为
A=[ B,N ]
X X
X
B
N
X也可相应地分成其中 XB为 m× 1向量，称为基变量
XN为 (n-m)× 1向量，称为非基变量约束方程 AX=b 的分块矩阵表示
B N XX b,,B
N
AX=b可表示为或 BXB+NXN=b
Page:15
QSC华东理工大学 工商经济学院 生产与运作管理若 XN取确定的值,则 XB有唯一的值与之对应
XB=B-1b-B-1NXN
特别,取 XN=0,这时有 XB=B-1b
Page:16
QSC华东理工大学 工商经济学院 生产与运作管理定义 线性规划的解称为线性规划与基 B对应的基本解 。
若其中 B-1b?0,则称以上的基本解为一基本可行解,相应的基 B称为可行基 。
X XX B b
0
B
N
1
基本解与基本可行解的定义
Page:17
QSC华东理工大学 工商经济学院 生产与运作管理定理 线性规划的基本可行解就是可行域的极点
Page:18
QSC华东理工大学 工商经济学院 生产与运作管理单纯形原理的矩阵描述设标准的线性规划问题为
min z= CTX
s.t,AX=b
X?0
矩阵 A可以分块记为 A=[B,N]
相应地,向量 X和 C可以记为
X XX C CC
B
N
B
N
,
Page:19
QSC华东理工大学 工商经济学院 生产与运作管理
AX=b可以写成
BXB+NXN=b
即
XB=B-1b-B-1NXN
对于一个确定的基 B,目标函数 z可以写成
z T BT NT B
N
B
T
B N
T
N
C X C C X
X
C X C X,.
目标函数 z用非基变量表出的形式
z BT N NT N
B
T
B
T
N
T
N
C B b B NX C X
C B b C B N C X
( )
( )
1 1
1 1
Page:20
QSC华东理工大学 工商经济学院 生产与运作管理单纯形表的结构
C
B
C
N
X
B
X
N
C
B
X
B
I B -1 N B -1 b
检验数 0 C
N
-C
B
B
-1
N
Page:21
QSC华东理工大学 工商经济学院 生产与运作管理求解方法 — 单纯形方法
max z= 50x1 +40x2
s.t,3x1 +5x2 ≤150
x2 ≤ 20
8x1 +5x2 ≤300
x1,x2 ≥ 0
Page:22
QSC华东理工大学 工商经济学院 生产与运作管理
1 0
3 0
2 0
6 0
5 0
4 0
X
2
1 0 2 0 3 0 4 0 5 0
A B
C
DE
( 1 )
( 2 )
( 3 )
X
1
X
4
= 0
X
5
= 0
X
2
= 0
X
3
= 0
X
1
= 0
Page:23
QSC华东理工大学 工商经济学院 生产与运作管理标准化
max z= 50x1 +40x2
s.t,3x1 +5x2 ＋ x3 =150 (1)
x2 +x4 = 20 (2)
8x1 +5x2 +x5 =300 (3)
x1,x2,x3,x4,x5 ≥ 0
Page:24
QSC华东理工大学 工商经济学院 生产与运作管理信息表 (单纯形表 )
当前基本可行解,(0,0,150,20,300),Z=0
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
0 3 5 1 0 0 150 150 / 3
0 0 1 0 1 0 20 -
0 8 5 0 0 1 300 300 / 8
50 40 0 0 0
x 5
检验数
x 3
x 4
Page:25
QSC华东理工大学 工商经济学院 生产与运作管理当前基本可行解,(75/2,0,75/2,20,0),Z=1875
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
0 0 25 / 8 1 0 - 3/ 8 75 / 2 12
0 0 1 0 1 0 20 20
50 1 5/ 8 0 0 1/ 8 75 / 2 60
0 35 / 4 0 0 - 25 / 4
x 3
x 4
x 1
检验数
Page:26
QSC华东理工大学 工商经济学院 生产与运作管理
50 40 0 0 0
x 1 x 2 x 3 x 4 x 5 R H S 比值
40 0 1 8/ 25 0 - 3/ 25 12
0 0 0 - 8/ 25 1 3/ 25 8
50 1 0 - 5/ 25 0 5/ 25 30
0 0 - 14 / 5 0 - 26 / 5
x 1
检验数
x 2
x 4
当前基本可行解,(30,12,0,8,0),Z=1980
Page:27
QSC华东理工大学 工商经济学院 生产与运作管理一般问题的初始基本可行解
max z= 4x1 +2x2 -3x3 +5x4
s.t,2x1 -x2 + x3 +2x4 ≥50 (1)
3x1 -x3 +2x4?80 (2)
x1 +x2 +x4 = 60 (3)
x1,x2,x3,x4 ≥ 0
Page:28
QSC华东理工大学 工商经济学院 生产与运作管理标准化
max z= 4x1 +2x2 -3x3 +5x4
s.t,2x1 -x2 + x3 +2x4 － x5 =50 (1)
3x1 -x3 +2x4 +x6 = 80 (2)
x1 +x2 +x4 = 60 (3)
x1,x2,x3,x4,x5,x6 ≥ 0
Page:29
QSC华东理工大学 工商经济学院 生产与运作管理添加人工变量
max z= 4x1 +2x2 -3x3 +5x4 -Mx7 -Mx8
s.t,2x1 -x2 + x3 +2x4 － x5 +x7 =50 (1)
3x1 -x3 +2x4 +x6 = 80 (2)
x1 +x2 +x4 ＋ x8 = 60 (3)
x1,x2,x3,x4,x5,x6,x7,x8 ≥ 0
Page:30
QSC华东理工大学 工商经济学院 生产与运作管理几种特殊情况 -无可行解
max z= x1 -x2
s.t,0.5x1 +x2 ≥4 (1)
x1 +x2 ≤3 (2)
x1,x2 ≥0
Page:31
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M
x
1
x
2
x
3
x
4
x
5
RH
S
比值
-M 1/2 1 -1 0 1 4
4/ 1
0 1 1 0 1 0 3
3/ 1
M / 2+ 1 M -1 -M 0 0
x
5
x
4
检验数当前基本可行解,(0,0,0,3,4),Z=-4M
Page:32
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M
x 1 x 2 x 3 x 4 x 5 R HS
-M - 1/2 0 -1 -1 1 1
-1 1 1 0 1 0 3
-M / 2 +1 0 -M -M 0
x 5
x 2
检验数当前基本可行解,(0,3,0,0,1),Z=-M-3
Page:33
QSC华东理工大学 工商经济学院 生产与运作管理无可行解的判别准则最优解时，人工变量仍为基变量
Page:34
QSC华东理工大学 工商经济学院 生产与运作管理可行域无界
max z= x1 -x2
s.t,0.5x1 +x2 ≥4 (1)
x1 +x2 ≥3 (2)
x1,x2 ≥0
Page:35
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
-M 1/2 1 -1 0 1 0 4
4/ 1
-M 1 1 0 -1 0 1 3
3/ 1
3M / 2+ 1 2M -1 -M -M 0
检验数
x 5
x 6
当前基本可行解,(0,0,0,0,4,3),Z=-7M
Page:36
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
-M - 1/2 0 -1 1 1 -1 1 1/ 1
-1 1 1 0 -1 0 1 3 -
-M / 2 +2 0 -M M -1 0 -
2M + 1
x 2
检验数
x 5
当前基本可行解,(0,3,0,0,1),Z=-M-3
Page:37
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
0 - 1/2 0 -1 1 1 -1 1
-
-1 1/2 1 -1 0 1 0 4
8
3/ 2 0 1 0 -
M + 1
-M
x 4
x 2
检验数当前基本可行解,(0,4,0,1,0),Z= -4
Page:38
QSC华东理工大学 工商经济学院 生产与运作管理
1 -1 0 0 -M -M
x 1 x 2 x 3 x 4 x 5 x 6 R HS
比值
0 0 1 -2 1 2 -1 5
1 1 2 -2 0 2 0 8
0 -3 2 0 -M -2 -M
x 4
x 1
检验数当前基本可行解,(8,0,0,5,0),Z= 8
Page:39
QSC华东理工大学 工商经济学院 生产与运作管理可行域无界的判别准则存在非基变量，检验数 >0，
技术系数均?0
Page:40
QSC华东理工大学 工商经济学院 生产与运作管理无穷多最优解
max z= 8x1 +5x2
s.t,3x1 +5x2 ≤150 (1)
x2 ≤ 20 (2)
8x1 +5x2 ≤300 (3)
x1,x2 ≥ 0
Page:41
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x
1
x
2
x
3
x
4
x
5
R HS
比值
0 3 5 1 0 0 150
150/ 3
0 0 1 0 1 0 20
-
0 8 5 0 0 1 300
300/ 8
8 5 0 0 0
x
5
检验数
x
3
x
4
当前基本可行解,(0,0,150,20,300),Z=0
Page:42
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x 1 x 2 x 3 x 4 x 5 R HS
比值
0 0 25/8 1 0 - 3/8 75/2
0 0 1 0 1 0 20
8 1 5/8 0 0 1/8 75/2
0 0 0 0 -1
x 3
x 4
x 1
检验数当前基本可行解,(75/2,0,75/2,20,0),Z=300
Page:43
QSC华东理工大学 工商经济学院 生产与运作管理
8 5 0 0 0
x 1 x 2 x 3 x 4 x 5 R HS
比值
5 0 1 8/25 0 - 3/25 12
0 0 0 - 8/25 1 3/25 8
8 1 0 - 5/25 0 5/25 30
0 0 0 0 -1
x 1
检验数
x 2
x 4
当前基本可行解,(30,12,0,8,0),Z=300
Page:44
QSC华东理工大学 工商经济学院 生产与运作管理无穷多解的判别准则存在非基变量，检验数 =0
Page:45
QSC华东理工大学 工商经济学院 生产与运作管理对偶线性规划
Page:46
QSC华东理工大学 工商经济学院 生产与运作管理产品 1 产品 2
资源限量
（ 吨 ）
资源 1 1,0 3,0 200
资源 2 2,0 2,0 350
资源 3 4,0 1,0 220
资源 4 3,0 2,0 400
利润
（万元 / 件）
3,0 5,0
如何合理使用资源，使总利润最大？
有限资源下的利润最大化问题
Page:47
QSC华东理工大学 工商经济学院 生产与运作管理
max z = 3x
1
+5 x
2
s.t,x
1
+3 x
2 ≤ 200
2x
1
+2 x
2 ≤ 350
4x
1
+x
2 ≤ 220
3x
1
+2 x
2 ≤ 400
x
1
,x
2 ≥ 0
线性规划模型
Page:48
QSC华东理工大学 工商经济学院 生产与运作管理最优生产计划为：
x1= 41.82 (件 )，
x2= 52.73 (件 )
最大利润 z=389.09（ 万元 ）
资源的剩余量：
资源 1,200-(x1+3x2)= 0 （ 吨 ）
资源 2,350-(2x1+2x2)= 160.9 （ 吨 ）
资源 3,220-(4x1+2x2)= 0 （ 吨 ）
资源 4,400-(3x1+2x2)= 169.09 （ 吨 ）
最优解
Page:49
QSC华东理工大学 工商经济学院 生产与运作管理问题：
每种资源的价值如何？
应如何定价？
与市场采购价关系如何？
影子价格的引入
Page:50
QSC华东理工大学 工商经济学院 生产与运作管理影子价格满足的条件：
m i n y = 200w 1 + 3 5 0 w 2 + 2 2 0 w 3 + 4 0 0 w 4
s,t,
w 1 + 2 w 2 + 4 w 3 + 3 w 4 ≥ 3
3w 1 + 2 w 2 +w 3 + 2 w 4 ≥ 5
w 1,w 2,w 3,w 4 ≥ 0
最优解 (四种资源的影子价格：万元 /吨 ),
w1=1.55,w2= 0,w3= 0.36,w4= 0
目标函数值 y=389.09（ 万元 ）
Page:51
QSC华东理工大学 工商经济学院 生产与运作管理产品 2 产品 3
资源限量
（吨）
资源剩余
（吨）
影子价格
（万元 / 吨）
资源 1 1,0 3,0 200 0? 1,5 5
资源 2 2,0 2,0 350 1 6 0,9 0? 0
资源 3 4,0 1,0 220 0? 0,3 6
资源 4 3,0 2,0 400 1 6 9,0 9? 0
利润率
( 万元 / 件 )
3,0 5,0
机会成本
( 万元 / 件 )
3,0 5,0
机会成本－利润率
( 万元 / 件 )
0
0
产品产量
( 件 )
4 1,8 5 2,7
影子价格的经济意义
Page:52
QSC华东理工大学 工商经济学院 生产与运作管理利润最大化问题影子价格的经济解释每一种资源的影子价格
=
当该资源增加一个单位时，
总利润 Z的增加量
Page:53
QSC华东理工大学 工商经济学院 生产与运作管理成本最小化问题影子价格的经济解释每一种需求的影子价格
=
当该需求增加一个单位时，
总成本 Z的增加量
Page:54
QSC华东理工大学 工商经济学院 生产与运作管理对偶的定义定义 设以下线性规划问题
Max z=CTX
s.t,AX ≤ b (P)
X≥0
为原始问题,则称以下问题
Min z=bTW
s.t,ATW ≥ C (D)
W≥0
为原始问题的对偶问题。
Page:55
QSC华东理工大学 工商经济学院 生产与运作管理例
max Z= 4x1 +7x2
s.t,3x1 +5x2 ≤6
x1 +2x2 ≤8
x1,x2 ≥0
(P)
min W= 6w1 +8w2
s.t,3w1 +w2 ≥4
5w1 +2w2 ≥7
w1,w2 ≥0
(D)
Page:56
QSC华东理工大学 工商经济学院 生产与运作管理对偶的对偶设原始问题 (P)为：
max z=CTX
s.t,AX ≤ b
X≥0
(P)的对偶 (D)为,
min w=bTY
s.t,ATY ≥ C
W≥0
(D)的等价问题为,
max w’=-bTY
s.t,-ATY≤ -C
Y≥0
(D) 的对偶 为,
minz’=-CTX
s.t,-AX ≥- b
X≥0
Page:57
QSC华东理工大学 工商经济学院 生产与运作管理定理 对偶问题的对偶就是原始问题
Page:58
QSC华东理工大学 工商经济学院 生产与运作管理一般问题的对偶 -处理方法
m i n z= 8x1 +5 x2 m ax z ' = - 8x 1 - 5x 2
s,t,-x
1
+2 x
2
≤ 4 s,t,-x
1
+2 x
2
≤ 4
3x
1
-x
2
=7 3x
1
-x
2
≤ 7
2x
1
+4 x
2
≥ 8 - 3x
1
+x
2
≤ -7
x
1
≥ 0,x
2
≤ 0 - 2x
1
- 4x
2
≤ - 8
x
1
≥ 0,x
2
≤ 0
Page:59
QSC华东理工大学 工商经济学院 生产与运作管理极小化问题
（ m i n ）
极大化问题
（ m ax ）
变
x
j
≥ 0? ——?
a
ij
w
j
≤ b
i 约量
x
j
,u n r? ——?
a
ij
w
j
=b
i 束
x
j
≤ 0? ——?
a
ij
w
j
≥ b
i
约? a ij
x
j
≥ b
i
——? w
j
≥ 0
变束? a ij
x
j
=b
i
——? w
j
,u n r
量
a
ij
x
j
≤ b
i
——? w
j
≤ 0
Page:60
QSC华东理工大学 工商经济学院 生产与运作管理例
max z= 8x1 +5x2
s.t,-x1 +2x2 ≤4
3x1 -x2 =7
2x1 +4x2 ≥8
x1≥0,x2≤0
min w= 4y1 +7y2 +8y3
s.t,-y1 +3y2 +2y3 ≥8
2y1 -y2 +4y3 ≤5
y1≥0,y2:unr y3≤0
Page:61
QSC华东理工大学 工商经济学院 生产与运作管理与对偶有关的定理
Page:62
QSC华东理工大学 工商经济学院 生产与运作管理弱对偶定理若 X,Y分别是原问题
LP与其对偶问题 DP的可行解，且
z=CTX,w=bTY,
则
w≥z
bAX?
TTT bAX?
YbYAX TTT?
YbCX TT?
wy?
Page:63
QSC华东理工大学 工商经济学院 生产与运作管理强对偶定理若 X,Y分别是原问题 LP
与其对偶问题 DP的可行解，且
CTX=bTY,
则 X,Y分别是原问题 LP
与其对偶问题 DP的最优解。
Page:64
QSC华东理工大学 工商经济学院 生产与运作管理最优解定理若原问题 LP有最优解 X*，
则其对偶问题 DP也有最优解 Y*，且
z*=CTX * =bTY *=w*
Page:65
QSC华东理工大学 工商经济学院 生产与运作管理对偶解定理若用单纯形法解原问题 LP，
得有最优解 X*，相应的最优基为 B，则
Y*=CBB-1
为其对偶问题 DP的最优解
Page:66
QSC华东理工大学 工商经济学院 生产与运作管理互补松弛定理量。
的松弛变量与剩余变与分别是和其中件是：
是最优解的充分必要条与的可行解与
DP
LPYX
XY
XY
YXDPLP
SS
S
S
0
0
Page:67
QSC华东理工大学 工商经济学院 生产与运作管理互补松弛定理的应用
min z= 6x1 +8x2 +3x3
s.t,x1 +x2 ≥1
x1 +2x2 +x3 ≥-1
x1,x2,x3 ≥0
求解以下线性规划问题 LP,
Page:68
QSC华东理工大学 工商经济学院 生产与运作管理
max w= y1 -y2
s.t,y1 +y2 ≤6
y1 +2y2 ≤8
y2 ≤3
y1,y2 ≥0
写出对偶问题 DP：
利用图解法,可以求得 DP的最优解为
(y1,y2)T=(6,0)T
Page:69
QSC华东理工大学 工商经济学院 生产与运作管理得到对偶问题各松弛变量的值
y3=0,y4=2,y5=3
即对偶问题的最优解和最优目标函数值为
YT=(y1,y2,y3,y4,y5)T=(6,0,0,2,3)T
w=6
根据互补松弛定理,以下的互补松弛关系成立由 y1>0 得到 x4=0
由 y4>0 得到 x2=0
由 y5>0 得到 x3=0
Page:70
QSC华东理工大学 工商经济学院 生产与运作管理因此原始问题的约束条件
x1 +x2 -x4 =1
x1 +2x2 +x3 -x5 =-1
成为
x1 =1
x1 -x5 =-1
由此得到
x1=1,x5=2
即原始问题的最优解为
X=(x1,x2,x3,x4,x5)T=(1,0,0,0,2)T
z=6
Page:71
QSC华东理工大学 工商经济学院 生产与运作管理对偶单纯形法
C
B
C
N
X
B
X
N
C
B
X
B
I B -1 N B -1 b
检验数 C
B
-C
B
B
-1
B C
N
-C
B
B
-1
N
ABCC B 1
0?
0?
LP可行解
DP可行解
Page:72
QSC华东理工大学 工商经济学院 生产与运作管理当 LP与 DP均为可行时，
LP与 DP均得到最优解单纯形方法：
保持 LP可行的同时，
逐步将 DP变可行对偶单纯形方法：
保持 DP可行的同时，
逐步将 LP变可行
Page:73
QSC华东理工大学 工商经济学院 生产与运作管理
max z= -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
Page:74
QSC华东理工大学 工商经济学院 生产与运作管理
max z= -2x1 -3x2 -4x3
-x1 -2x2 -x3 +x4 =-3
-2x1 +x2 -3x3 +x5 =-4
x1,x2,x3,x4,x5 ≥0
Page:75
QSC华东理工大学 工商经济学院 生产与运作管理
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 -1 -2 -1 1 0 -3
0 x 5 -2 1 -3 0 1 -4
-2 -3 -4 0 0-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 0 - 5 / 2 1 / 2 1 - 1 / 2 -1
-2 x 1 1 - 1 / 2 3 / 2 0 - 1 / 2 2
0 -4 -1 0 -1
m i n |z cy y z cyj j
rj
rj
k k
rk
0
m i n |z cy y z cyj j
rj
rj
k k
rk
0
Page:76
QSC华东理工大学 工商经济学院 生产与运作管理
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
0 x 4 0 - 5 / 2 1 / 2 1 - 1 / 2 -1
-2 x 1 1 - 1 / 2 3 / 2 0 - 1 / 2 2
0 -4 -1 0 -1
-2 -3 -4 0 0
x 1 x 2 x 3 x 4 x 5 R H S
-3 x 2 0 1 - 1 / 5 - 2 / 5 1 / 5 2 / 5
-2 x 1 1 0 7 / 5 - 1 / 5 - 2 / 5 1 1 / 5
0 0 - 9 / 5 - 8 / 5 - 1 / 5
Page:77
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析
Page:78
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析目的灵敏度分析所要解决的问题：
系数在什么范围内变化,不会影响已获得的最优基 。
如果系数的变化超过以上范围,如何在原来最优解的基础上求得新的最优解
当线性规划问题增加一个新的变量或新的约束,如何在原来最优解的基础上获得新的最优解 。
Page:79
QSC华东理工大学 工商经济学院 生产与运作管理灵敏度分析内容
※ 目标函数系数 cj的改变
※ 常数项 bi的改变
※ 技术系数 aij的改变
Page:80
QSC华东理工大学 工商经济学院 生产与运作管理目标函数系数 cj的改变
C B C N
X B X N
C B X B I B -1 N B -1 b
检验数 0 C
N -C B B
-1
N
非基变量在目标函数中系数的灵敏度分析基变量在目标函数中系数的灵敏度分析
Page:81
QSC华东理工大学 工商经济学院 生产与运作管理非基变量在目标函数中系数的灵敏度分析
-例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 c2进行灵敏度分析 。
Page:82
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
得到以上问题的最优单纯形表：
Page:83
QSC华东理工大学 工商经济学院 生产与运作管理当 c2’=c2+?时，相应的单纯形表为：
-1 - 1+δ 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0
0 -1 0
-2
Page:84
QSC华东理工大学 工商经济学院 生产与运作管理
0
12
47
要使原来的解仍保持最优解，就要 zj-cj≤ 0（ j=1,2,3,4,5），即
12
47
由此得到，,即当 c2?35/12时，最优解保持不变
12
47
Page:85
QSC华东理工大学 工商经济学院 生产与运作管理基变量在目标函数中系数的灵敏度分析
-例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 c1进行灵敏度分析 。
Page:86
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
4 7 / 1 2
0 -1 0 -2
得到以上问题的最优单纯形表：
Page:87
QSC华东理工大学 工商经济学院 生产与运作管理
- 1+δ -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
- 1+δ x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0
-47/12-1/4? 0 -1+1/3? 0 - 2- 2/ 3?
当 c1’=c1+?时，相应的单纯形表为：
Page:88
QSC华东理工大学 工商经济学院 生产与运作管理
03/22
03/11
01 / 3 -4-
要使原来的基仍保持最优基，就要 zj-cj≤ 0（ j=1,2,3,4,5），即
3
3
12
δ
δ
δ
由此得到,-33，即当 -2?c1?4时，最优基保持不变
Page:89
QSC华东理工大学 工商经济学院 生产与运作管理右边常数的灵敏度分析
C B C N
X B X N
C B X B I B -1 N B -1 b
检验数 0 C
N -C B B
-1
N
右边常数的灵敏度分析
Page:90
QSC华东理工大学 工商经济学院 生产与运作管理例
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
在线性规划问题中，对 b1进行灵敏度分析 。
Page:91
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
0 x
4
1 1 2 1 0 0 9
0 x
5
1 1 -1 0 1 0 2
0 x
6
-1 1 1 0 0 1 4
-1 -1 4 0 0 0
最优单纯形表
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
初始单纯形表
Page:92
QSC华东理工大学 工商经济学院 生产与运作管理对于上述最优解，最优基为：
B
1
1 3 0 2 3
0 1 1
1 3 0 1 3
/ /
/ /
b B b
1
1 3 0 2 3
0 1 1
1 3 0 1 3
9
2
4
1 3
6
13 3
/ /
/ /
/
/
101
111
201
B
Page:93
QSC华东理工大学 工商经济学院 生产与运作管理当 b1’=b1+?=9+?时，最后一张单纯形表中的右边常数将成为
3/3/13
6
3/3/1
4
2
9
3/103/1
110
3/203/1
1
bBb
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3+δ / 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3+δ / 3
0 -
47/ 12
0 -1 0 -2
最后一张单纯形表中的右边常数将成为：
Page:94
QSC华东理工大学 工商经济学院 生产与运作管理原始可行条件 为：
1 3 1 3 0
13 3 1 3 0
/ /
/ /
1
13
-1,b1’=b1+8时，原来的最优基仍为原始可行基
Page:95
QSC华东理工大学 工商经济学院 生产与运作管理增加一个新的变量 -例增加一个新的变量 x7，它在目标函数中的系数 c7=1，在约束条件中的系数向量为,
1
1
1
7a
求新的最优基和最优解。
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
Page:96
QSC华东理工大学 工商经济学院 生产与运作管理
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
0 x
4
1 1 2 1 0 0 9
0 x
5
1 1 -1 0 1 0 2
0 x
6
-1 1 1 0 0 1 4
-1 -1 4 0 0 0
最优单纯形表
-1 -1 4 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 1/ 3
0 x
5
0 2 0 0 1 1 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 13 / 3
0 -
47/ 12
0 -1 0 -2
初始单纯形表
Page:97
QSC华东理工大学 工商经济学院 生产与运作管理对于上述最优解，最优基为：
B
1
1 3 0 2 3
0 1 1
1 3 0 1 3
/ /
/ /?
101
111
201
B
单纯形表中 x7对应的系数：
0
2
3/1
1
1
1
3/103/1
110
3/203/1
7
1
aB
Page:98
QSC华东理工大学 工商经济学院 生产与运作管理加入 x7后的单纯形表为：
-1 -1 4 0 0 0 1
x 1 x 2 x 3 x 4 x 5 x 6 x 7 R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 - 1/ 3 1/ 3
0 x
5
0 2 0 0 1 1 2 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 -
47/ 12
0 -1 0 -2 2/ 3
……
Page:99
QSC华东理工大学 工商经济学院 生产与运作管理增加一个新的约束 -例增加一个新的约束,-x1+2x2≥ 2，求新的最优基和最优解。
max z= -x1 -x2 +4x3
s.t,x1 +x2 +2x3 ≤9
x1 +x2 -x3 ≤2
-x1 +x2 +x3 ≤4
x1,x2,x3 ≥0
-x1+2x2≥ 2 -x1+2x2-x7=2 x1-2x2+x7=-2
Page:100
QSC华东理工大学 工商经济学院 生产与运作管理在原最优单纯形表中加入新方程信息：
-1 -1 4 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 0 1/ 3
0 x
5
0 2 0 0 1 1 0 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 x
7
1 -2 0 0 0 0 1 -2
Page:101
QSC华东理工大学 工商经济学院 生产与运作管理变成单纯形表：
-1 -1 4 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
-1 x
1
1 - 1/ 4 0 1/ 3 0 - 2/ 3 0 1/ 3
0 x
5
0 2 0 0 1 1 0 6
4 x
3
0 2/ 3 1 1/ 3 0 1/ 3 0 13 / 3
0 x
7
0 - 7/ 4 0 - 1/ 3 0 2/ 3 1 - 7/ 3
0 - 47 / 12 0 -1 0 -2 0
……
