第7讲：网络模型 上次图论课我们重点关注的是图中顶点之间静态的关系，如距离，连接关系 这节课我们来关注对边的限制和边与顶点之间的关系.

Presentation on theme: "第7讲：网络模型 上次图论课我们重点关注的是图中顶点之间静态的关系，如距离，连接关系 这节课我们来关注对边的限制和边与顶点之间的关系."— Presentation transcript:

1 第7讲：网络模型 上次图论课我们重点关注的是图中顶点之间静态的关系，如距离，连接关系 这节课我们来关注对边的限制和边与顶点之间的关系

2 【主要内容】 介绍最大流问题、动态规划问题及搜索引擎中的核心问题-网页评级问题。
数学建模 数学建模 第7讲 网络模型 【主要内容】 介绍最大流问题、动态规划问题及搜索引擎中的核心问题-网页评级问题。 【主要目的】了解构建在网络上的信息流动和基于网络结构进行评价的基本算法思想和过程。 近三年ICM题目： 2013 C题：Network Modeling of Earth's Health 2014C题：Using Networks to Measure Influence and Impact 2015C题：Managing Human Capital in Organizations

3 最大流问题及其算法 第7讲 网络模型 最大流问题是网络优化中的一个经典问题。 问题描述：
有向图N=(V,A,C)，Cij(>0)为弧(i ,j)上的容量（道路最大通过量，管道最大流量，送电线路最大送电量,这样的图也称为容量网络）。假定在网络中一点s处有大批货物要通过网络运送到另一点t. s称为网络的源，t 称为网络的汇。 前面图论中边的权值刻画的是点之间的关系，边上的权值是刻画其连接的两个点之间的关系 这里网络中边上的权值对边的限制

4 设 是定义在弧集A上的一个实函数， 第7讲 网络模型 即 设 若f 满足：
即 设 若f 满足： 则称f 是容量网络N上的一个流,此时fij 称为弧(vi,vj)上 的流量。对于源点s， 为流值。

5 则称f 为N上的一个可行流。也即满足下面三个条件：
第7讲 网络模型 若网络N中的流f 还满足流量限制条件： 则称f 为N上的一个可行流。也即满足下面三个条件： 零流 饱和流

6 考虑如下的问题： 第7讲 网络模型 （1） 最大流问题：容量网络中从源点到汇点的流值最大的可行流
（2）若还考虑对于每条边a上存在单位流量的费用w(a)=wij，一条可行流的费用定义为： 最小费用流：给定流值，求最小费用。 最小费用最大流：费用最小的最大可行流。

7 第7讲 网络模型 假设源点流入为0，最大流问题可建立线性规划模型：

8 第7讲 网络模型 假设源点流入为0，最小费用流问题可建立线性规划模型：

9 假设源点流入为0，最小费用最大流问题可建立多目标规划模型：
第7讲 网络模型 假设源点流入为0，最小费用最大流问题可建立多目标规划模型： 利用图的特殊性，可将这个问题转化为图论来解决。

10 最大流算法 定义： 零弧：fij=0, 饱和弧:fij=Cij 前向弧：源点s至汇点t方向的弧 后向弧：汇点t至源点s方向的弧
第7讲 网络模型 最大流算法 3 1 1 2 4 1 2 也就是说增广路还有可能增大流量，当然增大流量必须保持流量平衡 2 1 3 结论1：若f 存在增广路，则f 不是最大流。

11 第7讲 网络模型 算法目标：保持流量平衡条件下，增加增广路流量。 若 P 是增广路，记 P 的前向弧集合为A1，后向弧集合为A2. 令

12 结论2：（增广路定理）设 f 是网络的可行流，则 f 是最大流，当且仅当不存在关于f 的增广路。
第7讲 网络模型 结论2：（增广路定理）设 f 是网络的可行流，则 f 是最大流，当且仅当不存在关于f 的增广路。 结论3： （整数定理）若弧容量都是正整数，则一定存在一个整数最大流。 最大流算法基本思想：不断寻找增广路（当然要是可行流）和修正增广路，直到不存在增广路。 算法关键是找增广路

13 最大流的Ford-Fulkerson算法 Step 0: 求图N中任意一个可行流 f = { f ij } ，一般取零流;
第7讲 网络模型 最大流的Ford-Fulkerson算法 Step 0: 求图N中任意一个可行流 f = { f ij } ，一般取零流; Step 1: 求增广路 1.0 给 s 以标号 Ps = 0，且δ (s ) =∞ ，规定s为未检查顶点。 1.1 如果所有已标号顶点都已检查过，转Step 3； 否则，任取一个已标号未检查顶点vi，检查所有与vi关联的弧。 求增广路中涉及到两个方面的因素： 1、一条从源点S到汇点t的路 2、记录前向弧的容量增量和后向弧的流量以便获取最小值 这两个过程就涉及到两个状态标志的改变：是否标号和是否检查 标号状态：若已标号表示从S出发的路已经扩充到这里，未标号表示还未扩散过去 检查状态：表示是否已经计算过其可增加的流量最小值

