运筹学课程教案(胡运权版)

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

《绪论》（2课时）

【教学流程图】

举例引入，绪论

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

课堂练习

课堂小结

布置作业

【教学方法】

,.

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

【教学内容】

一 、教学过程：

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

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

绪 论

一、运筹学的基本概念 （用实例引入）

例1-1 战国初期，齐国的国王要求田忌和他赛马，规定各人从自己的上马、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支付一千两银子给予获胜者。当时齐王的马比田忌的马强，结果每年田忌都要输掉三千两银子。但孙膑给田忌出主意，可使田忌反输为赢。 试问：如果双方都不对自己的策略保密，当齐王先行动时，哪一方会赢？赢多少？反之呢？

,.

例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课时）

【教学流程图】

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

,.

目标函数

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

约束条件为不等式

课堂练习

课堂小结

布置作业

【教学方法】

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

,.

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

【教学内容】

一 、教学过程：

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

第一节 线性规划问题及其数学模型

（用实例引入）

例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

例1-4 有A、B、C三个工地，每天需要水泥各为17、18、15百袋。为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三

,.

个工地。其单位运价如下表，求最佳调运方案。 工地 水泥厂 甲 乙

工地 水泥厂 甲 乙 需求量/百袋 A B C x11 x12 x13 x21 x22 x23 17 18 15

供应量/百袋 23 27 50 A 1 2 B 1．5 4 C 2 2 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、 当约束条件中出现ai1x1ai2x2ainxnbi时，在左边加上一

个“松弛变量”xi10，使不等式变为等式；当约束条件中出现ai1x1ai2x2ainxnbi时，则在左边减去一个“松弛变量”xi10。

3、 当某个决策变量xj0或符号不限时，则增加两个决策变量

x'j和x'j'，令xjx'jx'j'；

4、 当约束条件中有常数项bi0时，则在方程两边同乘以（-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规划求解法

图解法的操作步骤

单纯形法的原理

课堂小结

布置作业

【教学方法】

坐标系 求出可行域

平移目标函数直线

化为标准型 迭代法 ,.

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

【教学内容】

一 、教学过程：

（一）举例引入：（5分钟） 复习中学数学中的图解法。

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

第二节 图解法

一、图解法的步骤 （以学生自学引入）

学生自学P16-17，教师检查看不懂文字的学生，并做好记录。

提问：以P44的1.4题第1小题为例，图解法第一步是什么？以下逐步提出问题。

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

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

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

,.

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

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

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

例1-5

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

解

x2 5x1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规划求解法

化为标准型

,.

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

课堂小结

布置作业

【教学方法】

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

【教学内容】

一 、教学过程：

（二）举例引入：（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

解：先化为标准型：

maxZ2x1x20x30x40x55x2x315 s.t. 6x12x2x424x1x2x55x1,x2,x3,x4,x50

其约束条件的系数增广矩阵为 0 5 1 0 0 15 6 2 0 1 0 24 1 1 0 0 1 5 初始始基可行解为：X(0,0,15,24,5)T，以此列出单纯形表如下。 得：X(7/2,3/2,15/2,0,0,0)T，代入目标函数得：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 4 0 [2/3] 0 -1/6 1 1 2 2/3 0 1/3 0 0 1/3 0 -1/3 0 x1 ←x5 Zj j min(,第二 次迭 代 x3 111,)3/2 51/32/32/30 2 1 0 0 1 5/4 -15/2 15/2 1 0 0 1/4 -1/2 7/2 0 1 0 -1/4 3/2 3/2 2 1 0 1/4 1/2 0 0 0 -1/4 -1/2 x1 x2 Zj j 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求解中的困难 两阶段法的例题讲解 第一阶段的模型

第二阶段的模型

课堂小结

布置作业

【教学方法】

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

【教学内容】

一 、教学过程：

（三）举例引入：（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 常数 xj -M -M 1 1 1 1 0 0 7 [2] -5 1 0 -1 1 10 始表 ←x6 ,.

计 算 Zj -3M 4M -2M -M M -M 3M+2 3-4M 2M-5 0 -M 0 min(7/1,10/2)5 j 一次 ←x4 迭代 x1 Zj -M 2 0 [7/2] 1/2 1 1/2 -1/2 2 1 -5/2 1/2 0 -1/2 1/2 5 MMM1 -M 1 1 2227MM3M0 M8 6 0 1 1 22222 M5 72j x2 x1 3 2 0 1 1/7 2/7 1/7 -1/7 4/7 1 0 6/7 5/7 -1/7 1/7 45/7 2 3 15/7 16/7 1/7 -1/7 0 0 -50/7 -M-16/7 -1/7 Zj j -M+1/7 所以最优解为：X=（45/7，4/7，0，0，0，0） 例1-8 对LP模型：

minw15y124y25y3 s.t. 6y2y32y1305y12y2y31

用两阶段法求解。 解：先分为标准型：

max(w)15y124y25y30y40x5 s.t. 6y2y3y4y62y1705y12y2y3y5y71

,.

对

minZy6y7 s.t.

6y2y3y4y625y12y2y3y5y71y170

使用单纯形法求解，化为标准型后，列出单纯形表并迭代如下 目标函数 决策变量 基变量 初 y6 Cj 0 0 0 0 0 -1 -1 常数 y1↓ y2↓ y3 y4 y5 y6 y7 yj -1 -1 0 0 [6] 1 -1 0 1 0 2 5 2 1 0 -1 0 1 1 5 8 2 -1 -1 0 0 0 1 1/6 -1/6 0 1/6 0 1/3 始表 ←y7 一次 j y2 迭代 ←y7 j y2 -1 [5] 0 2/3 1/3 -1 -1/3 1 1/3 5 0 2/3 1/3 -1 -4/3 0 0 0 1 1/6 -1/6 0 1/6 0 1/3 0 1 0 2/15 1/15 -1/5 -1/15 1/1/15 0 0 0 0 0 -1 -1 y1 j 在上表中的最终表中除去人工变量y6,y7后，回归到原来的标准型：

max(w)15y124y25y30y40x5 s.t. 6y2y3y4y62y1705y12y2y3y5y71

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

,.

目标函数 决策变量 基变量 初 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 始表 ←y1 一次 迭代 j y2 y3 -24 -5/4 1 0 -1/4 1/4 1/4 -5 15/2 0 1 1/2 -3/2 1/2 j -15/2 0 0 -7/2 -3/2 故Y(0,1/4,1/2,0,0)T 1.15题分析：

令i=1,2,3代表A，B，C三种商品，j=1,2,3代表前，中，后舱，

xij0代表装载于第j舱位的第i中商品的数量（件）。

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

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

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

8x116x215x3120008x136x235x3315008x126x225x323000

前中后舱体积：

10x115x217x31400010x135x237x33150010x125x227x3200

,.

三商品的数量：

x11x12x13600x21x22x231000 x31x32x33800舱体平衡条件：

前舱载重/中舱载重为：(10.15)后舱载重/中舱载重为：(10.15)前舱载重/后舱载重为：(10.10)4312238x116x215x312(10.15)

8x126x225x3238x136x235x331(10.15)

8x126x225x3228x116x215x314(10.10)

8x136x235x333上三式中，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课时）

【教学流程图】

举例引入

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

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

,.

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

课堂小结

布置作业

【教学方法】

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

【教学内容】

一 、教学过程：

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

,.

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

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

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

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

maxZ2x1x2

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

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

设y1,y2,y3分别为单位时间内设备A，B和调试工序的出让价格，

,.

其线性规划模型如下表：

原问题 对偶问题 目标函数 最大利润为maxZ2x1x2，某公司最小出让价为：其中： x1和x2为两种产品的产量。 minW15y124y25y3，其中： y1,y2,y3分别为单位时间内设备A，B和调试工序的出让价格。 原问题 对偶问题 约束条件 每生产1件商品在A，B设每生产1件商品的出让价不小备和调试工序上的时间约束于利润：5y12y2y31 y1,,y2,y306y2y325x215为：xx5126x1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分别用单纯形法和两阶段法可求得上述例题的原问题和其对偶问题的最终单纯形表如下： 目标函数 决策变量 基变量 最 终 表 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 7/2 0 -1/4 3/2 3/2 0 -1/4 -1/2 对偶问题变量 y1 y2 y3 x2 j 变量 目标函数 Cj -15 -24 -5 0 0 常数 ,.

决策变量 基变量 一次 迭代 y2 y3 yj 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 1/2 -15/2 0 0 -7/2 -3/2

j 从上两表看出两个问题变量之间的对应关系，同时看出只需求解其中一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。即原问题的最优解为：X(7/2,3/2,0,0,0)T；其对偶问题的最优解为：

Y(0,1/4,1/2,0,0)T。

对偶问题的基本性质

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

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

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

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

,.

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 设对偶变量为y1和y2，剩余变量为y3，y4，y5，由上性质，有

Y(y1,y2,y3,y4,y5)(4,5,1,2,3)(2,2,0,0,11) 为对偶问题的基本解。

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

,.

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

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

《影子价格》（2课时）

