带有不确定损失的不确定网络最大流量的计算方法

摘要

本发明涉及一种带有不确定损失的不确定网络最大流量的计算方法，所述方法包括模型（1）、（2）和（3），并且包括n个节点和m条弧具有单源点和单汇点的网络，令c

说明书

技术领域

本发明涉及一种流量的计算方法，具体涉及一种不确定损失的不确定网络最 大流量的计算方法。

背景技术

众所周知，最大流问题起源于前苏联铁路系统^[1]。Ford和Fulkerson^[2]通过T.E. Harris提到了最大流问题：考虑通过一定数量的中间城市来连接两个城市的一个 铁路网络，在网络的每一个链都有一个数字代表它的通行能力（称为弧容量）。 假设在一个稳定的条件下，找到从一个城市到另一个城市的最大通行量。

最大流问题是一个经典的网络优化问题，并且已经广泛应用于各个领域，如 电力，交通，通讯系统，计算机网络和物流等。所以从理论和实践的角度来看研 究此问题是非常重要的。在过去的五十年，关于最大流问题涌现了许多高效的算 法^[3-9]。对于一个固定的网络，如果给定网络的弧容量，就可以计算出这个网络 的最大流。在经典的最大流问题中，我们不仅需要知道网络的弧容量，而且除了 源点和汇点外，其它任何中间点要满足守恒原则。然而，在实践中经常遇到的各 种各样的不确定性信息，处理实际问题时必须考虑这些不确定性信息。特别地， 在现实世界的网络中，我们不仅不知道每条弧的容量，而且网络中的某些节点的 流量也不守恒。这就意味着，网络中的一些节点流量丢失。有时我们不知道已丢 失了多少流量，这就使得传统的方法不能用于验证的最大流问题的性质。一些研 究人员认为这些属于随机性因素，他们使用概率论来研究这些不确定现象，如 Nawathe和Rao^[10]；同时，一些研究人员采用模糊理论来处理这件事^[11-14]。

然而，概率论的应用前提是我们获知的概率分布必须充分接近实际频率。不 幸的是，我们经常面对的问题恰恰缺乏观测数据，从而既无法计算事件发生的频 率也无法确定概率分布。在这种情况下，我们不得不依据专家的经验和知识估 计事件可能发生的信度。由于人们经常高估不太可能发生的事件，这使得信度的 方差远远大于频率。此时，如果把信度看成主观概率，则推导出的结果与我们的 预期大相径庭。为了研究主观不确定现象，不确定理论^[15-16]应运而生，不仅发展 成为公理化数学分支，而且取得了一系列成功的应用。这为我们把不确定理论引 入最大流问题的研究提供了一个动机，不确定理论为最大流问题的研究提供了一 种新方法。本文我们将基于不确定理论研究带有不确定损失的最大流问题。同时， 我们可以看到，不确定理论是处理这个问题的一个功能强大工具。

2.1不确定性理论

不确定理论是清华大学刘宝碇^[15]教授在2007年提出并于2010年由刘^[16]进行 了精炼修编,它为处理不确定因素提供了一种新的研究方法。如今它已成为基于 规范性、对偶性、次可加性及乘积测度公理系统的一个数学分支。到目前为止, 理论和实践都表明处理不确定信息,特别是处理经验数据和主观估计信息，不确 定性理论是一种非常有效的工具。

在这里我们简单介绍不确定理论在不同领域的主要发展情况。刘^[17]介绍了不 确定过程并且给出了不确定微分方程的定义，刘^[18]在2010年建立了不确定集理 论并提出了包含一种新推理规则的不确定推理。作为不确定理论的应用,刘^[19]在2009年提出了不确定规划即包含不确定变量的数学规划.高^[20]在2009年证明 连续不确定测度的一些性质。高^[21]等人在2010年讨论了刘的带有多个先行词 和有多个假设条件的推理规则。You^[22]给出了一些不确定序列的收敛定理。2011 年高^[23]研究了弧长不确定的最短路问题。基于不确定理论，一些重要的理论研究 如不确定分析^[24]，不确定微分方程^[25]，不确定逻辑^[26]，不确定性风险分析^[27]已 经建立。简而言之，不确定理论的研究与应用日益广泛，读者可以查阅文献[28]。

发明内容

现在,我们介绍一些本文所需要的不确定理论的概念和结果。

令Γ是一个非空集合，L是Γ上的σ-代数.任意元素Λ∈L称为一个事 件.若集函数满足下面三个公理（规范性、对偶性、次可列可加性）则被称 为不确定测度^[15]：

公理1.（规范性）M{Γ}=1.

公理2.（对偶性）对任意事件Λ，都有M{Λ}+M{Λ^c}=1.

公理3.（次可列可加性）对每个可数的事件序列{Λi}，都有