14 对前向弧（i , j ), 如果 vj 未标号，且f ij < C ij ，给vj 标号Pj = i , 并令
第7讲 网络模型 对前向弧（i , j ), 如果 vj 未标号，且f ij < C ij ，给vj 标号Pj = i , 并令 （弧（i , j ),上可增加的流量） 对后向弧（ j , i), 如果 vj 未标号，且f ji >0，给vj 标号Pj = －i , 并令 （弧（ j, i),上可减少的流量） 当所有与vi 关联的弧都检查完毕，称 vi 已检查。 1.2 如果 t 已经得到标号，则一条增广路已经找 到，转Step 2；否则，返回1.1。

15 Step 3：（结束） f = { f ij } 是N 中的最大流。
第7讲 网络模型 Step 2：（修改增广路上的流值） 在增广路上，对前向弧（i , j ), 令 对后向弧（j , i), 令 Step 3：（结束） f = { f ij } 是N 中的最大流。

16 第7讲 网络模型 最大流算法算例：初始流取为0流。 第一次找到增广路: 1->2->4->6 增5

17 第7讲 网络模型 最大流算法算例： 第二次找到增广路: 1->3->4->6 增2

18 第7讲 网络模型 最大流算法算例： 第三次找到增广路: 1->2->3->5->6 增3

19 第7讲 网络模型 最大流算法算例： 找到最大流！

20 第7讲 网络模型 对于最小费用最大流问题，在上述算法上作两点改进： （1) 定义前向弧的费用为wij,后向弧费用为-wij,则可定义每条增广路上的费用； （2）每次找出所有增广路，选择费用最小的增广路进行调整

21 动态规划是解决 第7讲 网络模型 动态规划模型(Dynamic Programming) 多阶段决策过程最优化 的一种方法。多阶段决
策问题，是指一个问题 可以分为若干个阶段， 每一阶段需要做出决策 ，而一个阶段的决策， 常常会影响下一个阶段的决策。要在各个阶段决定一个最 优决策， 使整个系统达到最佳的效果。下面先以最短路为例， 说明如何建立动态规划模型，然后我们再来总结。

22 第7讲 网络模型 最短路问题的动态规划最优化原理 : 假设一条最短路线经过状态 xk  ，那么，这条路线上从 xk  到终点的一段，是从 xk  出发到终点的所有路线中最短的。 逆序法（回溯法）： 从后向前逐步求出各点到终点的最佳路线，最后得到由起点到终点的最短路线。

23 第7讲 网络模型 ① 从最后一个段开始，设k = 5 ,这时从E到E最短路为f5(E)=0,

24 第7讲 网络模型 ② k = 4 ， 有三个状态D1 , D2 , D3 ,它们分别到E的最短路为

25 第7讲 网络模型 ③ k = 3 ， 有四个状态C1 , C2 , C3 , C4,它们分别到E的最短路为

26 第7讲 网络模型 ④ k = 2 ， 有2个状态B1 , B2 ,它们分别到E的最短路为 ⑤ k = 1,

27 （1）动态规划的特点是将问题按时间或空间特征而分成若干个阶段，从而将整个决策过程转化为多阶段的决策问题。
第7讲 网络模型 动态规划模型的特点: （1）动态规划的特点是将问题按时间或空间特征而分成若干个阶段，从而将整个决策过程转化为多阶段的决策问题。 （2）无论过去的状态和决策如何，对当前状态而言，余下的诸决策必须构成最优策略。 （3）一般模型 也可能为最大，依问题而定

28 如何将问题转化为动态规划模型是建模的关键 如对某些静态决策问题可以引入时间因素，将问题转化为多阶段的决策问题，然后利用动态规划方法求解。
第7讲 网络模型 如何将问题转化为动态规划模型是建模的关键 如对某些静态决策问题可以引入时间因素，将问题转化为多阶段的决策问题，然后利用动态规划方法求解。 设有某种资源总数量为a，用于生产n 种产品。如果分配数量xk 用于生产第k种产品，其效益为gk(xk )。问应如何分配资源使生产总效益最大？ 可能非线性

29 第7讲 网络模型 引入潜在时间轴，应用动态规划方法求解 令sk 表示分配用于生产第k种至第n种产品的资源数量，即状态转移方程sk＋1 ＝sk-xk （s1=a ,sn＋1 = 0）， fk(sk )为最大效益。则逆序递推方程为

30 第7讲 网络模型 网页评级（PageRank）问题 —Google搜索中的数学模型

31 第7讲 网络模型 将互联网上所有网页（网站）按照超链接关系建立网络。 模型前提：
对网页级别的评价是基于超链接构建的网页结构，但重要度并不仅仅依赖超链接； 网页的重要度最终由被访问的概率决定（访问得越多，越重要，这是由网络用户来决定的）； 问题：由超链接如何判断哪一个网页将被访问的概率有多大？