【教学流程图】

举例引入

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

,.

影子价格的实质

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

课堂小结

布置作业

【教学方法】

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

,.

【教学内容】

一 、教学过程：

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

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

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

第三节 影子价格

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

z*=w*= Y*b=

byii1m*i （2.26）

对bi求偏导数，得到：

z*yi*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课时）

【教学流程图】

举例引入

,.

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

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

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

出基

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

课堂小结

布置作业

【教学方法】

,.

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

【教学内容】

一 、教学过程：

（三）举例引入对偶问题的基本概念：（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

解 引入非负松弛变量y35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目标函数 决策变量 基变量 Cj -3 -9 0 0 0 常数 y1↓ y2↓ y3 y4 y5 yj ,.

初 始 表 计 算 ←y3 y4 y5 Zj 0 0 0 [-1] -1 1 0 0 -2 -1 -4 0 1 0 -3 -1 -7 0 0 1 -3 0 0 0 0 0 j -3 -9 0 0 0 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 Zj -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 -3 -9 1 2 0 0 0 -1 -2 0 j 最优解为：Y=(5/3,1/3,0,0,1) 3、 总结对偶单纯形法求解过程：

由于用单纯形法求解极大化线性规划问题时，通过迭代直至所有检验数

j≤0，这时所得最优基也是对偶问题的可行基，因此单纯形法的求解过程

是：在保持原始可行（即常数列保持≥0）的前提下，通过迭代实现对偶可

,.

行（全部j≤0）。

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

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

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

第三步：进行基变换

先确定出基变量：选取常数列中绝对值最小的负元素对应的基变量出基，相应行为主元行。然后确定入基变量：由最小比值原则，选

min{ij'aij'aij0}k'aik'所在的列为主元列。这里j为第j列的检验数，aij为j对

应的主元行中非基变量的系数。主元行与主元列相交叉处的系数元素为主

'元素aik，其对应的非基变量为换入基变量。

第四步：对主元素进行换基迭代后，用矩阵的初等变换将主元素变成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课时）

【教学流程图】

举例引入灵敏度

,.

灵敏度

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

线性规划模型参数

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

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

课堂小结

布置作业

【教学方法】

,.

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

【教学内容】

一 、教学过程：

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

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

第五节 灵敏度分析 一、灵敏度分析的基本概念与原理 由LP单纯形迭代法的基本原理： 将LP的标准型写成矩阵形式： maxZ=CX s.t. AX=b X≥0

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

（A∣I）→（I∣A）

,.

3 -1 0

例1-11 求矩阵A= -2 1 1 的逆矩阵。 2 -1 4 解 3 -1 0 1 0 0

-2 1 1 0 1 0

2 -1 4 0 0 1

R3R2,R1R2 1 0 1 1 1 0

= -2 1 1 0 1 0 0 0 5 0 1 1 R3,R22R1 1 0 1 1 1 0 = 0 1 3 2 3 0 0 0 1 0 1/5 1/5

R1(1)R3,R2(3)R3 1 0 0 1 4/5 -1/5 = 0 1 0 2 12/5 -5/3 0 0 1 0 1/5 1/3 再看美佳公司的LP约束条件系数的初始表与最终表： 目标函数 决策变量 基变量 初 始 表 x3 Cj 152 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 ←x4 x5 ,.

计 算 Zj 0 0 0 0 0 2 1 0 0 0 min(,24/6,5/1)24/64 j 第二 次迭 代 x3 0 2 1 0 0 1 5/4 -15/2 15/2 1 0 0 1/4 -1/2 7/2 0 1 0 -1/4 3/2 3/2 2 1 0 1/4 1/2 x1 x2 Zj j 0 0 0 -1/4 -1/2 因此有：

目标函数的系数 CB CN 决策变量 XB XN

初始表中约束条件的系数 B N b 最优表约束条件的系数 B1B B1N B1b 最优表的检验数 CBCBB1B CNCBB1N

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

将c11.5,c22代入原最优表中并继续迭代，得： 目标函数 Cj 1.5 2 0 0 0 常数 ,.

决策变量 基变量 第二 次迭 代 第三 次迭 代 ←x3 x1 x2 x1↓ x2↓ x3 x4↓ x5 0 1.5 2 0 1．5 2 0 0 1 [5/4] -15/2 15/2 1 0 0 1/4 -1/2 7/2 0 1 0 -1/4 3/2 3/2 0 0 0 1/8 -9/4 0 0 4/5 1 -6 6 1 0 -1/5 0 1 2 0 1 1/5 0 0 3 0 0 -1/10 0 -3/2 j x4 x1 x2 j 如果c21，代入原最优表，得 目标函数 决策变量 基变量 第二 次迭 代 x3 Cj 2 1 0 0 0 常数 x1↓ x2↓ x3 x4 x5 0 1.5 1 1412320 0 1 [5/4] -15/2 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 14141232x1 x2 7/2 3/2 j 140 0 0   13212。 3解 0 和 0，得：1，故 三、 分析bi的变化

设初始表中的常数列为b,那么最优表中的常数列为B1b，现设初始表中

111的常数列为bb，那么最优表中的常数列为B(bb)BbBb，也就

,.

是当初始表中的常数列有增量b时，那么最优表中的常数列有增量B1b。 例5-3 设美佳公司这一例中的单纯形表中的初始表中的常数列中有增量： 0

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

1 5/4 -15/2 0 10 b'= 0 1/4 -1/2 8 = 2 0 -1/4 3/2 0 -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 0 0 0 -1/4 -1/2 0 5 1 0 0 15 1 1 0 0 1 5 0 -4 0 1 -6 2 0 -1 0 0 -2 x1 x2 j x3 x1 x4 四、 增加一个变量xj的分析（采用教材第三版P66的分析步骤和P67的

例7。

,.

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

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

教学重点： 初始调运方案的确定。 教学难点： 初始调运方案的确定。 教学过程： 1.举例引入运输问题（ 5分钟） 2.举例讲解新课 （70分钟） 运输问题的基本概念； 3.课堂练习（穿插在例题讲解过程中） 4.课堂小结（5分钟） 5．布置作业：（10分钟） 《运输问题：表上作业法与规划求解法》（2课时）

【教学流程图】

举例引入运输问题

,.

产地 运输问题的基本概念 销地

运价与运量

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

课堂小结

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

【教学方法】

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

,.

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

【教学内容】

一 、教学过程：

（一）举例引入运输问题的基本概念：（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的表上作业计算。

【教学方法】

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

,.

【教学内容】

一 、教学过程：

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

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

第三章 运输问题

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

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

求应如何调运才使总运费最小？

销地 产地 B1 B2 B3 B4 产量 A1 x11 4 x12 12 x13 4 x14 11 16 A2 2 x21 10 x22 x23 3 x24 9 10 A3 8 x31 x32 5 x33 11 x34 6 22 销量 8 14 12 14 解：先写出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. x11x21x318

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 x24 x31 x32 x33 1 1 1 1

1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 由上可见，单纯形表的系数矩阵有m+n=3+4=7行，有m*n=3*4=12列。基变量个数有m+n-1=3+4-1=6个，不能采用普通单纯形法求解，只能

x34 1 1

,.

用表上作业法求解。 二、 表上作业法

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

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

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

空格闭回路指在一个封闭的直角回路的若干角点处，除了xlk处为空格以外，其余角点都是实格。作法：从xlk所在的空格开始，沿直线前进，碰到实格可拐弯也可不拐，但碰到空格应不改变方向，如此曲折前进，一直返回到起始空格。再将xlk所在空格的单位运费加上正号，沿它的空格闭回路按顺时针方向再在第二个、第三个等有数格的单位运费前依次加上负号，正号，…，如此正负交错，最后得xlk所在空格的检验数lk。 ②位势法

方法：在初始调运方案表中增加一行和一列，在列中填ui，在行中填vj（ui和

vj称为位势），于是对于m+n-1个有数格成立下列关系：

,.

cijuivj （1）

由于ui和vj共有m+n个，因此上式组成的m+n-1个方程中多一个未知数，可任设一个未知量为一任意常数（一般设u10），求出全部ui和vj的值。再把这些ui和vj的值代入空格检验数的表达式：

ijcij(uivj) （2）

3、换基

对各空格检验数按max(ij,ij0)lk的原则先选择xlk进基，再做xlk的空格闭回

路，以角点xlk为0号，按顺时针或反时针方向把其他角点依次标为1号，2号，…，如此排出各转角点的奇偶性，再求调整量min（各奇数转角点的调运量），按“偶点处加调运量，奇点处减调运量”的方法，重新安排空格闭回路上转角点的调运量。

4、再求新调运方案的检验数，再换基求更新的调运方案…，如此迭代，直至 空格检验数不出现负值为止。

5、当某空格检验数ij0时，同样可以选取它所在的空格进基，运用调整量调节

器整后的方案仍为最优，不过目标函数值不会有所改善，称之为多解。

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

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

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

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

,.

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

2 10 3 9 A2 8 8 × 2 10 × 5 14 11 6 8 A3 × × 22 销量 8 14 12 14

