《运筹学》课程教学资源（授课教案，共八章讲义）

《运筹学》教案（本教案适用于20课时的班级）

《运筹学》教案 （本教案适用于 20 课时的班级）

第一章线性规划与单纯形法1、教学计划

第一章 线性规划与单纯形法 1、教学计划

第1次课2学时绪论；第一章第1节、第2节、第3节授课章节授课方式口理论课口讨论课口实验课口习题课口其他了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。课堂教学掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了目的及要求解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何意义。重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式：在标准形中，要求学生掌握非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性课堂教学规划问题的最优解。重点及难点难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基：多个最优解如何表示，教学过程教学方法及手段引言多媒体讲解运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。实例讲解1.1线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3线性规划问题的解教学过程基、基变量、基解、基可行解和可行基。1.4单纯形法单纯形数表的构造，要注意代数形式和表格形式的一一对应性。单纯形法选代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最优。1.5单纯形法的进一步讨论及小结人工变量法的思想，大M法和两阶段法的求解思路和步骤。单纯形法小结

第 1 次课 2 学时 授课章节 绪论；第一章第 1 节、第 2 节、第 3 节 授课方式 □√理论课 □讨论课 □实验课 □习题课 □其他 课堂教学 目的及要求 了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。 掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了 解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何 意义。 课堂教学 重点及难点 重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉 矩阵形式；在标准形中，要求学生掌握非标准形式的几种具体情形 及其相应的标准化方法；如何用几何的方法求两个决策变量的线性 规划问题的最优解。 难点：线性规划的基本概念，例如基、基变量、基解、基可行解和 可行基；多个最优解如何表示。 教学过程 教学过程 教学方法及手段 引 言 运筹学模型，运筹学发展历史与现状，研究 方法；考核方法与教学大纲等。 1.1 线性规划问题及其数学模型 线性规划的数学模型： 变量的确定、约束条件与目标函数。 1.2 线性规划问题的标准形式 线性规划的标准形式及非标准形式的标准 化处理。 1.3 线性规划问题的解 基、基变量、基解、基可行解和可行基。 1.4 单纯形法 单纯形数表的构造，要注意代数形式和表格 形式的一一对应性。 单纯形法迭代过程：（1）换入基变量的确定； （2）换出基变量的确定；（3）判定当前解已经 最优。 1.5 单纯形法的进一步讨论及小结 人工变量法的思想，大 M 法和两阶段法的求 解思路和步骤。 单纯形法小结 多媒体讲解 实例讲解

2、教案1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1：某工厂要安排生产丨、Ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？II112设备8台时40原材料A16kg04原材料B12kg23单位产品的利润（元）解：设生产产品1、ⅡI的数量分别为x和x2。首先，我们的目标是要获得最大利润，即max z = 2x, +3x2其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即X, +2x2≤8原材料约束：生产所用的两种原材料A、B不得超过所用有的原材料总数即4x, ≤164xz ≤12非负约束：生产的产品数必然为非负的，即Xi,x, ≥0由此可得该问题的数学规划模型：max z= 2x, +3x2x+2x,≤84x, ≤164x,≤12( xi,x2 ≥0总结：

2、教案 1.1 线性规划问题及其数学模型 线性规划模型的建立就是将现实问题用数学的语言表达出来。 例 1：某工厂要安排生产Ⅰ、Ⅱ两种产品，每单位产品生产所需的设备、材 料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？ Ⅰ Ⅱ 设备 1 2 8 台时 原材料 A 4 0 16kg 原材料 B 0 4 12kg 单位产品的利润（元） 2 3 解：设生产产品Ⅰ、Ⅱ的数量分别为 1 x 和 2 x 。 首先，我们的目标是要获得最大利润，即 max 2 1 3 2 z = x + x 其次，该生产计划受到一系列现实条件的约束， 设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即 x1 + 2x2  8 原材料约束：生产所用的两种原材料 A、B 不得超过所用有的原材料总数， 即 4x1 16 4x2 12 非负约束：生产的产品数必然为非负的，即 x1 , x2  0 由此可得该问题的数学规划模型：           +  = + , 0 4 12 4 16 2 8 max 2 3 1 2 2 1 1 2 1 2 x x x x x x z x x 总结：

线性规划的一般建模步骤如下：（1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的x,和x2。确定决策变量是建立数学规划模型的关键所在。（2）确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。（3）确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。1.2线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“≤”或“≥”的不等式，也可以是“二”；虽然决策变量一般是非负的，但也可是无约束的，即，可以在一00,+0)取值。为了分析问题的简化，一般规定如下的标准形式：max z= Cx, +C,X2 +.,+c,xnaux,+ai2x,+.+ainx,=ba21x,+a22x2+.,+a2nx,=b2*+*amx,+am2X2+...,+ammX,=bmX,X2...X,≥0非标准形式转化为标准形式：（1）若目标函数要求实现最小化minz，则可令2=-z，可将原问题的目标函数转化为maxz即可。（2）若约束方程为“≤”，则可在“≤”的左边加上非负的松弛变量；若约束方程为“≥”，则可在“≥”的左边减去非负的剩余变量