32 第7讲 网络模型 模型建立 （1）结构上，将整个互联网的网页建立成一个有向图，其中结点为网页，边为网页之间的超链接；
（2）语义上，每一个网页看成一个状态，那么从一个网页链接到另外一个网页看成是从一个状态转换到另外一个状态，而这个过程可描述为用户从一个网页点击超链接进入另外一个页面的过程； （3）将这种状态转移的过程建模成寻找最终各个状态出现的概率问题。而各个状态（网页）之间本身存在状态转移。最终出现概率对应了根据网络结构预测到的用户访问网页的概率问题。也就是网页级别。

33 上述这种由各状态转移概率获取最终状态出现概率的问题本质上就是马尔科夫链的平衡问题。
第7讲 网络模型 上述这种由各状态转移概率获取最终状态出现概率的问题本质上就是马尔科夫链的平衡问题。 用图的邻接矩阵表示网页之间的链接关系，设G为表示网页之间超链接关系的邻接矩阵，显然矩阵中元素只能为0或1，记： 表示页面 j 的链出页面总数和页面 i 的链入页面总数。

34 第7讲 网络模型 假设用户在上网浏览页面并选择下一个页面的过程，与过去浏览过哪些页面无关，而仅仅依赖于当前页面并且与内容无关，完全由页面上的链接数来决定（随机冲浪），则从一个状态(页面）转换为另外一个状态（页面）的转移概率矩阵可写成A=(aij)： 有两种理解:(1)概率gij/cj与1/N之间的加权系数，表示转移只以d的可能满足转移概率gij/cj；（2）表示以d 的概率信任从页面j过来的超链接，而(1-d)/N为基本转移概率。 PageRank中 d=0.85。

35 第7讲 网络模型 A即为马尔科夫链的状态转移矩阵，aij表示从页面j转移到页面i的概率，根据马尔科夫链的基本性质：正则马尔科夫链存在平稳分布 满足: x 表示的极限状态（转移次数趋于无限）下各网页被访问的概率分布。将其定义为网页的PageRank值，即为 转移矩阵A的最大特征值（=1）对应的特征向量即为PageRank值。

36 （2）利用整个网络的网页来决定单个网页的质量； （3）将一个网页级别排序问题转化成了一个公共参与、以群体民主投票的方式求解的问题。
第7讲 网络模型 由PageRank的模型，我们可以发现： （1）若将超链接看成是”投票”方式，网页A链接到网页B，则认为网页A投了网页B一票，但重要度并不简单由其得票数决定,各个站点投票权重不同，重要的网站投票具有较大的分量，而该网站是否重要的标准还需要依照其PageRank值； （2）利用整个网络的网页来决定单个网页的质量； （3）将一个网页级别排序问题转化成了一个公共参与、以群体民主投票的方式求解的问题。

37 第7讲 网络模型 计算案例： 邻接矩阵： 概率转移矩阵： 2 3 4 5 6 1

38 第7讲 网络模型 计算A矩阵的特征值1所对应的特征向量，并归一化后得到：
PageRank=(0.2675,0.2524,0.1323,0.1697,0.0625,0.1156) 2 3 4 5 6 1

39 第7讲 网络模型 Hypertext induced topic selection(HITS)算法 HITS算法是另外 一个衡量网页重要性 的算法。其用两个量 来衡量网页的好坏： （1）权威性 （2）集线性 权威性反映网页本身的好坏，内容越好，权威性越高，而集线性反映了网页作为路由的好坏，网页所指向的高质量的网页越多，则集线性就越好。

40 第7讲 网络模型 两个基本假设 （1）一个好的权威性页面会被很多好的集线性页面指向。 （2）一个好的集线性页面会指向很多好的权威性页面。 HITS算法与PageRank算法最大的不同：PageRank算法与用户输入的查询无关，其是将整个互联网作为一个整体进行分析；而HITS是根据用户输入的查询内容选择跟查询内容相关的网络子图进行计算和分析。

41 第7讲 网络模型 HITS模型 设参与计算的子图的所有节点的集线性用向量h表示，而所有节点的权威性用向量a表示，两者之间的关系可以表示为 其中 给定初值可对上面模型进行迭代计算，可以证明收敛时a为ATA最大特征值对应特征向量，而h为AAT最大特征值对应特征向量.

42 第7讲 网络模型 对上面提到的网络进行计算

43 第7讲 网络模型 作业： 7.1. 某贸易公司在每个月的月初订购货物，订购后能及时到货、进库并供应市场。货物与当月售出，则不必付存贮费。当月未出售的货物，盘点后转入下月，每件要付库存费6个单位。库存的最大贮量是120件。预测1月到6月的订购价格和需求量如下： 月份 需求量 价格 假设1月初的库存量为零，要求6月底的库存量也为零，不允许缺货。试做出6个月的订货计划，使成本最低。 7.2. 简述PR算法与HITS算法的基本思想。

44 谢 谢！