《对偶理论和灵敏度分析-第1节.ppt》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析-第1节.ppt（15页珍藏版）》请在三一办公上搜索。
1、,运筹学,（第三版）运筹学教材编写组 编清华大学出版社,第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 钱颂迪 制作,第2章 对偶理论和灵敏度分析,第1节 单纯形法的矩阵描述 第2节 改进单纯形法第3节 对偶问题的提出第4节 线性规划的对偶理论第5节 对偶问题的经济解释影子价格第6节 对偶单纯形法第7节 灵敏度分析第8节*参数线性规划,第1节 单纯形法的矩阵描述,设线性规划问题:目标函数 max z=CX;约束条件 AXb;非负条件 X0,给这线性规划问题的约约束条件加入松弛变量以后，得到标准型：,max z=CX+0Xs;AX+IXs=b;X，X s0这里I 是mm单位矩阵。,若以
2、Xs为基变量，并标记成XB,这是将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。决策变量分为：,将目标函数的系数C分为CB，CN,分别对应于基变量XB和非基变量XN。并且记作C=（CB,CN）。,两边左乘B-1，得到xB+B1NxN=B1b 即：xB=B1b B-1 NxN,因此z=cBxB+cNxN=cBB1b cBB1NxN+cNxN=cBB1b+(cNcBB1N)xN,令非基变量=0；由上式得到：,一般来说，经过迭代运算之后N由两部分构成：1)原决策变量中非基部分XN12)松弛变量XSz=cBB1b+(cN-cBB1N)xN=cBB1b(cN1-cBB1N1)xN1(cS-cBB1I)xS cBB1b(cN1-cBB1N1)xN1(-cBB1)xS（25）,（1）非基变量的系数表示为：,（2）规则表示为：,RHS值 表示选用0的分量换入变量的系数向量,（3）单纯形表与矩阵表示的关系,矩阵关系式：,单纯形表中的数据,小结,1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。,
