第八讲 网络最优化模型

《第八讲 网络最优化模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八讲网络最优化模型实用管理运筹学------基于Excel求解程序和求解模板第八讲网络最优化模型本讲主要讨论的问题1、网络最优化模型的基本概念2、最小支撑树模型3、最大流模型4、最小费用流模型5、最小费用最大流模型6、最小支撑树模型第八讲网络最优化模型基本概念图1、点和边●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)e3e1e2e5e4人群中相互认识关系图------无向图第八讲网络最优化模型基本概念图1、点和边人群中相互认识关系图------无向图（另一种表述形式）●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)e3

2、e1e2e5e4第八讲网络最优化模型基本概念图2、弧人群中相互认识关系图------有向图钱(v2)●●●●●●王(v7)●赵(v1)孙(v3)李(v4)周(v5)吴(v6)a1a2a3a4a5a6a13a9a10a11a12a8a7第八讲网络最优化模型基本概念图人群中相互认识关系图------无向赋权图●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)w23w12w13w67w343、赋权图第八讲网络最优化模型基本概念图人群中相互认识关系图------有向赋权图●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)c43c12c

3、21c13c31c23c32c34c56c67c76c47c35●●●3、赋权图第八讲网络最优化模型基本概念图4、链在无向图中，点和边的交替序列，其中点和边不能重复。上图中（v2，v3，v4）就是一条链。●●●钱(v2)孙(v3)李(v4)e3e4第八讲网络最优化模型基本概念图5、圈在无向图中，始点和终点重合的链就是一个圈。上图中（v1，v2，v3，v1）就是一条圈。●●●赵(v1)钱(v2)孙(v3)e3e1e2第八讲网络最优化模型基本概念图6、路在有向图（或无向图）中，点和弧（或边）的交替序列，但点和边均不能重复。上图中（v1，v2，v3，v4）就是一条路。●●●赵(v1)钱(v2)孙(v

4、3)e3e1●李(v4)e4第八讲网络最优化模型基本概念图7、回路始点和终点重合的路叫做回路。上图中（v3，v5，v6，v7，v4，v3）就是一条回路。王(v7)孙(v3)李(v4)周(v5)吴(v6)●●●●●第八讲网络最优化模型基本概念图8、连通图若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。下图就是一个非连通图。●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)w23w12w13w67w34第八讲网络最优化模型基本概念图9、树树就是无圈的连通图●●●●●●●王(v7)赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)第八讲网络最优

5、化模型基本概念网络在赋权的有向图中指定了一点，称为发点（或称为源,记为vs），指定另一点为收点（或称为汇,记为vt），其余的点称为中间点，并把图中的每一条弧的赋权数cij称之为弧（vi，vj）的容量，这样的赋权有向图就称之为网络。网络最优化问题就是基本于这样的网络，建立相应的网络模型，求最大值或最小值。第八讲网络最优化模型基本概念网络最优化问题的主要特征1、最短路模型2、最小费用流模型3、最小支撑树模型4、最大流模型5、最小费最大流模型可研究的模型：第八讲网络最优化模型最短路模型最短路模型要解决的问题：对一有向的赋权图中，指定一个发点vs和一个收点vt。目标是使通过网络找到一条路，使两点间的总

6、距离为最短。第八讲网络最优化模型最短路模型例8.1如下图所示，某人每天从住处S开车到工作地T上班，图中各弧旁的数字表示道路的长度（千米），试问他从家出发到工作地，应选择哪条路线，才能使路上行驶的总距离最短？第八讲网络最优化模型最短路模型最短路模型的基本特征1、在网络中选择一条路，始于发点（源点）,终于收点（目的地）2、连接两个节点的连线叫做边（允许向任一个方向行进）或弧（只允许沿着一个方向行进）4、目标是为了寻找从发点到收点的最短路（总长度最小的路）3、每条边（弧）都有一个相关的非负权数，表示该边（弧）所示的路长第八讲网络最优化模型最短路模型最短路模型的求解例8.1中的图中，每两个节点的路线都

7、可以视为有向的，可以将其改画为如下的示意图（将各条边都改为直线段）第八讲网络最优化模型最短路模型最短路模型的求解求解最短路问题实际上就是找一条总长度最短的路线，对于这样的最短路问题，可以建立0-1整数规划数学模型求解（如下图）。第八讲网络最优化模型最短路模型最短路模型的求解为简化求解过程，可以建立专门的最短路求解模型，用计算机求解：可以将图中各条边和每条边是的权数直接录入到求解模型中，直接得到结果