运筹学对偶理论与灵敏度分析幻灯片.ppt

对应目标系数 原线性规划可改写为：约束条件第1页，共11页，编辑于2022年，星期三第2页，共11页，编辑于2022年，星期三单纯形表的几个特征: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页，编辑于2022年，星期三2、规则的表达形式第4页，共11页，编辑于2022年，星期三3、单纯形表的矩阵表达形式 将目标和约束条件改写为：z+CBXB+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页，编辑于2022年，星期三分块的系数矩阵可用下列表格形式表示：一般线性规划问题具体对应如下：第6页，共11页，编辑于2022年，星期三最后表初始表第7页，共11页，编辑于2022年，星期三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页，编辑于2022年，星期三2 改进的单纯形算法主要是计算 的差别第9页，共11页，编辑于2022年，星期三第10页，共11页，编辑于2022年，星期三z用改进的单纯形法求解下面的线性规划问题第11页，共11页，编辑于2022年，星期三