运筹学对偶理论与灵敏度分析精.ppt

《运筹学对偶理论与灵敏度分析精.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶理论与灵敏度分析精.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对应目标系数 原线性规划可改写为：约束条件第1页，本讲稿共11页第2页，本讲稿共11页单纯形表的几个特征:1、检验数:非基底的检验数(等于对应的目标系数)cj zj=(CNCBB-1N)基变量的检验系数为零，即cj zj=CBCBB-1 B=0 进一步，非基底变量可分解XN（XN1，Xs），其中 XN1 表示除去松弛变量以后的非基变量；Xs是松弛变量，其目标系数为零。Xs非基底的检验数cj zj=(0CBB-1)=CBB-1所有的检验数可用CCBB-1A与CBB-1表示第3页，本讲稿共11页2、规则的表达形式第4页，本讲稿共11页3、单纯形表的矩阵表达形式 将目标和约束条件改写为：z+CBXB

2、+C NXN+0 Xs=0，N,s对应非基变量 B XB+NXN+IXs=b XB为基变量时，经基底转换后有XB,z的表达式:XB+B-1 N1XN+B-1Xs=B-1b z+(C N-CB B-1 N)XN1-CB B-1 Xs=-CB B-1 b 用矩阵表示为第5页，本讲稿共11页分块的系数矩阵可用下列表格形式表示：一般线性规划问题具体对应如下：第6页，本讲稿共11页最后表初始表第7页，本讲稿共11页1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；2）初始单纯形表中基变量Xs=b，迭代后的表中变为XB=B-1b；3）初始单纯形表中的系数矩阵A，I=B，N，I，迭代后的表中约束系数矩阵为：B-1A，B-1I=B-1B，B-1N，B-1I=I，B-1N，B-1I；4）初始单纯形表中变量xj的系数向量为Pj，迭代后为Pj，则有Pj=B-1 Pj；第8页，本讲稿共11页2 改进的单纯形算法主要是计算 的差别第9页，本讲稿共11页第10页，本讲稿共11页z用改进的单纯形法求解下面的线性规划问题第11页，本讲稿共11页