线性规划的一般建模步骤如下： （1）确定决策变量 确定决策变量就是将问题中的未知量用变量来表示，如例 1 中的 1 x 和 2 x 。 确定决策变量是建立数学规划模型的关键所在。 （2）确定目标函数 确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。 （3）确定约束条件 将现实的约束用数学公式表示出来。 线性规划数学模型的特点 （1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题 的不同，追求的目标可以是最大化，也可以是最小化。 （2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。 （3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备 选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函 数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小 的角度看，这是最优化问题。 1.2 线性规划问题的标准形式 根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要 求最小化的；约束条件可以是“  ”或“  ”的不等式，也可以是“=”；虽然决 策变量一般是非负的，但也可是无约束的，即，可以在 (−,+ ) 取值。为了分析 问题的简化，一般规定如下的标准形式：           + + + = + + + = + + + = = + + + , ,., 0 ., . ., ., max ., 1 2 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 1 1 2 2 n m m mn n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b z c x c x c x 非标准形式转化为标准形式： （1）若目标函数要求实现最小化 min z ，则可令 z' = −z ，可将原问题的目标 函数转化为 max z' 即可。 （2）若约束方程为“  ”，则可在“  ”的左边加上非负的松弛变量；若约 束方程为“  ”，则可在“  ”的左边减去非负的剩余变量

（3）若存在取值无约束的变量x，则可令x=x-x，其中，x，x≥0。例：将如下问题转化为标准形式：min z = Xj + 2x22x, +3x, ≤6X +x, ≥4X - X2 =3x≥0,x,无约束解：首先，用x-x替换x2，其中，x,x≥0；其次，在第一个约束条件的左端加上非负的松弛变量xs；再次，在第二个约束条件的左端减去非负的剩余变量x6；最后，令z=-z，将求minz改为求maxz。由此，可得标准形如下：max z'= -x, -2x, +2x4 +0xs +0x62x, +3x,-3x +x,=6X +X-4-X=4X, -X, +x =3[X,,4,X5,X≥01.3线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：max z = Cx[AX = B[X≥0其中,C=(cj.c2..c,); X=(X2...)",B=b,b..b.)"[auai2ana21a22a2nA=amnLamlam21、可行解和最优解满足约束条件的所有解X=（x,x2x,）成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解

（3）若存在取值无约束的变量 k x ，则可令 ' " k k k x = x − x ，其中， , 0 ' " xk xk  。 例：将如下问题转化为标准形式：         − = +  +  = + 2无约束 1 2 1 2 1 2 1 2 0, 3 4 2 3 6 min 2 x x x x x x x x z x x 解： 首先，用 3 4 x − x 替换 2 x ，其中， x3 , x4  0 ； 其次，在第一个约束条件的左端加上非负的松弛变量 5 x ； 再次，在第二个约束条件的左端减去非负的剩余变量 6 x ； 最后，令 z' = −z ，将求 min z 改为求 max z' 。由此，可得标准形如下：         − + = + − − = + − + = = − − + + + , , , , 0 3 4 2 3 3 6 max ' 2 2 0 0 1 3 4 5 6 1 3 4 1 3 4 6 1 3 4 5 1 3 4 5 6 x x x x x x x x x x x x x x x x z x x x x x 1.3 线性规划问题的解 首先，将线性问题的标准形式用矩阵和向量形式表示如下：     = = 0 max X AX B z CX 其中， ( , ,., ) 1 2 n C = c c c ； T n X (x , x ,., x ) = 1 2 ， T B b b bm , ,., ) = 1 2             = m m mn n n a a a a a a a a a A . . . . . . . 1 2 21 22 2 11 12 1 1、可行解和最优解 满足约束条件的所有解 T n X (x , x ,., x ) = 1 2 成为线性规划问题的可行解，其 中，使目标函数达到最大的可行解成为最优解

