前面介绍了关于线性规划和非线性规划的一系列知识点,作为本次系列的最后一篇,严格来讲,本篇是针对网络优化问题来进行展开的,之前写了一系列专门针对网络模型的算法,包括最短路径、最小生成树,后面我会专门列出来,有兴趣的朋友可以去看看。
图模型
前面几篇介绍了系列LP和NLP的优化问题,这一篇将针对NETWORK的优化问题来进行讲解。
网络优化问题向来流行已久,尤其最近比较火的社交网络分析中SAS的SNA将社交网络分析的一个大致架构展现在了众人面前,让我们也得以窥视其中一二。而上述SNA的问题其实就是属于网络优化问题,也可以称之为图模型(Graph model)的优化问题。
为了能够了解什么是图模型,首先介绍这么几个概念:
图:G为一个图,那么它可以表示为一个有序的三元组 (V(G),E(G),jG),其中V(G)是非空的顶点集,E(G)是非空的边集,jG是V对应到G的关联函数。
无向图:若图G中的每条边都是没有方向的,则称G为无向图(Undigraph)。
有向图:若图G中的每条边都是有方向的,则称G为有向图(Digraph)。
有限图:一个图,如果它的顶点集和边集都是有限的,则称之为有限图。
赋权图:对一个图G的每一条边e,可赋以一个实数w(e),称为e的权,G连同它边上的权称为赋权图。
无圈图:不包含圈的图。连通:在一个无向图 G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。
连通图:如果图中任意两点都是连通的,那么图被称作连通图。
树:连通的无圈图。顶点的度:连通图中与该顶点关联的边的数目。
最小生成树:连通图中的最小连通无圈图,要求图的顶点囊括原图中的所有顶点,同时各条边的权值之和最小。
为了让大家理解上面一系列概念,给出一图形如下所示:
上图为一无向图,V(G) ={A,B,C,D,E,F},因为无向图,图中所有边都没有方向,也可以理解为双向图,所以顶点A到顶点B等于从顶点B到顶点A,E(G)={AB,AC,BC,BD,CD,CE,DE,DF,EF},此图为有限图,每条边都有相应的权值,为赋权图,明显不是无圈图,此图任一顶点到另外一顶点都存在路径可以走通,因此为连通图。
在了解了上述有关图的一系列概念之后,我们回到图模型上。图模型主要是由点和线构成的结构化图形,根据图的方向性可以分为有向图和无向图,构成图模型的图形不同于一般的几何图形。例如,它的每条边可以被赋以权,组成加权图。权可取一定数值,用以表示距离、流量、费用等。加权图可用于研究电网络、运输网络、通信网络以及运筹学中的一些重要课题。图模型广泛应用于自然科学、工程技术、社会经济和管理等方面。
算法
关于图模型算法很多,例如常用的dijkstra算法、Kruskal算法等,关于这些算法,之前写过一系列的文章来专门讲述如何用SAS的data步和proc步以及IML过程步来实现这些算法,具体我会在后面放出来,这里不再重复,如果有兴趣的可以看看。
案例
接下来将为大家介绍一个案例:关于道路网的优化问题。问题描述:考虑建立一个SAS雇员家里到SAS总部的一个交通道路网,在这一道路网中,道路和道路之间由节点连接,每条道路从一端节点到另一端节点所需要花费的时间都有很清楚的描述,关于这一道路网的具体数据如下所示:
目标:如何通过这一段道路网数据来找到一个从SAS雇员家里(614 Capital Blvd)到SAS总部(SAS Campus Drive)的最短路径。通过上述数据,我们可以通过miles*miles_per_hour求得每一段道路所需要花费的时间,那么首先我们需要建立一个交通道路网的图展示,如下所示:
从上图可以看出此图为无向图,且从614CapitalBlvd到SASCampusDrive可以明显看出只有三条路径,因此我们其实只需要对这三条路径进行总时间的计算即可比较得出,那么下面我们通过OPTMODEL这一过程来对此问题进行求解。
利用OPTMODEL过程得到如下代码:
运行程序之后,我们可以得到如下结果:
运行时间在log中如下所示:
NOTE: “PROCEDURE OPTMODEL”所用时间(总处理时间):
实际时间 0.21 秒
CPU 时间 0.04 秒
从结果可以看到此图为无向图,问题类型为Shortest Path,从solver来看属于Network优化,且模型达到了优化状态,solution Status为OK。模型最终的结果保存在数据集shortpath里,如下所示:
从上述数据结果可以看到最短路径的具体路线,每段路线所走的顺序,也包括了每段路线所需花费的时间。 好了,本次OPTMODEL系列也就到这里结束了,希望观看此系列的各位朋友能够有所收获,也欢迎一起交流切磋,水平有限,这一系列难免有不足之处,也欢迎各位指出道明,由于还没开通留言功能,所以可以直接在公众号上给我回复即可。
另外,关于下次系列还没想好写什么,所以新文章出炉时间可能待定,但是一旦有新的想法我会及时奉献出来,非常感谢各位的捧场,各位敬请期待。
附录:图模型系列算法:菜单栏“算法”>“图模型”,即可获取图模型的系列算法。