匈牙利法、非标准指派问题的求解方法、实际问题的建模。 第6单元图与网络分析 理论课时10 教学内容: 6.1图与网络的基本知识 62树 65最小费用流问题 知识要求 ①知道网络图在管理中的应用 ②掌握图与树的基本概念。 ③掌握避圈法和破圈法的基本原理。 ④熟练掌握求解最短路问题的 Di jkstra算法(标号法)的基本步骤与适用条件, ⑤了解求解最短路问题的逐次逼近法和 Floyd法的适用条件, ⑥掌握可行流、增广链、最大流、最大流一最小割等网络流基本概念。 ⑦理解最小割的经济意义。 ⑧了解最小费用最大流问题的求解原理。 能力要求 ①会用避圈法和破圈法求一个图的最小支撑树。 ②会用 Di jkstra算法求解最短路问题 ③能够判定一个网络链是否为增广链。 ④在适当条件下,能够建立实际问题对应的最短路/最大流模型。 ⑤会用标号法求解最大流问题,并能够给出最小割、最小割量 教学重点 图与树的基本概念、最小树算法、最短路问题、网络流的相关概念(包括可行流、最大 流、增广链)最大流问题、最大流一最小割 教学难点 最短路算法、最大流算法、最小费用最大流的求解原理、实际问题建模。 七、评价方式与成绩 总评构成(1+X) 评价方式 占比 评测的毕业要求/指标点编号 期末闭卷考试 LO513/LO1 12 平时表现 LO212/Lo112 X2 阶段测验 20% LOS13/LO1 12 X3 课程报告 20% LO2 12/LO611/L0612 撰写人:3, 系主任审核:-x匈牙利法、非标准指派问题的求解方法、实际问题的建模。 第 6 单元 图与网络分析 理论课时10 教学内容： 6.1 图与网络的基本知识 6.2 树 6.3 最短路问题 6.4 最大流问题 6.5 最小费用流问题 知识要求： ① 知道网络图在管理中的应用。 ② 掌握图与树的基本概念。 ③ 掌握避圈法和破圈法的基本原理。 ④ 熟练掌握求解最短路问题的Dijkstra算法（标号法）的基本步骤与适用条件。 ⑤ 了解求解最短路问题的逐次逼近法和Floyd法的适用条件。 ⑥ 掌握可行流、增广链、最大流、最大流—最小割等网络流基本概念。 ⑦ 理解最小割的经济意义。 ⑧ 了解最小费用最大流问题的求解原理。 能力要求： ① 会用避圈法和破圈法求一个图的最小支撑树。 ② 会用Dijkstra算法求解最短路问题。 ③ 能够判定一个网络链是否为增广链。 ④ 在适当条件下，能够建立实际问题对应的最短路/最大流模型。 ⑤ 会用标号法求解最大流问题，并能够给出最小割、最小割量。 教学重点： 图与树的基本概念、最小树算法、最短路问题、网络流的相关概念（包括可行流、最大 流、增广链）最大流问题、最大流—最小割。 教学难点： 最短路算法、最大流算法、最小费用最大流的求解原理、实际问题建模。 七、评价方式与成绩 撰写人： 系主任审核： 总评构成（1+X） 评价方式 占比 评测的毕业要求/指标点编号 1 期末闭卷考试 50% LO513/LO112 X1 平时表现 10% LO212/LO112 X2 阶段测验 20% LO513/LO112 X3 课程报告 20% LO212/LO611/ LO612