《改进单纯形法》PPT课件.ppt

《《改进单纯形法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《改进单纯形法》PPT课件.ppt（28页珍藏版）》请在三一办公上搜索。

1、单纯形法的矩阵描述,设线性规划问题可以用如下矩阵形式表示：目标函数 max z=CX 约束条件 AXb 非负条件 X0,将该线性规划问题的约束条件加入松弛变量后，得到标准型：,max z=CX+0Xs AX+IXs=b X，X s0 其中，I 是mm单位矩阵。,若以Xs为基变量，并标记成XB，可将系数矩阵(A，I)分为(B，N)两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分：相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作:C=（CB,CN）,若经过迭代运算后，可表示为：相应有:,线性规划问题可表示为：,将（2-2）

2、式移项及整理后得到：,令非基变量=0，由上式得到：,（1）非基变量的系数表示为：,（2）规则表示为：RHS值 表示选用0的分量 换入变量的系数向量,（3）单纯形表与矩阵表示的关系:,单纯形表中的数据:,小结,1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。,改进单纯形法,求解线性规划问题的关键是计算B-1。以下介绍一种比较简便的计算B-1的方法。,设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。,以a11为主元素,进行变换：,然后构造含有（1）列，而其他列都是单位列的矩阵,可得到：,而后以第2列的 为主元素，进行变换:,然后构造含有（2）列，而其他列都是单位列的矩

3、阵:,可得到:,重复以上的步骤，直到获得:,可见，EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-1,以例1为例进行计算。,第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。,(3)确定换出变量,表示选择0的元素,（4）基变换计算将新的基 单位矩阵。计算：,（5）计算非基变量的系数矩阵（6）计算RHS,第1步计算结束后的结果:,计算非基变量的检验数，确定换入变量：,确定换出变量：,由此得到新的基：,计算RHS,第2步计算结束后的结果：,第3步：计算非基变量（x3,x5）的检验数:,确定换出变量:,新的基:,计算B的逆矩阵：,计算非基变量的检验数:,得到最优解：,目标函数的最优值为：,