论文部分内容阅读
随机运输网络在现实生活中有着很多实际应用，而随机运输网络中供给能够满足需求，使得供给和需求能相互匹配，从而网络中存在一个可行流的概率更是被当作评定随机运输网络性能一个十分重要的指标。已有研究表明，随机运输网络中供给与需求相匹配从而存在可行流的充分必要条件是一些指数多个的不等式同时成立，而Prékopa和Boros(Prékopa A, Boros E.On the Existence of a Feasible Flow in a StochasticTransportation Network.Operations Research,1991，39(1):119-129.）则给出了现有估计存在可行流概率最好的方法，该方法分两部分来给出随机运输网络中存在可行流的概率的上界和下界。然而，在该方法的第一部分，可能遇到还剩余很多非冗余不等式的情况。在这种情况下，即使是对较小规模的网络，计算第二部分线性规划的数据输入也非常困难。 在本学位论文中，我们首先指出Prékopa和Boros文章中第一部分里面去除冗余不等式步骤中存在的某处错误，并给出正确的模型。基于新的模型，我们也给出新的数值计算结果。同时，基于Prékopa和Boros文章中第一部分的结果，我们还说明如何利用multitree和hypermultitree等超图结构来分别来提升随机运输网络中存在可行流概率的下界和上界。数值计算结果表明，基于超图的概率估计方法能够得到更好的估计效果。最后，我们给出一种基于空间分解的方法来计算概率的精确值。我们首先从一个需求状态空间中得到一个可行需求状态。在满足一定的条件下，我们可依据此可行需求状态把该状态空间分解成一些不相交的状态子空间，从而在该状态空间下存在可行流的概率即等于在这些子空间下存在可行流的概率的和。通过迭代分解，最终可得到整个状态空间下存在可行流的概率。基于Prékopa和Boros文章中的例子以及一个24点的Sioux-Falls例子的数值计算结果表明，我们的方法能够非常有效地得到精确概率。