运筹学教案

授课题目 ： 绪论 教学目的与要求： 1.知识目标：掌握运筹学的概念和作用及其学习方法 2.能力目标：掌握运筹学的数学模型 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 运筹学的数学模型 教学难点： 运筹学的数学模型 教学过程： 1.举例引入（ 5分钟） 2.新课 （60分钟） （1）举例引入，绪论（30分钟） （2）运筹学与管理学（30分钟） 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业

运筹学教案

《绪论》（2课时）

【教学流程图】 举例引入，绪论

运筹学

运筹学与数学模型的基本概念 管理学

课堂练习

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动

运筹学教案

是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一） 举例引入：（5分钟）

（1）xx马的故事 （2）两个囚犯的故事 导入提问：什么叫运筹学？ （二） 新课： 绪 论

一、运筹学的基本概念

（用实例引入）

例1-1 战国初期，xx的国王要求xx和他赛马，规定各人从自己的xx、中马、下马中各选一匹xx比赛，并且说好每输一匹马就得支

运筹学教案

付一千两银子给予获胜者。当时xx的xx忌的马强，结果每年xx都要输掉三千两银子。但xx给xx出主意，可使xx反输为赢。

试问：如果双方都不对自己的策略保密，当齐xx行动时，哪一方会赢？赢多少？反之呢？

例1-2 有甲乙两个囚犯正被隔离审讯，若两人都坦白，则每人判入狱8年；若两个人都抵赖，则每人判入狱1年；若只有一人坦白，则他初释放，但另一罪犯被判刑10年。求双方的最优策略。

乙囚犯 抵赖坦白

甲囚犯 抵赖 -1，-1-10，0 坦白 0，-10-8，-8

定义：运筹学（Operation Research）是运用系统化的方法，通过建成立数学模型及其测试，协助达成最佳决策的一门科学。它主要研究经济活动和军事活动中能用数学的分析和运算来有效地配置人力、物力、财力等筹划和管理方面的问题。 二、学习运筹学的方法

1、读懂教材上的文字； 2、多练习做题，多动脑筋思考；

运筹学教案

3、作业8次； 4、考试；

5、EXCEL操作与手动操作结合。 二、学生练习 （20分钟） 三、课堂小结（5分钟）

运筹学教案

授课题目 ： 第一章 线性规划及单纯形法 第一节：线性规划问题及数学模型。 教学目的与要求： 1.知识目标：掌握线性规划的基本概念和两种基本建模方法。 2.能力目标：掌握线性规划建模的标准形式及将普通模型化为标准模型的方法。要求学生完成P43习题1.2两个小题。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1、线性规划的基本概念和两种基本建模方法； 2、线性规划建模的标准形式及将普通模型化为标准模型的方法。 教学难点： 1、线性规划的两种基本建模方法； 2、将线性规划模型的普通形式化为标准形式。 教学过程： 1.举例引入（ 5分钟） 2.新课 （60分钟） （1）运筹学与线性规划的基本概念（20分钟） （2）结合例题讲解线性规划标准型的转化方法（20分钟） 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业

运筹学教案

《线性规划及单纯形法》（2课时）

【教学流程图】 运筹学

运筹学与线性规划的基本概念 线性规划 （结合例题讲解）线性规划的标准型

目标函数

结合例题讲解线性规划标准型的转化方法约束条件的右端常数

约束条件为不等式

课堂练习

课堂小结

布置作业

运筹学教案

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

第一章线性规划及单纯形法

第一节 线性规划问题及其数学模型 （用实例引入）

例1-3 美佳公司计划制造Ⅰ、Ⅱ两种产品，现已知各制造一件时分别占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应制造两种家电各多少件时才能使获取的利润最大？ 生产1件Ⅰ产品 生产1件Ⅰ产品 每天可用能力（小时） 运筹学教案

15 24 5 设备A（台时） 0 设备B（台时） 6 调试 （小时） 1 利润（元） 2 5 2 1 1 maxZ2x1x2

5x215 s.t. xx5126x12x224x1,x20

例1-4 有A、B、C三个工地，每天需要水泥各为17、18、15百袋。为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地。其单位运价如下表，求最佳调运方案。 工地 水泥厂 甲 乙

工地 水泥厂 甲 乙 需求量/百袋 x11 x12 x13 x21 x22 x23 17 18 15 23 27 50 A B C 供应量/百袋 1 2 1．5 4 2 2 A B C 运筹学教案

maxZx111.5x122x132x214x222x23x11x12x1323x21x22x2327 s.t.

x11x2117x12x2218x13x2315xij0(i1,2;j1,2,3)

一、 线性规划的基本概念

如果规划问题的数学模型中，决策变量的取值是连续的整数、小数、分数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则称这种规划问题为线性规划。 二、 将线性规划的普通型化为标准型

1、 对于minZ=CX,可转化为min(-Z)=-CX ；

2、 当约束条件中出现时，在左边加上一个“松弛变量”，使不

等式变为等式；当约束条件中出现时，则在左边减去一个“松弛变量”。

3、 当某个决策变量或符号不限时，则增加两个决策变量和，令； 4、 当约束条件中有常数项时，则在方程两边同乘以（-1）。

例1-5 将下列非标准4型线性规划问题转化为标准型。

运筹学教案

minZ3x12x24x3s.t. 2x13x24x3300x15x26x3400x1x2x3200x1,x20,x3不限

解：

''min(Z)3x12x24(x3x30x40x50x6's.t.''2x13x24(x'3x3)x4300x15x26(x3x)x5400''x1x2x3x3x6200'''x1,x2,x3,x3,x4,x5,x60''''3

学生练习：P42习题1.2。 二、学生练习 （20分钟） 三、课堂小结（5分钟）

运筹学教案

授课题目 ： 第二节 图解法 第三节 教学目的与要求： 1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念； 2.能力目标：掌握用图解法和单纯形法求解线性规划的原理； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 单纯形法原理 教学重点： 1、用图解法求解线性规划的计算步骤； 2、用单纯形法求解线性规划的计算步骤。 教学难点： 用单纯形法求解线性规划的计算原理； 教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） （1）图解法（40分钟） （2）单纯形法原理（40分钟） 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一。

运筹学教案

《线性规划的求解》（2课时）

【教学流程图】 以学生自学引入

图解法

线性规划求解方法介绍单纯形法

EXCEL规划求解法

坐标系

图解法的操作步骤求出可行域

平移目标函数直线

化为标准型 单纯形法的原理 迭代法

运筹学教案

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一）举例引入：（5分钟）

复习中学数学中的图解法。

导入提问：线性规划图解法中有哪些基本概念？ （二） 新课：

运筹学教案

第二节 图解法 一、图解法的步骤

（以学生自学引入）

学生自学P16-17，教师检查看不懂文字的学生，并做好记录。 提问：以P44的1.4题第1小题为例，图解法第一步是什么？以下逐步提出问题。

教师演示并总结如下：图解法适用于两个决策变量的线性规划非标准型。步骤如下；

1、 用决策变量建立直角坐标系；

2、 对于每一个约束条件，先取等式画出直线，然后取一已知点

（一般取原点）的坐标代入该直线方程的左边，由其值是否满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域。

3、 令Z等于任一常数，画出目标函数的直线，平移该直线，直

至它与凸多边形可行域最右边的角点相切，切点坐标则为最优解。 例1-5

运筹学教案

maxZ10x15x2s.t.3x14x295x12x28x1,x20

解

x25x12x28 G（1，1.5） 3x14x29 x1 10x15x210 可行解——满足约束条件的解，全部可行解的集合叫可行域。 最优解——使目标函数达到最大值的可行解。

基变量——利用矩阵的初等变换从约束条件的m×n(n>m)阶系数矩阵找出一个m×m阶单位子矩阵，它们对应的变量叫基变量，其余的叫非基变量。

矩阵的初等变换——将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。

运筹学教案

4.课堂小结（5分钟）

5.布置作业：要求学生完成P43习题1.3两个小题。

授课题目 ： 第四节 教学目的与要求： 1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念； 2.能力目标：掌握用单纯形法求解线性规划的计算步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 单纯法的计算步骤 教学重点： 用单纯形法求解线性规划的计算步骤。 教学难点： 1、用单纯形法求解线性规划的计算原理； 2、用单纯形法求解线性规划的计算步骤。 运筹学教案

教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） 单纯形法求解步骤 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一。

第四节《单纯法的计算步骤》（2课时） 【教学流程图】 以学生自学引入

图解法

线性规划求解方法介绍单纯形法

EXCEL规划求解法

化为标准型

运筹学教案

单纯形法的操作步骤 求出初始表 迭代法

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（二）举例引入：（5分钟）

运筹学教案

复习中学数学中的图解法。

导入提问：线性规划图解法中有哪些基本概念？

（二） 新课：

一、三个基本定理

可行解——满足约束条件的解，全部可行解的集合叫可行域。 最优解——使目标函数达到最大值的可行解。

基变量——利用矩阵的初等变换从约束条件的m×n(n>m)阶系数矩阵找出一个m×m阶单位子矩阵，它们对应的变量叫基变量，其余的叫非基变量。

矩阵的初等变换——将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。 二、 单纯形表迭代法

教师先演示： 1、 化为标准型

2、 做出初始单纯形表，求出检验数；

3、 确定检验数中最大正数所在的列为主元列，选择主元列所对

应的非基变量为进基变量

运筹学教案

4、 按最小比值原则，用常数列各数除以主元列相对应的正商

数，取其最小比值，该比值所在的行为主元行；主元列与主元行交叉的元素为主元，主元所对应的基变量为出基变量。 5、 对含常数列的增广矩阵用初等变换把主元变为1，主元所在

的列的其余元素化为0。

6、 计算检验数，直到全部检验数小于等于0，迭代终止。基变

量对应的常数列为最优解，代入目标函数得最优目标函数值。 例1-6

maxZ2x1x2s.t. 5x2156x12x224x1x25x1,x20

解：先化为标准型： s.t.

其约束条件的系数增广矩阵为 0 5 1 0 0 15 6 2 0 1 0 24 1 1 0 0 1 5

初始始基可行解为：，以此列出单纯形表如下。

运筹学教案

得：，代入目标函数得：Z=2*7/2+1*3/2+15/2*0+0*0=17/2。

目标函数 决策变量 基变量 初 始 表 计 算 x3 Cj 2 1 0 0 0 x1↓ x2↓ x3 x4 x5 常数 0 0 0 0 5 1 0 0 15 [6] 2 0 1 0 24 1 1 0 0 1 5 0 0 0 0 0 ←x4 x5 Zj j 2 1 0 0 0 min(,24/6,5/1)24/64 第一 次迭 代 x3 0 2 0 0 5 1 0 0 15 1 1/3 0 1/6 0 0 [2/3] 0 -1/6 1 2 2/3 0 1/3 0 0 1/3 0 -1/3 0 4 1 x1 ←x5 Zj j min(,第二 次迭 代 x3 15411,)3/2 51/32/32/30 2 1 0 0 1 5/4 -15/2 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 2 1 0 1/4 1/2 7/2 3/2 x1 x2 Zj 运筹学教案

j 0 0 0 -1/4 -1/2 4.课堂小结（5分钟）

5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一

授课题目 ： 第五节 单纯形法的进一步讨论 教学目的与要求： 1.知识目标：理解求解线性规划的人工变量法中大M法和两阶段法； 2.能力目标：利用习题1.15巩固线性规划的建模； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 1、求解线性规划的人工变量法中两阶段法的计算步骤。 2、人工变量法与普通单纯形法的区别。 运筹学教案

教学难点： 1、两阶段法的计算步骤； 2、习题1.15中的约束条件分析。 教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） （1）人工变量法（40分钟） （2）两阶段法（40分钟） 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结与单纯形法小结（5分钟） 5．布置作业。 《单纯形法的进一步讨论》（2课时）

【教学流程图】 用实例引入人工变量法

初始单纯形表中无单位矩阵 人工变量法的例题讲解引入人工变量

运筹学教案

在目标函数中引入大M

两阶段法用EXCEL求解中的困难 两阶段法的例题讲解第一阶段的模型

第二阶段的模型

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

运筹学教案

【教学内容】 一 、教学过程：

（三）举例引入：（5分钟）

复习单纯形法。

导入提问：当初始单纯形表中不出现单位矩阵怎么办？ （二） 新课：

第五节 单纯形法的进一步讨论 （用实例引入人工变量法）

例1-7 用单纯形法求解下列线性规划问题：

maxZ2x13x25x3x1x2x372x15x2x310x1,x2,x30

解：将第二个约束条件化为等式（左边减去一个松弛变量）后，约束条件的系数矩阵不存在单位矩阵，这时可在约束条件第一、二等式的左边分别加上一个人工变量作为初始基变量，使之出现单位矩阵。为了使目标函数中的人工变量为0，令它们的系数为任意大的负值“-M”，然后采用一般单纯形表法求解。

运筹学教案

minZ2x13x25x3Mx40x5Mx6x1x2x3x472x15x2x3x5x610x1,x2,x3,x4,x5,x60

目标函数 决策变量 基变量 初 x4 Cj 2 3 -5 -M 0 -M x1↓ x2↓ x3 x4 x5 x6 常数 7 xj -M -M 1 1 1 1 0 0 始表 ←x6 计 算 Zj [2] -5 1 0 -1 1 10 -3M 4M -2M -M M -M j 3M+2 3-4M 2M-5 0 -M 0 min(7/1,10/2)5 2 5 一次 ←x4 迭代 x1 Zj -M 2 0 [7/2] 1/2 1 1/2 -1/2 1 -5/2 1/2 0 -1/2 1/2 2 M5 0 72MMM1 -M 1 1 222j 7MM3MM8 6 0 1 1 2222 x2 x1 3 2 0 1 1/7 2/7 1/7 -1/7 1 0 6/7 5/7 -1/7 1/7 2 3 15/7 16/7 1/7 -1/7 4/7 45/7 Zj j 0 0 -50/7 -M-16/7 -1/7 -M+1/7 所以最优解为：X=（45/7，4/7，0，0，0，0）

运筹学教案

例1-8 对LP模型： s.t.

用两阶段法求解。 解：先分为标准型： s.t. 对 s.t.

使用单纯形法求解，化为标准型后，列出单纯形表并迭代如下

