2.1单纯形法的矩阵描述.ppt

第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 单纯形法的矩阵描述 * 单纯形法的矩阵描述 考虑线性规划问题： 则 A=(B,N)，X＝(XB,XN)T，C＝(CB,CN) 目标函数 约束条件 单纯形法的矩阵描述 线性规划问题 B是A的一个基 则线性规划问题可写成以下形式： 由上述模型可看出，当XB=B-1b,XN=0, 满足AX=b条件 当XB=B-1b≥0XN=0时，B是可行基，X是基本可行解 再当CN－CBB-1N ? 0时，B是最优基，X是最优解 最优基判别定理 设B是(LP)的一个基,若基B满足: (1) B-1b?0 (2) CN－CBB-1N ? 0 则B是(LP)的最优基. 可证明：CN－CBB-1N ? 0等价于C－CBB-1A ? 0 检验数 单纯形法的矩阵描述 则线性规划也可表示成： 定理(最优解判别准则）对于可行基B ,若 C -CB B-1A ≤ 0 则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。 σ=C - CB B-1A为检验数。 基变量的检验数： CB- CB B-1B = 0 C - CB B-1A =（0， CN - CB B-1N ） 检验数σ=C - CB B-1A= （0， CN - CB B-1N ） 非基变量检验数σ= CN - CB B-1N 时,达到最优。 CN CB Cj-zj N B CB XB b 非基变量 XN 基变量 XB 项目 CN-CB B-1N CB-CB B-1B Cj-zj B-1 N B-1B CB XB B-1 b 非基变量 XN 基变量 XB 项目 初始单纯形表 迭代单纯形表 单纯形法的矩阵描述（2） 0 CB CN Cj-zj I B N 0 XS b 基变量 XS 非基变量 XB XN 项目 CN-CBB-1N -CBB-1 0 Cj-zj B-1N B-1I I=B-1B CB XB B-1b 非基变量 XN XS 基变量 XB 项目 初始单纯形表 *