XB记：A=[BN],rXNBxp+Nxn=bAx=bBxB=b -NxnXp= B-1 b - B-IN Xn基本解定义2：对应于基B?Ax=b的基B-1 b本可行解称为Ax=b的一个基本解x=最多有：Qm!m若B-1 b≥0,则称基B为基本可行基。nn!(n-m)B-1 b称为Ax=b的一个基本可行解。=16
16 xB = B-1 b - B-1N xN A=[B N]， x= xB xN Ax=b 记: BxB +NxN=b BxB =b -NxN 定义2：基本解 称为Ax=b的一个基本解. B-1 b 0 x= 则称基B为基本可行基。 称为Ax=b的一个基本可行解。 B-1 b 0 x= ——对应于基B 若B-1 b0， !( )! ! n n m m c m n − = Ax=b的基 本可行解 最多有：
=30,Xi+2x2+X3=60,3x +2x+X4例2X2+xs=24,Xi ... Xs ≥0 ;30200113002160b=A=0200124P1PP2P3P4取B=[P, P4 Ps]=I 可逆,基阵。非基阵 N=[P1 P2] ·(X3[xiXNX4非基向量xn基向量解向量XB=x=X2XBXs17
17 x1+2x2 +x3 =30, 3x1+2x2 +x4 =60, 2x2 +x5=24, x1 . x5 0; 例 b= 30 60 24 取B=[P3 P4 P5 ]=I 可逆, 基阵。 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1 P1 P2 P3 P4 P5 A= , N=[P1 P2 非基阵 ] . 非基向量xN = x1 x2 xB = , x3 x4 x5 基向量 , x= xN xB 解向量
Ax-bXβ= B-1 b - B-IN Xn[3] -{8]AXv=00因为x≥0,XN30则基本解YXB是基本可行解602418
18 xB = B-1 Ax=b b - B-1N xN 令 = 0 0 xN = x1 x2 则基本解 0 0 30 60 24 x= xN xB = 因为x 0， 是基本可行解
21320又若取B,=(P P2 P3)002由det(B)=6+0,知B,可逆,可以充当基矩阵N, =[P4 Ps]相应的非基阵[xi(x4非基变量 XN1XB1 = X2 基变量[xs]12X3120XB]X(B1)-1-6得基本解XXNIXs000非基本可行解019
19 又 由det(B1 ) =6≠0, 知B1可逆,可以充当基矩阵. 1 2 1 3 2 0 0 2 0 若取B1 =(P1 P2 P3 ) = 相应的非基阵 N1 =[P4 P5 ] xB1 = x1 x2 x3 基变量 , x4 x5 xN1 = 非基变量 . 令 得基本解 12 12 -6 0 0 xB1 xN1 x= = (B1 ) -1 b 0 = . x4 x5 xN1 = = 0 0 , 非基本可行解
6、求解线性规划的MATLAB命令求解 min z=cT x,A·x≤bx=linprog(c, A, b):x=linprog(c, A, b, Aeq, beq): 求解:min z=cT x, A.x≤ b, Aeqx = beq :x-linprog(c, A, b, Aeq, beq, Ib, ub):指定Ib≤x≤ub;若没有不等式约束，可用替代A和b若没有等式约束，可用[替代Aeq和beq若某个x：下无界或上无界，可设定-inf或inf；用[x，Fval代替上述命令行中的x，可得最优解处的函数值Fval。20
20 x=linprog(c, A, b): 求解 min z = c T x, Ax ≤ b 6、求解线性规划的MATLAB命令 若没有不等式约束,可用[ ]替代A和b, 若没有等式约束,可用[ ]替代Aeq和beq, 若某个xi下无界或上无界,可设定-inf或 inf； 用[x, Fval]代替上述命令行中的x，可得最优解处的函 数值Fval。 x=linprog(c, A, b, Aeq, beq): 求解： min z = c T x, Ax ≤ b, Aeqx = beq； x=linprog(c, A, b, Aeq, beq, lb, ub): 指定lb ≤ x ≤ ub;