单纯形解法表格形式.doc

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

1、线性规划单纯形解法的表格形式教学目标1.回顾单纯形解法基本思路的基础上，理解单纯形解法表格形式的得出过程；2.理解单纯形表的得出过程基础上，学会用单纯形解法表格形式解决以下特殊形式的线性规划问题：s.t.(*)教学重点难点教学重点1.引导学生理解为什么把矩阵作为单纯性表;2.引导学生体会在计算过程中,如何运用初等变换的方法获得单纯形表;3.在用单纯形解法表格形式求解线性规划问题时,(1).如何找到初始单纯形表;(2).当检验数有负值时,进基变量与离基变量的选择.教学难点1.引导学生理解为什么把矩阵作为单纯性表;2.引导学生

2、理解为何选择(*)这种特殊形式的线性规划问题入手进行研究;3.引导学生思考探寻(*)这种特殊形式的线性规划问题的初始单纯形表形式.教学方法设计和教学过程设计（1）采用引导学生自主思考,师生共同互动的方式来推进课堂.（2）教学过程从”已知”向”未知”推广,迁移运用高等代数解线性方程组的思想方法来寻找单纯形表;同时通过穿插对单纯形法思想方法的回顾,完善单纯形表,从而得到单纯形表表格形式的解题方法.（3）在学生理解单纯形表法表格形式解题方法之后,教学过程从理论向实践过渡,首先引导学生从”特殊”到”一般”,发现(*)特殊形式的线性

3、规划问题,然后和学生一起实践单纯形解法表格形式求解线性规划问题.教学内容回顾1.线性规划问题标准形式:s.t.(*)2.线性规划单纯形解法步骤：（1）最优解检验：检验数若，令非基变量为零，目标函数值最小，相应的基可行解为最优解，目标函数值为最优值；若存在某个，再判断.（2）基可行解的转换：若，目标函数值无限减小，没有下界，原线性规划问题无最优解；否则，进行基转换。3.线性方程组解法：增广矩阵解法：通过初等变换将增广矩阵或为阶梯形解方程组.4.矩阵分块原则（乘法）：（1）左矩阵的列块数等于右矩阵的行块数；（2）左矩阵的每个列

4、快所含列数等于右矩阵的对应行块的行数.单纯形解法表格形式对进行初等行变换，将换成矩阵，这相当于左乘.则化成，得到所要的单纯形表。因而在计算过程中，只要：（1）将中基变量对应的列组成的子矩阵通过初等行变换化成单位阵；（2）将基变量对应的检验数化成零即可。特殊形式线性规划问题s.t.(*)这种形式的线性规划问题标准化后，松弛变量在约束矩阵中的列组成一个单位矩阵，我们就用这个单位阵作为基阵，松弛变量是基变量，这是一个基可行解，目标函数值为0，相应的初始单纯形表为实例：用单纯形法求解下列线性规划（LP）s.t.解：第一步：先将原问

5、题化为标准形式：s.t.第二步：列出初始单纯形表（表1.7）：表1.72311010033201120-40-45-24000此时，基可行解为，目标函数值为0.第三步：检查检验数。此时均小于零，该基可行解不是最优解，要进行基的转换。当小于零的检验书不止一个时，选取最小的一个为进基变量，迭代更快。我们选进基，则，为离基变量，于是新的基变量为和.如何从原来的单纯形表转到新的基相应的单纯性表呢？由刚才的讨论知，只要把中，相应的列向量通过初等变换化成单位阵即可，并将其检验数化为零即可，得到新的单纯性表（表1.8）：表1.82/31

6、1/31/30100/3101-1120-100-9150这样我们作了一次转换，新的基可行解为.第四步：现在均小于零，仍不是最优解，取进基，，离基，得到新的单纯形表为表1.9：表1.901-1/31-2/320101-1120001510现在所有的检验数均大于等于零，这个基可行解：是最优解原问题最优值为.