2、基和基解设A为约束方程组的mxn维矩阵，其秩为m。设B为矩阵A中的mxm阶非奇异子矩阵（B±0），则称B为线性规划的一个基。不妨设前m个变量的系数矩阵为线性规划的一个基，则X=(x,x2.x.）为对应于这个基的基变量。用高斯消去法可求得一个解X= (X,X.. ..,0)该解得非零分量的数目不大于方程个数m，称X为基解。3、基可行解若基解X满足非负约束，则称其为基可行解。4、可行基对应于基可行解的基，成为可行基。1.4单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“<”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得X, +ai,m+IXmI +...+ai,x,=b,X2+a2,m1Xm+1+...+a2nxn=b,.....Xm+amm+Xm+1+...+ammx,=bmx, ≥0,j=1,...n将其与目标函数的变换形式-z+c,x,+C2×2+.,+Cmm+Cm1m+.,+C,x，=0组成n+1个变量、m+1个方程的方程组。若将=看成不参与基变换的基变量，它与x,x2…,x.的系数构成一个基，利用初等变换将ci,C2.C变为零，则可得

2、基和基解 设 A 为约束方程组的 mn 维矩阵，其秩为 m 。设 B 为矩阵 A 中的 mm 阶非 奇异子矩阵（ B  0 ），则称 B 为线性规划的一个基。 不妨设前 m 个变量的系数矩阵为线性规划的一个基，则 T B m X (x , x ,., x ) = 1 2 为对应于这个基的基变量。用高斯消去法可求得一个解 T n X (x , x ,., x ,0,.,0) = 1 2 该解得非零分量的数目不大于方程个数 m ，称 X 为基解。 3、基可行解 若基解 X 满足非负约束，则称其为基可行解。 4、可行基 对应于基可行解的基，成为可行基。 1.4 单纯形法 一、单纯形表 考察一种最简单的形式：目标函数最大化、所有约束条件均为“  ”。利用 所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理， 重新对变量及系数矩阵进行编号，得           = + + + = + + + = + + + = + + + + + + x j n x a x a x b x a x a x b x a x a x b j m m m m mn n m m m n n m m n n 0, 1,2., . . . . , 1 1 2 2, 1 1 2 2 1 1, 1 1 1 1 将其与目标函数的变换形式 − z + c1 x1 + c2 x2 +.,+cm xm + cm+1 xm+1 +.,+cn xn = 0 组成 n +1 个变量、 m+1 个方程 的方程组。若将 z 看成不参与基变换的基变量，它与 m x , x ,., x 1 2 的系数构成一个 基，利用初等变换将 m c ,c ,.,c 1 2 变为零，则可得

bX-2xX2xmXm+l.01br00ain...ai,m+10010b2a2n"..a2,m+1.................bm0001amnamm+l...-Nc.aNca2eb1000..Cm+1Cali=1i=li=l据此，可设计如下的数表..-cjCmCm+lC.ci0,b.XBCBXiXmXm+1Xn10...b,a1,m+1ain0,cixi00....b202a2nC2a2,m+1X2..........01.bm0mCmXmα m,m+Iamn0...Cj-2jc,aic,ai.m+i=li=1X,列表示基变量，在这里为x,x2XmC.列为基变量x,x2x对应的价值系数；b列为约束方程的右端项；c,行为所有变量的价值系数；0,列的数字是在确定换入变量后，按θ规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解max z=2xi+3x2[x +2x2 ≤84x,≤164x, ≤12X,x2 ≥0首先将其转换为标准形式

   = = = + + + + + + − − − − m i i i m i n i i n m i m i i m m m m n m m n m n m m n c c a c c a c b a a b a a b a a b z x x x x x b 1 1 1 , 1 1 1 , 1 , 1 2, 1 2 2 1, 1 1 1 1 2 1 1 0 0 . 0 . 0 0 0 . 1 . . . . . . . . . . 0 0 1 . 0 . 0 1 0 . 0 . . . 据此，可设计如下的数表 j c 1 c . m c m+1 c . n c  i CB XB b 1 x . m x m+1 x . n x 1 c 1 x 1 b 1 . 0 a1,m+1 . n a1 1 2 c 2 x 2 b 0 . 0 a2,m+1 . a2n  2 . . . . . . . . . . m c m x mb 0 . 1 am,m+1 . amn  m j j c − z 0 . = + − + m i m iai m c c 1 1 , 1 . = − m i n iain c c 1 XB 列表示基变量，在这里为 m x , x ,., x 1 2 ； CB 列为基变量 m x , x ,., x 1 2 对应的价值系数； b 列为约束方程的右端项； j c 行为所有变量的价值系数；  i 列的数字是在确定换入变量后，按  规则计算后填入； 最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。 例，求解           +  = + , 0 4 12 4 16 2 8 max 2 3 1 2 2 1 1 2 1 2 x x x x x x z x x 首先将其转换为标准形式

maxz=2x,+3x,+0x,+0x,+0xsX,+2x2+=84x, +x4 =164x2 +x, = 12,x2,x,x,x,≥0构造初始单纯形表如下：23000ceCBXBbX3xsXIX2X420811004X300164010X4一[4] 00012013Xs23000c,-2j由上表可得初始基可行解X(0) = (0,0,8,16,12)由于x和x,的检验数大于零，表明上述解不是最优解，由于x,的检验数更大，所以，先以x，为换入变量。根据θ规则，可确定x。为换出变量，计算得新表如下：23000c,0,bCBXBX3xsXiX4X202[1] 0102X3-1/2016400104X43301001/4X22000-3/4Cj-zj可得新解X()）=03,2,16,0)，目标函数取值z=9。x的检验数为2，换入。根据θ规则，可确定x为换出变量，计算得新表如

        + = + = + + = = + + + + , , , , 0 4 12 4 16 2 8 max 2 3 0 0 0 1 2 3 4 5 2 5 1 4 1 2 3 1 2 3 4 5 x x x x x x x x x x x x z x x x x x 构造初始单纯形表如下： j c 2 3 0 0 0  i CB XB b 1 x 2 x 3 x 4 x 5 x 0 3 x 8 1 2 1 0 0 4 0 4 x 16 4 0 0 1 0 - 0 5 x 12 0 [4] 0 0 1 3 j j c − z 2 3 0 0 0 由上表可得初始基可行解 T X (0,0,8,16,12) (0) = 由于 1 x 和 2 x 的检验数大于零，表明上述解不是最优解，由于 2 x 的检验数更 大，所以，先以 2 x 为换入变量。根据  规则，可确定 5 x 为换出变量，计算得新表 如下： j c 2 3 0 0 0  i CB XB b 1 x 2 x 3 x 4 x 5 x 0 3 x 2 [1] 0 1 0 -1/2 2 0 4 x 16 4 0 0 1 0 4 3 2 x 3 0 1 0 0 1/4 - j j c − z 2 0 0 0 -3/4 可得新解 T X (0,3,2,16,0) (1) = ，目标函数取值 z = 9。 1 x 的检验数为 2，换入。根据  规则，可确定 3 x 为换出变量，计算得新表如

