单纯形解法表格形式.doc

线性规划单纯形解法的表格形式教学目标1. 回顾单纯形解法基本思路的基础上，理解单纯形解法表格形式的得出过程；2. 理解单纯形表的得出过程基础上，学会用单纯形解法表格形式解决以下特殊形式的线性规划问题： s.t. (*) 教学重点难点教学重点1. 引导学生理解为什么把矩阵作为单纯性表;2. 引导学生体会在计算过程中,如何运用初等变换的方法获得单纯形表;3. 在用单纯形解法表格形式求解线性规划问题时,(1).如何找到初始单纯形表;(2).当检验数有负值时,进基变量与离基变量的选择.教学难点1. 引导学生理解为什么把矩阵作为单纯性表;2. 引导学生理解为何选择(*)这种特殊形式的线性规划问题入手进行研究;3. 引导学生思考探寻(*)这种特殊形式的线性规划问题的初始单纯形表形式.教学方法设计和教学过程设计（1）采用引导学生自主思考,师生共同互动的方式来推进课堂.（2）教学过程从”已知”向”未知”推广,迁移运用高等代数解线性方程组的思想方法来寻找单纯形表;同时通过穿插对单纯形法思想方法的回顾,完善单纯形表,从而得到单纯形表表格形式的解题方法.（3）在学生理解单纯形表法表格形式解题方法之后,教学过程从理论向实践过渡,首先引导学生从”特殊”到”一般”,发现(*)特殊形式的线性规划问题,然后和学生一起实践单纯形解法表格形式求解线性规划问题.教学内容回顾1. 线性规划问题标准形式: s.t. (*) 2. 线性规划单纯形解法步骤：（1） 最优解检验：检验数若，令非基变量为零，目标函数值最小，相应的基可行解为最优解，目标函数值为最优值；若存在某个，再判断.（2） 基可行解的转换：若，目标函数值无限减小，没有下界，原线性规划问题无最优解；否则，进行基转换。3. 线性方程组解法：增广矩阵 解法：通过初等变换将增广矩阵或为阶梯形解方程组.4. 矩阵分块原则（乘法）：（1） 左矩阵的列块数等于右矩阵的行块数；（2） 左矩阵的每个列快所含列数等于右矩阵的对应行块的行数.单纯形解法表格形式对进行初等行变换，将换成矩阵，这相当于左乘.则化成，得到所要的单纯形表。因而在计算过程中，只要：（1） 将中基变量对应的列组成的子矩阵通过初等行变换化成单位阵；（2） 将基变量对应的检验数化成零即可。特殊形式线性规划问题 s.t. (*) 这种形式的线性规划问题标准化后，松弛变量在约束矩阵中的列组成一个单位矩阵，我们就用这个单位阵作为基阵，松弛变量是基变量，这是一个基可行解，目标函数值为0，相应的初始单纯形表为 实例：用单纯形法求解下列线性规划（LP） s.t. 解：第一步：先将原问题化为标准形式： s.t. 第二步：列出初始单纯形表（表1.7）：表1.72311010033201120-40-45-24000此时，基可行解为，目标函数值为0.第三步：检查检验数。此时均小于零，该基可行解不是最优解，要进行基的转换。当小于零的检验书不止一个时，选取最小的一个为进基变量，迭代更快。我们选进基，则，为离基变量，于是新的基变量为和.如何从原来的单纯形表转到新的基相应的单纯性表呢？由刚才的讨论知，只要把中，相应的列向量通过初等变换化成单位阵即可，并将其检验数化为零即可，得到新的单纯性表（表1.8）：表1.82/311/31/30100/3101-1120-100-9150 这样我们作了一次转换，新的基可行解为.第四步：现在均小于零，仍不是最优解，取进基，离基，得到新的