College of Management
Linear Optimization
线性优化
Chapter 8
College of Management
例：
两产品,甲 乙单位利润,2个单位 3个单位生产约束,总量限制单位消耗能源 I,1 2 8
单位消耗能源 II,4 0 16
单位消耗能源 III,0 4 12
8.1 建模初步
College of Management
建模如下：
max z = 2x1+3x2
s.t,x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1,x2 ≥ 0 (非负约束 )
College of Management
8.2 基本概念
目标函数,z(x1,x2) = 2x1+3x2
决策变量,x1,x2
约束条件：
资源约束,x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
变量非负约束,x1,x2 ≥ 0
College of Management
模型的一般表示法：
min CX C,价值向量 (目标函数系数向量 )
X,决策变量 (列向量 ),n维
s.t,AX≤ b
X≥ 0
A,m行 n列矩阵 表示 m个约束条件
b：常数 (右端 )列向量
opt
m a x
College of Management
Feasible Solution
任一满足 AX ≤ b 的解 X
X≥ 0
Optimal Solution
使目标函数取最优值的可行解
有不等号：用图解法，仅限两维
处理方法：将不等式化为等式，再结合线性方程组处理，求解
College of Management
max z = 2x1+3x2 从等值线看变化
s.t,x1+2x2 ＋ x3 ＝ 8
4x1 ＋ x4 ＝ 16
4x2 ＋ x5＝ 12
x1,x2,x3,x4,x5 ≥ 0
松弛变量 x3,x4,x5 ≥ 0表达不等式方向
College of Management
图解法的启示：
可行解：无穷点集
最优解必在边界上 (常在顶点处 )
顶点＝ 某线性方程组的解
常用的算法有单纯形法 (简单的几何图形 )
AX＝ b
X≥0
College of Management
8.3 建模的有关讨论
B1 B2 B3 供给量
A1
A2
A3
x11 x12 x13
x21 x22 x23
x31 x32 x33
8
4
6
需求量
9 5 4
18
18
运输问题举例：三个供应源 Ai,三个需求源 Bj
College of Management
供需平衡的问题：
如何安排运量可使总费用最小？
单位运价 (Cij) B
1 B2 B3
A1
A2
A3
3 2 4
4 5 2
6 8 1
College of Management
建模：
min c11x11 + c12x12 +c13 x13 =8
s.t,x11 + x12 + x13 =8
x21 + x22 + x23 =4
x31 + x32 + x33 =6
x11 + x21 + x31=9
x12 + x22 + x32 =5
x13 + x23 + x33 =4
xij≥0
College of Management
供需不平衡,供给 > 需求 B4：就地入库
B1 B2 B3 B4
A1
A2
A3
3 2 4 0
4 5 2 0
6 8 1 0
8
4?7
6
9 5 4 3
18 +3
18+3
College of Management
供需不平衡：供给 < 需求 A4：打白条
B1 B2 B3
A1
A2
A3
A4
3
3
3
1 0 0
8
4
6
4
9 5 4?8
18 +4
18+4
College of Management
作平衡 (问题 )表，给出对应的单位运价表
解：平衡表
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
X11 X12 X13 X14 X15
X21 X22 X23 X24 X24
X31 X32 X33 X34 X35
X41 X42 X43 X44 X45
8
4
6
6
2 6 4 6 6
18+6
24
College of Management
单价运输表：
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
3 3 2 4 4
4 4 5 2 2
6 6 8 1 1
M 0 M M 0
College of Management
特殊需求问题：
b1 b2 b3
最低 2 4 6
最高 8 4 不限
B1 B2 B3
A1
A2
A3
X11 X12 X13
X21 X22 X23
X31 X32 X33
8
4
6
9 5 4
18
18
College of Management
供需平衡表 （ Bi’为最低需求,Bi’’为刚性需求）：
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
3 3 2 4 4
4 4 5 2 2
6 6 8 1 1
M 0 M M 0
8
4
6
6
2 6 4 6 6
24
24
（ 8+4+6）－（ 2+4）－ 6=6
College of Management
8.4 Shadow Prices
影子价格 (P499)
前例：最优解为,w=12 p=9
最优值为,130x12+100X9=2460
(见 P481之图 8.9,P480之图 8.8)
“紧约束,为,1.5w+p=27 ①
w+p=21 ②
若将①式中的 27增加 1单位至 28，
则得 w=14
p=7
College of Management
相应的,z＝ 130× 14＋ 100× 7＝ 2520
∴ △ z ＝ 2520－ 2460＝ 60(百 $),即 60$/lb
（ 1000lb→60000$ ）
Shadow Price on the Steel Constraint
若将②式中的 21增加 1单位至 22，
则得 w=10
p=12 → △ z ＝ 40(百 $),即 60$/hour
（ molding machine constraint）
,松约束,的影子价格为 0.
Linear Optimization
线性优化
Chapter 8
College of Management
例：
两产品,甲 乙单位利润,2个单位 3个单位生产约束,总量限制单位消耗能源 I,1 2 8
单位消耗能源 II,4 0 16
单位消耗能源 III,0 4 12
8.1 建模初步
College of Management
建模如下：
max z = 2x1+3x2
s.t,x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1,x2 ≥ 0 (非负约束 )
College of Management
8.2 基本概念
目标函数,z(x1,x2) = 2x1+3x2
决策变量,x1,x2
约束条件：
资源约束,x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
变量非负约束,x1,x2 ≥ 0
College of Management
模型的一般表示法：
min CX C,价值向量 (目标函数系数向量 )
X,决策变量 (列向量 ),n维
s.t,AX≤ b
X≥ 0
A,m行 n列矩阵 表示 m个约束条件
b：常数 (右端 )列向量
opt
m a x
College of Management
Feasible Solution
任一满足 AX ≤ b 的解 X
X≥ 0
Optimal Solution
使目标函数取最优值的可行解
有不等号：用图解法，仅限两维
处理方法：将不等式化为等式，再结合线性方程组处理，求解
College of Management
max z = 2x1+3x2 从等值线看变化
s.t,x1+2x2 ＋ x3 ＝ 8
4x1 ＋ x4 ＝ 16
4x2 ＋ x5＝ 12
x1,x2,x3,x4,x5 ≥ 0
松弛变量 x3,x4,x5 ≥ 0表达不等式方向
College of Management
图解法的启示：
可行解：无穷点集
最优解必在边界上 (常在顶点处 )
顶点＝ 某线性方程组的解
常用的算法有单纯形法 (简单的几何图形 )
AX＝ b
X≥0
College of Management
8.3 建模的有关讨论
B1 B2 B3 供给量
A1
A2
A3
x11 x12 x13
x21 x22 x23
x31 x32 x33
8
4
6
需求量
9 5 4
18
18
运输问题举例：三个供应源 Ai,三个需求源 Bj
College of Management
供需平衡的问题：
如何安排运量可使总费用最小？
单位运价 (Cij) B
1 B2 B3
A1
A2
A3
3 2 4
4 5 2
6 8 1
College of Management
建模：
min c11x11 + c12x12 +c13 x13 =8
s.t,x11 + x12 + x13 =8
x21 + x22 + x23 =4
x31 + x32 + x33 =6
x11 + x21 + x31=9
x12 + x22 + x32 =5
x13 + x23 + x33 =4
xij≥0
College of Management
供需不平衡,供给 > 需求 B4：就地入库
B1 B2 B3 B4
A1
A2
A3
3 2 4 0
4 5 2 0
6 8 1 0
8
4?7
6
9 5 4 3
18 +3
18+3
College of Management
供需不平衡：供给 < 需求 A4：打白条
B1 B2 B3
A1
A2
A3
A4
3
3
3
1 0 0
8
4
6
4
9 5 4?8
18 +4
18+4
College of Management
作平衡 (问题 )表，给出对应的单位运价表
解：平衡表
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
X11 X12 X13 X14 X15
X21 X22 X23 X24 X24
X31 X32 X33 X34 X35
X41 X42 X43 X44 X45
8
4
6
6
2 6 4 6 6
18+6
24
College of Management
单价运输表：
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
3 3 2 4 4
4 4 5 2 2
6 6 8 1 1
M 0 M M 0
College of Management
特殊需求问题：
b1 b2 b3
最低 2 4 6
最高 8 4 不限
B1 B2 B3
A1
A2
A3
X11 X12 X13
X21 X22 X23
X31 X32 X33
8
4
6
9 5 4
18
18
College of Management
供需平衡表 （ Bi’为最低需求,Bi’’为刚性需求）：
B’1 B’’1 B’2 B’3 B’’3
A1
A2
A3
A4
3 3 2 4 4
4 4 5 2 2
6 6 8 1 1
M 0 M M 0
8
4
6
6
2 6 4 6 6
24
24
（ 8+4+6）－（ 2+4）－ 6=6
College of Management
8.4 Shadow Prices
影子价格 (P499)
前例：最优解为,w=12 p=9
最优值为,130x12+100X9=2460
(见 P481之图 8.9,P480之图 8.8)
“紧约束,为,1.5w+p=27 ①
w+p=21 ②
若将①式中的 27增加 1单位至 28，
则得 w=14
p=7
College of Management
相应的,z＝ 130× 14＋ 100× 7＝ 2520
∴ △ z ＝ 2520－ 2460＝ 60(百 $),即 60$/lb
（ 1000lb→60000$ ）
Shadow Price on the Steel Constraint
若将②式中的 21增加 1单位至 22，
则得 w=10
p=12 → △ z ＝ 40(百 $),即 60$/hour
（ molding machine constraint）
,松约束,的影子价格为 0.
