5、线性规划的单纯性法首先找到一个初始基本可行解，然后判断是否最优解，如果是最优解则停止选代：否则，按照一定法则，继续寻求使目标函数得到改善的B相邻基本可行解D再进行判优，直到找不到更O优的基本可行解，或者判定该线性规划无解为止。Z=011
11 5、线性规划的单纯性法 首先找到一个初始基本可行解，然后判断是否最优解， 如果是最优解则停止迭代； 再进行判优，直到找不到更 优的基本可行解，或者判定 该线性规划无解为止。 否则，按照一定法则，继续 寻求使目标函数得到改善的 相邻基本可行解；
单纯形法的理论基础用单纯形法求解线性规划时，首先将一般线性规划问题通过引入松变量化为标准型：(1)maxZ=cTx(LP)(2)Ax=b(3)x≥012
12 单纯形法的理论基础 maxZ=c T x (1) Ax=b (2) x 0 (3) 用单纯形法求解线性规划时，首先将一般线性 规划问题通过引入松弛变量化为标准型： （LP）
非标准型转化为标准型举例：原非标准型：minf（x）=3x-2x，+4x32x+3x,+4x≥300x+5x2+6x,≤400S.t.X+X+x≤200±不限,,≥0标准型：max f(x) = -3xi +2x2 -4x' + 4x' + 0x4 + 0xs + 0x62x, + 3x2 + 4x§ - 4x - x4 = 300Xi + 5x2 +6xs -6x' + Xs = 400s.t.Xi + X2 + x - x+ X= 200X1,X2,X3,x3,X4,Xs,X, ≥ 013
13 非标准型转化为标准型举例： + + + + + + = − + , , 0 200 5 6 400 2 3 4 300 . . :min ( ) 3 2 4 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x s t f x x x x 不 限 原非标准型 + + − + = + + − + = + + − − = = − + − + + + + , , , , , , 0 200 5 6 6 400 2 3 4 4 300 . . max ( ) 3 2 4 4 0 0 0 1 2 3 3 4 5 6 1 2 3 3 6 1 2 3 3 5 1 2 3 3 4 1 2 3 3 4 5 6 x x x x x x x x x x x x x x x x x x x x x x s t f x x x x x x x x 标准型：
考虑标准的线性规划问题(1)maxZ-cTx(LP)(2)Ax=b(3)x≥0设Amxn,秩(A)=m,A的m个线性无关定义1：基（基阵）的列向量构成的子矩阵B称为LP问题的一个基阵ai1...aimiaim+1 ...ain记a21a2ma2na2m+1BNA=B= [Pi... Pm]1mm!mamm+1..amnN=[Pm+1 ... P,]Pi... PmPPm+1基向量非基向量14
14 记 B＝ [P1 . Pm] N =[Pm+1 . Pn ] a11 . a1m a21 .a2m . am1 .amm P1 . Pm a1m+1 . a1n a2m+1 .a2n . amm+1 .amn Pm+1 . Pn A＝ ， 定义1：基(基阵) 设Am×n ,秩（A)=m,A的m个线性无关 的列向量构成的子矩阵B称为LP问题的一个基阵. 基向量 非基向量 maxZ=c T x (1) Ax=b (2) x 0 (3) （LP） 考虑标准的线性规划问题 B N
ai ... aim iaim+1 ... ainB=[Pi... Pm]a21 ... a2m a2m+1 ..a2nA=N=[Pm+1 ... Pn]aml ... amm i amm+1...amnPi ... Pm Pm+1 ... P,H称为基变量：XB[XBXmmx=XN)Xm+1Xm+1称为非基变量Xnxn15
15 B＝ [P1 . Pm] N =[Pm+1 . Pn ] a11 . a1m a21 .a2m . am1 .amm P1 . Pm a1m+1 . a1n a2m+1 .a2n . amm+1 .amn Pm+1 . Pn A＝ ， 称为基变量: x1 xm . xB = xN = 称为非基变量 xm+1 xn . x= x1 xm . xm+1 xn . = xB xN