教案四线性规划单纯形法.docVIP

教案四 线性规划的单纯形法 教学内容 第三节 单纯形法 1．单纯形法 2．单纯形法的基本原理 3．单纯形解法 4．大法 教学学时 9学时 教学目标 1．理解单纯形法的解题思想 2．掌握单纯形法的基本原理 3．掌握单纯形解法和大法 重点难点 重点单纯形法的基本原理、单纯形解法和大法，难点单纯形法的基本原理 教学方法及手段 教师讲解 使用多媒体课件 教学过程 一、复习巩固 1．线性规划图解法的步骤（见课件） 2．线性规划数学模型解的几种情况（见课件） 二、讲授新课 1．单纯形法基本概念（见课件） 典型方程组 一般线性规划问题标准形式的约束条件如下式（2-1），是一个有n个未知数、m个方程的线性方程组．如果这m个方程是独立的（即其中任一方程均不能由其它方程代替），则通过初等变换，必能使式（2-1）化成式（2-2）形式的同解方程组： （2-1） + + （2-2） ………………………………………………………… + 式中是重新排序后的变量．式（2-2）被称为典型方程组．即如果在一个线性方程组中的每一个方程中都有系数为1，并且不再出现在其它方程的一个未知量，则此方程组称为典型方程组． 基本变量 如果变量在某一方程中系数为1，而在其它一切方程中的系数为零，则称为该方程中的基本变量．否则为非基本变量．如式（2-2）中的为基本变量，为非基本变量．基本变量的个数为线性无关的方程的个数．事实上，个变量中任意个都可能作为基本变量，因此由排列组合知识可知，基本变量的组数为个，为未知变量的个数，为线性无关的方程的个数． 基本解 在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解．基本解的个数为个． 基本可行解 基本变量为非负的一组基本解称为基本可行解，基本可行解的个数最多不超过个． 例如，对方程组 ① ② 施行初等变换[①×（－2）＋②],可以得到： ① ③ [③×(－1)] : ① ④ [④×（－1）＋①]: ⑤ ④ 式⑤和④为典型方程组，基本变量是和，非基本变量为和．设非基本变量和为零，则和分别等于-2和5，即对应于典型方程组⑤和④，基本解为：=． 因基本变量中为负值，所以此解不是基本可行解．根据方程组①和②有4个未知变量，因此通过初等变换可得到组（即6组）典型方程组和基本解．若令和为基本变量，通过初等变换，方程组①和②可变换为： [①×（－1）＋②]: ① ③ [③×（－1/5）]: ① ④ [④×（－2）＋①] : ⑤ ④ 此时，典型方程组的基本变量为和，非基本变量为和．基本解为：，因为基本变量为非负值，所以此基本解也为基本可行解． 2．单纯形法的基本原理（见课件） 理论上已经证明，线性规划的基本可行解与可行域的顶点是一对一的．这就决定了线性规划可行域的顶点个数最多也不超过个．上面讨论线性规划问题解的特点时已指出，如果线性规划有最优解，一定可以在可行域的某个顶点处达到．因此，单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解． 在用单纯形法求解线性规划问题时，应考虑的问题： 建立初始基本可行解 在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以右端常数非负的典型方程组表示，确定初始基本可行解．在前面的阐述中，已讨论了如何将一般线性规划问题转化为标准形式的线性规划问题，如何将约束条件通过初等变换以典型方程组形式表示，以及如何得出基本可行解（最初得到的基本可行解也称初始基本可行