三元组(Γ,L,Μ)被称为一个不确定空间.不确定变量是指从不确定空间 (Γ,L,Μ)到实数集上的一个测度函数ξ.2009年刘^[24]定义了乘积不确定测度， 得到下面的公理4（乘积公理）：

公理4.（乘积公理）令是不确定空间，k=1，2，···，n.则乘积不 确定测度是乘积σ-代数上的不确定测度，满足

这里是中的任意闭事件，k=1，2，···，n.

如果对任意的实Borel集B₁,B₂,…,B_m，满足

$M\left\{\underset{i=1}{\overset{m}{\cap }}({\xi }_i\in B_i)\right\}=\underset{1\le i\le m}{\min }M\{{\xi }_i\in B_i\}$

则不确定变量ξ₁,ξ₂,…,ξ_m被称为是独立的。

定义1（刘^[15]）一个不确定变量ξ的不确定性分布Φ：R→[0，1]被定义的 变量为

注1不确定分布Φ（x）是一个递增函数。

定义2（刘^[15]），假如对任意的α∈（0，1），一个不确定分布Φ的逆函数φ^-1(α) 都存在且唯一，则称这个不确定分布Φ是正则的。

本文中，我们假设所有给定的不确定分布都是正则的。否则，我们可以给不 确定分布一个小的扰动，使得它变成为正则的。由一个不确定分布计算不确定度 度，刘^[16]提出了测度逆定理，即

一个实值函数f(x₁，x₂，…，x_n)是严格递增的，假如f满足以下条件

（1）如果x_i≤y_i，i＝1，2，…，n，则f(x₁，x₂，…，x_n)≤f(y₁，y₂，…，y_n)；

（2）如果x_i＜y_i，i＝1，2，…，n，则 f(x₁，x₂，…，x_n)＜f(y₁，y₂，…，y_n).

定义3（刘^[15]）令ξ是一个不确定变量。则ξ的期望值被定义为

假如这两个积分的中至少一个是有限的。

为了通过不确定逆分布计算期望值，刘^[16]证明了

$E\left[\xi \right]={\int }_0^1{\phi }^{-1}\left(\alpha \right)\mathrm{d\alpha }$

同时，对两个独立的不确定变量ξ，η和两个清晰的数字a,b，刘^[16]证明了 期望值运算的线性性质，即

E[aξ+bη]＝aE[ξ]+bE[η]。

带有不确定的损失最大流模型：

一般来说，一个确定性网络表示为N=（V，A），其中V={1，2，...，n} 有限的顶点集，而A＝{(i，j)|i，j∈V}是弧集。在本文中，我们假设n个节 点和m条弧网络具有单源点和单汇点。如图1所示，6节点和8条弧的网络，其 中节点1是源和节点6是汇。

令c_ij表示从节点i到节点j的弧容量，并用x_ij来表示节点i到节点j流量， u_i表示流在节点i损失的流量，i,j=1，2，...，n，s表示源节点和t是汇节点。 则带有损失的最大流问题可以归结如下：

$\left(\begin{array}{c}\max v\\ \mathrm{subjectto}:\\ \underset{j}{\Sigma }(x_{8j}-x_{j8})=v,\\ \underset{j}{\Sigma }(x_{\mathrm{tj}}-x_{\mathrm{jt}})=-v+\underset{i\ne 8,t}{\Sigma }{u}_i,\\ \underset{j}{\Sigma }(x_{\mathrm{ij}}-x_{\mathrm{ji}})\ge -u_i,i\in N,i\ne s,t,\\ 0\le x_{\mathrm{ij}}\le c_{\mathrm{ij}},(i,j)\in A\end{array}\right)---\left(1\right)$

在上述模型，需要的数量c_ij，u_i都假定是清晰准确的数字。但是，有时网 络计划需要预先制定，所以这些数量一般不是固定的，而是从专家经验评价或专 业知识中获得的。在这种情况下，我们可以假设的数量是不确定的变量。然后将 模型（1）仅仅是一个概念模型，而不是一个数学模型，因为在一个不确定的世 界中不存在一个本质规律。这里我们以期望值准则或置信水平作约束函数。则模 型（1）变成了下面的数学模型：

其中β_i，γ_ij是一些预定的置信水平，i≠s，t，(i，j)∈A.下定理表明，模型（2） 相当于一个确定的模型，求解此模型有许多高效的算法。

定理1假设c_ij，u_i是独立的不确定变量，其不确定分布分别为φ_ij，ψ_i.则模 型（2）相当于下面的模型：

