系统工程第2版 作者 杜瑞成 等主编第3章 线性规划 3-5.pptVIP

3.5 改进单纯形法 3.5.1 单纯形法的矩阵表示 3.5.2 改进单纯形法 作业 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 3.5 改进单纯形法 * 《系统工程》主编 杜瑞成 闫秀霞 * 电子制作 齐向阳 在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： 3.5.1 单纯形法的矩阵表示 标准型 maxf=CX AX=b X ? 0 已知：A、b、c A= (N B) B=E 3.5.1 单纯形法的矩阵表示 用非基变量表示基变量 f= CBB-1b + (CN - CBB-1 N)XN XB =B-1 b-B-1 NXN CBB-1b CN - CBB-1 N 0 B-1 b B-1 N E 3.5.1 单纯形法的矩阵表示 CBB-1b C - CBB-1 A B-1 b B-1 A C - CBB-1A= (CN CB )- CBB-1 (NB ) = (CN - CBB-1N, CB -CBB-1B) B-1A= B-1(NB )= (B-1N, B-1B) 单个检验数：λj = Cj - CBB-1 Pj 某列 Pj = B-1 Pj 3.5.1 单纯形法的矩阵表示 从单纯形法的矩阵表示中可以看出，要求解一个线性规划模型需要经过以下过程： (1)只须存贮原始数据A、B、C，每步需知B-1 。 (2)每步必须计算的数据 ① 检验数 ?N = CN - CBB-1N CBB-1 =? 单纯形乘子 ② 当某个?m+k﹥ 0时，需关键列： 3.5.1 单纯形法的矩阵表示 Pm+k = B-1Pm+k = a1m+k amm+k … ③ 基变量XB = B-1b = b1 bm … 由② 、③，用最小? 比值法得主元arm+k ④ 主元已知，新基B确定。返回(1) 3.5.2 改进单纯形法 对 max f=CX AX ? b X?0 A=(P1 P2 … Pn) (1) 已有初始可行基B，求B-1 ， XB = B-1 b (2) 计算λj = Cj -CB B-1Pj 若全部 λj ?0，则计算f0 = CB B-1 b, 停止；否则，取 λm+k = maxλj ， xm+k换入。 λj0 3.5.2 改进单纯形法 θ=min bi Aim+k aim+k 0 = br arm+k xr 换出 (4)最小θ比值法： (3)计算Pm+k = B-1Pm+k ，若Pm+k ?0，则无有限最优解, 停；否则 (5)新基B。转(1)。 3.5.2 改进单纯形法 与单纯形表解法类似，改进单纯形法通常也是用m个单位向量构成的单位矩阵作为初始基矩阵，即： 1 1 1 1 1 B0= 3.5.2 改进单纯形法 以列向量Pm+k代换Pr后，得到新的基矩阵B1，即： 1 a1m+k 1 ar-1m+k arm+k ar+1m+k 1 amm+k 1 B1= 3.5.2 改进单纯形法 根据线性代数的理论，不难求得B1的逆矩阵B1-1 ，即： a1m+k arm+k - ar-1 m+k arm+k