4 ?
1 ?
8 14 C B B 1b [1.5 1 / 8 0] 16 12
Байду номын сангаас 单纯形法的矩阵描述
例
用单纯形法求解下述线性规划问题.
m axz 2 x 1 3 x 2 x1 2 x 2 8 16 4 x1 s .t. 4 x 2 12 x1 , x 2 0
单纯形法的矩阵描述
继续讨论上例
XB x1 x5 x2 -z x1 1 0 0 0 x2 0 0 1 0 x3 0 -2 0.5 -3/2 x4 x5 1/4 0 0.5 1 -1/8 0 -1/8 0 b 4 4 2 -14
0 1 / 4 0 1 0 0 2 B 1a3 2 0 . 5 1 0. 5 1 / 8 0 0 0. 5
1 0 2 B2 4 1 0 0 0 4
迭代
XB x1 x5 x2 -z x1 1 0 0 0 x2 0 0 1 0 x3 x4 0 1/4 -2 0.5 0.5 -1/8 -3/2 -1/8 x5 0 1 0 0 b R 4 4 2 -14 X*=(4, 2)T z*=14
对偶理论与灵敏度分析
(Dual Theories and Sensitivity Analysis)
单纯形法的矩阵描述 线性规划的对偶问题 对偶问题的基本性质 对偶问题的经济解释 对偶单纯形法 灵敏度分析
----影子价格
单纯形法的矩阵描述
(Matrices Description)
m axz CX AX b s .t. X 0
令 A=(B N)
(LP)
A Cmn, R(A)=m .
X=(XB XN)T C=(CB CN)
可行基
相应于非基变量的系数矩阵
单纯形法的矩阵描述
max z C B X B C N X N BX B NX N b s.t. X B , X N 0
B 1 1 / 4 0 0 2 0 . 5 1 0.5 1 / 8 0
1 / 4 0 1 0 1 / 4 0 8 x 1 0 0 x 0 0 3 2 0.5 1 16 x 2 0 . 5 1 5 x 4 0.5 1 / 8 0 0 1 0.5 1 / 8 0 12 x 2
•
对称性形式
m axz 60x 1 30x 2 20x 3
8 x 1 6 x 2 x 3 48 4 x 2 x 1.5 x 20 1 2 3 s.t. 2 x 1 1.5 x 2 0.5 x 3 8 x 1 , x 2 , x 3 0
单纯形法的矩阵描述
选定主元，做完初等变换以后（相当于对增广矩阵/线性 方程组两边同时左乘了基的逆矩阵B-1）
单纯形表中变量 xj 的系数列向量 ： B-1pj 单纯形表中约束方程的右端项： B-1b 单纯形表中目标函数值： CBB-1b 单纯形表中变量 xj 的检验数 ： Cj - CBB-1pj
• •
例1与例2是一个问题的两个方面 两个线性规划模型是一对对偶问题
线性规划问题的对偶问题
2. 原问题与对偶问题的关系
m ax z CX minw Y Tb T T AX b A Y C s.t. X O s.t. Y O 例 3 求下列问题的对偶问题 min w 48 y 1 20 y 2 8 y 3
限制条件 135 405
如何组织生产，使总利润最大？ x1 , x2 , x3 ------分别生产甲、 乙、丙产品的数量
maxZ 2 x1 3 x 2 11 / 3 x 3 s.t. x1 x 2 x 3 135 x1 4 x 2 7 x 3 405 x1 , x 2 , x 3 0.
线性规划问题的对偶问题
•
非对称性形式
max z CX AX b s.t. X O
min w Y T b s.t. A TY C T
练习：
m ax z 6x 1 + 8x 2 3x 1 x 2 s.t .5x 1 2x 2 x , x2 , 1
8 16 12
b
单纯形法的矩阵描述
1 0 2 x 1 1 0 8 4 0 0 x 0 0 x 3 16 5 x 4 12 0 1 4 0 1 x 2
8 y 1 4 y 2 2 y 3 60 6 y 2 y 1.5 y 30 1 2 3 s.t. y 1 1.5 y 2 0.5 y 3 20 y 1, y 2 , y 3 0
线性规划问题的对偶问题
对称性形式的对偶关系
m inw ( y1 0) ( y 2 0) ( y m 0) y1 y2 ym ( x1 0) x1 a11 a 21 a m1 c1 m ax z ( x 2 0) x2 a 12 a 22 am2 c2 ( x n 0) xn a 1n b1 a 2n b2 a mn bm cn
1 0 2 B3 4 0 0 0 1 4
线性规划问题的对偶问题
(Dual Problems)
1. 对偶问题的提出 (Dual Problem)
例1 某工厂用两台机器生产三种产品,有关数据如下表:
机器 I 机器 II 利润
甲(m) 1 1 2
乙(m) 1 4 3
丙(m) 1 7 11/3
x3 1 0 0 0
x4 0 1 0 0
x5 -0.5 0 1/4 -3/4
b
R
2 2 16 4 3 -9
1 0 2 B1 0 1 0 0 0 4
单纯形法的矩阵描述
迭代
XB x1 x4 x2 -z x1 1 0 0 0 x2 0 0 1 0 x3 1 -4 0 -2 x4 0 1 0 0 x5 -0.5 2 1/4 1/4 b 2 8 3 -13 R 4 12
B 1a4 ?
B 1a5 ?
单纯形法的矩阵描述
CB=[2 0 3]
1 / 4 0 0 B 1 2 0 . 5 1 0 .5 1 / 8 0
CBB -1=[1.5 1/8 0]
1 1.5 3 c3 C B B 1a3 0 [1.5 1 / 8 0] 0 0
XB x3 x4 x5 -z x1 1 4 0 2 x2 2 0 4 3 x3 1 0 0 0 x4 0 1 0 0 x5 0 0 1 0 b 8 16 12 0 R 4 3
1 0 0 B0 0 1 0 0 0 1
迭代
XB
x3 x4 x2 -z
x1 1 4 0 2
x2 0 0 1 0
C [2 3
单纯形法的矩阵描述
CB
max z 2 x 1 3x 2 8 x 1 2x 2 x 3 4x x 4 16 1 s.t. 4x 2 x 5 12 x 1 , x 2 , x 3 , x 4 , x 5 0
CN
XN
B
x 1 x3 m ax z [ 2 0 3] x 5 [ 0 0 ] x 4 XB x 2 1 0 2 x 1 0 1 x 3 s.t. 4 0 0 x 5 0 1 x 4 x 2 0 1 4 0 0 x 1 0 x x 5 0 , 3 0 . 0 x 4 x N 0 2
1/ 4 x 1 0 4 x 3 x 5 2 0.5 x 4 4 2 0 . 5 1 / 8 x 2
B-1 b
B-1 N
单纯形法的矩阵描述
XB x1 x5 x2 -z x1 1 0 0 0 x2 0 0 1 0 x3 0 -2 0.5 -3/2 x4 x5 1/4 0 0.5 1 -1/8 0 -1/8 0 b 4 4 2 -14
例
m ax z 2 x 1 3x 2 m axz 2 x1 3 x 2 8 x 1 2x 2 x 3 x1 2 x 2 8 4x 1 x4 16 16 4 x1 s.t. s.t. 4x 2 x 5 12 4 x 2 12 x 1 , x 2 , x 3 , x 4 , x 5 0 x1 , x 2 0 x 1 x 1 2 1 0 0 8 2 0 0 0] X x 3 A 4 0 0 1 0 16 b 0 4 0 0 1 x 4 12 x 5
矩阵形式的单纯形表
max z C B B 1 b (C N C B B 1 N ) X N X B B 1 NX N B 1 b s.t. X B , X N 0
XB XB -z
XB I 0
XN B-1N CN - CB B-1N
b B-1b - CB B-1b
1 0 2 B 4 0 0 0 1 4
1 0 N 0 1 0 0
XB
x 1 x 5 x 2
XN
x 3 x 4
CB=[2 0 3]
CN=[0 0]
单纯形法的矩阵描述
考虑线性规划问题的标准型
线性规划问题的对偶问题
例2 若另一工厂想要租赁这两台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？