$\left(\begin{array}{c}\max v\\ \mathrm{subjectto}:\\ \underset{j}{\Sigma }(x_{8j}-x_{j8})=v,\\ \underset{j}{\Sigma }(x_{\mathrm{tj}}-x_{\mathrm{jt}})=-v+\underset{i\ne 8,t}{\Sigma }{\int }_0^1{\phi }_i^{-1}\left(\alpha \right)\mathrm{d\alpha },\\ \underset{j}{\Sigma }(x_{\mathrm{ij}}-x_{\mathrm{ji}})\ge {\psi }_i^{-1}\left({\beta }_i\right),i\in N,i\ne s,t,\\ x_{\mathrm{ij}}\le {\phi }_{\mathrm{ij}}^{-1}(1-{\gamma }_{\mathrm{ij}}),(i,j)\in A\\ x_{\mathrm{ij}}\ge 0\end{array}\right)---\left(3\right)$

证明：从期望值算子的线性性质可得

$E\left[\underset{i\ne s,t}{\Sigma }{u}_i\right]=\underset{i\ne s,t}{\Sigma }E\left[u_i\right],$

其中u_i是独立的不确定变量，i∈N，i≠s，t.

因为

$E\left[u_i\right]={\int }_0^1{\phi }_i^{-1}\left(\alpha \right)\mathrm{d\alpha },$

可得

$E\left[\underset{i\ne s,t}{\Sigma }{u}_i\right]=\underset{i\ne s,t}{\Sigma }{\int }_0^1{\phi }_i^{-1}\left(\alpha \right)\mathrm{d\alpha }.$

因为u_i和c_ij具有不确定分布ψ_i和φ_ij，由测度逆定理可得

等价于

$\underset{j}{\Sigma }(x_{\mathrm{ij}}-x_{\mathrm{ji}})\ge {\psi }_i^{-1}\left({\beta }_i\right),i\in N,i\ne s,t,$

而

等价于

$x_{\mathrm{ij}}\le {\phi }_{\mathrm{ij}}^{-1}(1-{\gamma }_{\mathrm{ij}}),(i,j)\in A.$

因此，综上所述定理得证。

附图说明：

图1是6节点和8条弧的网络；

图2是实施例1中的网络G。

具体实施方式：

在本节中，我们将举一个例子，如何计算带有不确定损失的不确定网络的最 大流量。

实施例1：

假设G是有五条弧的向网络，如图2所示。

在不确定的环境中，我们假设第i节点损失的流量ξ_i是线性不确定变量，其 分布为φ_i，i＝2，3。

${\phi }_2\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<2,\\ (x-2)/2,& \mathrm{if}2\le x\le 4\\ 1,& \mathrm{ifx}>4.\end{array}\right)$

${\phi }_3\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<1\\ (x-1)/2,& \mathrm{if}1\le x\le 3\\ 1,& \mathrm{ifx}>3.\end{array}\right)$

我们假设(i，j)弧的容量是线性不确定变量η_ij其不确定分布为 ψ_ij，i≠j，i，j＝1，2，3，4，5，

${\psi }_{12}\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<8,\\ (x-8)/4,& \mathrm{if}8\le x\le 12\\ 1,& \mathrm{ifx}>12.\end{array}\right)$

${\psi }_{24}\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<5\\ (x-5)/4,& \mathrm{if}5\le x\le 9\\ 1,& \mathrm{ifx}>9.\end{array}\right)$

${\psi }_{23}\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<1,\\ (x-1)/4,& \mathrm{if}1\le x\le 5\\ 1,& \mathrm{ifx}>5.\end{array}\right)$

${\psi }_{13}\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<4,\\ (x-4)/4,& \mathrm{if}4\le x\le 8\\ 1,& \mathrm{ifx}>8.\end{array}\right)$

${\psi }_{34}\left(x\right)=\left(\begin{array}{cc}0,& \mathrm{ifx}<7,\\ (x-7)/4,& \mathrm{if}7\le x\le 11\\ 1,& \mathrm{ifx}>11.\end{array}\right)$

由定理1可得下面的等价模型（4）

注意，线性不确定变量L(a，b)的期望值是其逆不确定分布为

φ^-1(α)＝(1-α)a+αb.

则上述模型变成

$\left(\begin{array}{c}\max v\\ \mathrm{subjectto}:\\ \underset{j}{\Sigma }(x_{1j}-x_{j1})=v,\\ \underset{j}{\Sigma }(x_{4j}-x_{j4})=-v+5\\ \underset{j}{\Sigma }(x_{\mathrm{ij}}-x_{\mathrm{ji}})\ge (1-{\beta }_i)a_i+{\beta }_i{b}_i,i=2,3,\\ x_{\mathrm{ij}}\le {\gamma }_{\mathrm{ij}}{a}_{\mathrm{ij}}+(1-{\gamma }_{\mathrm{ij}})b_{\mathrm{ij}},(i,j)\in A\\ x_{\mathrm{ij}}\ge 0\end{array}\right)---\left(5\right)$

