举例说明单纯形法的计算步骤

《举例说明单纯形法的计算步骤》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性规划与单纯形法2.4、2.5单纯形法的计算步骤及其进一步讨论教学目的使学生理解并掌握运用单纯形表计算线性规划问题的步骤及解法。教学要求熟悉：单纯型法计算中出现退化问题时的解决方法掌握：运用单纯形表计算线性规划问题的步骤及解法，大M法求解线性规划问题。了解：两阶段法求解线性规划问题。教学重难点重点：运用单纯型表计算线性规划问题的步骤及解法，大M法求解线性规划问题。难点：基可行解原表及单纯型表的对应关系。教学方法启发式教学模式教学提纲一、举例说明单纯形法的计算步骤二、单纯形法的进一步讨论——大M法1818第2章线性规划与单纯形法2.4、2.

2、5单纯形法的计算步骤及其进一步讨论一、举例说明单纯形法的计算步骤为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。线性规划的方程组为了便于迭代运算，可将上述方程组写成增广矩阵形式若将z看作不参与基变换的基变量，它与的系数构成一个基，这时可采用行初等变换将c1,c2,…,cm变换为零，使其对应的系数矩阵为单位矩阵。得到18可根据上述增广矩阵设计计算表，表1-2注：表1-2的说明1、列中填入基变量，这里是；2、列中填入基变量的价值系数，这

3、里是；它们是与基变量相对应的；3、列中填入约束方程组右端的常数；4、行中填入基变量的价值系数；5、列的数字是在确定换入变量后，按规则计算后填入；6、最后一行称为检验数行，对应各非基变量的检验数是18表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。计算步骤：(1)按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2)计算各非基变量xj的检验数，检查检验数，若所有检验数，则已得到最优解，可停止计算。否则转入下一步。(3)在中，若有某个对应的系数列向量，则此问题是无界，停止计算。否则，转入下一步。(4)根据，确定为换入变量，按规则计算

4、(5)以为主元素进行迭代(即用高斯消去法或称为旋转运算)，把所对应的列向量将列中的换为，得到新的单纯形表。重复(2)～(5)，直到终止。现用例1的标准型来说明上述计算步骤(1)取松弛变量18为基变量，它对应的单位矩阵为基。这就得到初始基可行解将有关数字填入表中，得到初始单纯形表，见表1-3。表中左上角的是表示目标函数中各变量的价值系数。在列填入初始基变量的价值系数，它们都为零。表1-3目标函数中各变量的价值系数。→23000Xb08121008/2=401640010-0120[4]00112/4=3023000计算非基变量的检验数各非基变量的检

5、验数为填入表1-3的底行对应非基变量处。进行（2），（3）（2）因检验数都大于零，且P1，P2有正分量存在，转入下一步；（3），对应的变量为换入变量，计算。它所在行对应的为换出变量，所在列和所在行的交叉处，[4]称为主元素或枢元素(pivotelement)，进行（4）。（4）以[4]为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为,在列中将替换,于是得到新表1-4.18换人变量换出变量主元素（5）检查表1-4的所有,这时有；说明应为换入变量。重复(2)～(4)的计算步骤，得表1-5。cj→23000CBXBbx1x2x3x4x5θ2x

6、121010-1/2-0x4800-41[2]43x2301001/412-z-1300-201/4换人变量换出变量主元素还存在检验数大于0，继续进行。(6)表1-6最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解23000θ241011/400400-21/2132011/2-1/80-1400-3/2-1/8018（注：）最优解目标函数的最大值例2、用单纯形法求解下列线性规划问题解：首先把原问题化为标准形式，即然后取变量的系数列向量组成基，那么，基对应的单纯形表以及换基迭代寻找最优基的过程如下所示。18二、单纯

7、形法的进一步讨论——大M法1、人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量得到以为基变量，并可得到一个单位矩阵。令非基变量为零，便可得到一个初始基可行解注：1、因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。2、基变量中不再含有非零的人工变量，这表示原问题有解。3、若在最终表中当所有，而在其中还有某个非零人工变量，这表示原问题无可行解。以下讨论如何解含有人工变量的线性规划问题。2、大M法在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目

8、标函数取值不受影响；为此假定人工变量在目标函数中的系数为()(为任意大的正数)，这样目标函数要实现最大化时，必须把人工变量从基变量换出。