二、学生练习（穿插在例题讲解中） 三、布置作业：用表上作业法进行计算求解。

,.

授课题目 ： 第三章 运输问题 第三节：运输问题进一步讨论。 教学目的与要求： 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课时）

【教学流程图】

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

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

基变量的个数

,.

增加一个产地 求解不平衡的运输问题的表上作业法 增加一个销地

最后几个单元格的数据填充

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

课堂小结

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

【教学方法】

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

,.

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

【教学内容】

一 、教学过程：

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

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

1、 总产量大于总销量，需增加一个虚拟的销地（收点），其运费设为0，再用表上作业法求解。

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

,.

增加以后调整的工作量。 销地 产地 B1 B2 B3 B4 B0 产量 A1 2 2 10 × 7 11 × 3 3 8 4 × × 3 3 5 × 1 3 4 0 2 9 2 2 × 0 0 7 A2 5 A3 × × 7 销量 2 3 4 6 4 19 19

由于所有的检验数大于等于0，此方案最优，但其中130，还可以有另外的最优调拨方案，但总运费不会下降。

2、 总产量小于总销量，需增加一个虚拟的产地（发点），其运费设为0，再用表上作业法求解。

二、产量有上下限的产销不平衡运输问题 教材上例7：根据下表1求最优运输方案：

解 方法：这是一个产地A1和A3的产量有上下限的运输问题，先求出A3的产量上限为7（20-6-7=7）。由于该两地产量都取上限时，总产量为25，大于总需求20，故增加一个虚销地B4。当某地产量有最高产量和最低产量时，可以把它的产量分为基本产量和多余产量两部分，前者应发往实在的需用地，而不能

,.

发往虚销点B4，从而将这部分产量运往虚销点的单位运价取为充分大的M，另一部分多余产量可以运往虚销点，但实际上没有运输，故取相应的单位运价为0。现将初始方案表列于下表2：

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

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

表2 初始调运方案表

销地 产地 B1 B2 B3 B4 产量 A ‘1 2 3 2 × 1 4 × 4 × 5 3 3 3 × 3 2 6 M 6 A1 A2 0 5 M 7 ,.

7 × × 4 × 4 × × M 0 0 3 4 A3 × 3 2 4 A ’33 2 × × 3 销量 10 4 6 5 25 25 用位势法求得各空格检验数为：

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 最优调运方案表

销地 产地 B1 B2 B3 B4 产量 A‘1 2 3 2 × 1 4 × 4 × 5 × 3 3 3 × 3 2 6 × 4 0 × M 6 A1 0 5 A2 M 7 × 3 × 2 4 7 A3 M 4 ,.

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

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

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

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

第三步：设多余船只数为产量，缺少的船只数为销量（需求量），船只调出的港口为产地，调入港口为销地，作运输问题求解的作业表如下： 表1 初始方案表 至（销地） 从（产地） A B E 产量（多余船只） C 2 1 14 × × 1 3 0 13 2 5 2 D 17 2 ,.

F 2 × 1 × 1 8 1 3 3 1 5 5 销量（缺少船只） 210，222，317，327。以222所在格为进基变量换基，得一最优解：xCA1,xCE1,xDB1,xDE1,xFE1 表2 最优表Ⅰ 至（销地） 从（产地） A B E 产量（多余船只） C 2 1 14 × 2 × 1 × 1 1 × 3 1 13 1 8 1 3 5 2 D 17 2 F 3 1 5 5 销量（缺少船只） 以210所在格为进基变量换基，得另一最优解：

xCE2,xDA1,xDB1,xDB1,xFE1

表3 最优表Ⅱ 至（销地） 从（产地） A B E 产量（多余船只） ,.

C 2 0 14 1 2 × 1 × 1 1 × 3 2 13 × 8 1 3 5 2 D 17 2 F 3 1 5 5 销量（缺少船只）

二、学生练习（结合例题进行） 三、布置作业

授课题目 ： 第四章 目标规划 第一节 目标规划问题及其数学模型 第二节 目标规划的图解法 ,.

教学目的与要求： 1.知识目标：了解目标规划的定义，特点与分类；掌握目标偏差变量的概念和目标规划的模型及目标规划的图解法步骤；掌握目标规划的规划求解法。重点要求是目标规划的三种求解方法的比较。 2.能力目标：能够运用目标规划的求解原理进行表上操作与计算机操作。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1.掌握目标规划的图解法与规划求解法。 2.掌握目标规划的三种求解方法的区别。 3．目标偏差变量的概念、 教学难点： 目标规划的图解法。 教学过程： 1.复习旧课（通过提问方式复习回顾上次内容，情景假设导入本次内容。5分钟） 2.新课 （60分钟） (1) 目标规划的定义与分类（30分钟） (2) 目标规划的图解法与规划求解法（30分钟） 3.课堂练习（20分钟） ,.

4.课堂小结（5分钟） 5.布置作业 《目标规划》（2课时）

【教学流程图】

复习旧课

定义 目标规划概述 特点

分类

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

学生操作

,.

回顾 目标规划的规划求解法 例题操作

学生操作

具体实例

课堂练习

课堂小结

布置作业

【教学方法】

,.

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

【教学内容】

一 、教学过程：

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

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

老师归纳。

导入提问：什么叫目标规划？ （二） 新课：

一、举例引入：

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

,.

衬衫售价20元，成本14元。求使利润最大时男女衬衫的生产量

x1和x2。

解：LP模型为：

maxZ8x16x22x1x220000x1x213000x1,x20s.t. 2x13x236000

用单纯形求解，得x17000件，x26000件。总销售额=15x120x2225000元。

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

minfdd2x1x220000 s.t.

2x13x236000x1x21300015x120x2dd250000x1,x2,d,d0

二、目标规划的基本概念

目标规划是对每个优化目标预先给定一个理想的期望值，再把实际达到值与期望值之偏差作为目标的偏差变量（d和d分别叫正负偏差变量），将对目标函数求极值问题转化为对目标偏差变量求极值的问题。具体地说，就是引入一个达成函数作为目标函数，也可以把原优化系统中的任何一个约束条件视为一个优化目标，而把原目标函数视为一个目标约束增加在原优化问题的约束条件中。

,.

三、目标规划的数学模型（以上例为依据） 1、引入偏差变量与目标约束

设d0为预定销售额目标的差值，叫负偏差变量；d0为超过预定销售额目标的差值，叫正偏差变量。在上例中，有下列三种情况： ①当销售额小于250000元时，有d＞0且d0，则

15x120x2d250000 成立；

②当销售额大于250000元时，有d＞0且d0，则

15x120x2d250000成立；

③当销售额等于250000元时，有d=d0，则15x120x2250000成立。

这三种情况可全并为一个等式：15x120x2dd250000，把为目标约束，其中d和d至少有一个为0。 2、引入达成函数

设目标约束的一般式为：g(x)ddE，其中E为目标的预定值，那么达成函数有五种形式：

①minfd，不关心超过量大小（越大越好），不足量越小越好，最优值为d0，这时目标约束为g(x)dE，即g(x)E，希望

g(x)最好超过E；