该模型是一个典型的线性规划问题，其可行域是一个多面凸集。假设的置信 水平是β_i＝0.5，γ_ij＝0.75.由单纯形法可得，图2所示的网络的最大流量是14。

结论：

本文基于不确定理论主要研究了一种新的最大流模型。它是以期望值或置信 水平为约束函数，然后将其转化确定性模型。最后给出了一个数值例子并用单纯 形法得到最优解。

参考文献：

[1]Billera L.J.,Lucas W.F.,Delbert Ray Fulkerson August14,1924-January10, 1976,Mathematics of Oper-ations Research1(1976)299--310.

[2]Ford L.R.,Fulkerson Jr.and D.R.,Flows in Networks,Princeton Univ.Press, Princeton,NJ,1962.

[3]Mazzoni G.,Pallottino S.,Scutellμa M.G.,The maximum flow problem:A max-preflow approach,European Journal of Operational Research, 53(3)(1991)57--278.

[4]Karzanov A.V.,Determining the maximum flow in a network by the method of  preflows,Soviet Mathematics Doklady,15(3)(1974)43--47.

[5]Takao A.,Yasuhito A.,Recent developments in maximum flow algorithms. Journal of the Operations Research Society of Japan,43(1)(2000)2--31.

[6]Ford L.R.,Fulkerson Jr.and D.R.,Maximal flow through a network,Canadian  Journal of Mathematics,3(3)(1956)399--404.

[7]Dinic E.A.,Algorithm for solution of a problem of maximum flow in networks  with power estimation,Soviet Mathematics Doklady,11(8)(1970)1277--1280.

[8]Malhotra V.M.,Pramodh Kumar M.,Maheshwari S.N.,An O(V³)algorithm for  finding maximum flows in networks,Information Processing Letters, 7(6)(1978)277--278.

[9]Tarjan R.E.,Algorithms for maximum network flow,Mathematical Programming  Studies,26(1986)1--11.

[10]Nawathe S.P.,Rao B.V.,Maximum flow in probabilistic communication  networks,International Journal of Circuit Theory and Applications,8(1980)167--177.

[11]Chanas S.,W.,Integer flows in network with fuzzy capacity  constraints,Networks,16(1996)17-31.

[12]Chanas S.,W.,Maximum flow in a network with fuzzy arc  capacities,Fuzzy Sets and Systems,8(2)(1982)165-173.

[13]James J.B.,Leonard J.J.,Fuzzy Max-Flow Problem,Studies in Fuzziness and  Soft Computing,222(2008)195-198.

[14]Tang Z.,Tang B.,The Maximum Flow Problem with Fuzzy Constraints,Fuzzy  systems and Mathematics,15(4)(2001)77-80.

[15]Liu B.,Uncertainty Theory,2nd ed.,Springer-Verlag,Berlin,2007.

[16]Liu B.,Uncertainty Theory:A Branch of Mathematics for Modeling Human  Uncertainty,Springer-Verlag,Berlin,2010.

[17]Liu B.,Fuzzy process,hybrid process and uncertain process,Journal of  Uncertain Systems,vol.2,no.1,3-16,2008.

[18]Liu B,Uncertain Set Theory and Uncertain Inference Rule with Application to  Uncertain Control,Journal of Uncertain Systems,Vol.4,No.2,83-98,2010.

[19]Liu B.,Theory and Practice of Uncertain Programming,2nd ed.,Springer-Verlag, Berlin,2009.

[20]Gao X.,Some properties of continuous uncertain measure,International Journal  of Uncertainty,Fuzziness and Knowledge-Based Systems,vol.17,no.3,419-426, 2009.

[21]Gao X.,Gao Y.and Ralescu D.,On Liu’s Inference Rule for Uncertain Systems, International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems, vol.18,no.1,1-11,2010.

[22]You C.,Some convergence theorems of uncertain sequences,Mathematical and  Computer Modelling,vol.49,no.3-4,482-487,2009.

[23]Gao Y.，Shortest Path Problem with Uncertain Arc Lengths,Computers and  Mathematics with Applications，Vol.62,No.6,2591-2600,2011.

[24]Liu B.,Some research problems in uncertainty theory,Journal of Uncertain  Systems,3(1)(2009)3-10.

[25]Chen X.,Liu B.,Existence and uniqueness theorem for uncertain differential  equations,Fuzzy Optimization and Decision Making,9(1)(2010)69-81.

[26]Li X.,Liu B.,Hybrid logic and uncertain logic,Journal of Uncertain  Systems,3(2)(2009)83-94.

[27]Liu B.,Uncertain risk analysis and uncertain reliability analysis,Journal of  Uncertain Systems,4(3)(2010)163-170.

[28]Liu B,Uncertainty Theory,4th ed.,http://orsc.edu.cn/liu/ut.pdf.