运筹学教案 - 湖南工学院欢迎您

《运筹学教案 - 湖南工学院欢迎您》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《运筹学》教案（本教案适用于20课时的班级）第一章线性规划与单纯形法1、教学计划第1次课2学时授课章节绪论；第一章第1节、第2节、第3节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何意义。课堂教学重点及难点重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握非标准形式的几

2、种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性规划问题的最优解。难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基；多个最优解如何表示。教学过程教学过程教学方法及手段引言运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。1.1线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3线性规划问题的解基、基变量、基解、基可行解和可行基。1.4单纯形法单纯形数表的构

3、造，要注意代数形式和表格形式的一一对应性。单纯形法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最优。1.5单纯形法的进一步讨论及小结人工变量法的思想，大M法和两阶段法的求解思路和步骤。单纯形法小结多媒体讲解实例讲解2、教案1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1：某工厂要安排生产Ⅰ、Ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？ⅠⅡ设备128台时原材料A4016kg原材料

4、B0412kg单位产品的利润（元）23解：设生产产品Ⅰ、Ⅱ的数量分别为和。首先，我们的目标是要获得最大利润，即其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即原材料约束：生产所用的两种原材料A、B不得超过所用有的原材料总数，即非负约束：生产的产品数必然为非负的，即由此可得该问题的数学规划模型：总结：线性规划的一般建模步骤如下：（1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的和。确定决策变量是建立数学规划模型的关键所在。（2）确定

5、目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。（3）确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标

6、函数最大或最小的角度看，这是最优化问题。1.2线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“”或“”的不等式，也可以是“=”；虽然决策变量一般是非负的，但也可是无约束的，即，可以在取值。为了分析问题的简化，一般规定如下的标准形式：非标准形式转化为标准形式：（1）若目标函数要求实现最小化，则可令，可将原问题的目标函数转化为即可。（2）若约束方程为“”，则可在“”的左边加上非负的松弛变量；若约束方程为“”，则可在“”的左边减去非负的剩余变量。

7、（3）若存在取值无约束的变量，则可令，其中，。例：将如下问题转化为标准形式：解：首先，用替换，其中，；其次，在第一个约束条件的左端加上非负的松弛变量；再次，在第二个约束条件的左端减去非负的剩余变量；最后，令，将求改为求。由此，可得标准形如下：1.3线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：其中，；，1、可行解和最优解满足约束条件的所有解成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解。2、基和基解设为约束方程组的维矩阵，其秩为。设为矩阵中的阶非奇异子矩阵（），则

8、称为线性规划的一个基。不妨设前个变量的系数矩阵为线性规划的一个基，则为对应于这个基的基变量。用高斯消去法可求得一个解该解得非零分量的数目不大于方程个数，称为基解。3、基可行解若基解满足非负约束，则称其为基可行解。4、可行基对应于基可行解的基，成为可行基。1.4单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，