《教案四--线性规划的单纯形法》由会员分享，可在线阅读，更多相关《教案四--线性规划的单纯形法（19页珍藏版）》请在金锄头文库上搜索。
1、教案四 线性规划的单纯形法教学内容 第三节 单纯形法1单纯形法2单纯形法的基本原理3单纯形解法4大法教学学时 9学时教学目标 1理解单纯形法的解题思想2掌握单纯形法的基本原理3掌握单纯形解法和大法重点难点 重点单纯形法的基本原理、单纯形解法和大法，难点单纯形法的基本原理教学方法及手段 教师讲解 使用多媒体课件教学过程 一、复习巩固 1线性规划图解法的步骤（见课件）2线性规划数学模型解的几种情况（见课件）二、讲授新课1单纯形法基本概念（见课件）典型方程组一般线性规划问题标准形式的约束条件如下式（2-1），是一个有n个未知数、m个方程的线性方程组如果这m个方程是独立的（即其中任一方程均不能由其它方
2、程代替），则通过初等变换，必能使式（2-1）化成式（2-2）形式的同解方程组： （2-1） + + （2-2） + 式中是重新排序后的变量式（2-2）被称为典型方程组即如果在一个线性方程组中的每一个方程中都有系数为1，并且不再出现在其它方程的一个未知量，则此方程组称为典型方程组基本变量如果变量在某一方程中系数为1，而在其它一切方程中的系数为零，则称为该方程中的基本变量否则为非基本变量如式（2-2）中的为基本变量，为非基本变量基本变量的个数为线性无关的方程的个数事实上，个变量中任意个都可能作为基本变量，因此由排列组合知识可知，基本变量的组数为个，为未知变量的个数，为线性无关的方程的个数基本解在典
3、型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解基本解的个数为个基本可行解基本变量为非负的一组基本解称为基本可行解，基本可行解的个数最多不超过个例如，对方程组 施行初等变换（2）,可以得到： (1) : （1）: 式和为典型方程组，基本变量是和，非基本变量为和设非基本变量和为零，则和分别等于-2和5，即对应于典型方程组和，基本解为：=因基本变量中为负值，所以此解不是基本可行解根据方程组和有4个未知变量，因此通过初等变换可得到组（即6组）典型方程组和基本解若令和为基本变量，通过初等变换，方程组和可变换为：（1）: （1/5）: （2） : 此时，典型方程组的基本变量为和，非基本变量为
4、和基本解为：，因为基本变量为非负值，所以此基本解也为基本可行解2单纯形法的基本原理（见课件）理论上已经证明，线性规划的基本可行解与可行域的顶点是一对一的这就决定了线性规划可行域的顶点个数最多也不超过个上面讨论线性规划问题解的特点时已指出，如果线性规划有最优解，一定可以在可行域的某个顶点处达到因此，单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解在用单纯形法求解线性规划问题时，应考虑的问题：建立初始基本可行解 在用单纯形法求解时，首先应将线性规划问题以标准形
5、式表达、约束条件以右端常数非负的典型方程组表示，确定初始基本可行解在前面的阐述中，已讨论了如何将一般线性规划问题转化为标准形式的线性规划问题，如何将约束条件通过初等变换以典型方程组形式表示，以及如何得出基本可行解（最初得到的基本可行解也称初始基本可行解），此处不再赘述经过变换，典型方程组和初始基本可行解可用式（2-3）表示： + + （2-3） + 初始基本可行解：最优性检验 得到一个基本可行解后，我们要判断它是不是最优解一般情况下，经过迭代后式（2-3）变为 （） （2-4）将式（2-4）代入目标函数式，整理后得 （2-5）令 , , 于是 （2-6） 由于当时，即（），所以式（2-6）也可
6、写作 再令 为变量的检验数则 （2-7）（1）最优解判别 若为基本可行解，且对一切,有，则为最优解（2）无有限最优解判别 若为一基本可行解，有一个0，且对一切有（为约束条件方程中的系数，），那么该线性规划问题无有限最优解（或称有无界解或无最优解）事实上，应用向量的乘法，可以将检验数的求法表示得简明一些令表示目标函数中变量的系数，表示基本变量在目标函数中的系数行向量，表示变量在典型方程中的系数列向量，则 （2-8）基本变量的检验数总等于0目标函数值.基本可行解的改进 若初始基本可行解不是最优解及不能判别无最优解时，需找一个新的基本可行解具体方法是：首先确定进基变量，再确定出基变量进基变量的确定：
7、由式（2-7）可知，检验数对线性规划问题的实际意义是：表示当变量增加1个单位时，目标函数的增加量；其经济意义表示相对利润当时，说明非基本变量增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加这时要将某个非基本变量换到基本变量中去（称为进基变量）为了使目标函数值增长最快，所以应选择值最大的一项所对应的非基本变量进基,. 则对应的为进基变量进基变量所在的列（）称为枢列出基变量的确定：当进基变量确定后（假设是进基变量），出基变量的选定是应用“最小比值规则”即用此时的各约束方程右端的常数项（非负数）与相应方程中的正系数相比，并选取最小商值的基本变量为出基变量（将由基本变量变为非基本变量）
8、出基变量所在的行（）称为枢行枢行与枢列交点处的元素（）称为枢元然后通过初等变换，将约束条件转为关于新的基本变量的典型方程组，并求得新的基本可行解对于新的基本可行解可再进行上述的最优性检验3 单纯形解法（见课件）上面介绍的单纯形法原理看似复杂，但如用表格形式计算，则比较容易操作单纯形法的计算步骤：第1步：找出初始基本可行解，建立初始单纯形表第2步：检验对应于非基本变量的检验数，若对所有的，则已得到最优解，计算最优值，即可结束否则，转入下一步第3步：在所有中，若有一个对应的系数列向量，即对均有，则此问题无有限最优解（或称有无界解或无最优解），停止计算否则转入下一步第4步：根据，确定为进基变量，再依
9、据“最小比值规则”（）确定为出基变量第5步：实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第二步，一直到没有新的非基本变量可以改善目标函数为止若线性规划模型为： 上述计算步骤仍有效，只是其中的第二步改为：若对所有的（），则已得到最优解；第三步改为在所有中，若有一个对应的系数列向量，即对均有，则此问题无有限最优解（或称有无界解或无最优解）；第四步改为，确定为进基变量例2-8 现以例2-1来说明单纯形法的表上解法解 首先将线性规划问题标准化，引入松弛变量、，则： 此时约束方程组已为典型方程组，根据上述线性规划模型可以列出初始单纯形表（表2-4）：
10、表2-4 单纯形法求解例2-1（1）2003000000022100012601201008404000101600400011232003000000=0表2-4中： 为典型方程组中变量的系数，为规划中出现的变量，为变量在目标函数中的系数，为基本变量，为基本变量在目标函数中的系数，为典型方程组右端常数项（非负值），为确定出基变量的商值， （），为变量的检验数，为此时目标函数值，根据初始单纯形表可以看出：初始基本可行解是，此时目标函数值0检验数200200 300300 =0（基本变量的检验数总等于零）由于，所以初始基本可行解非最优解又由于，所以确定为进基变量进一步求最小值：即从第4个方程中算
11、出的商值最小，而第4个方程中的基本变量是，于是为出基变量表中给第4个约束方程中的系数4加上方括号以突出其为枢元接下去是将取代，表2-4中的约束方程化为以、和为基本变量，和为非基本变量的典型方程从表2-4中可以看到，只需对方程组实行初等变换，使枢元位置变成1，而枢列中的其它元素变为零就可以了此处可先将第4个方程除以4，使枢元位置变成1；然后用新得到的第4个方程乘以（-2）后分别加到第1个和第2个方程上，使枢列中的第1个和第二个方程所在位变为零这样我们可以得到新的单纯形表（表2-5）表2-5给出的新的基本可行解是0，3，6，2，16，0此时目标函数值900检验数200-200 0- =0（基本变量的检验数总等于零）表2-5 单纯形法求解例2-1（2）2003000000020100630100102204000101643000100032000000-75=900由于，所以此时基本可行解非最优解，确定为进基变量进一步计算最小值：即从第