目标函数 决策变量 基变量 初 y6 Cj 0 0 0 0 0 -1 -1 y1↓ y2↓ y3 y4 y5 y6 y7 常数 2 1 1/3 1/3 yj -1 -1 0 0 [6] 1 -1 0 1 0 5 2 1 0 -1 0 1 5 8 2 -1 -1 0 0 0 1 1/6 -1/6 0 1/6 0 始表 ←y7 一次 j y2 迭代 ←y7 j -1 [5] 0 2/3 1/3 -1 -1/3 1 5 0 2/3 1/3 -1 -4/3 0 0 0 1 1/6 -1/6 0 1/6 0 y2 1/3 运筹学教案

1/15 y1 0 1 0 2/15 1/15 -1/5 -1/15 1/5 j 0 0 0 0 0 -1 -1 在上表中的最终表中除去人工变量后，回归到原来的标准型： s.t.

然后对该最终表继续使用单纯形法计算：

目标函数 决策变量 基变量 初 y2 Cj -15 -24 -5 0 0 常数 y1 y2 y3↓ y4 y5 0 1 1/6 -1/6 0 1/3 1 0 [2/15] 1/15 -1/5 1/15 0 -9 6 -3 -3 yj -24 -15 -24 -5 始表 ←y1 一次 迭代 j y2 y3 -5/4 1 0 -1/4 1/4 1/4 15/2 0 1 1/2 -3/2 1/2 j -15/2 0 0 -7/2 -3/2 故

1.15题分析：

令i=1,2,3代表A，B，C三种商品，j=1,2,3代表前，xx，后舱，代表装载于第j舱位的第ixx商品的数量（件）。

运筹学教案

1、目标函数为运费总收入：

maxZ1000(x11x12x13)700(x21x22x23)600(x31x32x33)

2、约束条件： 前中后舱载重限制：

8x116x215x3120008x126x225x323000 8x136x235x331500前中后舱体积限制：

10x115x217x31400010x125x227x325400 10x135x237x331500

三商品的数量限制：

x11x12x13600x21x22x231000 x31x32x33800舱体平衡条件： 前舱载重/中舱载重为： 后舱载重/中舱载重为： 前舱载重/后舱载重为：

运筹学教案

上三式中，2000/3000=2/3，1500/3000=1/2，2000/1500=4/3。

3.课堂练习（穿插在例题讲解过程中） 4.课堂小结与单纯形法小结（5分钟）

图1—9：强调当非基变量的检验数为零时，线性规划存在多重解。

5、布置作业二：1.15题

授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析 第一节 线性规划的对偶问题 第二节对偶问题的基本性质 运筹学教案

教学目的与要求： 1.知识目标： 掌握一般形式对偶问题的对应规律、理解并应用对偶定理 2.能力目标：掌握线性规划的对偶问题的基本性质； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 一般形式对偶问题的对应规律、对偶定理 教学难点： 对偶定理 教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） （1）对偶问题的基本概念与解的性质； （2）一般形式的对偶问题 （3）对偶问题的基本性质 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 《线性规划的对偶理论》（2课时）

运筹学教案

【教学流程图】 举例引入

对偶问题与原问题的结构特点

线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表

线性规划的单纯形法求解实质

学生练习（结合例题讲解进行）

课堂小结

布置作业 【教学方法】

运筹学教案

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一）举例引入对偶问题的基本概念：（5分钟）

导入提问：线性规划的对偶问题与原问题的解是什么关系？ （二） 新课：

第二章 线性规划的对偶理论与灵敏度分析

第一节 线性规划的对偶问题 回顾例1-3：

运筹学教案

例1-3 美佳公司计划制造Ⅰ、Ⅱ两种产品，现已知各制造一件时分别占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应制造两种家电各多少件时才能使获取的利润最大？ 生产1件Ⅰ产品 生产1件Ⅰ产品 每天可用能力（小时） 设备A（台时） 0 设备B（台时） 6 调试 （小时） 1 利润（元） 2 5 2 1 1 15 24 5 解：设为两种产品的产量，得线性规划问题：

maxZ2x1x2

5x215 s.t. xx5126x12x224x1,x20

现从另一角度提出问题：假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？

设分别为单位时间内设备A，B和调试工序的出让价格，其线性规划模型如下表：

运筹学教案

对偶问题 原问题 目标函数 最大利润为maxZ2x1x2，某公司最小出让价为：其中： x1和x2为两种产品的产量。 minW15y124y25y3，其中： y1,y2,y3分别为单位时间内设备A，B和调试工序的出让价格。 原问题 对偶问题 每生产1件商品的出让价不小6y2y32约束条件 每生产1件商品在A，B设备和调试工序上的时间约束5x215为：xx512于利润：5y12y2y31 y1,,y2,y306x12x224x1,x20 可见：

原问题（系数为m×n矩阵） maxZ 对偶问题（系数为n×m矩阵） minW 目标函数中的系数成为对偶问题约束 约束条件中的右端常数成为原问题中 条件中的右端常数 目标函数中的系数 约束条件系数矩阵为对偶问题约束条 约束条件系数矩阵为原问题约束条 件系数矩阵的转置。 件系数矩阵的转置。 运筹学教案

约束条件数有m个， 第i个约束条件为“≤”， 第i个约束条件为“≥” 第i个约束条件为“=” 变量数n个， 第i个变量为“≥0” 第i个变量为“≤0” 第i个变量为自由变量

变量数m个， 第i个变量为“≥0” 第i个变量为“≤0” 第i个变量为自由变量 约束条件数有n个， 第i个约束条件为“≥”， 第i个约束条件为“≤” 第i个约束条件为“=” 例1-6和例1-8分别用单纯形法和两阶段法可求得上述例题的原问题和其对偶问题的最终单纯形表如下： 目标函数 决策变量 基变量 最 终 表 j x3 x1 Cj 2 1 0 0 0 原问题变量 原问题松弛变量 x3 x4 x5 常数 0 2 1 x1 x2 0 0 1 0 0 1 0 0 对偶问题剩余变量 y3 y4 1 5/4 -15/2 15/2 0 1/4 -1/2 0 -1/4 3/2 0 -1/4 -1/2 对偶问题变量 y1 y2 y3 x2 7/2 3/2 变量 目标函数 Cj -15 -24 -5 0 0 常数 运筹学教案

决策变量 基变量 一次 迭代 y2 y3 y y1 y2 y3↓ y4 y5 -24 -5/4 1 0 -1/4 1/4 1/4 -5 15/2 0 1 1/2 -3/2 -15/2 0 0 -7/2 -3/2 1/2

j 从上两表看出两个问题变量之间的对应关系，同时看出只需求解其中一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。即原问题的最优解为：；其对偶问题的最优解为：。 对偶问题的基本性质

1、 若线性规划原问题（LP）有最优解，其对偶问题（DP）也有最优解； 2、 LP的检验数的相反数对应于其DP的一组基本解，其中第j个决策变

量的检验数的相反数对应于DP第i个剩余变量的解；LP第i个松弛变量的检验数的相反数对应于其DP的第i个对偶变量的解。反之DP的检验数对应于其LP的一组基本解。 例1-9

maxZ6x12x2x3 2x1x22x32x14x33x130

解 加入松弛变量后，单纯形表迭代为：

运筹学教案

x1 x2 x3 x4 x5 b x4 [2] -1 2 1 0 2 x5 1 0 4 0 1 4 j 6 -2 1 0 0 x1 1 -1/2 1 1/2 0 1 x5 0 [1/2] 3 -1/2 1 3 j 0 1 -5 -3 0 x1 1 0 4 0 1 4 x2 0 1 6 -1 2 6 j 0 0 -11 -2 -2 y3 y4 y5 y1 y2

设对偶变量为和，剩余变量为，，，由上性质，有 为对偶问题的基本解。

二、课堂练习（穿插在例题讲解过程中） 三、课堂小结（5分钟）

运筹学教案

授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析 第三节 影子价格 教学目的与要求： 1.知识目标：了解影子价格的实质 2.能力目标：掌握求解线性规划的对偶单纯形法的计算步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 对影子价格的理解。 教学难点： 对影子价格的理解 运筹学教案

教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） （1）影子价格的概念 （2）影子价格的实质 （3）影子价格的性质与计算 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟）

《影子价格》（2课时）

【教学流程图】 举例引入

线性规划影子价格基本概念

影子价格的实质

运筹学教案

学生练习（结合例题讲解进行）

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（二）举例引入影子价格的基本概念：（5分钟）

运筹学教案

导入提问：什么是影子价格？ （二） 新课：

第二章 线性规划的对偶理论与灵敏度分析

第三节 影子价格

对偶变量的意义——代表在资源最优利用条件下对单位第种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。

z*=w*= Y*b=（2.26） 对bi求偏导数，得到： （2.27）

即第i种资源影子价格yi*是z*对资源数量bi的变化率，是第i种资源增加一个单位时，最大产值的改变量。

1．资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。

资源的影子价格实际上又是一种机会成本.

在纯市场经济条件下,当第2种资源（设备B）的影子价格是0.25，当市场价格高于0.25时，可以卖出这种资源；

运筹学教案

相反当市场价格低于影子价格时，就会买入这种资源。 随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。

一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。

授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析 第四节 对偶单纯形法 教学目的与要求： 1.知识目标：理解线性规划单纯形法求解的实质； 2.能力目标：掌握求解线性规划的对偶单纯形法的计算步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 1、 对偶单纯形法的计算步骤； 2、 对偶单纯形法与原问题单纯形法求解思路上的区别。 教学难点： 1、对偶单纯形法的计算步骤； 2、用单纯形法求解线性规划的实质。 运筹学教案

教学过程： 1.举例引入（ 5分钟） 2.举例讲解新课 （80分钟） （1）对偶问题的基本概念与解的性质；（20分钟） （2）对偶单纯形法与原问题单纯形法解之间的关系；（20分钟） （3）对偶单纯形法与原问题单纯形法的求解原理（20分钟） （4）对偶单纯形法原理（20分钟）求解步骤（20分钟） 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟）

《线性规划的对偶理论与对偶单纯形法》（2课时） 【教学流程图】 举例引入

对偶问题与原问题的结构特点

线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表

线性规划的单纯形法求解实质

初始表

运筹学教案

对偶单纯形法计算步骤进基

出基

学生练习（结合例题讲解进行）

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】

运筹学教案

一 、教学过程：

（三）举例引入对偶问题的基本概念：（5分钟）

导入提问：线性规划的对偶问题与原问题的解是什么关系？ （二） 新课：

第四节 对偶单纯形法

一、对偶单纯形法的原理

LP与DP在求解迭代过程中有三种情形： LP的b列 LP的检验数j 均≥0 均 ≤0 含义 则DP的检验数i≤0且yi0，这时 LP与DP均达到最优解。 均≥0 某个j＞0 则DP的某个变量yj＜0，说明原问题可 行，对偶问题不可行。 某个bi＜0 全部j≤0 则DP的检验数i≤0且yi0，说明原 问题不可行，对偶问题可行。 对于第二种情形用单纯形法求解，第三种情形用对偶单纯形法求解。 二、 对偶单纯形法求解过程

1、用实例引入：

运筹学教案

例1-10

minW3y19y2y1y22 y14y23y17y23y1,y20

解 引入非负松弛变量，化为标准型；

maxZ3y19y2y1y2y32y14y2y43y17y2y53y150

将三个约束式两边分别乘以-1，得

maxZ3y19y2y1y2y32 y14y2y43

y17y2y53y150目标函数 决策变量 基变量 初 始 表 计 算 ←y3 y4 y5 Cj -3 -9 0 0 0 y1↓ y2↓ y3 y4 y5 常数 yj 0 0 0 [-1] -1 1 0 0 -2 -1 -4 0 1 0 -3 -1 -7 0 0 1 -3 Zj 0 0 0 0 0 -3 -9 0 0 0 j 运筹学教案

min(3/1,9/1)3 -3/-1 -9/-1 第一 y1 -3 0 0 1 1 -1 0 0 2 0 [-3] -1 1 0 -1 0 -6 -1 0 1 -1 次迭 ←y4 代 y5 Zj -3 -3 3 0 0 0 -6 -3 0 0 j min(6/3,3/1)2 -6/-3 -3/-1 第二 次迭 代 y1 y2 y5 -3 -9 0 1 0 -4/3 1/3 0 5/3 0 1 1/3 -1/3 0 1/3 0 0 1 -2 1 1 Zj -3 -9 1 2 0 0 0 -1 -2 0 j 最优解为：Y=(5/3,1/3,0,0,1) 3、 总结对偶单纯形法求解过程：

由于用单纯形法求解极大化线性规划问题时，通过迭代直至所有检验数≤0，这时所得最优基也是对偶问题的可行基，因此单纯形法的求解过程是：在保持原始可行（即常数列保持≥0）的前提下，通过迭代实现对偶可行（全部≤0）。

运筹学教案

换一个角度考虑线性规划的求解过程：能否在保持对偶可行（全部≤0）的前提下，通过迭代实现原始可行（即常数列保持≥0）？这就是对偶单纯形法的求解思路。

第一步：建立初始单纯形表，计算检验数行，当全部≤0（非基变量的＜0）时，如果常数项≥0，即得最优解。如常数项至少有一元素＜0，且检验数仍然非正，则转下一步。

第二步：将常数项＜0所在的约束条件两边同乘以-1，将常数列全变成非负，再使用原始单纯形xx求解。如果上述处理过程中出现原始可行基不再是单位矩阵，可适当增加人工变量构造人造基，再用大Mxx求解。

第三步：进行基变换

先确定出基变量：选取常数xx绝对值最小的负元素对应的基变量出基，相应行为主元行。然后确定入基变量：由最小比值原则，选所在的列为主元列。这里为第j列的检验数，为对应的主元行xx基变量的系数。主元行与主元列相交叉处的系数元素为主元素，其对应的非基变量为换入基变量。

第四步：对主元素进行换基迭代后，用矩阵的初等变换将主元素变成1，并把主元列变成单位向量，得到新的单纯形表。 二、课堂练习（穿插在例题讲解过程中） 三、课堂小结（5分钟）

运筹学教案

授课题目 ： 第二章 线性规划的对偶理论与灵敏度分析 第五节：灵敏度分析 教学目的与要求： 1.知识目标：理解求解线性规划的单纯形法中灵敏度分析的基本原理； 2.能力目标：分析Cj的变化；分析bj的变化；增加一个变量xj的分析。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 1、分析Cj的变化； 2、分析bj的变化； 3、增加一个变量xj的分析。 运筹学教案

