《高等数学》课程PPT教学课件（章节知识点）7.2 单纯形法

§72单纯形法 、几个基本概念 1.基、基变量、非基变量 设线性规划问题为 min s= cx AX= b (7.11) X>0 其中 C=(C2 C2.Cn

§7.2 单纯形法 一、几个基本概念 1. 基、基变量、非基变量 设线性规划问题为 min S = CX AX = b (7.11) X ≥0 其中 C = ( c2 c2 ··· cn ).    s t

n 21 22 2n b= m2 mn n 且m 若B是矩阵A的m阶非奇异子矩阵,则称B是线性规 划问题(7的一个基

              =               =               = m m m n m n n n x x x b b b a a a a a a a a a         2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 A , b , X 且 m ≤ n, r(A) = m. 若B是矩阵A 的m 阶非奇异子矩阵, 则称B是线性规 划问题(7.11)的一个基

12 不妨设B=(P1,P2,…,Pm)=21 m2 mm N=(Pm+1,…,Pn) 则把P1,P2,…,Pm对应的变量x1,x2,…xn叫做对应基B的 基变量,Pm,…,Pn对应的变量xmH1xm+2,…xn叫做非基 变量

不妨设 B = (P1 , P2 , ···,Pm ) 则把P1 ,P2 , ···,Pm对应的变量x1 , x2 , ···,xm叫做对应基B的 基变量, Pm+1, ···,Pn对应的变量xm+1,xm+2, ···,xn叫做非基 变量. ,               = m m mm m m a a a a a a a a a       1 2 2 1 2 2 2 1 1 1 2 1 N (P , ,P ). = m+1  n

2.基础解、基础可行解、基础最优解 d 设 B N m+1 若X满足X=b且x=0,则称X=为(1)关 于基B的基础解

2. 基础解、基础可行解、基础最优解 设 若X 满足AX = b且xN = 0，则称X = 为(7.11)关 于基B 的基础解.         =                       = + N B n m m x x x x x x x X   1 2 1         0 B x

若基础解X=≥0,则称此基础解为基础可 行解,此时B称为可行基 若基础可行解X是最优解,则称X为基础最优解, 此时相应的基B称为最优基. 3.线性规划问题的典式 对于线性规划问题

若基础解X= ≥0 , 则称此基础解为基础可 行解, 此时 B 称为可行基. 若基础可行解 X 是最优解, 则称 X 为基础最优解, 此时相应的基 B 称为最优基. 3. 线性规划问题的典式 对于线性规划问题         0 B x