运筹学之线性规划设计.ppt

图解法求解线性规划 基向量;基中每一个列向量, aj 基变量：若B为基，则B中列所对应的变量称为基变量，用XB表示，余下的其他变量称为非基变量 ， 用XN表示。 若B是从A中任取m个列所构成的方阵， 则称B是线性规划问题的一个基。 基：设A是m×n维线性方程组的系数矩阵， A= (a1 … am am+1 … an )=(BN) 基向量 非基向量 … X= (X1 … Xm Xm+1 … Xn )T=(XB XN)T 基变量 非基变量 XB XN … AX=b的求解 A=(BN) X=(XB XN )T XB XN BXB +NXN=b BXB =b-NXN XB = B-1 b - B-1N XN 令 XN = 0 (BN) = b 基本解——对应于基B， X= 为AX=b的一个解。 B-1 b 0 ※ 基本解中最多有m个非零分量。 ※基本解的数目不超过Cnm = 个。 n! m!(n-m)! ※若基本解中有一个或更多个基变量XJ=0则称之为退化基本解。 4. 基本可行解——基B 基本解X= 若B-1 b?0，称基B为可行基, X为基本可行解 。 最优基本可行解对应的基称为最优基 B-1 b 0 退化的基本可行解——若基本可行解有一个或更多个基变量为零则称为退化的基本可行解。 注意两点： 1)B在A中是任意取的。故A中有很多基B 。 2)基变量是针对B而言的，不同的B ，其对应的基变量和非基变量是不同的。 例、 X1 +X3 =8 2X2 +X4 =12 3 X1 +4X2 +X5=36 X1 … X5 ?0 1 0 1 0 0 0 2 0 1 0 3 4 0 0 1 a1 a2 a3 a4 a5 A= X1 X2 X3 X4 X5 X= b= 8 12 36 B=(a3 a4 a5)=I 可逆 N=(a1 a2) X3=8- X1 X4=12-2 X2 X5 =36 -3X1 -4X2 令X1 = X2 =0, X3=8, X4=12, X5=36 X0= = = XN 0 XB B-1 b 0 0 8 12 36 0 1 0 又：Ｂ1 =( a2 a3 a4)= 2 0 1 4 0 0 |B1|=4≠0, B可逆 X2=(36-3X1-X5)/4 X3 =8-X1 X4=3/2 X1 + 1/2X5-6 令X1=X5=0 X=(0, 9, 8, -6, 0)T 1 0 1 若取Ｂ2 =(a1 a2 a3 )= 0 2 0 3 4 0 X*=（4，6，4，0，0）T |B2|=-6≠0, B可逆 例：给定约束条件 -X3+X4 =0 X2 +X3 +X4 =3 -X1 +X2 +X3+X4 =2 Xj ?0 ( j=1,2,3,4 ) 求出基变量是X1 , X3 , X4的基本解，是不是可行解？ 0 -1 1 解：B=(a1 a3 a4)= 0 1 1 -1