教学难点： 1、灵敏度的基本概念； 2、增加一个变量xj的分析。 教学过程： 1.举例引入灵敏度（ 5分钟） 2.举例讲解新课 （80分钟） （1）灵敏度的基本概念；（20分钟） （2）分析Cj的变化；（20分钟） （3）分析bj的变化；（20分钟） （4）增加一个变量xj的分析。（20分钟） 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 《灵敏度分析》（2课时）

【教学流程图】 举例引入灵敏度

灵敏度

线性规划灵敏度的基本概念分析灵敏度的方法

线性规划模型参数

运筹学教案

分析的变化

分析线性规划模型中参数的变化 分析的变化 增加一个变量的分析

学生练习（结合例题讲解进行）

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生

运筹学教案

参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（四）举例引入对偶问题的基本概念：（5分钟）

导入提问：线性规划的对偶问题与原问题的解是什么关系？ （二） 新课： 第五节灵敏度分析

一、灵敏度分析的基本概念与原理

由LP单纯形迭代法的基本原理： 将LP的标准型写成矩阵形式： maxZ=CX s.t.AX=b X≥0

其约束条件的系数矩阵为A，加上人工基I（I为单位矩阵）以后，迭代过程实际上为：

运筹学教案

（A∣I）→（I∣A） 3 -1 0

例1-11 求矩阵A= -21 1 的逆矩阵。 2 -1 4

解3 -1 01 0 0

-21 10 1 0

2 -1 40 0 1 1 0 11 1 0 =-2 1 10 1 0 0 0 50 1 1 1 0 11 10 =0 1 32 30 0 01 0 1/5 1/5 10014/5-1/5 =010212/5 -5/3 00101/51/3

运筹学教案

再看美佳公司的LP约束条件系数的初始表与最终表： 目标函数 决策变量 基变量 初 始 表 计 算 x3 Cj 2 1 0 0 0 常数 x1↓ x2↓ x3 x4 x5 0 0 0 0 5 1 0 0 15 [6] 2 0 1 0 24 1 1 0 0 1 5 0 0 0 0 0 ←x4 x5 Zj j 2 1 0 0 0 min(,24/6,5/1)24/64 第二 次迭 代 x3 0 2 1 0 0 1 5/4 -15/2 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 2 1 0 1/4 1/2 7/2 3/2 x1 x2 Zj j 0 0 0 -1/4 -1/2 因此有： 目标函数的系数 决策变量

初始表中约束条件的系数BNb 最优表约束条件的系数

运筹学教案

最优表的检验数

由上表看出，目标函数中的决策变量的系数（又叫参数）变动时，只影响最优表中的检验数，因此只要对最优表继续使用单纯形表法，直至得到最优解为止。 二、 分析的变化

例5-2 用教材上的例5。

将代入原最优表中并继续迭代，得：

目标函数 决策变量 基变量 第二 次迭 代 第三 次迭 代 ←x3 x1 x2 j Cj 1.5 2 0 0 0 常数 x1↓ x2↓ x3 x4↓ x5 0 1.5 2 0 1．5 2 0 0 1 [5/4] -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 1/8 -9/4 0 0 4/5 1 -6 1 0 -1/5 0 1 0 1 1/5 0 0 0 0 -1/10 0 -3/2 15/2 7/2 3/2 6 2 3 x4 x1 x2 j 如果，代入原最优表，得

运筹学教案

目标函数 决策变量 基变量 第二 次迭 代 x3 Cj 2 1 0 0 0 常数 x1↓ x2↓ x3 x4 x5 0 1.5 1 0 0 1 [5/4] -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 4422 15/2 7/2 3/2 x1 x2 j 11130 0 0   解和 ，得：，故 。 三、 分析的变化

设初始表中的常数列为b,那么最优表中的常数列为，现设初始表中的常数列为，那么最优表中的常数列为，也就是当初始表中的常数列有增量时，那么最优表中的常数列有增量。

例5-3 设美佳公司这一例中的单纯形表中的初始表中的常数列中有增量：

0

8，设最优表中的常数列为，那么其增量为： 0

15/4 -15/2010

运筹学教案

= 01/4-1/28=2 0 -1/43/20-2

用对偶单纯形法继续计算得：

目标函数 决策变量 基变量 第二 次迭 代 第三 次迭 代 x3 Cj 2 1 0 0 0 常数 x1↓ x2↓ x3 x4↓ x5 0 2 1 0 2 0 j 0 0 1 5/4 -15/2 35/2 1 0 0 1/4 -1/2 11/2 0 1 0 [-1/4] 3/2 - 1/2 x1 x2 j x3 0 0 0 -1/4 -1/2 0 5 1 0 0 1 1 0 0 1 0 -4 0 1 -6 0 -1 0 0 -2 15 5 2 x1 x4 四、 增加一个变量的分析（采用教材第三版P66的分析步骤和P67的例7。 二、课堂练习（穿插在例题讲解过程中） 三、课堂小结（5分钟）

运筹学教案

授课题目 ： 第三章：运输问题 第一节 运输问题及其数学模型 教学目的与要求： 1.知识目标：掌握运输问题的基本概念； 2.能力目标：掌握运输问题的模型特点，特别是基变量个数。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 初始调运方案的确定。 教学难点： 初始调运方案的确定。 运筹学教案

教学过程： 1.举例引入运输问题（ 5分钟） 2.举例讲解新课 （70分钟） 运输问题的基本概念； 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 5．布置作业：（10分钟） 《运输问题：表上作业法与规划求解法》（2课时） 【教学流程图】 举例引入运输问题

产地

运输问题的基本概念销地

运价与运量

学生练习（结合例题讲解进行）

运筹学教案

课堂小结

布置作业：要求学生完成习题中例7的表上作业计算。 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一）举例引入运输问题的基本概念：（5分钟）

导入提问：线性规划在管理实践中有哪些应用？ （二） 新课：

运筹学教案

第三章 运输问题

第一节 运输问题及其数学模型

一、 引入P82的例1

二、 运输问题的数学模型及其特点

运输问题的数学模型具有下述特点： 1、约束条件系数矩阵的元素为0或1；

2、约束条件系数矩阵的每一列有两个元素，这对应于每一个元素在前m个约束条件中出现一次，在后n个约束条件中出现一次； 3、对于产销平衡运输问题，所有约束条件都有是等式约束，各产地产量之和等于各销地销量之和。 运输问题的解

初始基可行解的确定应本着下列原则

（1） 皆应满足模型中的所有约束；

（2）基变量对应的约束方程组的系数列向量线性无关 （3） 基变量的个数（非零变量的个数）≤m+n-1。 （4） 为使迭代顺利进行，基变量的个数在迭代的过程 中一直保持为（m+n-1）个。

运筹学教案

二、学生练习（穿插在例题讲解中） 三、布置作业：对本章例题7进行具体推导

授课题目 ： 第三章：运输问题 第二节 用表上作业法求解运输问题 教学目的与要求： 1.知识目标：掌握运输问题的表上作业法； 2.能力目标：掌握运输问题的建模和表上作业求解法；掌握解的最优性检验法中的闭回路法和位势法的计算步骤。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 1、运输问题的建模和表上作业求解法； 2、求检验数的两种方法； 3、求解运输问题的EXCEL规划求解法。 教学难点： 1、运输问题的建模和表上作业求解法及其解的最优性检验法中的闭回路法和位势法（求检验数的两种方法）； 2、求解运输问题的EXCEL规划求解法。 运筹学教案

教学过程： 1.举例引入运输问题的求解（ 5分钟） 2.举例讲解新课 （70分钟） （1）求解运输问题的表上作业法； （2）求解运输问题的规划求解法； 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 5．布置作业：（10分钟）

《运输问题：表上作业法与规划求解法》（2课时） 【教学流程图】 举例引入运输问题的解

用最小元素法求初始方案

求解运输问题的表上作业法 闭回路法 位势法

学生练习（结合例题讲解进行）

运筹学教案

课堂小结

布置作业：要求学生完成习题中例7的表上作业计算。 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（二）举例引入运输问题的基本概念：（5分钟）

导入提问：线性规划在管理实践中有哪些应用？

运筹学教案

（二） 新课： 第三章 运输问题

第二节 用表上作业法求解运输问题 一、 一般单纯形法

例 3-1 某部门有三个生产同类产品的工厂，产品由四个销地销售（数据

见下表），求应如何调运才使总运费最小？

销地 产地 B1 4 B2 12 B3 B4 4 11 产量 A1 A2 A3 x11 x21 x12 2 10 x13 x14 3 9 16 x22 8 5 x32 x23 x24 11 6 x34 10 22 14 x31 x33 销量 8 14 12 解：先写出LP数学模型如下：

minZ4x1112x124x1311x142x2110x223x239x248x315x3211x336x34

x11x12x13x1416 x21x22x23x2410 x31x32x33x3422

s.t.

运筹学教案

x12x22x3214 x13x23x3312 x14x24x3414

xij0(i1,2,3;j1,2,3,4)

(目标函数和约束条件模型见教材P83) 由模型可列出约束条件的系数矩阵如下：

x11

x12 x13 x14 x21 x22 x23 x24x34

1111 1111 1111 111 111 111 111

x31 x32x33

运筹学教案

由上可见，单纯形表的系数矩阵中共有m+n=3+4=7行，有

m*n=3*4=12xx。基变量个数有m+n-1=3+4-1=6个，不能采用普通单纯形法求解，只能用表上作业法求解。

二、 表上作业法

1、求初始可行解——最小元素法

先在表中找出一个运价最小的数（最小元素），给予尽可能满足，然后在余下的格子中，继续按此法安排调运。注意每次安排时，如果销地已满足需求，就划去该列；如果产地已分配完产量，就划去该行（划去是打“×”之意）；如二者同时满足，只能在该最小元素所在的行或列上的其它空格上打“×”，而不能同时划去该最小运价格所在的行与列。当最后只剩下一行（一列）还存在没有填数和打“×”的格子时，规定应先在能同时满足所在行与列的格子内填数（填数前所在行与列已同时满足时，该格子内应填写0），再按最小元素法填写其他格，直到满足填数的格子数等于m+n-1为止。

2、调运方案的检验方法（怎样求空格检验数？） ① 空格闭回路法

空格闭回路指在一个封闭的直角回路的若干角点处，除了处为空格以外，其余角点都是实格。作法：从所在的空格开始，沿直线前进，碰到实格可拐弯也可不拐，但碰到空格应不改变方向，如此曲折前进，一直返回到起始空格。再将所在空格的单位运费加上正号，沿它的空

运筹学教案

格闭回路按顺时针方向再在第二个、第三个等有数格的单位运费前依次加上负号，正号，…，如此正负交错，最后得所在空格的检验数。

②位势法

方法：在初始调运方案表中增加一行和一列，在列中填，在行中填（和称为位势），于是对于m+n-1个有数格成立下列关系：

（1）由于和共有m+n个，因此上式组成的m+n-1个

方程xx一个未知数，可任设一个未知量为一任意常数（一般设），求出全部和的值。再把这些和的值代入空格检验数的表达式：

（2）

3、换基

对各空格检验数按的原则先选择进基，再做的空格闭回路，以角点为0号，按顺时针或反时针方向把其他角点依次标为1号，2号，…，如此排出各转角点的奇偶性，再求调整量（各奇数转角点的调运量），按“偶点处加调运量，奇点处减调运量”的方法，重新安排空格闭回路上转角点的调运量。

4、再求新调运方案的检验数，再换基求更新的调运方案…，如此迭代，直至

空格检验数不出现负值为止。

运筹学教案

5、当某空格检验数时，同样可以选取它所在的空格进基，运用调整量调节器整后的方案仍为最优，不过目标函数值不会有所改善，称之为多解。

例3-2 对例3-1用表上作业法求解。

解 先用最小元素法求初始调运方案如下表1，用空格闭回路法或位势法求得各空格检验数为：，由于存在负检验数，再进行迭代。得新调运方案如下表2。由于所有非基变量（空格）的检验数为正值，故这个调运方案为最优解。和检验数为：

110，122，222，231，319，3312

作业二：习题3.8表3-32，33。(答案见2006级物流本科教案)

表1 初始调运方案

销地 产地 B3 B1 4 B2 12 × 2 10 B4 4 11 6 3 9 产量 A1 × 10 16 A2 A3 8 8 × 5 14 2 11 × 6 8 14 10 22 × 8 × 14 12 销量 表2 最优调运方案

运筹学教案

B3 销地 产地 B1 4 B2 12 × 2 10 B4 4 11 6 3 9 产量 A1 × 8 8 12 16 A2 × 5 14 2 11 6 8 14 10 × × 14 12 A3 × 8 22 销量

二、学生练习（穿插在例题讲解中）

三、布置作业：用表上作业法进行计算求解。

运筹学教案

授课题目 ： 第三章 运输问题 第三节：运输问题进一步讨论。 教学目的与要求： 1.知识目标：掌握运输问题的基本概念； 2.能力目标：掌握运输问题的建模和表上作业求解法；掌握解的最优性检验法中的闭回路法和位势法的计算步骤。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。 教学重点： 1、运输问题的建模和表上作业求解法； 2、求检验数的两种方法； 3、求解运输问题的EXCEL规划求解法。 教学难点： 1、运输问题的建模和表上作业求解法及其解的最优性检验法中的闭回路法和位势法（求检验数的两种方法）； 2、求解运输问题的EXCEL规划求解法。 教学过程： 1.举例引入产销不平衡的运输问题（ 5分钟） 2.举例讲解新课 （80分钟） （1）产销不平衡的运输模型相关的基本概念；（20分钟） （2）产大于销的运输问题；（20分钟） （3）销大于产的运输模型；（20分钟） （4）产销不平衡的运输模型在实际中的应用。（20分钟） 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 运筹学教案

《运输问题进一步讨论》（2课时）

【教学流程图】

举例引入产销不平衡的运输问题

产大于销

产销运输问题的基本概念销大于产

基变量的个数

增加一个产地

求解不平衡的运输问题的表上作业法增加一个销地 最后几个xx的数据填充

学生练习（结合例题讲解进行）

课堂小结

运筹学教案

布置作业：要求学生完成习题中例7的表上作业计算。 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一）举例引入不平衡运输问题的基本概念：（5分钟） 导入提问：在运输问题中当产大于销或者销大于产怎么办？ （二） 新课：

一、产销不平衡的运输问题

1、总产量大于总销量，需增加一个虚拟的销地（收点），其运费

