改进单纯形法.ppt

《改进单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、后以第2列的为主元素，进行变换:然后构造含有（2）列，而其他列都是单位列的矩阵:可得到:17重复以上的步骤，直到获得:可见，En…E2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-118以例1为例进行计算。19第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。20(3)确定换出变量表示选择>0的元素（4）基变换计算将新的基单位矩阵。计算：21（5）计算非基变量的系数矩阵（6）计算RHS22第1步计算结束后的结果:计算非基变量的检验数，确定换入变量：23确定换出变量：由此得到新的基：

4、24计算RHS第2步计算结束后的结果：25第3步：计算非基变量（x3,x5）的检验数:确定换出变量:26新的基:计算B的逆矩阵：27计算非基变量的检验数:得到最优解：目标函数的最优值为：28