经济数学教学课件作者陈笑缘电子教案8.2课件.ppt

* 8.2　单纯形方法 8．2．1 单纯形法的基本概念 1．线性规划问题解的基本概念 以8．1．1为例，写出约束方程组的系数矩阵： ＝ 的变量 其中 代表线性规划问题的一组基，构成这组基 称为基变量，记为 ，则剩余的变量 为非基变量，记为 。 从约束条件可得 将上式代入目标函数式，得到 令 ，代入上式便得 称基本解。 ， 又因为基本解 满足所有约束条件。所以则 称为一个基本可行解。 基本可行解经济含义： 企业没有安排生产产品甲、乙。因此，A、B、C三种原料都没有被利用，所以企业的利润指标 ＝0。 2．单纯形法的基本概念 “单纯形”法的基本思路是：根据线性规划标准型的矩阵表示，从一个基本可行解（可行域的一个顶点）开始，转换到另一个基本可行解（新的顶点），并使目标函数值逐渐增大，直至取到最大值。 继续以例8．1．1为例，对上面建立的基本可行解进行最优性检验。 1）从经济意义检验基本可行解的最优性 ①先确定进基变量。选择正系数最大的那个非基变量变成基变量（称为“进基”）。如，因为 数4是非基变量 的系数，因此，确定非基变量 “进基”。 从经济意义上讲，只要在目标函数表达式中有正系数的非基变量，这表示目标函数值（利润或收益）还有增加的可能，就需要将非基变量与基变量进行对换． ②再确定出基变量。 令 ，得 从经济意义上讲：全部A种原料用于生产乙，即第一个等式中令 ＝0， 可生产乙6件；同理，令 ＝0，可生产乙 ＝4件，令 为了同时兼顾三种原料，即： ＝0， 可生产乙3件。 最小值3所在的第三个方程中的基变量 。 应出基，故称为最小比值原则。 2）．用高斯消元法求出新的基本可行解 注：①用“ ”表示变量 进基，用“ ”表示 出基。 ②交叉元 ，打上一个方括号，并称此元为主元或旋转元。 ③对原约增广矩阵实施初等行变换，称为换基迭代。 ④变换顺序首先将主元（即打方括号的元）变为l，然后主元列的其它元素都变为0。 变换后用非基变量 、 来表示基变量 得 将上式代入目标函数，于是有 得到基本可行解 ＝ ， ＝12。 3）．检验最优解 从目标函数的表达式中可以看到，非基变量的 说明目标函数值还可能增大， 系数是正数， 不是最优解。重复上述方法， 确定非基变量 进基， 出基。 矩阵变换过程如下： 得到新的基变量为 、 、 ，非基变量为 、 。 得变换后方程： 使得到另一个基本可行解 ＝ ，得 这时，基本可行解 对应的目标函数值为 ＝18。 再分析目标函数式，非基变量 的系数是正数， 还不是最优解，再重复上述步骤，先 进基，由最小比值原则，即 ， 应出基。 矩阵变换过程如下： 又得到另一个基本可行解 ＝ ，得 再观察上式，所有非基变量的系数都非正数，这说明如果要使非基变量 或 进基，就必然会使目标函数值减小。所以， 即产品甲应当生产4件，生产乙应当生产2件，企业才能得到最大利润20元。 是最优解， 训练题：用高斯消元法求解 8．2．2单纯形法的算法步骤 例8.2.1 用单纯形方法求解 解： 将问题化为标准形式 取初始基变量 ，列单纯形表进行换基迭代，见表8．5 单纯形方法基本步骤： ①利用单纯形表，确定进基与出基变量； ②换基迭代的方法：利用初等行变换方法在单纯形表中进行换基迭代。 ③最优解的检验：只有当全部 非正数时，基本可行解为最优解。 例8.2.2 用单纯形方法求解 解： 将问题化为标准形式 *