设为0，再用表上作业法求解。

运筹学教案

例1 求下列运输问题的最优调拨方案；

销地 产地 B1 2 10 7 B2 11 3 8 3 B3 B4 3 5 1 4 9 2 6 产量 7 5 7 19 15 A1 A2 A3 销量 2 4 解 增加一个销地，令它的单位运费为0。在用最小元素法寻找初始调运方案时，每次不要考虑新增这一列的运价，否则会使初始方案距离最优方案更远，增加以后调整的工作量。

销地 产地 B3 B1 2 2 10 B2 11 × B4 3 4 3 5 × 1 3 2 9 B0 0 2 0 2 0 × 4 产量 7 5 7 A1 A2 A3 × 3 × 3 × 7 8 4 × × 销量 2 3 4 6 19 19 由于所有的检验数大于等于0，此方案最优，但其中，还可以有另外的最优调拨方案，但总运费不会下降。

2、总产量小于总销量，需增加一个虚拟的产地（发点），其运费

设为0，再用表上作业法求解。

运筹学教案

二、产量有上下限的产销不平衡运输问题

教材上例7：根据下表1求最优运输方案：

解 方法：这是一个产地和的产量有上下限的运输问题，先求出的产量上限为7（20-6-7=7）。由于该两地产量都取上限时，总产量为25，大于总需求20，故增加一个虚销地。当某地产量有最高产量和最低产量时，可以把它的产量分为基本产量和多余产量两部分，前者应发往实在的需用地，而不能发往虚销点，从而将这部分产量运往虚销点的单位运价取为充分大的M，另一部分多余产量可以运往虚销点，但实际上没有运输，故取相应的单位运价为0。现将初始方案表列于下表2：

表1 各产地和销地的产量、销量及单位运价

销地 产地 B1 2 1 3 B2 4 5 2 4 B3 产量 3 6 4 6a111 a27 A1 A2 A3 a34 20 销量 10 6

表2 初始调运方案表

运筹学教案

B4 3 M × 3 0 2 6 M × 4 M 0 4 0 3 5 产量 6 5 7 4 3 25 25 销地 产地 B1 2 3 2 B2 4 × B3 A A1 A2 ‘13 3 × × × 6 A3 ’A3 4 × × 1 5 7 × 3 2 × 4 3 2 × × 销量 10 4 用位势法求得各空格检验数为：

122M，14M,210,222M,324M,334,341M,

411M，431M,511,52M,531

再迭代得：

123，14M,210,223,325,334,341M, 410，44M1,511,521,531

表2 最优调运方案表

销地 产地 B3 B1 2 3 2 B2 4 × B4 3 M × 3 0 2 6 M × 4 M × 4 0 3 产量 6 5 7 4 3 A A1 A2 ‘13 3 × 0 × A3 A3 ’ 4 × × 1 5 7 × 3 2 × 4 3 2 × × 运筹学教案

5 25 25 销量 10 4 6 经计算，全部检验数为大于等于0。故为最优调运方案。 教材上例8

方法：该公司应配备的船只数等于各航线装船、卸船和航行所需要的船只数之和再加上调度所需要的船只数。

第一步：利用起点xx、终点xx及航班数表和各xx之间的航行时间表求得各航线在每个航行周期（一条船从出发到终点xx所需的天数，包括装船和卸船天数）内共需多少条船？

第二步：求各港口之间调度所需的船只数，它等于每天各港口为起点时发出的船只数与该港口为终点时到达的船只数之差的相反数。

第三步：设多余船只数为产量，缺少的船只数为销量（需求量），船只调出的港口为产地，调入港口为销地，作运输问题求解的作业表如下：

表1 初始方案表

至（销地） 从（产地） A 2 1 14 × × 2 × × 1 B 3 0 13 2 8 1 E 5 17 3 产量（多余船只） 2 2 C D F 1 运筹学教案

3 5 5 销量（缺少船只） 1 1 。以所在格为进基变量换基，得一最优解： 表2 最优表Ⅰ

至（销地） 从（产地） A 2 1 14 × 1 2 × × 1 × B 3 1 13 1 8 1 1 E 5 17 3 3 产量（多余船只） 2 2 C D F 销量（缺少船只） 1 5 5 以所在格为进基变量换基，得另一最优解：

表3 最优表Ⅱ

至（销地） 从（产地） A 2 0 14 1 1 2 × × 1 × B 3 2 13 × 8 1 1 E 5 17 3 3 产量（多余船只） 2 2 C D F 销量（缺少船只） 1 5 5 二、学生练习（结合例题进行）

运筹学教案

三、布置作业

授课题目 ： 第四章 目标规划 第一节 目标规划问题及其数学模型 第二节 目标规划的图解法 教学目的与要求： 1.知识目标：了解目标规划的定义，特点与分类；掌握目标偏差变量的概念和目标规划的模型及目标规划的图解法步骤；掌握目标规划的规划求解法。重点要求是目标规划的三种求解方法的比较。 2.能力目标：能够运用目标规划的求解原理进行表上操作与计算机操作。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1.掌握目标规划的图解法与规划求解法。 2.掌握目标规划的三种求解方法的区别。 3．目标偏差变量的概念、 教学难点： 目标规划的图解法。 运筹学教案

教学过程： 1.复习旧课（通过提问方式复习回顾上次内容，情景假设导入本次内容。5分钟） 2.新课 （60分钟） (1)目标规划的定义与分类（30分钟） (2)目标规划的图解法与规划求解法（30分钟） 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业 《目标规划》（2课时）

【教学流程图】 复习旧课

定义

目标规划概述 特点

分类

回顾

目标规划的图解法 例题讲解

运筹学教案

学生操作

回顾

目标规划的规划求解法例题操作 学生操作

具体实例

课堂练习

课堂小结

布置作业 【教学方法】

运筹学教案

本课主要采用任务驱动式教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

二、 复习旧课：（5分钟）

提问：（1）线性规划的求解方法有哪些？各有什么区别？ （学生边回答，老师边板书） 区别：适用环境不同 目的不同 老师归纳。

导入提问：什么叫目标规划？ （二） 新课： 一、举例引入：

运筹学教案

例1 某衬衫厂接受13000件男女衬衫订货，对男女衬衫的数量没有要求，只要求一周内完成。根据该厂的生产能力，一周内可利用的裁剪时间为20000分钟，缝纫时间为36000分钟。完成一件男衬衫需裁剪时间为2分钟，缝纫时间2分钟。完成一件女衬衫需裁剪时间1分钟，缝纫时间3分钟。每件男衬衫售价15元，成本7元；每件女衬衫售价20元，成本14元。求使利润最大时男女衬衫的生产量。

解：LP模型为： s.t.

用单纯形求解，得。总销售额=元。

例2 对上例规定销售额的期望值为250000元，要求实际销售额偏离预定目标的正负偏差量之和为最小。求该目标规划的数学模型。

解：数学模型为： s.t.

二、目标规划的基本概念

目标规划是对每个优化目标预先给定一个理想的期望值，再把实际达到值与期望值之偏差作为目标的偏差变量（分别叫正负偏差变量），将对目标函数求极值问题转化为对目标偏差变量求极值的问题。具体地说，就是引入一个达成函数作为目标函数，也可以把原优化系

运筹学教案

统中的任何一个约束条件视为一个优化目标，而把原目标函数视为一个目标约束增加在原优化问题的约束条件中。 三、目标规划的数学模型（以上例为依据）

1、引入偏差变量与目标约束

设0为预定销售额目标的差值，叫负偏差变量；为超过预定销售额目标的差值，叫正偏差变量。在上例中，有下列三种情况：

①当销售额小于250000元时，有＞0且，则 成立； ②当销售额大于250000元时，有＞0且，则成立； ③当销售额等于250000元时，有=，则成立。

这三种情况可全并为一个等式：，把为目标约束，其中至少有一个为0。

2、引入达成函数

设目标约束的一般式为：，其中为目标的预定值，那么达成函数有五种形式：

①，不关心超过量大小（越大越好），不足量xx好，最优值为，这时目标约束为，即，希望；

②，不关心不足量大小（越大越好），超过量xx好。这时最优值为，目标约束为，即，希望；

运筹学教案

③，希望不足量与超过量之和xx好，最优值为，即，意味着； ④，不足量，超过量超过最优值（为），意味着要求无关，超过值越大越好，相当于求。

⑤，不足量，超过量时，趋于最优值（为），意味着要求无关，不足值越大越好，相当于求。

3、下面以上述例题为例，说明达成函数与目标约束怎样配合？ ①，叫作销售额不少于250000元（即使不能达到也要尽可能接近250000元。

②，叫作销售额不超过250000元（即使超过了也要尽可能接近250000元。

③，叫作销售额尽可能接近250000元。 三、 目标规划的图解法（适用于两个决策变量）

例3 某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表： 产品 Ⅰ Ⅱ 1 2 限量 11 10 原材料（kg/件） 2 设备工时（h） 1 运筹学教案

利润（万/件） 9 10 解：该例用单纯形法求解，为：

maxz8x110x22x1x211x12x210x120解之，得：x1

