运筹学第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）。 若经过迭代运算后，可表示为： 相应有 线性规划问题可表示为： 将（2-2）式移项及整理后： 令非基变量=0；由上式得到： （1）非基变量的系数表示为： （2）Θ规则表示为： RHS值 表示选用0的分量 换入变量的系数向量 （3）单纯形表与矩阵表示的关系 矩阵关系式： 单纯形表中的数据 小结 1）掌握矩阵的运算； 2）理解基矩阵的作用； 3）了解矩阵运算与单纯表的关系。 * * 检验数 系数矩阵 等式右边 非基变量 基变量