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

单纯形法的矩阵描述单纯形法的矩阵描述1设线设线性性规规划划问题问题可以用如下矩可以用如下矩阵阵形式表示：形式表示：目目标标函数函数 max z=CX 约约束条件束条件 AXb 非非负负条件条件 X02 将将该该线线性性规规划划问问题题的的约约束束条条件件加加入入松松弛弛变变量后，得到标准型量后，得到标准型：max z=CX+0Xs AX+IXs=b X，X s0 其中，其中，I 是是mm单单位矩位矩阵阵。3 若若以以Xs为为基基变变量量，并并标标记记成成XB，可可将将系系数数矩矩阵阵(A，I)分分为为(B，N)两两块块。B是是基基变变量量的的系系数数矩矩阵阵，N是是非非基基变变量量的系数矩的系数矩阵阵。并同。并同时时将决策将决策变变量也分量也分为为两部分：两部分：相相应应地地可可将将目目标标函函数数系系数数C分分为为两两部部分分：CB和和CN，分分别对应别对应于基于基变变量量XB和非基和非基变变量量XN，并且，并且记记作作:C=（CB,CN）4若经过迭代运算后，可表示为：若经过迭代运算后，可表示为：相应有相应有:5线性规划问题可表示为：线性规划问题可表示为：6将（将（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而后以第而后以第2列的列的 为主元素，进行变换为主元素，进行变换:然后构造含有（然后构造含有（2）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵:可得到可得到:17重复以上的步骤，直到获得重复以上的步骤，直到获得:可见，可见，EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵用这方法可以求得单纯形法的基矩阵B的逆矩阵的逆矩阵B-1 18以例以例1为例进行计算。为例进行计算。19第第1步：确定初始基，初始基变量步：确定初始基，初始基变量;确定换入，换出变量确定换入，换出变量（1）确定初始基和初始基变量：）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。）计算非基变量的检验数，确定换入变量。20(3)确定换出变量确定换出变量表示选择0的元素（4）基变换计算）基变换计算将新的基将新的基 单位矩阵。计算：单位矩阵。计算：21（5）计算非基变量的系数矩阵）计算非基变量的系数矩阵（6）计算）计算RHS22第第1步计算结束后的结果步计算结束后的结果:计算非基变量的检验数，确定换入变量：计算非基变量的检验数，确定换入变量：23确定换出变量：确定换出变量：由此得到新的基：由此得到新的基：24计算计算RHS第第2步计算结束后的结果：步计算结束后的结果：25第第3步：步：计计算非基算非基变变量（量（x3,x5）的）的检验检验数数:确定换出变量确定换出变量:26新的基新的基:计算计算B的逆矩阵：的逆矩阵：27计算非基变量的检验数计算非基变量的检验数:得到最优解：得到最优解：目标函数的最优值为：目标函数的最优值为：28