运筹学——3.单纯形矩阵描述与改进单纯形法.ppt

《运筹学——3.单纯形矩阵描述与改进单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第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线性规划问题可表示为：将（2-2）式移项及整理后得到：5令

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

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

4、节改进单纯形法第1步计算结束后的结果25第2节改进单纯形法第2步：计算非基变量的检验数，确定换入变量26第2节改进单纯形法确定换出变量27由此得到新的基28计算RHS29第2步计算结束后的结果30第3步：计算非基变量（x3,x5）的检验数31确定换出变量32新的基基变换：33计算B的逆矩阵34计算非基变量的检验数35得到最优解：目标函数的最优值为：36改进单纯形法步骤1.求线性规划的标准形式，确定3.重复第2步（下标加1），直至求出最优解。37第6节对偶单纯形法在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步

5、迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cj−CBB-1Pj≤0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到最优解。38从该表看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。39对偶单纯形法的计算步骤：(1)把线性规划转化为“近似标准形式”，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以

6、下计算。(2)确定换出变量。按min｛(B-1b)i｜(B-1b)i＜0}＝(B-1b)l对应的基变量xi为换出变量(3)确定换入变量。在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。若存在αlj＜0(j=1,2,…，n),计算40按θ规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4)以αlk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)～(4)。41例6用对偶单纯形法求解minw=2x1+3x2+4x3x1+2x2+x3≥32x1−x2+3x3

7、≥4x1，x2，x3≥0解：先将此问题化成下列形式，以便得到对偶问题的初始基可行解maxz=−2x1−3x2−4x3−x1−2x2−x3+x4=−3−2x1+x2−3x3+x5=−4xj≥0，j=1,2,…,542例6的初始单纯形表，见表2-6。从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。43换出变量的确定：换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。按上述对偶单纯形法计算步骤(2)，即按min｛(B-1b)i

8、｜(B-1b)i＜0＝(