运筹学05第二章_对偶理论与灵敏度分析.ppt

《运筹学05第二章_对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章对偶理论与灵敏度分析§1单纯形法的矩阵描述线性规划maxz=CXmaxz=CX+OXs(1)AX≤bAX+IXs=bX≥0X≥0,Xs≥0其中I是m×m单位矩阵，松弛变量Xs=(xn+1,xn+2,…,xn+m)T.设B是一个可行基矩阵，N表示非基变量的系数矩阵(A，I)→(B，N)对应决策变量约束条件对应目标函数的价值向量原线性规划可改写为单纯形表的几个特征:1、检验数:非基变量的检验数(等于对应的目标系数)cj–zj=(CN–CBB-1N)j基变量的检验系数为零，即cj–zj=CB–CBB-1B=0进一步，非基底变量可分解XN→（XN1，Xs

2、），其中XN1表示除去松弛变量以后的非基变量；Xs是松弛变量，其目标系数为零。Xs的检验数cj–zj=(0–CBB-1)j=–CBB-1所有的检验数可用C–CBB-1A与–CBB-1表示(B-1b)i是向量(B-1b)中的第i个元素，(B-1Pj)i是向量(B-1Pj)中的第i个元素，j=1,2,…,n2、θ规则的表达形式基变量非基变量等式右端XBXN1XS系数矩阵IB-1N1B-1B-1b检验数0CN1-CBB-1N1-CBB-1-CBB-1b3、单纯形表的矩阵表达形式1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；2）初始单纯形表中

3、基变量Xs=b，迭代后的表中变为XB=B-1b；3）初始单纯形表中的系数矩阵[A，I]=[B，N1，I]，迭代后的表中约束系数矩阵为：[B-1A，B-1I]=[B-1B，B-1N1，B-1I]=[I，B-1N1，B-1]；4）初始单纯形表中变量xj的系数向量为Pj，迭代后为P’j，则有P’j=B-1Pj；§2改进的单纯形算法主要是计算的差别用改进的单纯形法求解下面的线性规划问题