运筹学》课程教案.pdf

《运筹学》课程教案

第 8 章图与网络模型

授课题目(教学章节或主题): 授课类型课堂讲授
9/4 课时
第 8 章图与网络模型授课时间(注:以上课时分别对应于教学
计划为 54/36 学时的情况)
教学基本内容:
第 8 章图与网络模型
图与网络的基本概念与典型举例
最短路问题及算法
最小生成树问题及算法
最大流问题及算法(教学计划为 36 学时的班级选学)
网络优化方法案例分析(教学计划为 36 学时的班级精选部分案例)
教学目的:
1) 理解图与网络的基本概念和特点,掌握最短路问题的网络模型建模方法及其求解
计算方法。
2) 理解树、生成树、网络流和最大流问题的基本概念和特点,掌握在网络中求解最
小生成树的计算方法。
3) 掌握网络最大流问题的求解算法,学会应用本章介绍的几种网络优化方法对管理
中的不同类型的实际问题进行优化分析,培养学生分析和解决实际问题的能力。
讲授要点:
1) 介绍图与网络的基本概念。结合实例讲授最短路问题及其应用以及计算方法.
2) 介绍树和生成树的概念、特点和性质。结合实例讲解最小生成树问题的应用和求
解最小生成树问题破圈法的原理。
3) 通过应用实例引入最大流问题,讲解有关最大流的相关概念。结合实例讲解最大
1
流问题的应用和计算方法。通过案例分析总结本章各方法在不同实际问题中的应用
及其特点,并通过案例分析和课堂讨论,使学生掌握进行网络优化的计算方法。
重、难、疑点:
重点:1) 最短路问题的相关概念和求解算法; 2) 最小生成树问题和最大流问题的相
关概念及算法。
难、疑点:
1)求解最短路问题的Dijkstra算法的计算原理;
2)应用最短路方法解决实际问题。
3)求解最大流的算法及其在管理实际问题中的应用。
解决办法:
1) 将其求解最短路问题的Dijkstra算法总结归纳为可在网络图上操作的标号法。通
过例题结合多媒体作图动态演示求解最短路问题的标号法分解计算步骤,并通过边
讲边练,讲练结合来讲解最短路问题的求解方法及其应用案例分析。
2) 通过例题结合多媒体作图动态演示求解最小生成树问题破圈法的分解计算步骤,
并通过边讲边练,讲练结合来讲解最小生成树问题的求解方法及其应用案例分析。
3) 通过例题结合多媒体作图动态演示讲解网络流增广链的概念以及在网络中寻找
增广链的方法,进而讲解求解最大流算法的分解计算步骤,并通过边讲边练,讲练
结合来讲解最大流问题的求解方法及其应用案例分析;同时对通过本章各方法在不
同实际问题中的应用及其特点进行归纳总结,并通过案例分析和课堂讨论,使学生
掌握进行网络优化的计算方法。
教学手段与方法:
,实现对作图和相应算法步骤进行图文并茂的
分步演示和讲解,生动地展现计算过程和结果,并进行边讲边练,讲练结合;
。
3. 通过案例分析和课堂讨论对本章各方法在不同实际问题中的应用及其特点进行
总结,使学生掌握进行网络优化的计算方法。
思考题、讨论题或作业:
思考题:思考最短路问题、最小生成树问题的不同