单纯形法的矩阵描述

1、1第一节 单纯形法的矩阵描述n 单纯形法的矩阵描述 n 单纯形法计算的矩阵描述2 单纯形法的矩阵描述不妨设基为不妨设基为mPPPB21基变量非基变量max.0zCXAXbs tX设线性规划问题设线性规划问题)()()()(21NBNBnCCCXXXNBPPPA则则312111112121121-Z . . 0 1 .0 1 . . . 0 1 .1 . mmnmnmnmmmnmmnx xxxxbaabaaaac cccc20mbbB基矩阵基矩阵N非基阵非基阵基变量基变量XB非基变量非基变量XNNC 单纯形表BC111()()BNBNBNNXAXbBNXBXNXbXBb NXB b B NX 单

2、纯形法的矩阵描述令令 得得0NX1BXB b当前基可行解约束方程组约束方程组11()()BBNBBNNNBNBNXzCCC XC XXC B bCC B N X目标函数目标函数10BzC B b令令 得得0NX非基变量的检验数当前目标值 单纯形法的矩阵描述1111111111()()mmBmnNNBmnBmnnBnCC B PCC B PCC B NCCC B PB P，当前检验数检验数检验数其中其中1jB P当前 对应的系数列jx 单纯形法的矩阵描述7线性规划问题可以等价写成：1111max(). .0,0BNBNBNBNzC B bCC B N XstXB NXB bXX 此形式为线性规划

3、对应于基B的典则形式（典式）。单纯形乘子812111112121121-Z . . 0 1 .0 1 . . . 0 1 .1 . mmnmnmnmmmnmmnx xxxxbaabaaaac cccc20mbbB基矩阵基矩阵N非基阵非基阵基变量基变量XB非基变量非基变量XNNCBC0N911110BNNBBXB bNB NCC B NzC B b当已知一个线性规划的可行基B时，先求出 ，再用这些运算公式可得到单纯形法所要求的结果。1B10线性规划问题线性规划问题max. .0zCXAXbs tX化为标准型，引入松弛变量化为标准型，引入松弛变量sX0, 0. .0maxsssXXbIXAXtsX

4、CXz 单纯形法计算的矩阵描述11标准型max0. .,0BBNNSBNSBNSzC XC XXBXNXIXbstXXX列初始单纯形表列初始单纯形表12初始单纯形表价值系数价值系数基变量基变量的价值的价值系数系数基变量基变量等式等式右边右边RHSRHS检验数检验数BXNXSXBCBCNCNCSXb000BNI13价值系数价值系数基变量基变量的价值的价值系数系数基变量基变量等式等式右边右边RHSRHS检验数检验数BXNXSXBCBCNCNCSXb000BNI迭代成基变量初始基变量初始单纯形表14迭代后单纯形表价值系数价值系数基变量基变量的价值的价值系数系数基变量基变量等式等式右边右边RHSRHS检验数检验数BXNXBXBC1BC BNC1NBCC B NSXb00BCBNI1B1B1B1B15迭代后单纯形表价值系数价值系数基变量的基变量的价值系数价值系数基变量基变量等式等式右边右边RHSRHS检验数检验数BXNXBXBC1BC BNC1NBCC B NSX1B b00BC