运筹学第一章：计算公式

§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 1 of 13
设有线性规划
max Z CX AX b X 0 其中Am×n且r(A)=m,
C＝（c1 , c2 ,cn )
X ( x1 , x 2 , , x n )
b (b1 , b2 , , bm )
T
T
X≥0应理解为X大于等于零向量，即xj≥0,j=1,2…,n。
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 2 of 13
ຫໍສະໝຸດ Baidu
不妨假设A＝（P1，P2，…，Pn）中前m个列向量构成 一个可行基，记为B=(P1 ，P2 ，…，Pm)。矩阵A中后n －m列构成的矩阵记为N＝（Pm+1,…Pn）,则A可以写成 分 块 矩 阵 A= （ B ， N ） 。 对 于 基 B ， 基 变 量 为 xB= （x1,x2，…，xm ）T, 非基变量为xN=(xm+1,xm+2,…xn)T. 则X可表示成 同理将C写成分块矩阵C=（CB， CN），CB=(c1,c2,…,cn), CN=(Cm+1Cm+2，…，cn) 则AX=b可写成
Z CB B b (C N CB B N )) X N
1
1
得到下列五个计算公式：
1. 2. Z 0 CB B b
1
(令XN=0)
1
N C N CB B N
C CB B 1 A
j c j ci aij
其中
3. 4. 5.
XB B b N B N
X B ( B，N ) BX B NX N b X N
X B X XN
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 3 of 13
因为r（B）=m（或|B|≠0）所以B —1存在，因此可有
CN X N
CB ( B b B
1
1
1 N
X N ) CN X N
1
CB B b (C N CB B N )) X N
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 4 of 13
1
B1
故单纯形乘子
C B B 1
1 3 1 9
1 2 3
1 3 (1,2) 1 9
1 1 7 ( ，) 2 9 3 3
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 9 of 13
(2)基变量的解为
XB x1 1 B b x2
25 1 15 2 20 35 3 3
35 3,
1
1 3 1 9
再将第二行左乘－CB后加到第三行,得到
XB XN b
XB
λ N
I
0 λΝ
B－1N
CN－CBB－1N XB
B－1b
－CBB－1b
－Z0
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 7 of 13
五个公式的应用 【例1.17】线性规划
将B化为I（I为m阶单位矩阵）,CB化为零,即求基本可 行解和检验数.用B－1左乘表中第二行,得到下表
XB XB I CB XN B-1N CN b B-1b 0
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 6 of 13
即
1
1 3
, 3 9
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 13 of 13
本节不作重点要求！
The End of Chapter 1
第二章 对偶线性规划
Exit
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 8 of 13
【解】(1)因为B1 由A中第一列、第二列组成,故x1 、x2 为基变量，x3、x4、x5为非基变量,有关矩阵为
CB=(c1,c2)=(1,2) CN=(c3,c4,c5)=(1,0,0)
2012年11月1日星期四 Page 11 of 13
(4) 要判断B1是不是最优基,亦是要求出所有检验数 则否满足λj≤0,j=1…,5.x1,x2是基变量,
故λ1=0,λ2=0,而 得
3
98 9
剩下来求λ4,λ5，由λN计算公式 0,
1
(4 , 5 ) (c4 , c5 ) C B B ( P4 P5 ) 1 7 1 0 (0,0) ( , ) 9 3 0 1 1 7 ( , ) 9 3
max Z x1 2 x 2 x3
2 x1 3 x 2 2 x3 x 4 15 1 x1 x 2 5 x3 x5 20 3 x j 0, j 1, ,5
已知可行基
2 3 B1 1 1 3
求(1)单纯形乘子π; (2)基可行解及目标值; (3)求λ3; (4)B1是否是最优基,为什么; (5)当可行基为 B ＝1 3 时求λ1及λ3. 2 0 1
因λj≤0,j=1,…,5,故B1是最优基.
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 12 of 13
(5) 因B2是A中第四列与第二列组成的,x4、x2是基变 量x1、x3、x5是非基变量,这时有
C B (c 4 , c 2 ) (0,2) 1 3 1 1 B , C B B (0,2) 0 1 1 (1 , 3 ) (c1 , c3 ) C B B ( P P3 ) 1 .2 2 (1,1) (0,2) 1 5 3 ( ,9) 3 1
1
1
i
aij ( B N ) j
1
CB B 1
称为单纯形算子
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 5 of 13
上述公式可用下面较简单的矩阵表格运算得到，
设初始矩阵单纯形表为
XB XB B CB XN N CN b b 0
故基本可行解为
X (25,
0,0,0, ) ,
T
目标函数值为
25 145 Z 0 C B B b C B X B (1，) 35 2 3 3
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming
2012年11月1日星期四 Page 10 of 13
BX B b NX N X B B (b NX n ) B b B NX N
1 1 1
令非基变量XN=0，XB=B—1b，由 B是 可行基的假设， 则得到基本可行解 X=(B－1b，0)T 将目标函数写成
X B Z (C B , C N ) CB X B X N
(3) 求λ3
2 1 7 2 107 1 P3 , CB B P3 P3 ( ， ) 9 3 5 9 5
3 c3 C B B 1 P 3
＝－ 1 ＝－ 107 9 98 9
§1.7 计算公式 Calculate Formula
Ch1 Linear Programming