4,x23,Z62(万元）例4 现对上例考虑：

①Ⅱ的产量不低于Ⅰ的产量（即，也就是的值不超过0）；

② 充分利用设备有效工时，但尽量不加班（即所用的总设备工时不大于10，也不小于10，也就是尽量接近于10）； ③ 总利润不小于56万元；

④引入优先因子。

解：由上原则，上述三种目标对应的目标函数和目标约束分别为： ① ②

③

总结以上分析，由例4的要求，该线性规划的数学模型为：

minZP1d1P2(d2d2)p3d32x1x211

运筹学教案

x1x2d1d10

x12x2d2d210

8x110x2d3d356x1,x2,d,d0ii

1、以为轴作出直角坐标系。

2、对于绝对约束的作直线方法与一般线性规划的图解法相同； 3、对于目标约束条件，先令=，作各目标约束的直线，在直线两侧标上和的方向，表明目标约束可以沿和所示的方向平移。

例如，对于直线，它右下半平面为（即>0）（因为当增加时有），所以该直线的右下方为增加的方向，那么它的左上方为增加的方向。

4、最后根据目标函数中的优先因子求解。本例子先考虑在⊿OBC边界和其中取值;再实现目标函数中的时，线段可在EDxx取值；最后在目标函数中实现，从图中判断可以使的取值范围缩小在线段GDxx。这就是该目标规划的解，可求得G和D的坐标分别是（2，4）和（10/3，10/3），GD的凸线性集合就是该目标规划的解。 x2

F E

B x1x20 d1 2x1x211 d1 运筹学教案

d3 G C x12x210 d2 O

三、课堂小结（5分钟） 四、布置作业：

授课题目 ： 第四章 目标规划 第三节 目标规划的单纯形法 教学目的与要求： 1.知识目标：了解目标规划的单纯形法的定义与操作步骤。 2.能力目标：能够运用目标规划的求解原理进行表上操作。目标规划单纯形求解步骤中检验数的计算。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 运筹学教案

教学重点： 1.掌握目标规划的单纯形法。 2.掌握目标规划的目标规划的单纯形法与普通单纯形求解方法的区别。 教学难点： 目标规划的单纯形法的定义与操作步骤。掌握目标规划法单纯法求解步骤与一般线性规划单纯形法求解步骤的区别。 教学过程： 1.复习旧课（通过提问方式复习回顾上次内容，情景假设导入本次内容。5分钟） 2.新课 （60分钟） (3)目标规划单纯形法的定义与分类（30分钟） (4)目标规划单纯形法操作步骤（30分钟） 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业 《目标规划：单纯形法求解》（2课时）

【教学流程图】 复习旧课

目标规划单纯形法概述

运筹学教案

目标函数的系数

目标规划单纯形法求解步骤检验数为多项式

检验数为负值的判定

具体实例

课堂练习

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动式教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标

运筹学教案

和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（一）复习旧课：（5分钟）

引入：（1）目标规划单纯形法的定义 （学生边回答，老师边板书）

导入提问：目标规划单纯形法与一般单纯形法的操作区别是什么？

（二） 新课： 一 实例引入

例5 对上例4用单纯形法求解。 解：列出单纯表如下：

Cj xB CB 0 x1↓ 0 0 0 d 1P1 d 1P2 d 2P2 d 2P3 0 d↓ 3x2↓ x3 d 3b 运筹学教案

11 x3 d1 d2 P2 2 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 -1 1 -1 0 10 56 [2] 10 d3 P3 8 2 j P1 P2 P3 x3 d1 -1 -8 3/2 3/2 1/2 [3] -2 -10 1 1 -1/2 1/2 1/2 1/2 -1/2 -1/2 1 6 5 5 x2

6 d3 P3 -5 5 -1 3 2 4 2 6

j P1 1 1 -5 -2 -3 P2 P3 x3 d1 -3 1 1 5 2 1 -1/2 1/2 -1 3 -1/2 [1/2] -1/6 1/6 1/3 -1/3 x2 x1 j P1 1 1 4/3 -4/3 -5/3 5/3 1 1 1 1

P2 P3 运筹学教案

1 -6 -1/3 -1/3 -1 1 1

1

x3 1 1 1 -1 2 1 -1 -2 6 d3 x2 x1 j P1 -1/3 2/3 1/3 1/3 -2/3 1/3 1 P2 P3 二、单纯形表的特点：

1、因目标函数为最小化，故以检验数作为最优准则； 2、因非基变量检验数含有不同等级的优先级因子，需逐级考虑。…，n为列序号，为行序号，因，从每个检验数的整体看，检验数的正负首先取决于的系数的正负，若=0，检验数的正负取决于的正负，下面依次类推。

三、目标规划单纯形求解的步骤：

1、化为标准型，建立初始单纯形表，表中将检验行按优先级因子个数分别列成K行，置；

2、检查该行中是否存在负数，且对应的前行的系数为0。若有，取其中最小（最负）者对应的变量为进基变量，再转第3步，若无负数，则转第5步；

运筹学教案

3、按最小比值原则确定离基变量，当存在两个或两个以上的相同最小比值时，就选具有较高的优先级别的变量为换出变量；

4、按单纯形法进行迭代运算，建立新的运算表，再返回第2步； 5、当，返回到第2步。 四、例5的求解分析：

下面以上例题为例，分析单纯形求解的步骤。

1、化为标准型：取第一个约束中加上松弛变量，取、、、为初始基变量，列出初始单纯形表；

2、对取=1，检查检验数的行，因该行无负检验数，执行步骤3；

3、按步骤5，因为<，返回步骤2；

4、按步骤2检查行有-1，-2，取-2对应的进基，执行步骤3，计算最小比值为离基变量，执行步骤4；

5、按步骤4进行迭代，得表的第二横栏，再返回步骤2，直至得到最优表为止。

二.课堂练习（20分钟） 三.课堂小结（5分钟）

运筹学教案

四.布置作业

授课题目 ： 第四章 目标规划 第四节 目标规划的灵敏度分析 教学目的与要求： 1.知识目标：了解目标规划的灵敏度分析。 2.能力目标 ：掌握目标规划的灵敏度分析。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 目标规划的灵敏度分析 教学难点： 目标规划的灵敏度分析 运筹学教案

教学过程： 1.复习旧课（通过提问方式复习回顾上次内容，情景假设导入本次内容。5分钟） 2.新课 （60分钟） 目标规划的灵敏度分析 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业

《目标规划：目标规划的灵敏度分析》（2课时） 【教学流程图】 复习旧课

目标规划灵敏度分析概述

目标规划灵敏度分析步骤

运筹学教案

具体实例

课堂练习

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动式教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】

运筹学教案

一 、教学过程：

（一）复习旧课：（5分钟）

引入：（1）目标规划灵敏度分析的定义 （学生边回答，老师边板书）

导入提问：目标规划灵敏度分析与对偶问题灵敏度分析的操作区别是什么？

（二） 新课：

目标规划的灵敏度分析

例5 已知目标规划问题

minP1d1,P2d2,P3(5d33d4),P4d1

x12x2d1d1 6 d2d2 9x12x2  d3d3 4 x12x2  x dd2244x1,x2,di,,di0 i1,2,3,4

目标函数分别变为：

（i） （ii）

运筹学教案

解 目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。

表4—6

cj 0 0 p1 d1 0 -1 0 0 1 0 0 1 p4 d1 0 1 0 0 0 0 0 0 0 p2 d2 -1/2 -1 1/4 -1/4 0 1 -3 1 5p3 0 3p3 d4 0 0 1 0 0 0 0 0 0 CB 0p43p30 XB x1d1d4 b 13/2 3 3/4 5/4 P1 P2 P3 P4 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d2 1/2 1 -1/4 1/4 0 0 3/4 -1 d3 1/2 0 1/4 -1/4 0 0 17/4 0 d3 -1/2 0 -1/4 1/4 0 0 3/4 0 d4 0 0 -1 0 0 0 3 0 x2cjzj 1．当目标函数变（i），就是要了解交换第三和第四优先级目标对原解的影响。此时，单纯形表变为表4—7

表4—7

cj 0 0 p1 d1 0 -1 0 0 1 0 1 0 p3 d1 0 1 0 0 0 0 0 0 0 p2 d2 -1/2 -1 1/4 -1/4 0 1 1 -3/4 5p4 d3 1/2 0 1/4 -1/4 0 0 0 17/4 0 3p4 d4 0 0 1 0 0 0 0 0 0 CB 0p33p40 XB x1d1d4 b 13/2 3 3/4 5/4 P1 P2 P3 P4 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d2 1/2 1 -1/4 1/4 0 0 -1 3/4 d3 -1/2 0 -1/4 1/4 0 0 0 3/4 d4 0 0 -1 0 0 0 0 3 x2cjzj 运筹学教案

表4—8

cj 0 0 p1 d1 1/2 -1 -1/4 1/4 1 0 0 3/4 p3 d1 -1/2 1 1/4 -1/4 0 0 1 -3/4 0 p2 d2 0 -1 0 0 0 1 0 0 5p4 d3 1/2 0 1/4 -1/4 0 0 0 17/4 0 3p4 d4 0 0 1 0 0 0 0 0 0 CB 003p40 XB x1d2d4 b 5 3 3/2 1/2 P1 P2 P3 P4 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d2 0 1 0 0 0 0 0 0 d3 -1/2 0 -1/4 1/4 0 0 0 3/4 d4 0 0 -1 0 0 0 0 3 x2cjzj 2．当目标函数变（ii），就是要了解第三优先级中两目标权系数取值对原解的影响。

表4—9

W2P3 cj 0 0 p1 d1 0 -1 0 0 1 0 0 1 p3 d1 0 1 0 0 0 0 0 0 0 p2 d2 -1/2 -1 1/4 -1/4 W1P3 0 0 CB 0P4W2P30 XB x1dd14 b 13/2 3 3/4 5/4 P1 P2 P3 P4 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d2 1/2 1 -1/4 1/4 0 0 W2/4 -1 d3 1/2 0 1/4 -1/4 d3 -1/2 0 -1/4 1/4 0 0 W2/4 0 d4 0 0 1 0 0 0 0 0 d4 0 0 -1 0 0 0 W2 0 x2cjzj 0 0 1 0 -W2/4 W1-W2/4 1 0

二.课堂练习（20分钟）

运筹学教案

三.课堂小结（5分钟） 四.布置作业

授课题目 ： 第五章 整数规划 第一节：整数规划的数学模型及解的特点 第三节：分支定界法 运筹学教案

教学目的与要求： 1.知识目标：掌握整数规划的概念、类型和作用及其求解方法概述；掌握分支定界法的基本概念与求解思路； 2.能力目标：掌握分支定界法的求解步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1、分支定界法的基本概念； 2、分支定界法的操作原理与步骤。 教学难点： 1、分支与定界的方法； 2、图解法在分支定界法中的应用。 教学过程： 1.举例引入（ 5分钟） 2.新课讲解 （80分钟） （1）分支与定界原则与方法（20分钟） （2）分支定界法操作步骤（40分钟） （3）学生操作（20分钟） 3.课堂小结（5分钟） 5.布置作业 《整数规划：定义、类型、求解综述和分支定界法》

（2课时）

【教学流程图】

运筹学教案

举例引入整数规划

整数规划的定义与分类

整数规划的定义、分类与求解综述整数规划的xx问题 整数规划的几种求解方法

分支方法 定界方法

分支定界法的求解过程解的搜索法

最优解的确定

课堂练习 （结合例题讲解进行）

课堂小结

布置作业

运筹学教案

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（二） 举例引入整数规划：（5分钟）

（1）整数规划的定义 （2）整数规划的分类 （3）整数规划的求解综述 导入提问：怎样运用分支定界法？ （二） 新课： 第五章整数规划

第一节 整数规划的数学模型及解的特点

运筹学教案

一、整数规划的定义与分类 二、整数规划的求解方法综述 第三节 分支定界法

一、 主要思路

1、要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，其相对应的线性规划问题叫该整数规划的松弛问题。求解整数规划时，首先求解与它相对应的松弛问题，如果它的松弛问题的最优解满足整数要求，则得该整数规划的最优解，否则通过增加新的函数约束来缩小其松弛问题的可行域，将原整数规划模型分为两个子规划模型，并除去可行域中的无整数解的部分，达到分枝的目的。然后对每一个子规划模型的松弛问题再求解，以此类推，并不断定界，最后求得原问题的最优解。

2、分枝的方法：

选择目标函数中系数绝对值最大的变量先分枝； 选择与整数值相差最大的非整数变量先分枝； 人为地按变量的相对重要性进行选择。

3、定界与剪枝 1）定界方法：

运筹学教案

①求解整数规划时，如果解它的松弛问题得到的不是一个整数解，则最优整数解一定不会优于所得松弛问题的目标函数值，即松弛问题的的解必是整数规划问题的目标函数值的一个界，它对于最大值问题是上界，对于最小值问题是下界。

②如果在求解整数规划的松弛问题的过程中已经得到了一个整数解，则最优整数解一定不会劣于该整数解，因此该整数解可构成最优整数解的另一个界，对于最大化问题它为下界，对于最小化问题它为上界。

③以上讨论可用不等式表示如下：

---松弛问题的解； ---目前已找到的整数解， ----最优整数解； ---上界，---下界。则最优整数解满足： 对于最大化问题：；对于最小化问题：。

显然如能找到一种方法，或降低上界或提出高下界，最后使得上界等于下界，就可以搜索得到最优整数解。

2）求解任何一个问题或子问题都有三种结果：

子问题无可行解，此时无须继续向下分枝，将其剪枝； 得到一个非整数解，继续向下分枝；

如得到一组整数解，则不必继续向下分枝，因该点有整数解而被关闭。 二、例题分析

运筹学教案

例1 求解下列整数规划：

maxZ40x190x29x17x256 7x120x270

xj0,j1,2,x1,x2是整数x29x17x256G(4.81，1.82） 7x120x270 x1

第一步：用图解法求出原整数规划问题的xx问题的解。对=4.81按 和

进行分支，得到原整数规划问题的xx问题的两个子xx问题如下。然

后对原整数规划问题的xx问题进行定界（上界与下界）。

两个子问题由原问题的xx问题分别加上分支的两个约束条件组成，再用图解法求出它们的解。

和

运筹学教案

x29x17x256G(4.81，1.82） 7x120x270 4 5 x1

第二步：根据对节点分支的三种情况：剪支、停止分支和继续分支，对上述两个子问题进行继续分支。又分别得到两个子问题。如此下去，是否无穷次分支？需由定界来确定。

第三步：最后如果得到一个整数解，即为最优整数解；如得到几个整数解，取目标函数值最大者为最优整数解。

运筹学教案

问题B

maxZ40x190x2

9x17x2567x120x270xj0,j1,2,x14.81 x21.81 Z0356Z0,Z356

 x14 x15 maxZ40x190x29x17x2567x120x270x14xj0,j1,2,问题B1 问题B2 maxZ40x190x29x17x256

x 1  4. 00 x1  5 .00 7x120x270x22.10 x21.57 Z1349Z2341x15xj0,j1,2, Z0,Z349 x22 x23 maxZ40x190x29x17x2567x120x270x14,x12xj0,j1,2,问题B3 问题B4 maxZ40x190x29x17x256

x 1  4 x 1  1 .42 7x120x270x22 x23 x14,x13Z3340Z4327xj0,j1,2,

Z340,Z341



x21 x22

maxZ40x190x29x17x256 7x120x270问题B5 问题B6 maxZ40x190x29x17x256

x 1  5 .44 7x120x270x21 无可行解 x15,x22Z5308xj0,j1,2,x15,x21xj0,j1,2,

Z340Z*

运筹学教案

三、课堂小结

四、学生作业，安排下次课内容。

授课题目 ： 第五章 整数规划 第二节：解整数规划的割平面法 教学目的与要求： 1.知识目标：掌握解整数规划的割平面法的概念与求解思路； 2.能力目标：掌握解整数规划的割平面法的求解步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1、割平面法的概念与求解思路； 2、割平面法的操作原理与步骤。 教学难点： 1、割平面法的概念与求解思路； 2．单纯形表的最终表结构； 2、割平面法的操作原理与步骤。 运筹学教案

教学过程： 1.举例引入（ 5分钟） 2.新课讲解 （80分钟） （1）割平面法的概念（20分钟） （2）割平面法的求解思路（20分钟） （3）割平面法的求解步骤（20分钟） （3）学生操作（20分钟） 3.课堂小结（5分钟） 5.布置作业 《整数规划：割平面法》（2课时） 【教学流程图】

举例引入整数规划的割平面法

解整数规划的割平面法的基本思路 单纯形法的最优表的结构 割平面方程的确定

解整数规划的割平面求解过程插入割平面约束的单纯形表 对偶单纯形法

用割平面方程求解整数规划时解的收敛性

运筹学教案

课堂练习 （结合例题讲解进行）

课堂小结

布置作业 【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是xx活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】 一 、教学过程：

（三） 举例引入整数规划：（5分钟）

运筹学教案

（1）整数规划的定义 （2）整数规划的分类 （3）整数规划的求解综述 导入提问：怎样运用分支定界法？ （二） 新课： 一、割平面法

（一）基本原理

线性规划的任一约束方程是n维空间的一个半平面，故先用单纯形法解它的松弛问题得最优解，若满足整数向量，则的最优解。若不全为整数，则设法给松弛问题增加一个线性约束条件（叫割平面方程），它将松弛问题的可行域割去一块，且这个非整数解恰恰在被割掉的区域内，但原问题的任何一个可行解都不会被割去。若把原松弛问题的最优单纯形表记为，把增加了割平面方程的问题记为，为原问题的一个改进的松弛问题，用对偶单纯形法求解，若得到的最优解为整数向量，则计算结束，否则对再增加一个割约束，形成问题，…，直到得到最优整数解。

（二）例题分析

例1 用割平面法求解纯整数规划：

运筹学教案

maxZx1x2

x1x213x1x24x12为0的整数

解 1、松弛问题的单纯形表为：

目标函数 决策变量 基变量 最优表 x2 Cj 1 1 0 0 常数 x1 x2 x3 x4 1 1 2、求割平面方程

0 1 3/4 1/4 1 0 -1/4 1/4 0 0 -1/2 -1/2 7/4 3/4 -5/2 x1 j 割平面方程并不惟一，一般取基变量的小数部分具有最大绝对值的变量所在行的约束方程为导出方程，能够更快地得出最优整数解。这里选取第二个约束，写出约束方程：

（1）

将上式左边的非基变量的系数和右端常数写成一个整数和一个非负真分数之和：

（2）

把上式系数为真分数的各项移到等式右端，将整数移到左端：

运筹学教案

（3）

因为整数，原整数规划约束条件中各系数和右端常数也为整数，所以也为整数。由于上式左边为整数，右边也应为整数。又，由于从所以3/4减去两个正数必有：

（4）

得：（因上式左边为整数）（5） 为避免引入工变量，将上式改写成：（6） 加入松弛变量，化为等式约束：（7）

（6）式和（7）式分别为割平面约束条件和割平面约束方程。将（7）式添加到原的约束条件中，得：

maxZx1x2x1x2x31 3x1x2x44313x3x4x5444xj0,j1,2,3,4

由灵敏度分析可知，增加一个割平面约束，只需把（7）式加入最优表作为第3行，由于为基变量，它的检验数为0，而原来的各变量的检验数和目标值均保持不变。现用对偶单纯形法求解如下： 目标函数 Cj 1 1 0 0 0 常数 运筹学教案

决策变量 基变量 原最 优 表 x2 x1 x5 1 1 0 x1 x2 x3↓ x4 x5 0 1 3/4 1/4 0 7/4 1 0 -1/4 1/4 0 3/4 0 0 [-3/4] -1/4 1 0 0 -1/2 -1/2 0 1/21/22，） 3/41/43 -3/4→ 1 j min(新最 x2 1 1 0 0 1 0 0 0 优表 x1 x3 1 0 0 1/3 -1/3 1 0 0 1 1/3 -4/3 1 0 0 0 -1/3 -2/3 j 二、学生练习（结合例题讲解进行） 三、课程小结

四．布置下次课的教学内容 授课题目： 第五章 整数规划 第四节 指派问题 运筹学教案

教学目的： 掌握整数规划的指派问题求解的步骤。 教学要求： 要求与学生与教师配合能操作上次课的例1。 教学重点： 掌握整数规划指派问题的求解原则。 教学难点： 整数规划指派问题求解中匈牙利法的步骤。 教学手段与方法： 先用实例引入，再采用比较演示方法。

一、 实例引入

例1 有一项说明书要由汉语分别译成英、日、xx、俄四种文字，交由甲、乙、丙、xx4个译员去完成。因各人专业不同，因此译成不同文字所

运筹学教案

需要的时间不同。假设各人完成各项工作的时间如下表，问应如何分配才能完成4项给定任务的总时间最少？

工作 译员 甲 乙 丙 丁 1 2 3 4 （汉译英） （汉译日） （汉译德） （汉译俄） 3 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 解 用0-1 模型 ，

1 分配第i人做第j件工作

xij

0 不分配第i人做第j件工作 那么有：

minZ3x1110x129x137x1415x2111x2214x238x2413x3114x3216x3311x344x4115x4213x439x44 x11x12x13x141

x21x22x23x241 x31x32x33x341 x41x42x43x441

s.t.

运筹学教案

x12x22x32x421 x13x23x33x431

x14x24x34x441

xij0(i1,2,3,4;j1,2,3,4)

定理1 如果从分配效率矩阵[]的每一行元素分别加（减）一个常数，从每一列元素分别加（减）一个常数，得到新的效率矩阵[]的最优解等价于原效率矩阵的最优解。

定理2 xx矩阵A中的元素分为零元素和非零元素两部分，则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为独立零元素）的最大个数。此定理告诉了效率表中有多少独立零元素的辨别方法。

二、指派问题的xx解法

第一步 转换效率矩阵[]，使各行各列都有出现零元素 从每行元素减去该行最小元素；再从所得的效率矩阵每列减去该列的最小元素。若某行（列）已有零元素，就不必再减了。

上例中：

3 10 9 70 7 6 40 714

=154 14 8 = 11 0 10 4 = 11 054

13 14 16 112 3 5 02300

运筹学教案

415 13 90 11 9 50 1145

第二步 试求最优解，找出m个独立零元素

1、从第一行开始，遇到每行只有一个零元素就用括号括上，记作（0），然后划去其所在列的其他零元素，用 ○表示，遇到有两个及其以上零元素的行先跳过去；

2、进行列检验，从第一列开始，给只有一个零元素的列中的那个零元素用括号括上，然后划去它所在行中的其它零元素。反复进行1、2步，直到所有零元素被划去或括上为止。

3、以上已划去或括上的零元素不算在内。 经过第二步以后，会出现三种情况：

其一、打上括号的零元素分布在不同的行与列，且其个数等于系数矩阵的阶n，即得最优解。令其对应的1，其余的为0；

其二、仍存在未括上与划去的零元素，且同行（列）的零元素至少有两个（即零元素形成闭回路），这时从含零元素最少的行（列）开始，比较该行（列）各零元素所在列（行）中零元素的个数，选择含零元素最少的那一列（行）的这个零元素加上括号，然后划去与这个零元素同行同列的其它零元素。

如此反复进行，直到所有零元素被划去或括上为止。

运筹学教案

其三、经过以上几步后，若被括上的零元素数目等于系数矩阵的阶n，即得最优解，否则进入第三步。

上例： （0） 714 11 （0） 54 23 （0） ○ ○1145

第三步 增加零元素

1、作能覆盖所有零元素（指括上的和划去的零元素）的最少直线，其数目等于加括号的零元素个数。

方法：1）对没有（0）的行打√；

2）对打√的行上所有○ 元素所在的列打√； 3）再对打√的列上所有（0）元素所在的行打√。 重复2）和3），直到得不出新的打√的行和列。

4）对没有打√的行画横直线，对所有打√的列画纵直线，得到能覆盖所有零元素的直线。

运筹学教案

（0） 714 11 （0） 54 23 （0） ○ ○1145

2、再对系数矩阵进行变换，以增加零元素

对没有被直线覆盖的部分找出最小元素，对没有画直线的行中所有非零元素各减去，对画直线的列中所有非零元素各加上，并保持原来零元素（划去和打括号的）不变，得到新的系数矩阵。

第四步 对新的系数矩阵又从第二步开始，若能求n个不同行与列的零元素，即得最优解，否则又进入第三步：增加零元素。

06030603 1105412054 23003300 0103401034

本例又从第二步开始：

○6 （0） 3

运筹学教案

12 （0） 54 33○ （0）

（0） 1034

授课题目： 第七章 动态规划 第一节 多阶段决策过程的最优化 第二节 动态规划的基本概念和基本原理 教学目的： 掌握动态规划的基本概念、基本思想和模型特点。 教学要求： 要求与学生与教师配合能操作上次课的例1。 运筹学教案

教学重点： 掌握动态规划的基本思想和模型特点。 教学难点： 动态规划的逆序解法和顺序解法。 教学手段与方法： 先用实例引入，再采用比较演示方法。

第七章动态规划 一、动态规划的基本概念

动态规划是解决多阶段决策各过程最优化问题的一种数学规划的方法。 二、基本概念

1、阶段：按时间/空间分解成若干相互联系的段落，用…表示。 2、状态：各阶段开始时的客观条件，用状态变量表示，的取值集合用表示，不具备无后效性的变量不能作状态变量；当某阶段的状

运筹学教案

态给定以后，这阶段以后过程的发展只受该阶段状态的影响，而与该阶段以前的状态无关，状态的这一性质叫无后效性

3、决策和策略

当各阶段的状态给定以后，就可以做出不同决定选择，从而确定下一阶段的状态，这种选择决定叫做决策，用表示第阶段的当状态为时的决策变量，其取值在一定范围内，此范围叫允许决策集合，用表示，因此有

uk(sk)Dk(sk)

整个问题的决策序列叫策略。用表示。 4、状态转移方程

用表示第阶段的状态是第阶段的状态和决策变的函数。 5、指标函数

用来衡量所选定策略优劣的数量指标。用表示。 三、动态规划求解的基本思想

把一个多目标决策划分为若干阶段，恰当地选取状态变量和决策变量及定义最优指标函数，从而把整个决策问题分解为一簇同类型的子问题，再从边界条件开始，逆（或顺）过程行进方向，逐段递推求出最优解。

运筹学教案

顺推法：

fk(sk)vk(sk,uk)fk1(sk1)f0(s0)0

逆推法：

fk(sk)vk(sk,uk)fk1(sk1)fn1(sn1)0

四、动态规划在经济管理中的应用

（一）背包问题 1、基本模型

一维背包：一位旅行者能承受重量bkg,，现有n种物品供他选择装入背包，第物品的单件重量为,总价值是携带数量的函数，求应如何选择携带物品的件数使总价值最大？

二维背包：如增加到两个约束条件，如背包体积限限制为立方米，并假设第i种物品每件体积为立方米，应如何选择携带物品的件数使总价值最大？

模型：一维背包

maxZcixii1n s.t.aixibi1n

xi0且为整数运筹学教案

二维背包

maxZcixii1n

wxi1nniiab

axi1iixi0且为整数2、求解方法：

①阶段序，每时间段装入一种物品，那么共需个时间段。

②状态变量表示第第阶段开始时允许装入前种物品的总重量，有，因已知，故用顺序解法。 ③决策变量种物品的件数。 ④状态转移方程：

⑤允许的决策集合是︱，为整数}，式中 为不超过的最大整数。

这里的最大值表示只装运第种物品，其余-1种物品的装运量为0。

⑥最优指标函数表示在背包中允许装入物品的总重量不超过 公斤时背包中允许装入第1-种物品的最大使用权用价值。

⑦于是得到动态规划的顺序递推方程： 阶段指标为 ，递推方程为：

运筹学教案

fk(sk)max{ckxkfk1(sk1)}max{ckxkfk1(skwkxk)}边界条件为f0(s0)0例1 货物装载问题L准备在一艘货船上装载3种货物，每箱重量和单价见下表，货物总载重为7t，求3种货物各装多少箱才使总价值最大？

货物编号 i 每箱重量 wi 每箱价值 vi 1 3 4 2 4 5 3 5 6 解：1、

s1 sx1[1] w10 1 2 3 5 0 1 6 7 8 9 10 0 0 0 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3 0 1 2 3 c1x1 f1(s1) x1* 0 0 0 0 4 0 0 0 0 0 0 4 1 0 4 4 1 0 4 8 0 4 8 0 4 8 0 4 8 12 8 2 8 2 8 2 12 3 0 4 8 12 12 3 2、

s2 x2[s2/w2] c2x2 s1=s2-c2x2 f1(s1) 0 1 2 3 0 0 0 0 0 0 0 0 0 1 2 3 0 0 0 4 4 0 1 0 5 4 0 4 0 5 6 7 0 1 0 5 7 2 8 4 8 0 1 2 0 5 10 8 3 0 8 4 0 9 0 1 2 10 0 1 2 0 1 0 1 0 5 0 5 5 0 6 1 4 0 8 0 0 5 10 0 5 10 9 4 0 12 4 0 10 5 0 12 8 0 运筹学教案

8 9 10 10 2 1 0 2 12 9 10 12 3 1 0 0 12 13 10 13 3 2 0 1 c2x2+f1(s1) f2(s2) x1 *x2 0 0 0 4 0 0 0 4 0 0 0 1 0 0 0 0 4 5 5 1 0 1 4 5 8 5 5 8 1 0 2 0 1 0 8 9 9 2 1 1 3、

s3 x3[s3/w3] 0 1 2 3 4 5 0 1 0 6 5 0 6 0 1 7 0 1 8 0 1 0 6 8 3 10 10 9 10 c3x3 s2=s3-c3x3 f2(s2) c3x3+f2(s2) f3(s3) *x3 0 0 0 0 0 0 0 0 0 0 0 1 2 3 5 0 1 0 1 2 0 6 9 4 12 5 12 0 6 12 10 5 0 13 5 0 13 11 12 13 0 0 6 0 6 6 1 8 8 0 2 8 5 5 5 5 由=13，对应=10，=0；由=-=-0*5=10，此时=1；由=-=10-4*1=6，对应=2。

3、总结建立动态规划模型的步骤： 1）划分阶段

2）确定状态变量及其取值范围：原则是它能描述过程演变的状态，

又满足无后效性的要求；

运筹学教案

3）确定决策变量及其取值范围；

4）建立状态转移方程 ，必须具有递推关系；

5）确定阶段效应函数，建立动态规划的函数方程：函数方程是动态

规划最优指标的函数形式，一种为加法型，一种为乘法型。阶段效应函数可以为收益函数（利润、产量等），也可为损失函数（成本）。第阶段的最优指标函数是从第阶段到第n阶段单调递增或递减的总效应。

授课题目： 第三节 动态规划模型的建立与求解 教学目的： 掌握动态规划中的生产与存贮问题求解的步骤。 教学要求： 要求与学生与教师配合能操作上次课的例1。 运筹学教案

教学重点： 掌握生产与存贮问题的求解原则。 教学难点： 生产与存贮问题的求解步骤。 教学手段与方法： 先用实例引入，再采用比较演示方法。况 课后小结：

例2 某工厂生产并销售某种产品，已知今后四个月的市场需求量预测如下表：

阶段k（月） 需求量dk 1 2 2 3 3 2 4 4

单位生产成本为： 0

运筹学教案

Ck

3+1·…，6

已知该厂最大的库存容量为3单位，每月最大生产能力为6单位，并假设第+1个月的库存量为第个月可销售量（等于第个月库存量与生产量之和）与该月用户需求量之差。每批产品的固定生产成本为3千元，不生产时设固定生产成本为0元，单位产品的生产变动成本为1千元，每月单位产品的库存费用为0.5千元。试制订4个月的生产计划，在满足用户需求条件下实现总费用最小（即从第1月初至第4月末的总生产成本最小）。

解： 1、分析：

① 阶段为月；

② 状态变量为第月初的库存量，其取值范围为0，1，2，3； ③ 决策变量月的生产量：当≥时，可以为0；当时，至少应生产；

由于每月最大生产能力为6，故6，而第月末（第月初）的库存为，其小于等于第月最大库存量

故有：

，

运筹学教案

。

故有允许决策集：

（1）

④ 状态转移方程

⑤ 逆推基本方程：由于每月的库存量是前一月库存量的函数，故

采用逆推，指标函数为第月状态为时，采用最佳生产，从第月初到第4月末的总成本。

fk(sk)minrk(sk,xk)fk1(sk1)

上式中

生产成本+库存成本=+ 0.5 0， 若

f5(5)0

⑥ 各阶段的允许状态集合和允许决策集合：

={0，1，2，3}，其中={0}，={0，1，2，3}。

D1(s1)D1(0)x1max[0,20]x1min[6,302]x12x152,3,4,5 D2(s2)x2max0,[3s2]x2min6[,3s23]

运筹学教案

D3(s3)x3max0,[2s3]x2min6[,3s32] D4(s4)x4max0,[4s4]x4min6[,0s44]

上式中第4个月因为=0，即。 2、逆推表： 1）的分布

，由公式（1）得下表1： 表1

s2 D2(s2) s3 0 1 2 3 {3，4，5，6} {2，3，4，5} {1，2，3，4} {0，1，2，3} 0 1 2 3 D3(s3) {2，3，4，5} {1，2，3，4} {0，1，2，3} {0，1，2} s4 D4(s4)

0 4 1 3 2 2 3 1 2）=4

表2 =4递推表

x4(s4) 状态s4 决策 （期末库（可能生 生产费用 本期费用r4(s4,x4) 库存费用 合计 总费用 f4(s4) 运筹学教案

存） 0 产量） 4 c(x4)31x4 3+4=7 E(s4)0.5s4 0.5*0 7 7 1 2 3 3 2 1 3+3=6 3+2=5 3+1=4 0.5*1 0.5*2 0.5*3 6.5 6 5.5 6.5 6 5.5 递推方程为： 。 3）=3

递推方程为：

f3(s3)minx3D3(s3)r3(s3,x3)f4(s4),式中r3(s3,x3)c(x3)E(s3)(3x3)0.5s3,f4(s4)见表2。

对=0，1，2，3分别求出

表3 =3递推表

本期费用r3(s3,x3) 生产费用库存费用 期末库存s4= 状态 决策 s3 x 3(s3) 0 2 3 4 5 以后各期最 小费用 总费用 f3(s3) c(x3)3x35 6 7 8 E(s3)0 0 0 0 0.5s3 合计 s3x320 1 2 3 f4(s4) 7 6.5 6 5.5 7 6.5 6 5.5 7 6.5 12 5 6 7 8 1 2 1 2 3 4 0 1 4 5 6 7 0 4 0.5 0.5 0.5 0.5 1 1 4.5 5.5 6.5 7.5 1 5 0 1 2 3 0 1 11.5 8 运筹学教案

2 3 1 2 3 6 5.5 6.5 6.0 5.5 8 3 2 3 0 1 2 5 6 0 4 5 1 1 1.5 1.5 1.5 6 7 1.5 5.5 6.5 4) =2

表3 =2递推表

本期费用r3(s3,x3) 生产费用库存费用 期末库存s3= 状态 决策 s2 x2(s2) 3 4 5 6 以后各期最 小费用 总费用 f2(s2)r2f3 c(x3)3x26 7 8 9 E(s3)0 0 0 0 0.5s2 合计 s2x230 1 2 3 f3(s3) 0 6 7 8 9 1 2 3 2 3 4 5 1 2 3 4 0 1 2 3 5 6 7 8 4 5 6 7 0 4 5 6 0.5 0.5 0.5 0.5 1 1 1 1 1．5 1．5 1．5 1．5 5．5 6．5 7．5 8．5 5 6 7 8 1．5 5．5 6．5 7．5 0 1 2 3 0 1 2 3 0 1 2 3 12 11．5 8 8 12 11．5 8 8 12 11．5 8 8 12 11．5 8 8 16 15.5 15 13.5 5）=1

表4 =1递推表

s2s1x1d1 s1 x1 c(x1) E(s1) 合计 f2(s2) r1(s1,x1) f1(s1)运筹学教案

5 6 7 8 16 15.5 15 13.5 5 6 21 7 8 0 0 1 2 3 2 3 4 5 5 6 7 8 0 0 0 0 由k1,f1(s1)2,得x12,s20;由s20,得x25,s32;由s32得x30,s40;由s40得x44.

授课题目 第四节 动态规划在经济管理中的应用 教学目的： 掌握动态规划中货郎担问题求解的步骤。 教学要求： 要求与学生与教师配合能操作上次课的例1。 教学重点： 掌握货郎担问题的求解原则。 教学难点： 货郎担问题求解的步骤。 运筹学教案

教学手段与方法： 先用实例引入，再采用比较演示方法。况 课后小结： 一、 求解方法

货郎担问题的一般描述：一个货郎从某村镇出发，经过若干个村镇、，…，一次且仅一次，最后仍回到原出发的村镇，已知从到的距离为，问应如何选择行走路线可使总行程最短？

1、顺推法分析：设S为从到中间所有可能经过的村镇之集合，但

S中点的个数要随阶段数而改变。为从到经过中间点的个数，以它来划分阶段。状态变量（,S）表示从出发经过S集合中所有村镇一次最后到达。最优指标函数表示从从出发经过含个村镇的S集合到的最短距离。,S）表示从出发经过含个村镇的S集合到的最短路线上邻接的前一个村镇。那么顺推方程为： ,,

f0(vi,)d1j(为空集，k1,2,,n1;i2,3,,n)

运筹学教案

例1 已知四个村镇之间的距离如下表，求从某村镇出发，经过村镇、，一次且仅一次，最后仍回到原出发的村镇，问应如何选择行走路线可使总行程最短？

v1 v2 6 0 8 5 v3 v4 9 7 8 0

v1 v2 v3 0 8 5 6 7 9 0 5 v4 解：（为方便起见，下面均以1，2，3，4代替、、、。）由边界条件，。

1）当=1（表示从出发经过由一个村镇组成的S集合到达的最短距离

为： ；

f1(2,4)f0(4,)d429514

；

f1(3,4)f0(4,)d439514

；

运筹学教案

f1(4,3)f0(3,)d347815

上述计算中，由于S集合中只有一个村镇，无需最小化。

2）当=2（表示从出发经过由二个村镇组成的S集合到达的最短距离

为 ， 所以

f2(3,2，4)min[f1(4,2)d43,f1(2,4)d23]min[35,149]18

所以

f2(4,2,3)min[f1(3,2)d34,f1(2,3)d24]min[158,157]22

所以

3）当=3（表示从出发经过由三个村镇组成的S集合到达的最短距离

为

f3(1,2,3，4)min[f2(2,3,4)d21,f2(3,2,4)d31,f2(4,2,3d41]min[208,185,226]23

所以

逆过程递推，————————，最短距离为23。 2、顺推法分析

运筹学教案

例2 2004年xx选举活动前一周，位于xx的候选人Walter Glenn先生必须访问迈阿密、达拉斯和xx三个xx，然后返回xx。已知这些xx之间的距离如下表。Walter Glenn先生希望最小化他必须经过的总距离，应该以什么顺序访问这些xx？

编号 1 2 3 4 城市 纽约 迈阿密 达拉斯 芝加哥 纽约 迈阿密 达拉斯 芝加哥 — 1334 1559 809 1334 — 1343 1307 1559 1343 — 921 809 1397 921 — 解：采用逆推法，按已经访问过的的xx数量来编号阶段；在任意阶段的状态由上一次访问过的xx和已经访问过的xx集组成。因为在任意阶段要确定接下来要访问哪一座xx需知道两个事件：Walter当前所处的位置xx和他已经访问过的xx集C（其中在任意阶段已经访问过的xx集C中有-1座xx），并规定为完成旅程所必须经过的最短距离，为他目前处于xx与下一步将要访问xx之间的距离 。

1、=4（阶段4），这时

这时状态变量，状态集={（2，{2，3，4}）、（3，{2，3，4}）、（4，{2，3，4}）}。，

， 。

2、=3（阶段3）

运筹学教案

由于Walter目前位于xx，并且将要到达xx，那么他需经过的距离为。然后他将处于阶段4，已经访问了xx，并且已经访问了中的每一个xx，因此他的剩余行程的距离将为。因此有：

（）

使用上公式时，注意Walter目前必须访问了{2，3}或{2，4}或{3，4}，并且接下来必须访问不等于1的非xx集C的xx。现用上式计算：

f3(2,2,3)d24f4(4,2,3,4)13978092206 f3(3,2,3)d34f4(4,2,3,4)9218091730 f3(2,2,4)d23f4(3,2,3,4)134315592480 f3(4,2,4)d43f4(3,2,3,4)92115592480 f3(3,3,4)d32f4(2,2,3,4)134313342077 f3(4,3,4)d42f4(2,2,3,4)139713342731

一般来说，对于

t1,2,3,有

ft(i,C)mindijft1[j,Cj]这里。因为如他现位于xx，并且接下来将要访问xx，那么他需经过的距离为。因此他的剩余的行程将从xx开始，，并且已经访问了中的每一个xx，因此剩余的行程距离必定为]。

3、=2（阶段2）

运筹学教案

在阶段2，因为Walter只访问了一个xx，因此唯一可能的状态为（2，{2}）、（3，{3}）和（4，{4}）。

d23f3(3,2,3)134317303073

f2(2,2)min

2480387 7 d24f3(4,2,4)1397

2731365 2 d34f3(4,3,4)921f2(3,3)min 22063549 d32f3(2,2,3)1343 2902429 9 d42f3(2,2,4)1397f2(4,4)min

2677359 8 d43f3(3,3,4)9214、=1（阶段1）

因此时Walter位于xx，并且还没有访问过任何xx，因此状态为，故有：

30734407 d12f2(2,2)1343 f1(1,)min d13f2(3,3)155935495108 35984407 d14f2(4,4)809

因此，Walter可以从xx1到2或4，任意地使其选择到4。然后必须选择访问可以得出的xx，这个xx要求Walter接下来访问3。然后必须访问可以得出的xx，这个xx要求Walter接下来访问2。然后

运筹学教案

必须选取择访问可以得出的xx，这个xx要求Walter接下来访问1。所以最优行程为：1-4-3-2-1，xx为。

授课题目 ： 第八章 图与网络分析 运筹学教案

第一节 图与网络的基本知识 教学目的： 掌握图与网络的的基本知识。 教学要求： 要求学生掌握欧拉图和中国邮递员问题。 教学重点： 掌握欧拉图和中国邮递员问题。 教学难点： 中国邮递员问题。 教学手段与方法： 先用实例引入，再采用比较演示方法。况

第八章 图与网络分析

第一节 图与网络的的基本知识

运筹学教案

一、引入：

例1（数学家xx与图）xx图

普瑞拉xx从xx哥尼斯堡市中心流过，河中有小岛两座，筑有七座xx，1736年，该市一市民向数学家提出一个问题：从家里出发，对七座桥每桥恰好通过一次，再回到家里，是否可行？

分析：xx把两岸分别用C、D表示，xx分别用A、B表示。此问题是寻找一条遍历多重图每条边恰好一次的回路，具有此性质的多重图叫xx图，对应的回路叫xx回路。

A B

C

运筹学教案

AB

D

二、图与网络的基本知识

1、图的定义

图是由点集和Vxx元素的无序对的一个集合组成的一个二元组，记为。

1）顶点和边 2）xx边 2、图的分类 1）xx和无向图 2）简单图与完全图

环和多重边 3）二部图 3、顶点的次

运筹学教案

1）孤立点

2）悬挂点和悬挂边 4、xx、支撑xx和生成xx 5、网络

1）有向网络和无向网络 2）权和最短路问题 6、连通图

1）点边序列和链、初等链 2）圈和初等圈 3）道路和回路

对于无向图，道路和链、回路和圈的意义相同。 7、图的两个定理

定理1 任何图中顶点次数的总和等于边数的两倍； 定理2任何图中次为奇数的顶点必有偶数个； 三、图的矩阵表示

四、xx回路与xx邮路问题

运筹学教案

1、xx回路与xx图

xx注意到哥尼斯堡多重图中每个结点的度都是奇数，因此图中任何结点都不能作为起始结点，因为回路都是从某个结点出发，再回到该结点，然后再从该结点出发，再返回，如此循环，那么这个结点的度应为偶数。

xx定理：多重图G是xx图当且仅当G是连通的且每个结点的度是偶数。

定理3 无向连通图G是xx图，当且仅当G中无奇点。

定理4 连通xxG是xx图，当且仅当每个顶点的出次等于入次。 2、xx邮路问题

例2 xx邮递员问题：xx邮递员从邮局出发，经过他所投递范围的每一条街道至少一次，完成投递任务后返回邮局，问应如何安排邮递员的行走路线才能使总行程路线最短？

解 1）、如G是xx回路，Euler 设计了一条求xx回路的算法： 2）、对于非xx图，邮递员返回邮局必须将图转换成xx图，为此需添加重复边以清除奇次顶点，与奇点xx的边应添加奇数条，与偶点xx的边应添加偶数条（含0条），现在的问题是求解使重复边总权重值最小的方案。

具体方法；

运筹学教案

1）、如果在配送范围内，街道拐弯处没有奇点，那么邮递员可以从配送中心出发，走过每条街道一次且仅一次最后回到配送中心，他走的路径为最短路径。

2）、对于有奇点的街道图，必须在一些街道重复走一次或多次，这样相当于我们在图中如之间增加几条重复边，令每条重复边的权与原来的边的权相等，于是这条路线就是新图中的xx图，它使新图不含奇点，并且重复边的总权最小。这一方案分两步（见下例）：

例1 一车辆从某配送中心出发，给街道上的7个超市-送货，求使总行程最短的送货方案。

第一步：使新图不含奇点而增加重复边

由图论，在任何一个连通图中，奇点个数必为偶数，所以如图中有奇点，可把它们配对。又因为图是连通的，故每一对奇点之间必有一条链，我们把这条链的所有边作为重复边加到图中去，新图中必无奇点。这就得出第一可行方案，即把使新图不含奇点而增加的重复边叫可行（重复边）方案。

图1 未加重复边前的图

24

533

运筹学教案

64

544

94

图2 将连接奇点和之间的一条链路加上重复边 24

533

64

544

94

运筹学教案

在图1xx，将奇点和、和配对。对前者连接两奇点的链路有好多条，任取一条（，，，，，，），把该链路上的每一条边加上重复边（见图2）。

同样对和之间的一条链（，，，，，，）也加上重复边（见图3）。在图3xx没有奇点，故它为xx图。其全部重复边的总权为51。

图3 对连接和之间的一条链路加上重复边

24

533

64

544

94

第二步 调整可行方案

运筹学教案

一般情况下如果在边[]上有两条或两条以上的重复边时，我们可以去掉偶数条，就能得到一个总长度较短的可行方案。现在我们图3进行这种处理，得到图4的最优方案。这种方案调整主要依据下面两个条件：

1）在最优方案中，图的每一边最多有一条重复边。2）在最优方案中，图中每个圈上重复边的总权不大于该圈总权的一半。

图4 24

533

64

544

94

对有两条或两条以上重复边的边去掉偶数条 运筹学教案

在图4xx，重复边的总权下降为21，但我们看到，的图4xx某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图xx仍然没有重复边。因而如果在某个圈上重复边的总权大于这个圈的总权的一半时，按这条原则又做一次调整， 使重复边的总长度下降为17，得最优方案（见图5）

图5 对图4进行调整后得到的可行方案

24

533

64

544

94

第三步 判断最优的标准

从上分析，一个最优方案，一定满足1）和2）的可行方案，反之，一个可行方案若满足1）和2），则一定为最优。因此对上述给

运筹学教案

定的可行方案图5，检查它是否满足1）和2），否则对该方案继续进调整，直至1）和2）均满足为止。在图5xx，圈（，，）xx重复边的总权为13，而圈的权为24，不满足条件2），对其再次进行调整得图6，使总权下降为15。

图6满足条件1）和2），其中任一个xx圈为汽车最优配送路线。

图6 最优方案 24

533

64

544

94

授课题目： 第二节 树 运筹学教案

第三节 最短路问题 教学目的： 掌握树的基本概念与最小生成树算法及求某点至某点的Dijkstra算法。 教学要求： 要求学生用表操作Dijkstra算法。 教学重点： 掌握用表操作Dijkstra算法。 教学难点： 用表操作Dijkstra算法。 教学手段与方法： 先用实例引入，再采用比较演示方法。 第二节树

运筹学教案

一、树的概念和性质

1、树的定义：连通且不含圈的无向图叫树。 2、定理6（略） 二、图的生成树

1、xx的生成xx是xx，叫该图的生成树。 2、找图的生成树的方法 ①探测法 ②广探法 三、最小生成树问题

1、具有最小权的生成树叫最小生成树。 2、求最小生成树的算法 ①避圈法

思路：从具有个点的图中的要边中选取条权尽量小的边，并且使之不构成回路，从而构成一棵最小树。

方法：将网络中所有边按权的大小由小到大排列起来，每步从未选的边中选取一条权最小的边逐条衔接，但不能xx圈。在每一步中，若有两条或更多条边都是权最小的边，则从中任选取一条。

运筹学教案

第一步：挑选边；

第二步：若已选定的边为：，则从中选取使：

1）所组成的圈为无圈图； 2）是满足1）的尽可能小的权。

第三步：当第二步不能继续执行时停止。

例1 某地有五个镇，拟架设电话线连接这五个镇，下图中边上的数字表示架设费用，问应如何架设电话线才能使总费用最小？

解：如图，可先连接权为1的—，再连接权为2的—，再连接权为3的—，再连接权为5的—，最后是权为5的—。

4 26 81

5 3 5

运筹学教案

②破圈法

思路：将图每一个圈权最大的一条边去掉，直到图中不含圈为止。 方法：在图中选取任何一个圈，从圈中去掉一条权最大的边（如有两条或两条以上的边都是权最大的边，则任意去掉其中的一条。然后在余下的圈中重复这个步骤，直到得到一个不含圈的图为止。这时的图就是最小树。

再以上图为例。

1）在图中找到一个圈，先去掉最大权8对应的边（，），得图； 2）在图中找到一个圈，去掉最大权数为6的边（，），得图；3）在图中找到一个圈，去掉最大权数4对应的边（，），得图；

4）在图中找到一个圈，去掉最大权数5对应的边（，）或（，），得图或，它们均为图的最小树。

第三节 最短路问题

一、Dijkstra算法

适用于所有权数为非负（则一切）的网络。能注出任意一点到各点的最短路径。其其基本思路是：若（，，…，， ）是从到的最短路径，则（，，…，）也是从到的最短路径。因此可采用标号的方法，从始点开始，逐步向外收缩从始点到其他各点的最短路径。

运筹学教案

例1．（6分）运用Dijkstra算法求出下面运输网络中从到的最短路径(不要求写出运算过程，可直接把最短路径填入下面的括号内)。

59

4474

5

45 61

76

设为连通图，图中各边（，）有权。令分别为固定标号集和临时标号集。固定标号最短路权，临时标号的估计最短路权的上界。

节点 迭代 序号 V3 V5 V6 V7 V8 V1 V2 V4 1 2 3 4 P,0 T，∞ T，∞ T，∞ ∞ T，∞ T， T，∞ T，∞ T，4 P,4 T，6 P,6 T，9 T，9 T，8 T，8 运筹学教案

P,8 5 6 7 8 9 P,9 T，13 T，13 P,13 T，14 T，14 T，14 P,14 T，17 T，15 P,15 步骤：

1）给以标号，则；其余各点给予标号，则；

2）若为刚得到标号的点，考虑这样的点：（，）属于且为标号，则对的标号值进行如下修改：；

3）比较所有标号的点的值，把最小者改为标号：。当存在两个最小值时，可同时改为标号；若全部点为标号时则停止，否则用代替，转向2）。

以上列表如上。

答：从到的最短路径为（）；路长。

例2运用Dijkstra算法求出下面运输网络中从A到B的最短路径和最短距离。

运筹学教案

（不要求在试卷上写出求解过程，可直接把结果写在下面的横线上）

●300● 200 275200● 100400100

●150 ●175●●

250 175150 200275● ●300● 125

节点 迭代 序号 V1 V2 V3 V4 V5 V6 V7 V8 B 1 2 3 4 T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T100 T150 T175 T，∞ T，∞ P,100 T400 T350 T375 T325 T425 P,150 运筹学教案

T425 5 6 7 8 P,150 T325 P,350 P,325 T725 T575 T550 P,425 T550 P,550 P,550 T650 P,550 答：A到B的最短路径为：A-----B；最短距离为650。

运筹学教案

授课题目 ： 第八章第3节某点到各点和某点到某点的距离摹乘法。 教学目的： 掌握距离摹乘法的操作程序。 教学要求： 学生能轮流上黑板做题。 教学重点： 掌握距离摹乘法的操作程序。 教学难点： 同重点。 运筹学教案

教学手段与方法： 先用实例引入，再采用比较演示方法。况 课后小结： 二、、逐次逼近算法（距离矩阵摹乘法）

适用于一切网络的最短路径的求解（含负权）。它基于这样的事实：从到的最短路径总是沿该路先到，再沿（，）到，。于是若从到为最短路，那么从到也为最短路。用分别表示从到和从到的最短路长，则必有下列方程：。

该方程可用迭代式求解：

1）令的直接距离作初始解，若它们之间无边，则 2）使用迭代法求，

当进行到第则停止计算。则为最多经t步到各点的最短路长。 （一）求各点到某点的最短路径

设距离矩阵为，先从走一步到（），再从走一步到，得到从走两步到的最短路径（）：

运筹学教案

（1）

这里为距离矩阵中的第i行元素，列的元素。它们的对应元素相加再取小，再从各点走一步到，然后走两步到（）：

（2）

最后得到从走一步到，再从走步到： （3）

最后得到的列中各元素是从第i行第个元素加取小而来，设这个元素为从到最短路径上的邻接点，最后按邻接点扒出最短路径。

例1求下图中各点到的最短路径。

解：第一步：写出网络的距离矩阵如下：其中第6列为各点到的距离。

从 至 s 2 3 4 5 6 s 2 3 4 5 6 0 5 2 ∞ ∞ ∞ ∞ 0 4 3 ∞ ∞ ∞ 4 0 ∞ -3 ∞ ∞ -2 5 0 1 ∞ ∞ ∞ 4 2 0 4 ∞ ∞ ∞ -2 ∞ 0 -2

运筹学教案

②④

3

5 -2 455 2

⑥

24 4 ⑤② -3

第二步：设从先走一步到中间点（），再从走一步到，得到从走两步到的最短路径（）：，相当于用距离矩阵各行与对应元素相加再取小。

(2)1)d16minwijd(j2 61j6052∞∞∞∞∞ ∞043∞∞∞∞

运筹学教案

=∞40∞-3∞ *∞1 ∞-2501∞∞=9 ∞∞420444 ∞∞∞-2∞000

第三步：设从走一步到中间点（），再从走两步到：

2(3))W*d16 d16minwijd(j261j6052∞∞∞∞3 ∞043∞∞∞5 =∞40∞-3∞ *11 ∞-2501∞9=6 ∞∞420444 ∞∞∞-2∞000 如此迭代得 3 5

运筹学教案

1

=6迭代终止得从走一步到的最短路径为： 4 0

由

______min3,05,41,33,4,05

～

______3,5,1,(2)3,,4,00 min0 05（2）∞∞∞

∞0（4 ）3∞∞

∞40∞（ -3 ） ∞

记为

∞ （ -2） 501∞

运筹学教案

∞∞420（4）

∞∞∞-2∞（0）

中第4个元素3来自（-2）+5，因0+3表示在原地踏步一次，得不到期最路径，故不予考虑。由上矩阵，知—，—，—，—，—，—在各点到的最短路径上。

最短路径最短距离 ———3 ———5 ——1 ————3 —4 —0

（二）、求某点到各点的最短路径 例1 求下图中到各点的最短路径。 4

运筹学教案

2-2-33 564 42 -3-1

7

v1 v2 v3 025 -3∞∞∞∞ ∞0-2 ∞4∞∞∞ ∞∞0 ∞∞6∞∞ ∞∞40∞∞∞∞ ∞∞∞ ∞0∞∞∞ ∞∞∞ ∞ -30∞4∞∞∞ 7∞20∞ ∞∞∞ ∞ 3∞-10L(2)(1)1iL1i*W

0025 -3∞∞∞ ∞0v4 v5

v6 v7v8

运筹学教案

2∞0-2 ∞4∞∞ ∞2 5∞∞0 ∞∞6∞ ∞0

-3 *∞∞40∞∞∞ ∞ = -3 ∞∞∞ ∞∞ 0∞∞ ∞6 ∞∞∞ ∞∞ -30∞411 ∞∞∞ ∞7∞20 ∞∞ ∞∞∞ ∞ ∞3∞-1 0∞

的各列对应元素相加再取最小，得各行的元素。 …，当时停止。

025-3∞∞∞∞ ∞0-2∞4∞∞∞ 06 40

0

-304 720

运筹学教案

3-10

所以—，—，—， —，—，—，—，-在到各点的最短路径上。 最短路径最短距离 —0 —2 ——0 —-3 ————3 ———6 ————-9 ————10

（三）从各点到各点的最短路径——Floyd算法 基本思路：

1、输入权矩阵，表示各点不经任何中间点到各点的最短路径长。 2、记，其中，表示从最多经一个中间点到达的最短路长。 3、一般有

运筹学教案

若>0，则关于P值的估计为此时给出各点到各点的最短距离。 例2 求下图中任意两点间的最短路。

v2

v1v5 v4

解：该图有四条无向边，每条均可以化为方向相反的有向边。则 0512∞ 5010∞2 23028

2∞604

∞2440

运筹学教案

1），其中，表示从最多经一个中间点到达的最短路长。按此规则修改得，如。

0512∞

50（ 6 ） （7）2 23028

2（7） （3）04 ∞2440

(1)(0)(0)(1)(0)(0)d24d21d14527 d42d41d12257

(1)(0)(0)d43d41d13213

2）

0512（7） 50672 2302（5）

27304 （7）2440

表示经过最多、两个中间点的最短路长。如

0（4 ） 12（6）

运筹学教案

50672 23025

2（6）304 （6）2440

表示经过最多、、等三个中间点的最短路长。

(3)(2)(0)(3)(2)(2)d12d13d32134 d15d13d35156 (3)(2)(2)d42d43d32336

04126 50672 23025

26304 62440

04126 506（6）2 23025

26304

运筹学教案

62440

给出了任意两点间不论几步到达的最短路长。最短路径由上述矩阵中经中间点的顺序确定。

运筹学教案

授课题目 ： 第四节 最大流问题 教学目的： 掌握求网络中各点至各点的Floyd算法及第4节求网络最大流问题。 教学要求： 要求学生掌握求网络中各点至各点的Floyd算法及求网络最大流问题的标号算法。 教学重点： 掌握Floyd算法和标号算法。 教学难点： Floyd算法。 教学手段与方法： 先用实例引入，再采用比较演示方法。况

运筹学教案

第四节

最大流问题

一、基本概念

1、网络流：满足下列条件： 1）网络中有一个始点和终点、 2）流过网络的流量均有一定方向； 3）每一条弧都赋予一个容量。

2、可行流：满足：1）实际流量不超过容量：

2）满足平衡条件：①由始点流出的所有流量之和等于网络通过的流量；

②对于始点和终点以外的任何一个中间结点，流进等于流出； ③对于终点，流进的所有流量之和等于网络通过的流量的负值-。 3、最大流：最大的可行流。 二、标号法

1、基本概念：1）割集：在一个网络中把所有结点的集合V分为两个集合，各集合中的点无需经由另一个集合中的点而均连通，则把到的一切弧构成的集合叫割集。某一割集所有弧的容量之和称为该割集的容量。最小割集最大流原理：网络的最大流等于最小割集容量。

运筹学教案

2）饱和弧和非饱和弧；3）零流弧和非零流弧； 4）前向弧和后向弧；5）增广链。

2、标号法的步骤：

1）先给网络分配一个初始可行流，如没有给定，可将零流作为初始可行流；

2）给予始点标号（-，∞），表示起点可给任意多的流量，则已标号待查，让和分别表示已标记点的集合和未标记点的集合。

3）取一个已标号待查的点对所有与相邻而未标号的点依次判断如下：

①若存在以中的点为起点，以中的点为终点的非饱和弧，即（，）上的流量，则给标号（），其中；②若存在以中的点为起点，以中的点为终点的非零流弧（，），这里，则

可标记为（），其中，而当时不给标号。

标号过程可能会出现两种结局：1）标号过程xx，收点得不到标号；说明网络中不存在增广链，现行的可行流就是最大流。（即S中不包含，且没有从S中的点到中的点非饱和弧，也没有从中的点到S中点的零流弧。）2）收点得到标号，说明在现可行流中存在从到的增广链，则称该可行流不是最大流，其流量可以增加，其调整量或，

运筹学教案

调整方法：在增广链的正向弧上增加，在反向弧上减少，其它弧上的流量不变。

例1

v2 v4

7（7） 15（4） 411（8）

vs vt

3（3）

9（9）5（1）10（5）

6（5）

解：1）标记寻找增广链 标号S ，，，， ， ，，，，

运筹学教案

==11

（），，，，， （），—--（增广链）

2）调整流量：=4，调整后得可行流如下 3）第二次迭代： 标号S ，，，， ， ，，，，

==7从S到的弧全饱和，从到S的弧（，）为非零弧。 （），=3 ，，，， （），）=3 ，，，，，， （），=3—---（增广链） 4）第二次调整流量

v2 v4

7（7）

运筹学教案

15（8） 4（4）11（8）

vs vt

3（3）

9（9）5（1）10（9）

6（5）

图1 第一次调整流量图

v2 v4

7（7） 15（11） 4（4）11（11）

vs vt

3（3）

9（9）5（4）10（9）

6（5）

运筹学教案

图2 第二次调整流量图 5）第三次迭代

vs(,)

v2(vs,4)

，从S到的弧全饱和，从到S全为零流弧，故当前可行流为最大流，最小割集为｛（，），（， ），（，）｝，其容量和为7+4+9=20。故最大流为20。

运筹学教案