②minfd，不关心不足量大小（越大越好），超过量越小越好。这时最优值为d0，目标约束为g(x)dE，即g(x）E，希望

g(x)不超过E；

③minfdd，希望不足量与超过量之和越小越好，最优值为

,.

dd0，即g(x)E，意味着g(x)尽量接近E；

④minfdd，不足量d0，超过量d，f超过最优值（为），意味着要求g(x)与E无关，超过值越大越好，相当于求

maxg(x)。

minfdd⑤minfdd，不足量d，超过量d0时，

趋于最优值（为），意味着要求g(x)与E无关，不足值越大越好，相当于求ming(x)。

3、下面以上述例题为例，说明达成函数与目标约束怎样配合？

15x120x2dd250000，叫作销售额不少①minfd(即d0)，于250000元（即使不能达到也要尽可能接近250000元。

15x120x2dd250000，叫作销售额不超②minfd(即d0)，过250000元（即使超过了也要尽可能接近250000元。

15x120x2dd250000，叫作销售额尽可能接③minfdd，近250000元。

三、 目标规划的图解法（适用于两个决策变量）

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

解：该例用单纯形法求解，为：

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

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

①Ⅱ的产量不低于Ⅰ的产量（即x1x20，也就是x1x2的值不超过0）； ② 充分利用设备有效工时，但尽量不加班（即所用的总设备工时不大于10，也不小于10，也就是尽量接近于10）； ③ 总利润不小于56万元； ④引入优先因子Pk1Pk1。

解：由上原则，上述三种目标对应的目标函数和目标约束分别为： ①x1x2d1d10,minZd1 ②x12x2d2d210,minZd2d2 ③8x110x2d3d356,minZd3

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

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

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

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

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

2、对于绝对约束的作直线方法与一般线性规划的图解法相同；

,.

3、对于目标约束条件，先令d=d0，作各目标约束的直线，在直线两侧标上d和d的方向，表明目标约束可以沿d和d所示的方向平移。 例如，对于直线x1x20，它右下半平面为x1x20（即d>0）（因为当，所以该直线的右下方为d增加的方向，那x2不变而x1增加时有x1x20）么它的左上方为d增加的方向。

4、最后根据目标函数中的优先因子求解。本例子先考虑

mind1，可满足d10,这时x1,x2在⊿OBC边界和其中取值;再实现目标函数中

的min(d2d2)，当d2d20时，线段可在ED上取值；最后在目标函数中实现mind3，从图中判断可以使d30,此时x1,x2的取值范围缩小在线段GD上。这就是该目标规划的解，可求得G和D的坐标分别是（2，4）和（10/3，10/3），GD的凸线性集合就是该目标规划的解。 x2 F E B x1x20 d1 2x1x211 d1 d3 G O C x12x210 d2 x110x356 x1 ,.

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

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

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

【教学流程图】

复习旧课

目标规划单纯形法概述

,.

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

检验数为负值的判定

具体实例

课堂练习

课堂小结

布置作业

【教学方法】

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

,.

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

【教学内容】

一 、教学过程：

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

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

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

一 实例引入

例5 对上例4用单纯形法求解。 解：列出单纯表如下： Cj 0 xB CB x3 d1 d2 P2 0 x2↓ 0 x3 0 d1 P1 d1 P2 d2 P2 d2 P3 0 d3↓ x1↓ d 3b 11 2 1 1 1 -1 1 1 -1 1 1 -1 1 -1 0 10 56 [2] 10 d3 P3 8 2 j P1 P2 -1 -2 ,.

P3 x3 d1 -8 -10 1 1 1 -1/2 -1 1/2 1/2 -1/2 -1/2 6 5 5 3/2 3/2 1/2 x2 1 1/2

6 d3 P3 [3] -5 5 1 -1 6

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

P3 x3 d3 1 -1 -2 6 x2 -1/3 1/3 1/3 -1/3 ,.

x1 1 2/3 -2/3 1/3 -1/3 j P1 1 1 1

P2 P3 二、单纯形表的特点：

1、因目标函数为最小化，故以检验数j0作为最优准则；

2、因非基变量检验数含有不同等级的优先级因子，需逐级考虑。

jCjZjakjPk,j1,2,…，n为列序号，k1,2,,K为行序号，因

P1P2PK，从每个检验数的整体看，检验数的正负首先取决于P1的系数a1j的正负，若a1j=0，检验数的正负取决于a2j的正负，下面依次类推。

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

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

2、检查该行中是否存在负数，且对应的前k1行的系数为0。若有，取其中最小（最负）者对应的变量为进基变量，再转第3步，若无负数，则转第5步； 3、按最小比值原则确定离基变量，当存在两个或两个以上的相同最小比值时，就选具有较高的优先级别的变量为换出变量；

4、按单纯形法进行迭代运算，建立新的运算表，再返回第2步；

，否则，置kk1，返回到第2步。 5、当kK时，表中的解为满意解四、例5的求解分析：

,.

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

1、化为标准型：取第一个约束中加上松弛变量x3，取x3、d1、d2、d3为

初始基变量，列出初始单纯形表；

2、对Pk取k=1，检查检验数的P1行，因该行无负检验数，执行步骤3； 3、按步骤5，因为k（1小比值min(11/1,,10/2,56/10)10/2,其对应的变量d2为离基变量，执行步骤

4；

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

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

授课题目 ： 第四章 目标规划 第四节 目标规划的灵敏度分析 ,.

教学目的与要求： 1.知识目标：了解目标规划的灵敏度分析。 2.能力目标 ：掌握目标规划的灵敏度分析。 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 目标规划的灵敏度分析 教学难点： 目标规划的灵敏度分析 教学过程： 1.复习旧课（通过提问方式复习回顾上次内容，情景假设导入本次内容。5分钟） 2.新课 （60分钟） 目标规划的灵敏度分析 3.课堂练习（20分钟） 4.课堂小结（5分钟） 5.布置作业 ,.

《目标规划：目标规划的灵敏度分析》（2课时）

【教学流程图】

复习旧课

目标规划灵敏度分析概述

目标规划灵敏度分析步骤

,.

具体实例

课堂练习

课堂小结

布置作业

【教学方法】

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

,.

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

【教学内容】

一 、教学过程：

（一）复习旧课：（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）minP1d1,P2d2,P3d1,P4(5d33d4)

（ii）minP1d1,P2d2,P3(W1d3W2d4),P4d1 (W1,W20)

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

表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 d3 1/2 0 1/4 -1/4 0 0 17/4 0 0 3p3 d4 0 0 1 0 0 0 0 0 0 CB XB b 13/2 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 3/4 0 d4 0 0 -1 0 0 0 3 0 0p43p30 x1d1d4 3 3/4 5/4 P1 P2 x2cjzj P3 P4 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 5p4 d3 1/2 0 1/4 -1/4 0 0 0 0 3p4 d4 0 0 1 0 0 0 0 0 0 CB XB b 13/2 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 0p33p40 x1d1d4 3 3/4 5/4 P1 P2 x2cjzj P3 P4 表4—8

-3/4 17/4 ,.

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 XB b 5 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 003p40 x1d2d4 3 3/2 1/2 P1 P2 x2cjzj P3 P4 2．当目标函数变（ii），就是要了解第三优先级中两目标权系数取值对原解的影响。

表4—9

W2P3cj 0 0 p1 p3 0 p2 W1P3 0 0 CB XB b 13/2 x1 1 0 0 0 x2 0 0 0 1 d1 0 -1 0 0 d1 0 1 0 0 d2 1/2 1 -1/4 1/4 d2 -1/2 -1 1/4 -1/4 d3 1/2 d3 -1/2 0 -1/4 1/4 d4 0 0 1 0 d4 0 0 -1 0 0P4W2P30 x1d1d4 0 1/4 -1/4 3 3/4 5/4 x20 P1 P2 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 W2/P3 P4 0 4 0 -1 0 1 -W2/4 1 0 0 W1-W2/4 0 0 0 0 0 W2/0 4 0 0 0 W2 0 0 cjzj ,.

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

,.

授课题目 ： 第五章 整数规划 第一节：整数规划的数学模型及解的特点 第三节：分支定界法 教学目的与要求： 1.知识目标：掌握整数规划的概念、类型和作用及其求解方法概述；掌握分支定界法的基本概念与求解思路； 2.能力目标：掌握分支定界法的求解步骤； 3.素质目标：培养学生良好的职业道德、树立爱岗精神 教学重点： 1、分支定界法的基本概念； 2、分支定界法的操作原理与步骤。 教学难点： 1、分支与定界的方法； 2、图解法在分支定界法中的应用。 ,.

教学过程： 1.举例引入（ 5分钟） 2.新课讲解 （80分钟） （1）分支与定界原则与方法（20分钟） （2）分支定界法操作步骤（40分钟） （3）学生操作（20分钟） 3.课堂小结（5分钟） 5.布置作业 《整数规划：定义、类型、求解综述和分支定界法》

（2课时）

【教学流程图】

举例引入整数规划

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

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

最优解的确定

,.

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

课堂小结

布置作业

【教学方法】

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

【教学内容】

一 、教学过程：

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

（1）整数规划的定义

,.

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

第五章 整数规划

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

一、 主要思路

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

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

,.

1）定界方法：

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

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

Z0---松弛问题的解； Zi---目前已找到的整数解， Z*----最优整数解； Z---上界，Z---下界。则最优整数解满足：

对于最大化问题：ZZiZZ0Z；对于最小化问题：ZZ0ZZiZ。

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

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

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

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

例1 求解下列整数规划：

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

xj0,j1,2,x1,x2是整数,.

x2 9x17x256 G(4.81，1.82） 7x120x270

x1

第一步：用图解法求出原整数规划问题的松驰问题的解。对x1=4.81按 x14 和x15

进行分支，得到原整数规划问题的松驰问题的两个子松驰问题如下。然后对原整数规划问题的松驰问题进行定界（上界与下界）。

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

maxZ40x190x29x17x256 7x120x270maxZ40x190x2和 7x120x270x15xj0,j1,2,9x17x256

x14xj0,j1,2,

,.

x2 9x17x256 G(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90x2 4 x1 .00 7x120x270x1 .00 5x22.10 x21.57 Z1349Z23419x17x256x1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

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

9x17x256x21 无可行解 Z 7x120x270 308 x15,x21xj0,j1,2,x15,x22xj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课时）

【教学流程图】

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

解整数规划的割平面法的基本思路

单纯形法的最优表的结构 割平面方程的确定 解整数规划的割平面求解过程 插入割平面约束的单纯形表 对偶单纯形法

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

,.

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

课堂小结

布置作业

【教学方法】

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

【教学内容】

一 、教学过程：

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

（1）整数规划的定义 （2）整数规划的分类

,.

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

一、割平面法 （一）基本原理

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

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

maxZx1x2

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

解 1、松弛问题的单纯形表为： 目标函数 决策变量 Cj 1 1 0 0 常数 x x x x 3124,.

基变量 最优表 x2 1 1 0 1 3/4 1/4 7/4 x1 j 1 0 -1/4 1/4 3/4 0 0 -1/2 -1/2 -5/2 2、求割平面方程

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

x1x3x4 （1） 将上式左边的非基变量的系数和右端常数写成一个整数和一个非负真分数之和：

x1(1)x3(0)x40 （2）

把上式系数为真分数的各项移到等式右端，将整数移到左端： x1x30x40x3x4 （3）

因x1,x2为整数，原整数规划ILP约束条件中各系数和右端常数也为整数，所以x3，x4也为整数。由于上式左边为整数，右边也应为整数。又

x3，x40，由于从所以3/4减去两个正数必有：

1414343414343434143313x3x4 （4） 4444331 得：x3x40 （因上式左边为整数） （5）

444313 为避免引入工变量，将上式改写成： x3x4 （6）

444313加入松弛变量x5(0)，化为等式约束：x3x4x5 （7）

444

,.

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

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

由灵敏度分析可知，增加一个割平面约束，只需把（7）式加入最优表作为第3行，由于x5(0)为基变量，它的检验数为0，而原来的各变量的检验数和目标值均保持不变。现用对偶单纯形法求解如下： 目标函数 决策变量 基变量 原最 优 表 x2 x1 x5 Cj 1 1 0 0 0 x1 x2 x3↓ x4 x5 常数 1 1 0 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 -3/4→ 0 0 -1/2 -1/2 0 j min(1/21/22，） 3/41/43 新最 x2 1 1 0 0 1 0 0 0 1 1 0 0 1/3 -1/3 1 0 0 1 1/3 -4/3 1 0 0 0 -1/3 -2/3 优表j x1 x3 j 二、学生练习（结合例题讲解进行）

,.

三、课程小结

四．布置下次课的教学内容

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

一、 实例引入

例1 有一项说明书要由汉语分别译成英、日、德、俄四种文字，交由甲、乙、丙、丁4个译员去完成。因各人专业不同，因此译成不同文字所需要的时间不同。假设各人完成各项工作的时间如下表，问应如何分配才能完成4项给定任务的总时间最少？

工作 译员 甲 乙 丙 丁 解 用0-1 模型 ，

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

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

4 15 13 9 13 14 16 11 15 4 14 8 3 10 9 7 1 2 3 4 （汉译英） （汉译日） （汉译德） （汉译俄） ,.

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. x11x21x31x411

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 如果从分配效率矩阵[cij]的每一行元素分别加（减）一个常数，从每一列元素分别加（减）一个常数，得到新的效率矩阵[bij]的最优解等价于原效率矩阵的最优解。

定理2 若某矩阵A中的元素分为零元素和非零元素两部分，则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为零元素）的最大个数。此定理告诉了效率表中有多少零元素的辨别方法。 二、指派问题的匈牙利解法

第一步 转换效率矩阵[cij]，使各行各列都有出现零元素

从每行元素减去该行最小元素；再从所得的效率矩阵每列减去该列的最小元素。若某行（列）已有零元素，就不必再减了。 上例中：

3 10 9 7 0 7 6 4 0 7 1 4 ,.

[cij]= 15 4 14 8 = 11 0 10 4 = 11 0 5

4

13 14 16 11 2 3 5 0 2 3 0 0

4 15 13 9 0 11 9 5 0 11 4 5

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

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

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

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

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

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

,.

素。

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

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

上例：

（0） 7 1 4 11 （0） 5 4 2 3 （0） ○ ○ 11 4 5

第三步 增加零元素

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

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

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

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

（0） 7 1 4 11 （0） 5 4 2 3 （0） ○ ,.

○ 11 4 5

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

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

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

0 6 0 3 0 6 0 3 11 0 5 4 12 0 5 4 2 3 0 0 3 3 0 0 0 10 3 4 0 10 3 4 本例又从第二步开始：

○ 6 （0） 3 12 （0） 5 4

3 3 ○ （0）

（0） 10 3 4

,.

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

教学难点： 动态规划的逆序解法和顺序解法。 教学手段与方法： 先用实例引入，再采用比较演示方法。

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

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

1、阶段：按时间/空间分解成若干相互联系的段落，用k1,2,3,…表示。 2、状态：各阶段开始时的客观条件，用状态变量sk表示，sk的取值集合用Sk表示，不具备无后效性的变量不能作状态变量；当某阶段的状态给定以后，这阶段以后过程的发展只受该阶段状态的影响，而与该阶段以前的状态无关，状态的这一性质叫无后效性 3、决策和策略

当各阶段的状态给定以后，就可以做出不同决定选择，从而确定下一阶段的

,.

状态，这种选择决定叫做决策，用uk(sk)表示第k阶段的当状态为sk时的决策变量，其取值在一定范围内，此范围叫允许决策集合，用Dk(sk)表示，因此有 uk(sk)Dk(sk)

整个问题的决策序列叫策略。用P1,n{u1(s1),u2(s2),,un(sn)}表示。 4、状态转移方程

用sk1T(sk,uk)表示第k1阶段的状态是第k阶段的状态sk和决策变

uk(sk)的函数。

5、指标函数

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

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

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种物品的单件重量为aikg,其价值为ci,总价值是携带数量的函数cixi，求应如何选择携带物品的件数使总价值最大？

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

模型：一维背包

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

xi0且为整数二维背包

maxZcixii1n

wxi1nniiab

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

①阶段k,即需装入n种物品的次序，每时间段装入一种物品，那么共需n个时间段。

②状态变量sk表示第第k阶段开始时允许装入前k种物品的总重量，有

snb，因sn已知，故用顺序解法。

③决策变量xk为装入第k种物品的件数。 ④状态转移方程： sk1skakxk

ss ⑤允许的决策集合是Dk(sk){xk︱0xkk，xk为整数}，式中kakak ,.

为不超过

ssk的最大整数。这里xk的最大值kakak表示只装运第k种物品，其余k-1种物品的装运量为0。

⑥最优指标函数fk(sk1)表示在背包中允许装入物品的总重量不超过sk1 公斤时背包中允许装入第1-k种物品的最大使用权用价值。 ⑦于是得到动态规划的顺序递推方程： 阶段指标为 vkckxk，递推方程为：

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、k1

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

,.

s2 0 1 2 3 4 5 6 7 8 0 1 2 9 0 1 2 10 0 1 2 x2[s2/w2] 0 0 0 0 0 0 1 0 1 0 1 1 c2x2 0 0 0 0 0 5 0 5 0 5 0 5 0 5 10 0 5 10 0 5 10 s1=s2-c2x2 0 1 2 3 4 0 5 0 6 1 7 2 8 3 0 9 4 0 10 5 0 f1(s1) 0 0 0 4 4 0 4 0 8 0 8 4 8 4 0 12 4 0 12 8 0 c2x2+f1(s1) 0 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10 f2(s2) x1 0 0 0 4 0 0 0 1 1 0 5 5 8 9 10 12 13 1 0 2 0 2 1 2 1 0 3 1 0 3 2 0 *x2 0 0 0 0 1 1 0 1 2 0 1 3、k3

s3 0 1 2 3 4 5 6 7 8 9 10 x3[s3/w3] 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 2 c3x3 0 0 0 0 0 6 0 6 0 6 0 6 0 6 0 6 12 ,.

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

由s1=s2-c2x2=10-4*1=6，对应x1*=2。 3、总结建立动态规划模型的步骤： 1）划分阶段

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

后效性的要求；

3）确定决策变量及其取值范围； 4）建立状态转移方程

sk1T(sk,uk)，必须具有递推关系；

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

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

,.

授课题目： 第三节 动态规划模型的建立与求解 教学目的： 掌握动态规划中的生产与存贮问题求解的步骤。 教学要求： 要求与学生与教师配合能操作上次课的例1。 教学重点： 掌握生产与存贮问题的求解原则。 教学难点： 生产与存贮问题的求解步骤。 教学手段与方法： 先用实例引入，再采用比较演示方法。况 课后小结： ,.

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

阶段k（月） 需求量dk 单位生产成本为：

0 xk0 Ck

2，3， 3+1·xk xk1，…，6

1 2 2 3 3 2 4 4

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

解： 1、分析： ① 阶段为月；

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

至少应生产dksk；由于每月最大生产能力为6，故xk6，而第k月末（第k1月初）的库存为skxkdk，其小于等于第k1月最大库存量

,.

故有：

0sk1skxkdk3，xkdksk xk3skdk。

故有允许决策集：

Dk(sk)xkmax[0,dksk]xkmin[6,3skdk] （1）

④ 状态转移方程sk1skxkdk

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

指标函数fk(sk)为第k月状态为sk时，采用最佳生产，从第k月初到第4月末的总成本。

fk(sk)minrk(sk,xk)fk1(sk1) 上式中xkDk(sk),0xk6，

本期成本rk(sk,xk)生产成本+库存成本= 3xk,若xk0 + 0.5sk

0， 若xk0 f5(5)0

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

sk={0，1，2，3}，其中s1={0}，s24={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)x2max[0,3s2]x2min[6,3s23] D3(s3)x3max[0,2s3]x2min[6,3s32]

,.

D4(s4)x4max[0,4s4]x4min[6,0s44]

上式中第4个月因为s4x4d4=0，即x4d4s44s4。 2、逆推表：

1）sk和xk(sk)的分布

s10,D1(s1)2,3,4,5，由公式（1）得下表1： 表1 sk和xk(sk)

s2 D2(s2)0 1 2 3 s3 {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 1 2 3

2）k=4

4 3 2 1 表2 k=4递推表

x4(s4) 状态s4 决策 （期末库存） 0 （可能生 产量） 4 生产费用 本期费用r4(s4,x4) 总费用 库存费用 合计 f4(s4) 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 f4(s4)minr4(s4,x4)f5(s5)minr4(s4,x4),因为由s50知f5(s5)0。

x4D4(s4)x4D4(s4)3）k=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。

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

f（3s3)的值，例如当s30时，有:f3(0)min[(3x3)0.5*0f4(s3x3d3s4)]min(57,66.5,76,85.5)

2x3512表3 k=3递推表

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

1 1 2 3 4 4 5 6 7 0 4 5 6 0 4 5 0.5 0.5 0.5 0.5 1 1 1 1 1.5 1.5 1.5 4.5 5.5 6.5 7.5 1 5 6 7 1.5 5.5 6.5 0 1 2 3 0 1 2 3 7 6.5 6 5.5 7 6.5 6 5.5 11.5 2 0 1 2 3 8 8 3 0 1 2 1 2 3 6.5 6.0 5.5 4) k=2

表3 k=2递推表

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

6 9 0 9 3 8 12 11．5 8 8 12 11．5 8 8 12 11．5 8 8 15 2 3 4 5 1 2 3 4 0 1 2 3 5）k=1

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 1 15.5 2 13.5 3 表4 k=1递推表

s1s2s1x1d1r1(s1,x1)f2(s2) 0

0 1 2 3 x1 c(x1) E(s1) 合计 f1(s1) 2 3 4 5 5 6 7 8 0 0 0 0 5 6 7 8 16 15.5 15 13.5 5 6 7 8 21 ,.

由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。 教学重点： 掌握货郎担问题的求解原则。 教学难点： 货郎担问题求解的步骤。 教学手段与方法： 先用实例引入，再采用比较演示方法。况 ,.

课后小结： 一、 求解方法

货郎担问题的一般描述：一个货郎从某村镇v1出发，经过若干个村镇v2、

v3，…，vn一次且仅一次，最后仍回到原出发的村镇，已知从vi到vj的距离为dij，

问应如何选择行走路线可使总行程最短？

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

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

fk(vi,S)min{fk1(vj,Svj)dij}

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

例1 已知四个村镇之间的距离dij如下表，求从某村镇v1出发，经过村镇v2、v3，

v4一次且仅一次，最后仍回到原出发的村镇，问应如何选择行走路线可使总行程

最短？

v1 v1 v2 v3 v4 0 6 7 9

,.

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

v4

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

f0(2,)d126,f0(3,)d327,f0(4,)d149。

1） 当k=1（表示从v1出发经过由一个村镇组成的S集合到达vi的最短距离为： f1(2,3)f0(3,)d327815； f1(2,4)f0(4,)d429514 f1(3,2)f0(2,)d236915； f1(3,4)f0(4,)d439514 f1(4,2)f0(2,)d246713； f1(4,3)f0(3,)d347815

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

2） 当k=2（表示从v1出发经过由二个村镇组成的S集合到达vi的最短距离为 f2(2,3，4)min[f1(4,3)d42,f1(3,4)d32]min[155,148]20， 所以P2(2,3,4)4

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

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

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

,.

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

所以P3(1,2,3,4)3

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

例2 2004年美国选举活动前一周，位于纽约的候选人Walter Glenn先生必须访问迈阿密、达拉斯和芝加哥三个城市，然后返回纽约。已知这些城市之间的距离如下表。Walter Glenn先生希望最小化他必须经过的总距离，应该以什么顺序访问这些城市？ 编号 1 2 3 4 城市 纽约 迈阿密 达拉斯 芝加哥 纽约 迈阿密 达拉斯 芝加哥 — 1334 1559 809 1334 — 1343 1307 1559 1343 — 921 809 1397 921 — 解：采用逆推法，按已经访问过的的城市数量来编号阶段；在任意阶段的状态由上一次访问过的城市和已经访问过的城市集组成。因为在任意阶段k要确定接下来要访问哪一座城市j需知道两个事件：Walter当前所处的位置城市i和他已经访问过的城市集C（其中在任意阶段k已经访问过的城市集C中有k-1座城市），并规定fk(i,C)为完成旅程所必须经过的最短距离，dij为他目前处于城市i与下一步将要访问城市j之间的距离 。

,.

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

这时状态变量sii,S，状态集S4={（2，{2，3，4}）、（3，{2，3，4}）、（4，{2，3，4}）}。f4(2,2,3,4d211334，

f4(3,2,3,4d211559，

f4(4,2,3,4d21809。

2、k=3（阶段3）

由于Walter目前位于城市i，并且将要到达城市j，那么他需经过的距离为

dij。然后他将处于阶段4，已经访问了城市j，并且已经访问了Cj中的每一

个城市，因此他的剩余行程的距离将为f4(j,Cj)。因此有： f3(i,C)mindijf4(j,Cj) （jC且j1）

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

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]这里jC且j1。因为如他现位于城市i，并且接下来将要访问城市j，那么他需经过的距离为dij。因此他的剩余的行程将从城市j开始，，并且已经访问

,.

了Cj中的每一个城市，因此剩余的行程距离必定为ft1[j,Cj]。 3、k=2（阶段2）

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

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

f2(2,2)min

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

d34f3(4,3,4)92127313652

f2(3,3)min d32f3(2,2,3)1343220639 d42f3(2,2,4)139729024299

f2(4,4)min

d43f3(3,3,4)92126773598 4、k=1（阶段1）

因此时Walter位于纽约，并且还没有访问过任何城市，因此状态为f1(1,•，故有：

d12f2(2,2)134330734407

f1(1,•)min d13f2(3,3)1559395108

d14f2(4,4)80935984407

因此，Walter可以从城市1到2或4，任意地使其选择到4。然后必须选择访问可以得出f2(4,4)的城市，这个城市要求Walter接下来访问3。然后必

,.

须访问可以得出f3(3,3,4)的城市，这个城市要求Walter接下来访问2。然后必须选取择访问可以得出f4(4,2,3,4的城市，这个城市要求Walter接下来访问1。所以最优行程为：1-4-3-2-1，长度为f1(1,•)4407。

,.

授课题目 ： 第八章 图与网络分析 第一节 图与网络的基本知识 教学目的： 掌握图与网络的的基本知识。 ,.

教学要求： 要求学生掌握欧拉图和中国邮递员问题。 教学重点： 掌握欧拉图和中国邮递员问题。 教学难点： 中国邮递员问题。 教学手段与方法： 先用实例引入，再采用比较演示方法。况

第八章 图与网络分析

第一节 图与网络的的基本知识 一、引入：

例1（数学家欧拉与图）欧拉图

普瑞拉尔河从古城哥尼斯堡市中心流过，河中有小岛两座，筑有七座古桥，

,.

1736年，该市一市民向数学家提出一个问题：从家里出发，对七座桥每桥恰好通过一次，再回到家里，是否可行？

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

A B

C

A B

,.

D

二、图与网络的基本知识 1、图的定义

图是由点集Vvi和V中元素的无序对的一个集合Eek组成的一个二元组，记为G(V,E)。 1）顶点和边 2）关联边 2、图的分类

1）有向图和无向图 2）简单图与完全图

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

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

1）有向网络和无向网络

,.

2）权和最短路问题 6、连通图

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

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

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

四、欧拉回路与中国邮路问题 1、欧拉回路与欧拉图

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

欧拉定理：多重图G是欧拉图当且仅当G是连通的且每个结点的度是偶数。 定理3 无向连通图G是欧拉图，当且仅当G中无奇点。

定理4 连通有向图G是欧拉图，当且仅当每个顶点的出次等于入次。 2、中国邮路问题

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

,.

解 1）、如G是欧拉回路，Euler 设计了一条求欧拉回路的算法：

2）、对于非欧拉图，邮递员返回邮局必须将图转换成欧拉图，为此需添加重复边以清除奇次顶点，与奇点关联的边应添加奇数条，与偶点关联的边应添加偶数条（含0条），现在的问题是求解使重复边总权重值最小的方案。

具体方法；

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

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

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

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

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

v1 2 v8 4 v7

5 3 3

,.

v2 6 v9 4 v6

5 4 4

v3 9 v4 4 v5

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

v1 2 v8 4 v7

5 3 3

v2 6 v9 4 v6

5 4 4

v3 9 v4 4 v5

在图1中，将奇点v2和v4、v6和v8配对。对前者连接两奇点的链路有好多条，任取一条（v2，v1，v8，v7，v6，v5，v4），把该链路上的每一条边加上重

,.

复边（见图2）。

同样对v6和v8之间的一条链（v8，v1，v2，v3，v4，v5，v6）也加上重复边（见图3）。在图3中没有奇点，故它为欧拉图。其全部重复边的总权为51。

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

v1 2 v8 4 v7

5 3 3 v2 6 v9 4 v6

5 4 4

v3 9 v4 4 v5

第二步 调整可行方案

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

1）在最优方案中，图的每一边最多有一条重复边。

,.

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

图4 对有两条或两条以上重复边的边去掉偶数条

v1 2 v8 4 v7

5 3 3

v2 6 v9 4 v6

5 4 4

v3 9 v4 4 v5

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

v1 2 v8 4 v7

5 3 3

,.

v2 6 v9 4 v6

5 4 4

v3 9 v4 4 v5

第三步 判断最优的标准

从上分析，一个最优方案，一定满足1）和2）的可行方案，反之，一个可行方案若满足1）和2），则一定为最优。因此对上述给定的可行方案图5，检查它是否满足1）和2），否则对该方案继续进调整，直至1）和2）均满足为止。在图5中，圈（v1，v2，v9,v6,v7,v8,v1）中重复边的总权为13，而圈的权为24，不满足条件2），对其再次进行调整得图6，使总权下降为15。

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

图6 最优方案

v1 2 v8 4 v7

5 3 3

v2 6 v9 4 v6

,.

5 4 4

v3 9 v4 4 v5

授课题目： 第二节 树 第三节 最短路问题 教学目的： 掌握树的基本概念与最小生成树算法及求某点至某点的Dijkstra算法。 教学要求： 要求学生用表操作Dijkstra算法。 教学重点： 掌握用表操作Dijkstra算法。 教学难点： 用表操作Dijkstra算法。 ,.

教学手段与方法： 先用实例引入，再采用比较演示方法。 第二节 树

一、树的概念和性质

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

1、若图的生成子图是一棵树，叫该图的生成树。 2、找图的生成树的方法 ①探测法

②广探法 三、最小生成树问题

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

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

,.

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

第一步：挑选边e1使w(e1)minw(e1)；

e1E第二步：若已选定的边为：e1,e2,,ei，则从Ee1,e2,,ei中选取ei1使：

1）e1,e2,,ei,eI1所组成的圈为无圈图； 2）w(ei1)是满足1）的尽可能小的权。

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

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

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

v1 4 v4 2 6 8 v 51

5 3

v2 ②破圈法

思路：将图G每一个圈权最大的一条边去掉，直到图中不含圈为止。

5 v

3,.

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

1）在图中找到一个圈v1v2v3v4v1，先去掉最大权8对应的边（v1，v2），得图G1； 2）在图G1中找到一个圈v1v4v5v1，去掉最大权数为6的边（v4，v5），得图G2；3）在图G2中找到一个圈v1v4v3v5v1，去掉最大权数4对应的边（v1，v4），得图G3；

4）在图G2中找到一个圈v2v3v5v2，去掉最大权数5对应的边（v2，v3）或（v2，

v5），得图G4或G5，它们均为图G的最小树。

第三节 最短路问题

一、Dijkstra算法

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

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

,.

4 5

6 1

v3 7 v5 6 v7

设G(V,E)为连通图，图中各边（vi，vj）有权lij。令Svk,TV\\vk分别为固定标号集和临时标号集。固定标号P(vj)表示从始点v1至vj最短路权，临时标号T(vj)表示从始点v1至vj的估计最短路权的上界。

节点 迭代 序号 V1 V2 V3 V4 V5 V6 V7 V8 1 2 3 4 5 6 7 8 9 步骤：

P,0 T，∞ T，∞ T，∞ ∞ T，∞ T， T，∞ T，∞ T，4 P,4 T，6 P,6 T，9 T，9 P,9 T，8 T，8 P,8 T，13 T，13 P,13 T，14 17 T，15 T，P,15 T，14 T，14 P,14 1）给v1以P标号，则P(v1)0；其余各点给予T标号，则T(vi)； 2）若vi为刚得到P标号的点，考虑这样的点vj：（vi，vj）属于E且vj为T标

,.

T(vj),P(vi)lij； 号，则对vj的T标号值进行如下修改：T(vj)min3）比较所有T标号的点的值，把最小者改为P标号：P(vi)minT(vi)。当存在两个最小值时，可同时改为P标号；若全部点为P标号时则停止，否则用vi代替

vi，转向2）。

 以上列表如上。

答：从v1到v8的最短路径为（v1v2v5v7v8）；路长P(v8)15。

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

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

275 200 ●v7 100 400 100

A● 150 v2● 175 ●v5 ●B

250 175 150 200 275 ●v8 v3● 300 ●v6 125

节V1 点 V2 V3 V4 V5 V6 V7 V8 B ,.

迭代 序号 1 2 3 T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T，∞ T100 T150 T175 P,10 0 4 T400 T375 P,15 0 T350 T325 T425 5 P,15 0 T325 T425 6 P,32 5 T725 T575 7 P,35 0 T550 8 P,42 5 T550 P,55 P,550 0 T650 P,55 0 答：A到B的最短路径为：A--V2-V4-V7-B；最短距离为650。

,.

授课题目 ： ,.

第八章第3节某点到各点和某点到某点的距离摹乘法。 教学目的： 掌握距离摹乘法的操作程序。 教学要求： 学生能轮流上黑板做题。 教学重点： 掌握距离摹乘法的操作程序。 教学难点： 同重点。 教学手段与方法： 先用实例引入，再采用比较演示方法。况 课后小结： 二、、逐次逼近算法（距离矩阵摹乘法）

适用于一切网络的最短路径的求解（含负权）。它基于这样的事实：从v1到vj的最短路径总是沿该路先到vi，再沿（vi，vj）到vj，。于是若从v1到vj为最短

,.

路，那么从v1到vi也为最短路。用P1j和P1i分别表示从v1到vj和从v1到vi的最短路长，则必有下列方程：P1jminP1ilij。

i该方程可用迭代式求解：

(1)1）令P,2,,n),则用v1到vj的直接距离作初始解，若它们之间无边，1jl1j(j1(1)则P,2,,n), 1j(j12）使用迭代法求P1(jk)minP1(ik1)lik,k2,3,,n，

i(t)(t1)当进行到第t步时若出现P,t1,2,,n,则停止计算。P1(jt)则为v1最多经t1jP1i步到各点的最短路长。 （一）求各点到某点的最短路径 设距离矩阵为Wwijnn，先从vi走一步到vj（j1,2,,n），再从vj走一步到

vr，得到从vi走两步到vr的最短路径（k2）：

(2)dirminwijd(jr21) （1）

1jn1)这里wij为距离矩阵中的第i行元素，d(jr为W的第r列的元素。它们的对应元素相

加再取小，再从各点vi走一步到vj，然后vj走两步到vr（k3）：

(3) dirminwijd(jr31) （2）

1jn最后得到从vi走一步到vj，再从vj走k1步到vr：

(k) dirminwijd(jrk1) （3）

1jn(k)最后得到的dir列中各元素是从wij第i行第n个元素加d(jrk1)取小而来，设这个元素

为从vi到vj最短路径上的邻接点，最后按邻接点xij扒出最短路径。

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

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

,.

从 至 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 4 5 5 2

S ⑥

2 4 ,.

4

⑤ ② -3

第二步：设从vi先走一步到中间点vj（i1,2,3,4,5,6），再从vj走一步到v6，得

1(2)1)到从vi走两步到v6的最短路径（k2）：d16，相当W*d16minwijd(j261j61于用距离矩阵各行与d16对应元素相加再取小。

(2)1) d16minwijd(j261j60 5 2 ∞ ∞ ∞ ∞ ∞ ∞ 0 4 3 ∞ ∞ ∞ ∞ = ∞ 4 0 ∞ -3 ∞ * ∞ 1

∞ -2 5 0 1 ∞ ∞ = 9 ∞ ∞ 4 2 0 4 4 4 ∞ ∞ ∞ -2 ∞ 0 0 0

第三步：设从vi走一步到中间点vj（i1,2,3,4,5,6），再从vj走两步到v6：

2(3))W*d16 d16minwijd(j261j60 5 2 ∞ ∞ ∞ ∞ 3 ∞ 0 4 3 ∞ ∞ ∞ 5 = ∞ 4 0 ∞ -3 ∞ * 1 1

∞ -2 5 0 1 ∞ 9 = 6 ∞ ∞ 4 2 0 4 4 4 ∞ ∞ ∞ -2 ∞ 0 0 0

,.

如此迭代得 3 5 1

(4)(5)d16d16= 6 迭代终止得从vi走一步到v6的最短路径为：

4 0

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

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

 ～

______ min3,5,1,(2)3,,4,000

 0 5 （2） ∞ ∞ ∞

∞ 0 （4 ） 3 ∞ ∞

∞ 4 0 ∞ （ -3 ） ∞

记为W

∞ （ -2） 5 0 1 ∞

∞ ∞ 4 2 0 （4）

,.

∞ ∞ ∞ -2 ∞ （0）

(5)d16中第4个元素3来自（-2）+5，因0+3表示在V4原地踏步一次，得不

到期最路径，故不予考虑。由上矩阵，知v1—v3，v2—v3，v3—v5，v4—v2，

v5—v6，v6—v6在各点到v6的最短路径上。

最短路径 最短距离 v1—v3—v5—v6 3 v2—v3—v5—v6 5 v3—v5—v6 1 v4—v2—v3—v5—v6 3 v5—v6 4 v6—v6 0 （二）、求某点到各点的最短路径 例1 求下图中v1到各点的最短路径。

v2 4 v5 2 -2 -3 3 v1 5 v3 6 v6 4 v8 4 2 -3 -1

v4 7 v7

,.

v1 v2 v3 v4 v5 v6 v7 v8 v1 0 2 5 -3 ∞ ∞ ∞ ∞ v2 ∞ 0 -2 ∞ 4 ∞ ∞ ∞ v3 ∞ ∞ 0 ∞ ∞ 6 ∞ ∞ W v4 ∞ ∞ 4 0 ∞ ∞ ∞ ∞ v5 ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ v6 ∞ ∞ ∞ ∞ -3 0 ∞ 4 v7 ∞ ∞ ∞ 7 ∞ 2 0 ∞ v8 ∞ ∞ ∞ ∞ 3 ∞ -1 0

0 0 2 5 -3 ∞ ∞ ∞ ∞ 0

2 ∞ 0 -2 ∞ 4 ∞ ∞ ∞ 2 5 ∞ ∞ 0 ∞ ∞ 6 ∞ ∞ 0 -3 * ∞ ∞ 4 0 ∞ ∞ ∞ ∞ = -3 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ -3 0 ∞ 4 11 ∞ ∞ ∞ ∞ 7 ∞ 2 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ -1 0 ∞

(k)(k1)L1各行的元素。 i分别与W的各列对应元素相加再取最小，得L1i(3)(2)(6)(5)(5)L1iL1i*W…，当L1iL1i*WL1i时停止。

(2)(1)L1iL1i*W

0 2 5 -3 ∞ ∞ ∞ ∞

,.

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

(6)(5)L1iL1i*W 0

-3 0 4 7 2 0 3 -1 0

所以v1—v1，v1—v2，v1—v4， v2—v3，v3—v6，v6—v5，v6—v8，v8-v7在v1到各点的最短路径上。

最短路径 最短距离 v1—v1 0

v1—v2 2 v1—v2—v3 0 v1—v4 -3 v1—v2—v3—v6—v5 3 v1—v2—v3—v6 6 v1—v2—v3—v6—v8-v7 9

v1—v2—v3—v6—v8 10 （三）从各点到各点的最短路径——Floyd算法 基本思路：

1、输入权矩阵D0d(0)ijnn，表示各点不经任何中间点到各点的最短路径长。

(1)2、记D1dij(1)(0)(0)(0)，其中表示从vi最多经一个中间点dmind,ddijiji11j，nn,.

v1到达vj的最短路长。

(k)(k1)(k1)(k1)3、一般有dij mindij,dikdkj若dij>0，则关于P值的估计为P1短距离。

例2 求下图中任意两点间的最短路。

lg(n1)P,此时DP给出各点到各点的最lg2 v2

v1v5 v4

解：该图有四条无向边，每条均可以化为方向相反的有向边。则 0 5 1 2 ∞ 5 0 10 ∞ 2 DD(0) 2 3 0 2 8

2 ∞ 6 0 4

∞ 2 4 4 0

,.

(1)1）D1dij(1)(0)(0)(0)，其中表示从vi最多经一个中间点v1dmind,ddijiji11j，nn(1)(0)(0)d21d13516。 到达vj的最短路长。按此规则修改D(0)得D(1)，如d23 0 5 1 2 ∞ 5 0 （ 6 ） （7） 2 （1)D 2 3 0 2 8 2 （7） （3） 0 4

∞ 2 4 4 0

(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)(1)2）dijmindij,di(11)d1()j

0 5 1 2 （7） 5 0 6 7 2

（2)D 2 3 0 2 （5）

2 7 3 0 4 （7） 2 4 4 0

（2)(2)(1)(1)d12d25527 表示经过最多v1、v2两个中间点的最短路长。如d15D(2)(1)(1)(2)(0)(0)d35d32d25325 d51d52d21257

0 （4 ） 1 2 （6）

5 0 6 7 2 （3)D 2 3 0 2 5

2 （6） 3 0 4

（6） 2 4 4 0

,.

（3）表示经过最多v1、v2、v3等三个中间点的最短路长。 D(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

0 4 1 2 6

5 0 6 7 2 （4)D 2 3 0 2 5 2 6 3 0 4

6 2 4 4 0

0 4 1 2 6

5 0 6 （6） 2 （5)D 2 3 0 2 5

2 6 3 0 4

6 2 4 4 0

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

,.

,.

授课题目 ： 第四节 最大流问题 教学目的： 掌握求网络中各点至各点的Floyd算法及第4节求网络最大流问题。 教学要求： 要求学生掌握求网络中各点至各点的Floyd算法及求网络最大流问题的标号算法。 教学重点： 掌握Floyd算法和标号算法。 ,.

教学难点： Floyd算法。 教学手段与方法： 先用实例引入，再采用比较演示方法。况

第四节

一、基本概念

1、网络流：满足下列条件：

1）网络中有一个始点和终点vs、vt 2）流过网络的流量均有一定方向； 3）每一条弧都赋予一个容量rij0。

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

2）满足平衡条件：①由始点流出的所有流量之和等于网络通过的流量f； ②对于始点和终点以外的任何一个中间结点，流进等于流出；

最大流问题

,.

③对于终点，流进的所有流量之和等于网络通过的流量的负值-f。 3、最大流：最大的可行流。 二、标号法

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

2）饱和弧和非饱和弧；3）零流弧和非零流弧； 4）前向弧和后向弧；5）增广链。 2、标号法的步骤：

1）先给网络分配一个初始可行流，如没有给定，可将零流作为初始可行流； 2）给予始点标号（-，∞），表示起点可给任意多的流量，则vs已标号待查，让S和S分别表示已标记点的集合和未标记点的集合。

3）取一个已标号待查的点vi对所有与vi相邻而未标号的点vj依次判断如下： ①若存在以S中的点为起点，以S中的点为终点的非饱和弧，即（vi，vj）

i,rijxij；上的流量xijrij，则给vj标号（v,j），其中jmin②若存在以Si中的点为起点，以S中的点为终点的非零流弧（vj，vi），这里vjS,viS，则

vj可标记为（vi,j）i,xji，而当xji0时不给vj标号。 ，其中jmin标号过程可能会出现两种结局：1）标号过程中断，收点得不到标号；说明网络中不存在增广链，现行的可行流就是最大流。（即S中不包含vt，且没有从S中的点到S中的点非饱和弧，也没有从S中的点到S中点的零流弧。）2）收点得到标号，说明在现可行流中存在从vs到vt的增广链，则称该可行流不是最大流，其

,.

流量可以增加，其调整量minj或t，调整方法：在增广链的正向弧上

j增加，在反向弧上减少，其它弧上的流量不变。 例1

v2 v4 7（7） 15（4）

4 11（8）

vs vt

3（3）

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

v3 6（5） v5 解：1）标记寻找增广链

标号 S S

vs(,) vs v2，v3，v4，v5，vt v2(vs,11)，

2mins,rs2xs2 vs，v2 v3，v4，v5，vt =min,11=11

11,40 vs，v2，v5 v3，v4，vt v5（v2，4），5min,4）vt（v5，tmin4,105 vs—v2-v5-vt（增广链）

2）调整流量：t=4，调整后得可行流如下 3）第二次迭代：

,.

标号 S S

vs(,) vs v2，v3，v4，v5，vt v2(vs,7)，

2mins,rs2xs2 vs，v2 v3，v4，v5，vt =min,158=7 从S到S的弧全饱和，从S到S的弧（v3，v2）为非零弧。

，3）v3（v2，3min2,x32=3 vs，v2，v3 v5，v4，vt ，4）v4（v3，4min(3,51）=3 ，vs，v2，v3，v4 v5，，vt

vt（v4,3），tmin4,118=3 vs—v2-v3-v4-vt（增广链）

4）第二次调整流量

v2 v4 7（7） 15（8）

4（4） 11（8）

vs vt

3（3）

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

v3 6（5） v5 图1 第一次调整流量图

v2 v4

7（7） 15（11）

,.

4（4） 11（11）

vs vt

3（3）

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

v3 6（5） v5 图2 第二次调整流量图 5）第三次迭代

vs(,) v2(vs,4)

Svs,v2,Sv3,v4,v5vt，从S到S的弧全饱和，从S到S全为零流弧，故当

前可行流为最大流，最小割集为｛（v2，v4），（vs， v3），（v2，v5）｝，其容量和为7+4+9=20。故最大流为20。

,.