第2章 对偶理论和灵敏度分析-第1节.ppt

运筹学 （第三版） 《运筹学》教材编写组 编 清华大学出版社 第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 第2节 改进单纯形法 第3节 对偶问题的提出 第4节 线性规划的对偶理论 第5节 对偶问题的经济解释——影子价格 第6节 对偶单纯形法 第7节 灵敏度分析 第8节* 参数线性规划 第1节 单纯形法的矩阵描述  设线性规划问题 : 目标函数 max z=CX; 约束条件 AX≤b; 非负条件 X≥0 给这线性规划问题的约约束条件加入松弛变量以后，得到标准型： max z=CX+0Xs; AX+IXs=b; X，X s≥0 这里I 是m×m单位矩阵。 若以Xs为基变量，并标记成XB 这是将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵， N是非基变量的系数矩阵。 决策变量分为： 将目标函数的系数C分为CB，CN 分别对应于基变量XB和非基变量XN。 并且记作C=（CB, CN）。 因此 z = cBxB + cNxN = cBB–1b – cBB–1NxN + cNxN = cBB–1b + (cN－cBB–1N)xN 令非基变量=0；由上式得到： 一般来说，经过迭代运算之后 N由两部分构成： 1)原决策变量中非基部分?XN1 2)松弛变量?XS z = cBB–1b + (cN-cBB–1N)xN = cBB–1b＋ (cN1-cBB–1N1)xN1＋ (cS-cBB–1I)xS ＝ cBB–1b＋ (cN1-cBB–1N1)xN1＋ (-cBB–1)xS 　　　（2－5） （1）非基变量的系数表示为： （2）Θ规则表示为： RHS值 表示选用0的分量 换入变量的系数向量 （3）单纯形表与矩阵表示的关系 矩阵关系式： 单纯形表中的数据 小结 1）掌握矩阵的运算； 2）理解基矩阵的作用； 3）了解矩阵运算与单纯表的关系。 *  第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 钱颂迪 制作 两边左乘B-1，得到 xB + B–1NxN = B–1b 即：xB = B–1b –B-1 NxN 检验数 系数矩阵 等式右边 非基变量 基变量 *