1、运筹学教案（本教案适用于 20 课时的班级）第 一 章 线性规划与单纯形法1、教学计划第 1 次课 2 学时授课章节 绪论；第一章第 1 节、第 2 节、第 3 节授课方式 理论课 讨论课 实验课 习题课 其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何意义。课堂教学重点及难点重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量
2、的线性规划问题的最优解。难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基；多个最优解如何表示。教学过程 教学方法及手段教学过程引 言运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。1.1 线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2 线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3 线性规划问题的解基、基变量、基解、基可行解和可行基。1.4 单纯形法单纯形数表的构造，要注意代数形式和表格形式的一一对应性。单纯形法迭代过程：（1）换入基变量的确定； （2）换出基变量的确定；（3）判定当前解已经最优。1
3、.5 单纯形法的进一步讨论及小结人工变量法的思想，大 M 法和两阶段法的求解思路和步骤。单纯形法小结多媒体讲解实例讲解2、教案1.1 线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例 1：某工厂要安排生产、两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？ 设备 1 2 8 台时原材料 A 4 0 16kg原材料 B 0 4 12kg单位产品的利润（元） 2 3解：设生产产品、的数量分别为 和 。1x2首先，我们的目标是要获得最大利润，即 213maz其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所
4、用的设备台时不得超过所拥有的设备台时，即 821x原材料约束：生产所用的两种原材料 A、B 不得超过所用有的原材料总数，即 164x2非负约束：生产的产品数必然为非负的，即 0,21x由此可得该问题的数学规划模型： 0,124683ma21xz总结：线性规划的一般建模步骤如下：（1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例 1 中的 和 。1x2确定决策变量是建立数学规划模型的关键所在。（2）确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。（3）确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为
5、一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小） ，从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。1.2 线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“ ”或“ ”的不等式，也可以是“=” ；虽然决策变量一般是非负的，但也可是无约束的，即，可以在 取值
6、。为),(了分析问题的简化，一般规定如下的标准形式： 0,.,.,max2122212 1nmmnxbaxaxccz非标准形式转化为标准形式：（1）若目标函数要求实现最小化 ，则可令 ，可将原问题的目ziz标函数转化为 即可。maxz（2）若约束方程为“ ”，则可在“ ”的左边加上非负的松弛变量；若约束方程为“ ”，则可在“ ”的左边减去非负的剩余变量。（3）若存在取值无约束的变量 ，则可令 ，其中，kx“kkx。0,“kx例：将如下问题转化为标准形式： 无 约 束2121,0346minxxz解：首先，用 替换 ，其中， ；43x2,43其次，在第一个约束条件的左端加上非负的松弛变量 ；5x
7、再次，在第二个约束条件的左端减去非负的剩余变量 ；6最后，令 ，将求 改为求 。由此，可得标准形如下：z zminaxz0,346202ax65431531 65xxx1.3 线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下： 0maxXBACz其中， ； ，),.(21ncCTnx),.(21 Tmb),.21mnmaaA.2121、可行解和最优解满足约束条件的所有解 成为线性规划问题的可行解，其TnxX),.(21中，使目标函数达到最大的可行解成为最优解。2、基和基解设 为约束方程组的 维矩阵，其秩为 。设 为矩阵 中的 阶AnmmBAm非奇异子矩阵（ ） ，则称 为线性
8、规划的一个基。0B不妨设前 个变量的系数矩阵为线性规划的一个基，则为对应于这个基的基变量。用高斯消去法可求得一个解TmBxX),.(21 TnxX)0.,.(21该解得非零分量的数目不大于方程个数 ，称 为基解。mX3、基可行解若基解 满足非负约束，则称其为基可行解。X4、可行基对应于基可行解的基，成为可行基。1.4 单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“ ”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得 njxbxaaxj mmnm.,21,0.221,211将其与目标函数的变换形式组成 个
9、变量、 个方.,.,121nmmccxcxz 11程的方程组。若将 看成不参与基变换的基变量，它与 的系数构成z mx,.2一个基，利用初等变换将 变为零，则可得mc,.21 miimininmii nmm bcacacbaaxxxz 11,1, 221,2 1121 .0.01 . .0.0据此，可设计如下的数表 jc1c mc1mc ncBCXbx xx xi1cx11 0 1,ma na1122b0 0 ,2 22 mcxm0 1 1,ma mnamjjz0 iic1, iinnc1列表示基变量，在这里为 ；BXmx,.21列为基变量 对应的价值系数；Cmx,.21列为约束方程的右端项；
10、b行为所有变量的价值系数；jc列的数字是在确定换入变量后，按 规则计算后填入；i最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解 0,124683max21xxz首先将其转换为标准形式，0,1246803max543211 5432xxxxz构造初始单纯形表如下： jc2 3 0 0 0BCXb1x23x45xi0 3x8 1 2 1 0 0 40 416 4 0 0 1 0 -0 5x12 0 4 0 0 1 3jjzc2 3 0 0 0由上表可得初始基可行解 TX)12,68()0由于 和 的检验数大于零，表明上述解不是最优解，由于 的检验数更1x2 2x大，所以，先以
11、为换入变量。根据 规则，可确定 为换出变量，计算得新5x表如下： jc2 3 0 0 0BCXb1x23x45xi0 3x2 1 0 1 0 -1/2 20 416 4 0 0 1 0 43 2x3 0 1 0 0 1/4 -jjzc2 0 0 0 -3/4可得新解 ，目标函数取值 。TX),1630()19z的检验数为 2，换入。根据 规则，可确定 为换出变量，计算得新表1x3x如下： jc2 3 0 0 0BCXb1x23x45xi2 1x2 1 0 1 0 -1/2 -0 48 0 0 -4 1 2 43 2x3 0 1 0 0 1/4 12jjzc0 0 -2 0 1/4得新解 ，目标
12、函数取值 。TX),8()23z的检验数为 1/4，换入。根据 规则，可确定 为换出变量，计算得：5xxjc2 3 0 0 0BCXb1x23x45xi2 1x4 1 0 0 1/4 00 54 0 0 -2 1/2 13 2x2 0 1 1/2 -1/8 0jjzc0 0 -3/2 -1/8 0得解 ，目标函数取值 。由于所有的检验都小于零，TX)4,()34z达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。1.5 单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。例：
