《线性代数6.3单纯形法ppt课件》由会员分享，可在线阅读，更多相关《线性代数6.3单纯形法ppt课件（29页珍藏版）》请在金锄头文库上搜索。
1、线性代数精品课程线性代数精品课程第六章 线性经济模型简介 投入产出模型简介投入产出模型简介 6.1 单纯形法单纯形法 6.3 线性规划线性规划 6.2.6.3 单纯形法单纯形法 一、引例一、引例 二、单纯形表二、单纯形表 .线性代数精品课程线性代数精品课程一、引例一、引例例例1 1 求解下列线性规划问题：求解下列线性规划问题： 解解: : 我们分以下四步完我们分以下四步完成：成： （1 1引入松弛变量引入松弛变量 ，将原问题化成标准形式：将原问题化成标准形式： .线性代数精品课程线性代数精品课程如果取标准形式的约束方程组中的变量如果取标准形式的约束方程组中的变量的系数列向量组成一个基的系数列向
2、量组成一个基, ,对应的基变量为对应的基变量为非基变量为非基变量为当非基变量取零值，即当非基变量取零值，即 得到一个基本可行解得到一个基本可行解 ，即，即 对应的目标函数值对应的目标函数值 很明显，这个解不合我们的要求。很明显，这个解不合我们的要求。 .线性代数精品课程线性代数精品课程（2 2寻找更好的可行解。寻找更好的可行解。为了使目标函数值逐步优化，可从目标函数maxS= 分析：因为的系数均为正数，所以将她们中的某一个换成基变量换入者称为进基变量，换出者称为出基变量），则目标函数值都会增加，为了使目标函数值增加得多些，我们对的系数作如下的选择： .线性代数精品课程线性代数精品课程即选取系数
3、最大的非基变量即选取系数最大的非基变量 进基，进基，因因为为基基变变量量只只能能有有三三个个，有有了了进进基基变变量量，就就必必须须从原基变量中换出一个出基，那么将原基变量从原基变量中换出一个出基，那么将原基变量中中的的哪哪一一个个换换成成非非基基变变量量呢呢？在在非非基基变变量量的的条条件件下，其标准形式下，其标准形式1 1中的约束方程可化为中的约束方程可化为.线性代数精品课程线性代数精品课程为了保证变量都要满足非负约束，所以为了保证变量都要满足非负约束，所以, , 解上述不等式组，得解上述不等式组，得 因而，因而， 应取最小比值应取最小比值 【注】上述确定【注】上述确定基变量的方法叫基变量
4、的方法叫作最小比值法。作最小比值法。它是用进基变量它是用进基变量的约束方程系数的约束方程系数列向量简称进列向量简称进基列中大于基列中大于0 0的元素作除数，的元素作除数，对应的常数作被对应的常数作被除数，取得到的除数，取得到的商的最小值。商的最小值。 .线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程对应的基阵是对应的基阵是 .线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程因而，有因而，有同样，应取最小比值同样，应取最小比值 因而，有因而，有 .线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程对应的基阵是对应的基阵是 .线性代数精品课程线
5、性代数精品课程（4 4寻找最优基可行解。寻找最优基可行解。 .线性代数精品课程线性代数精品课程对应的基阵是对应的基阵是.线性代数精品课程线性代数精品课程二、单纯形表二、单纯形表 把线性规划模型化为标准形式，从一把线性规划模型化为标准形式，从一个基本可行解开始，用换基迭代方法，个基本可行解开始，用换基迭代方法，转换到另一个基本可行解，使目标函转换到另一个基本可行解，使目标函数值逐步增大，当目标函数达到最大数值逐步增大，当目标函数达到最大值时，也就得到了最优解。这种方法值时，也就得到了最优解。这种方法称为单纯形法。称为单纯形法。 .线性代数精品课程线性代数精品课程单纯形表单纯形表例例1 1的解题过
6、程比较繁琐，为了简化叙述和的解题过程比较繁琐，为了简化叙述和计算，现将这一过程列成一张表格，称为计算，现将这一过程列成一张表格，称为单纯形表。单纯形表。 .线性代数精品课程线性代数精品课程单纯形表单纯形表检检验验数数主元素主元素主元列主元列 最大检验数最大检验数 .线性代数精品课程线性代数精品课程表6-5中第三行第二列中的数是目标函数非基化后的系数，称为检验数。从分析知道，当检验数全部非正时，目标函数才取得最优值。最大正检验数所在的列称为主元列，对应的变量为进基变量。用主元列中的正分量去除b列所对应的分量，取得最小比值的元素，称为轴心项即中括号中的数）。轴心项所在的行对应的基变量为出基变量。换
7、基变换的过程称为换基迭代，其主要一点就是在单纯形表中，利用矩阵的初等行变换，将轴心项自身“1化，主元列的其余元素“0化，因而，例1的后面三步，可分别用下列三表简单地表述。 .线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程例例2 2 用单纯形法解下列线性规划问题：用单纯形法解下列线性规划问题： 解解 引入松弛变量引入松弛变量将原问题化为标准形式：将原问题化为标准形式： 标准化标准化.线性代数精品课程线性代数精品课程用单纯形表作换基迭代，过程如下表用单纯形表作换基迭代，过程如下表6-96-9所示所示 .线性代数
8、精品课程线性代数精品课程上表中，检验数全非正，迭代结束。上表中，检验数全非正，迭代结束。最优解为最优解为 ，最优值，最优值 .线性代数精品课程线性代数精品课程.线性代数精品课程线性代数精品课程例例3 3 用单纯形法解下列线性规划问题：用单纯形法解下列线性规划问题： 解：引入松弛变量，将原问题化为标准形式：解：引入松弛变量，将原问题化为标准形式： .线性代数精品课程线性代数精品课程用单纯形表作换基迭代，过程如表用单纯形表作换基迭代，过程如表6-106-10： .线性代数精品课程线性代数精品课程作业与练习作业与练习作业：作业： 第第179页页 第第8题题1）（）（2） 课外练习：课外练习： 第第179页页 第第8题题3）（）（4）.