下:23000c0,CBXBbX3XsXiX2X4221010-1/2XI0800-41[2] 4X43301001/412X200-201/4C,-2j得新解X(2)=(2,3,08,0)，目标函数取值z=13。x,的检验数为1/4，换入。根据0规则，可确定x，为换出变量，计算得：23000c0,CBXBbXiX2X3X4Xs2410001/4XI0400-211/2xs32011/20-1/8X2000-3/2-1/8cj-2j得解X(3)=(4,2.00,4)，目标函数取值==14。由于所有的检验都小于零达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。1.5单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。例：

下： j c 2 3 0 0 0  i CB XB b 1 x 2 x 3 x 4 x 5 x 2 1 x 2 1 0 1 0 -1/2 - 0 4 x 8 0 0 -4 1 [2] 4 3 2 x 3 0 1 0 0 1/4 12 j j c − z 0 0 -2 0 1/4 得新解 T X (2,3,08,0) (2) = ，目标函数取值 z =13。 5 x 的检验数为 1/4，换入。根据  规则，可确定 3 x 为换出变量，计算得： j c 2 3 0 0 0  i CB XB b 1 x 2 x 3 x 4 x 5 x 2 1 x 4 1 0 0 1/4 0 0 5 x 4 0 0 -2 1/2 1 3 2 x 2 0 1 1/2 -1/8 0 j j c − z 0 0 -3/2 -1/8 0 得解 T X (4,2,00,4) (3) = ，目标函数取值 z = 14 。由于所有的检验都小于零， 达到最优。 PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。 1.5 单纯形法的进一步讨论及小结 一、人工变量法 如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和 初始基可行解，此时必须要构造人工变量。 在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有 解；反之，则表示无可行解。 例：