《运筹学》课程教学课件（讲稿）第1章 线性规划与单纯形法（Linear Programming, LP）

线性规划问题解的几个概念：PsPiP4P,P3002204A =0O05001基向量00取001B, = (p3, P4, Ps)=→基矩阵00122)0则: N,=(pl,P2)=4→非基矩阵05,非基向量2024-10-2727

2024-10-27 27 线性规划问题解的几个概念： P1 P2 P3 P4 P5 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 A        取 1 3 4 5 1 0 0 ( , , ) 0 1 0 0 0 1 B p p p          基矩阵 1 1 2 2 2 ( , ) 4 0 0 5 N p p         则：  非基矩阵 非基向量基向量

线性规划问题解的几个概念：2.基变量、非基变量基向量：基矩阵中每一列向量 p,(j=1,2,,m)对应的变量x,(j=1,2,.",m)为基变量。非基向量：非基矩阵中列向量对应的变量为非基变量。2024-10-2728

2024-10-27 28 线性规划问题解的几个概念： 2. 基变量、非基变量 基向量：基矩阵中每一列向量 对应的变量 为基变量。 非基向量：非基矩阵中列向量对应的变量为非基变量。 ( 1,2, , ) j p j   m ( 1,2, , ) j x j   m

线性规划问题解的几个概念3. 基解不失一般性，设基矩阵B=（p,P2,,Pm），则：N=（Pm+1,Pm+2,Pn）XA=(B:N)XXBAX =b =(B:N)YX即：BX+NX=b，有无穷多解。令：X~=0 则：BXβ=b得：Xβ= B-b(B-"b)0此时，X:X称为线性规划问题的基解。其.0中非零向量个数≤m。292024-10-27

2024-10-27 29 线性规划问题解的几个概念： 3. 基解 不失一般性，设基矩阵 ，则： 即： ，有无穷多解。 1 2 ( , , , ) B m  p p  p 1 2 ( , , , ) N m m n p p p     A  (B : N) B N X X X        AX  b  ( : ) B N X B N b X        BXB NX N   b 0 X N  BXB  b 1 XB B b   1 0 0 B b X          此时， X 称为线性规划问题的基解。其 中非零向量个数 m 。 令： 则： 得：

线性规划问题解的几个概念：4.可行解AX=b满足约束条件的解，X=(x,X2,,x,)X≥0称为线性规划问题的可行解。5.基可行解满足非负条件的基解，称为基可行解。或者说既是基解又是可行解的解，称为基可行解。2024-10-2730

2024-10-27 30 线性规划问题解的几个概念： 4. 可行解 满足约束条件 的解， ， 称为线性规划问题的可行解。 0 AX b X      1 2 ( , , , ) T X n  x x  x 5. 基可行解 满足非负条件的基解，称为基可行解。 或者说既是基解又是可行解的解，称为基可行解

可行解、基解、基可行解的关系图：基可行解非可行解基解可行解2024-10-273

2024-10-27 31 可行解、基解、基可行解的关系图： 可行解 非可行解 基 解 基可行解