论文研究-系统科学中的网络模型及其优化理论——综论与展望.pdf

所需积分/C币:8 2019-09-20 12:37:08 921KB .PDF

论文研究-系统科学中的网络模型及其优化理论——综论与展望.pdf, 本文综合评论系统科学中网络理论若干主要概念和近期的重要成果,探讨理论与实践中存在的若干问题;阐明网络优化与几个数学分支之间的关系和渗透;结合我国条件,展望和提议一些可能的待研究方向或课题。
际上,由于大多数被研究的对象都是点一线星罗棋布的大系统网络中还可能存在反馈环或循 环(圈),点“点之间可能存在增益或衰减,同一网络中可能存在多个起步点(源点, Source) 和多个终止点(收点, terminal),工期可以是确定性的(例如CPM)也可以是概率性的(例 如PERT),事件或活动都可能有某种不确定性或随机性(例如GERT)或网络中一部分确 定性而另一部分穊率性,考虑网络中的回路( circuit)还须引入拟阵( matroid)的运算 这些几乎只能利用计算机才能找到答案。即使用现代大型计算机,解大网络优化问题(例如 大数学规划问题)也总是要考虑数据结构(如矩阵的稀疏性、表处理能力)和程序效率(存 储量、计算机时间)等问题(例如大规划中矩阵元素位置数常在10-10范围内)。在这里, 有效的数据库安排和高效率专用网络码的设计往往成为问题的症结(一个专用转运网络程序 约比通用线性规划子程序快100倍!) 网络流理论 系统工程网络的很大一部分抽象理论基础来自网络流理论,因此有必要讨论一下有关的 概念和算法。 1.最短路线问题 已知网络(有向图)G=(N,A),其中=N是节点数,m=|A|,m≥n是弧数;或者认 为N是节点集,A是弧集,而每段弧a∈A是相异节点的有序偶a=(i,j),并有长度a;,规定弧 a=(i,j)是从i到j。一般说弧长可正可负,但若假定G不含有向圈弧长的和航是严格负的 个流(flow)就是满足某种借助流出节点i的净流f;规定的流约束的集的一个向量( a∈E),这里 如果f1为负,则一f;就是流入节点i的净流。流的物理意义可以粗浅地想象成某种商品流或 物料流。流约束可以是 ∑f1=1,f1≥0,i∈S,S=源点集 =0,i(S。USr,Sr=收点集 ∑f;=-1,f1≤0,i∈Sr 更一般的网络流问题中流约束形式是f;=b;,i∈N。 弧a的单位成本是某个数c,(例如通过弧长a;表达)我们希望使流的总成本∑cx,极 小化。当所有的c≥0,上述问题的答案将形成从源点到收点的一条链( chain)。一个路线 (path)是简单有向路,也就是一个序列i,at,,a2,2,…,i-,8L,i(交替的点和弧),而且 ak=(ik1,i)或ak=(ik,-)。如果路上无重复节点,即节点i,in,…,i相异,且每边ak= (ik-1,),就叫链。可见链是无循环(圈)的路,但有的文献不加区别。 求网络中二个指定节点间最短路长问题大都嵌入求一个从原点到其它节点的最短路长问 题中,后者是略大一点的问题。设从原点到节点j的最短路长为u,原点标号为1,其它节 点依次标以2,3,…,n,则最短路长须满足下述方程 0 u;=min u;+ail, j=2, 3,",n (i)6A (3-1) 如果存在任一这种路,就存在从原点起的带根有向树,使该树中从原点到模j的唯一路 长等于u。这种树叫最短路树。解方程(3-1)的算法都可以看成是在某特定条件下构成这种 最短路树。 解上述最短路问题的计算机算法,主要有以下一些: 1) Dijkstra算法适用于全部弧长非负的情形 2)Bel1man-Ford法这是一种逐次逼近法,适用于带圈和弧长并不全部非负的一般 惰形。 3)全偶(ll- pairs)算法这类算法适用于求有向网络中所有成对节点间的最短路线 例如用于全部弧长非负的Spia算法、 Floyd- Marshal1算法等 还存在大量的特定算法,有关文献可参看[6]。 2.最大流 L知网络G=(N,A),每段弧(i,j∈A具有特定的容量( capacity)a1,流x须满足 0≤x。≤a1,(i,j∈A 而流约束仍借助净流f;表示,流出源点或流入收点的净流量是 Q t i (;i}e (t, i)6A 则约束条件是 ∑f;=Q,f1≥0i∈ 0.igS。US ∑ f1≤0,i∈Sr 问题就是找出使Q极大化的流,而不考虑弧上的成本或弧长。 解最大流问题的早期算法是基于所谓扩张路( augmenting paths)的Ford- Fulkerson 算法⑩。扩张路是源点和收点间的无向路,其中对路中每个“正向”弧有x订α,每个“反 向”弧冇x>0。(方向从源点s到收点t叫正向:反之叫反向)。可以沿一个扩张路来扩大 流、通过每-一正向弧增大流,每个反向弧减小流,由此获得较大的Q流。仅当相对于流不仔 在扩张路时,流才是最大的。 解最大流问题的其它著名算法包括 amends-Karp法、 Dinic法、 barzano法、 Cheung 法等,近期的一篇论文对八种算法作了详细比较。 3.最小成本流 用弧长a;表网络中弧(i,j)的单位成夲ca,希望已Ⅻ从s到t的Q值的涴,使 得 (i,!EA ①即最大流-最小割(max- flow min-cut)算法0。 4 极小化。解这类最小成本流及其推广的问题已有大量算法,例如利用线性规划的原始和对偶 单纯形算法;采用最短路线和负循环过程作为子程序的算法;互补松弛性( complementary slackness算法以及相当巧妙的所谓离序(ot-of- kilter)算法。离序法中,设每段弧(i,j 已定出流的下界θ;和容量a;,因而此时 0≤1≤x1≤a 希望求出使 ai ]xij 极小化的一条环流( circulation)一即在每个节点上满足守恒律的流 当然,对这一极小化问题也有线性规划对偶,其基本变量是节点数或潜力( potential) u。如果给定的弧流集{xu}和节点数u全部“在序”(" in kilter"),则原始解和对偶解都是 最优的。给定弧(i,j)“离序”的程度由序数( kilter number)K;确定,它代表将弧(i,j归 入“序”中必需的x变化量的绝对值。确切点说, I xii-B: il 当u-1:<a ax{分u 0}当 qui-ui>aii 序数的和 K K 是给定一对原始-对偶解离序程度的一种度量 围绕上而提到的几种算法,近年来提出了各种修正算法和有关的结构理论°。通常最小 成本流算法主要用于非常大的网络优化,有人已解过包含20,000个以上节点和450,000段 以上弧的人网络最小成本流问题,当然所费计算机时间相当长。有人用原始算法在ⅠBM360/67 上解3,000节点、35,000弧的问题用了97秒钟:5,000节点和15,000弧则用去113秒钟 实际上,过去十年的许多实验硏究表明,采用线性规划原始单纯形法解一般带容量转运 capacitated transshipment)问题和运输问题,比作为原始-对偶线性规划算法的:离序算 法约节约时间30-40%。所以究竞何者为优,至今仍是个有争论的题目 4.带增益的广义网络流 这时网络中的流具有一定的增益(或衰减),即流穿行一段弧a时用因子k乘之,随着 时间推移,累积起来可在流中造成很大增益(或衰减)。这类问题有着广泛的应用领域,例如 计入各活动环节中创造的价值或消耗的资金的运输网络。不过这类问题的收敛性至今还是个 没有很好解决的问题。 5.多端流和多商品流问题 多端( multi- terminal)流问题中涉及各对节点间有给定流的网络,但不考虑分享弧容量 而同时存在的流。多商品(mult- commodity)流问题中要求各对节点间同时传送指定的或 最大的流。在一段弧中的总流必须不超过它的容量。有关的论题和算法已在近期的两篇综述 文里n作了极好的总结.最近正在探索具有包装约束的多商品流问题0 四、网络优化中的计算复杂性 计算机科学中近些年发展起来的计算复杂性理论已被作为重点论题引进网络优化算法的 评价和估计中来。这种理论的解析基础属于组合论范畴,形式理论则建立在图灵的自动机理 论基础之上。粗浅地说,网络优化中的计算复杂性问题就是是否可用一种有效的“好”算法 给出优化问题的解。例如网络最大流问题、网络匹配问题都有可能找到这种“好”算法,反 之,象图的着色、集覆盖、一般整数规划、经典的渐缩( knapsack)算法、多处理机调度问 题、流动售货车、推销员、作业区调度、多商品流等相当多的一类问题,计算上则从来是困 难的,几乎全部这类问题不久前还只能靠枚举法解决,其中涉及在一个网络中某种类型的折 返寻优,其层次或深度是以问题大小的多项式函数界定的。在最坏情况下,这些算法需要超 多项式(例如指数)吋间。探讨这类问题的理论和实用价值是显而易见的,它能使我们预见 个问题在什么条件下和怎样获得高质量的求解方法,并从问题的结构查明计算的有效程度 避免盲目性和甚至不可解性。 个算法是以多项式时间执行的,如果它全部运算数的上界是n的多项式,n是度量问 题规模的-·个输入参数。用P记用多项式时间的算法可解的所有问题的集,用p(n)记n的多 项式。进一步,用NP记可用多项式一层次折返寻优求解的所有问题的集,显然PcNP,即NP 类问题是不确定性的多项式时间算法(这里N与“不”字对应,也对应于不确定性图灵机理论) 再进一步,问题难到只能找到以指数时间执行的算法,也就是完全非多项式时间可解,其运 算数上界是2"),则相应的问题的集就叫NF-簇( ariety)或NP-完备( complete)。显然属 于NP簇的问题都不属于P;如果有一个属于P,则NP中的全部问题就都属于P了(此时 P=NP 多项式P(n)中n的最高次幂叫算法的阶数。当然,一个n3阶的算法优于一个n°阶的算 法。而问题要用指数时间求解时,一般均只能靠枚举法或近似算法。排队网络、调度网络中 许多问题都已证明是NP-完备的,例如前面提到的一系列难题,还有所谓B&B(分枝边界 问题。 比方某网络优化问题中用多项式时间和指数时间的算法所需运算数分别是10002和2 而n表节点数。如果n=1,后者将比前者快500倍,但一般系统工程中的活动网络,节点数 都远大于1。设想n=A0,前者就比后者快600,000倍!事实上从n=20开始,节点数增加 1,前者运算时间只增为4倍,后者则增为1,000,000倍!可见,如果算法占用的机时以几 分钟为限,则网络问题中属于P类的一些问题(如最短路流、最大流、最小成本流或最小生 成树),一般都能用准确算法处理较大规模的网络(节点数几百到几万);而属于NP-完备类 的间题,用准确算法只能处理很小规模的网络,而一般只能用近似法、探试法( heuristics)。 例如推销员问题、带容量的最小生成树问题、车辆运行路线问题等,目前用探试算法订在几 分钟计算机时间内求解节点数1000以上的网络优化问题,而用准确算法则最多只能有几十个 节点。 由于最近几年对计算复杂性理论的深入探索,使我们弄清了许多NP-完备问题的可解条 件。例如推销员问题是NP-完备的,除非P=NP,一般是不能用多项式时间找到最优解的 但在特殊条件下(例如属于所谓欧基里得推销员问题),可以多项式时间找到最优(50%以内) 的一个解。用多面体( polyhedra)表征NP-完备性问题,近年已找到确定推销员多胞形(po ly tope)各面所服从的不等式的集;在相应的线性规划中加进较少的面,已准确地解决了多 达318个节点的网络优化问题。过去十年,还研究了各种NP完备问题的紧凑表达法;利用 这些表达方式,成功地设计和分析了采用运筹学中熟知的 Benders分解或 Lagrange松弛的 新求解算法,准确算法和探试算法都有。对于NP-完备问题,也存在问题之间实现转换的可 能性,此时能在转换后导致计算时间的下降。此外,象图论中图的同构问题(具邻接关系的 二图顶集之间是否存在一对一映射)、拟阵交问题和非双枝匹配问题等产生的拟阵奇偶性问 题、三机单位时间平行作业问题等,近年来也都获得了在系统工程中可以找到应用领域的一 些重要结果 由于NP-完备问题不能以多项式时间最优地求解,促使近十年集中力量分析和评价探试 算法(它们具有多项式时间边界)的精度或解的质量,并寻求相应的快速探试算法。在这一方 向上,例如进行与可能的最优解作比较的实验分析,求决定最优解和探试解的权值之间最大 可能的差的边界的所谓最坏条件分析。新近发展的两种分析方法是概率性分析和统计分析 概率性分析中硏究几乎全部冋题均保证提供最优或近最优解的算法问题,这需要给定每一规 模(如节点数n)的问题整个集上的概率分布。其中用的准则是下述概率 Prob 探试解 最优解 ≤1+ 这里c>0和→0,当n→∞。至于统计分析,则是采用传统的统计推断方法来估计探试解的 “最优性” 总之,计算复杂性仍为网络优化中人们最关心的问题之一。 五、实用网络优化 除了在网络优化时考虑了弧上活动和点上活动两种模式外,用于工程实际的网络主要分 成三类Uu0uL1:确定性网络、概率性网络和广义(随机)网络。较早的文献主要按计划协调 技术(PERT)、关键路法(CPM)和随机型计划协调法(GERT)来划分。但从十年来的发展 情况看,这种分法并不完全符合方法论的要求,因为在大量实际问题中已更多地采用了它们 的混合技术,网络优化的应用范围已迅速扩大和深化,已经不是原始的PERT等所能代表的 虽然在确定性条件下的工期-成本平衡算法、受资源限制的工程计划算法等,说到底仍为 CPM法,但早已不是它的本来面日了 作为概率性网络代表的PERT有几个基本假定:活动全部是独立的;关键路包含了足够 多的活动,从而可应用中心极限定理;一项活动的持续时间的概率密度函数可以用B-分布 逼近;如果用ta、tb、t。分别代表估计的活动最短、最长和最可能时间,则-分布的平均时 间或即统计期望时间 te≈(t+tb+4te)/6 (5-1) 而方差是 (tb-ta)2/36 (5-2) β8-密度函数实际上是一个四参数分布,不象高斯分布那样仅由平均值和方差就能确定。但这 反过来提供了-分布下的灵活性,可以“拟合”任意预期的形状和位置。此外,采用月-分 布计算上也比较简单易行,当然根据问题的性质,也可以采用高斯分布或其它分布。十多年 来提出了各种估计工期的密度函数的实用算法,并为此建立了许多通用数表利计算用的程序 广义网络模型可以包括把CPM与PERT结合起来的PERT/CPM模型,但一般均指 GERT。PERT考虑了弧上的概率,但点上(事件)的概率为1(确定性),而且不能处理环 流,只能有一个终点等。特别是制定科研发展计划时,计划既有成功也有失败的可能,因而 会出现若干概率分支和通过反馈环(环流)的重复活动,有的科学实验甚至要重复上千次 在这种情况下更有利于采用灵活性大得多的GERT。 GERT模型所有节点的“输入”一边具有“异-或”判定模式:它是一种半马尔可夫过程 的表现形式;在简单的变量变换后,刚络实质上就是常见的信号流图。近些年还大大推广了 GERT的结枃,例如允许存在非异一或模式、能处理离散随机变量和多重随机变量的复杂 情况等,其应用范围甚至包插人口动力学、讣算机算法、交通网络分析、维修和可靠性研究 等 在编制科研发展计划时,很可能存在多个科研梯队同时交叉地完成多个科研项目。这时 GERT刚络变得极为复杂,达到无法辨认的程度。近年发展的排队-GERT(Q-GERT)1有 效地克服了这一-困难。它除包含了概率性分支、网络环沉、多收点点、多节点实现和多概 率分布等GERT的主要特征外,还通过排队( queue)节点贼予每一个别项目独特的网络属性 (活动时间、节点分支概率),然后通过单一网络处理每一项目。 在实网络的理论研究方面,目前比较活跃的领域还有概率性网络中的最大流问题t11 排队网络的分析[、随机网络的可靠性研究12151、算法与硬件环境的相互影响和算法与信 息系统的相互影响、数据通信网络的分散算法p,以及特别是交互式网络优化算法间题 等 交互式网络优化的思想,早几年已被日本学者成功地用于日4新干线铁路网客货运调度 和服务计划的编制上,其中通过熟练的调度员与计算机之间的对话来随时修正计划,使铁路 运行处于最优状态。文献[2]的作者及其同事曾描述过交通网络上调度公共汽车驾驶员的 交互式算法,其中通过最小成本流或序列匹配算法由机器快速解出,再通过人一机对话进行 修正。 十年来围绕着传统的CPM、PERT和GERT,在实用方面进行了范围极其广泛的研究 其中值得一提的有下面一些: 1.考虑能源合理开发、布局、运输和存储的能源网络模型和能源政策模型。 2.把涉及发货站、多周期路线、混合车队生产力、多目标、补给站位置、随机霈求量 和随机旅游时间、多维(海、陆、空)运输等因素引进车辆和乘务员路线和调度网络模型。 3.流水线和设备布置和定位设计。 4.计算机通信和数据处理网络的优化。 5.程计划中采用推广的PERT-CPM法。 6.流动资金的管理冈络 7.销售学的网络模型 8.考虑多种随机因素的资源分配网络。 电力网络扩建规划和合理布局。 l0.区域性污水处理系统的设计 这些实例都散见在各有关杂志或会议文集中,包括文末所附文献的各个出处。限于篇幅,没 有将它们一一列举出来。 在实用网络优化研究中,平行地发展了大量的专用或通用彷真语言、程序包或程序库象 GERTS就是专为GERT设计的仿真话言。至于采用GPSS等通用仿真语言或用 FORTRAN 等高级语言配备的程序包就更是多如牛毛了 六、若干可能的研究方向 下面根据国内外有关网络优化问题的研究现状和趋势,结合我国具体条件,谈谈个人对 可能的一些研究课题的初步估计或设想。 1.理论方面 1)把整数规划、组合论、图论、线性规划作为整体进行研究,过去十年里已经尝到很 大甜头。例如图论中匹配、点合并、点覆盖和边爱盖等主要的优化问题已能用整数或线性规 划解决;它们的结合还将产生许多新结果,为抽象网络问题建立许多新方法论 2)开展计算复杂性的研究。今天计算机科学中一个尚未解决的问题是究竟能否P= NP?一般的推测是P≠NP。对于NP-完备类的问题,目前还有大量工作可做。例如对前面 提到的一些NP-完备问题,是否象推销员问题一样有以多项式时间可解的特殊情况?推销员 问题本身也可以探索其他可宦的特殊情況 3)建立理论与应用之间的桥梁,即开展应用基础研究。目前在图论和组合论中存在许 多明显地可用于实际的抽象理论,但缺乏把抽象理论变为解决实际系统工程问题的更广泛的 理论和算法研究,而这类研究往往是个关键问题。例如最小无向和有向生成树问题采用拟阵 概念的算法推广“后,已使得在多项式界定的计算机步数中可解的一类问题扩大了:全么模性 ( totally unimodularity)的概念促进了分配间题和最小成本流问题中约束矩阵数学结构的 研究等。 4)探试算法的分析。对于大量存在的NP-完备问题,探试法是一个有力工具。但目 前还没有很满意的评价准则,特别是概率性分析和统计分析,缺乏能较普遍适用的分析依 据 5)建立网络优化程序库或程序包。就作者所知,国内虽已开展了这方面的工作,并已 有个别软件出售,但大都偏于经典方法,很少或几乎没有反映最新的一些理论成果 6)开展多目标或多判据线性(整数)规划方面的研究,并探讨怎样在网络模型中引进 多目标决策的一些基本持征。这里在确定性情况下可以结合决策关键路法(DCPM)进行; 而在概率性网络中,宜于将GERT的“异-或”判定加以适当改道来适应多目标要求。 2.应用方面 1)结合我国工程实际和经济结构,摸索出一套网络化建模的规律,并编写出有关文件 ①混合整数线性规划问题可写成 极值化c 满足 Ax+By≤e,x≥0且整数,y≥ 这里A,B为矩阵,x、y、C、d和e为向量。 多目标混合整数线性规划问题可写成 极值化Cx+Dy 满足x+By≤e,x≥0且整教,y≥0 其iC、D为矩阵。 9 或手册,便于工程人员按图索骥,管理人员顺蔓摸瓜,而少用或不用数学工具,争取每把锁 都能找到合适的钥匙。这对于我国现阶段尤属必需。 2)为计算机配备起码的网络优化软件,其中特别是仿真语言的编译和编辑、人机接口 软件和计算机科学新兴软件能力(交互式计算、表处理、数据结构、微程序设计等)和硬件 能力(微型机,海量存储器等)怎样迅速地被利用来为网络优化服务。各先进省市都应当建 立网络优化用的数据库。这些论题都有大量工作等着我们去完成 3)在我国,有关网络优化问题尚局限于小规模网络。牵涉国家或地方经济系统分析、 能源问题、环境污染冋问题、农业规划问题、科研规划问题、城市规划问题等都可能釆用大网 络模型进行研究。这方面还牵涉到算法问题 4)我国的数学家较少跟工程师(特别是系统工程专家们)对话或交流的现象是很普遍 的,尤其有的人掌握计算机知识较少,妨碍了应用研究和普及工作的开展。数学家与其他专 家的结合,势将发现更多的应用领域 參考文献 1] Assad, A, Multicommodity Network Flows--A Survey, Networks, 8,1( 1978), 37-91 2] Ball, M.O., The Complexity of Network Reliability Computations, Networks, 10, 2 (1980), 153-165. 31 Cheung, T-Y., Computational Comparison of Eight Methods for the Maximum Network Flow Pro- blem, A CM Trans. Math Software, 6, 1(1980), 1-16 I 4]Elmaghraby, S. E, Activity Networks: Project Planning and Control by Network Models, John Wiley &c sons, New York, 1977. 5] Gershwin, S. B. and Ammar, M., Reliability in Flexible Manufacturing Systems, Proc. 18th IEEE Conf. on Decision Control, Vol. 1, 1979, pp. 540-545 [6 Golden, B, Ball, M. and Bodin, L. Current and future Research Directions in Network Optimization Op8,Res.8,2(1981),71-81 [ 7] Kennington, J, A Survey of Linear Cost Multicommodity Network Flows, Ops. Res, 26, 2(1978), 209-236 I8 Lawler, E. L,, Combinatorial Optimization: Networks and Matroids, Holt Rinehart, and winston New York. 1976 [9]Meditch, J. S. and Mandojana, J. C, A Decentralized Algorithm for Optimal Routing in Data- communication Network, Proc. 18th IEEE Conf. on Decision Control. Vol 1, 1979, pp 134 40 10] Moder, J. J. and Elmaghraby, S. E(Eds ) Handbook fo Operations Research, Van Nostrand rein hold. New York. 1978 [11] Moore, L. J, and Clayton, E. R, GERT Modeling and Simulation: Fundamentals and Applications Petrocelli-Charter. New York, 1976. 12| Nawathe, S. P. and rao, B. V, Maximum Flow in Probabilistic Communication Networks, Int J Circuit Theory applications, 8, 2( 1980), 167-177. [ 13] Noetzel, A. S, Conditions for Product Form Network Solution Through the Analysis of Finite ith Overflows, Proc. 1978 Conf on Info Sci. Syst, Department of Electr. Eng, The Johi Hopkins Univ, Baltimore, Maryland, 1979, 482486 [14] Taylor Ill, B. W. and Moore, L J,, R&D Project Planning with Q-GERT Network Modeling and Simulation, Manag. Sci., 26, 1(1980), 44-59 151 Whitehouse, G. E, Systems Analysis and Design Using Network Techniques, Prentice-Hall, Engle wood CliES,N.J.1973 「16]人见胜人,笙产沙又厶工学,共立,东京,1975, 10

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