赋权有向图中最小生成树问题的显式整数规划模型

An Explicit Integer Programming Model of the Minimal Spanning Tree Problem for Digraphs

就具有不对称权重的有向图中的最小生成树问题，本文首次建立了相应的显式整数规划模型，这一模型可以成功地运用整数规划软件包如Ｌｉｎｄｏ等求解。并进一步将这一模型推广到随机最小生成树问题，也即具有随机变量权重的有向图中的最小生成树问题，并设计了相应的求解算法，给出了数值例示。

As far as the minimal spanning tree problem for the digraph with asymmetric weights is concerned,an explicit integer programming model is proposed,which could be solved successfully by using the integer programming packages such as Lindo.And furthermore this model is extended into the stochastic version,that is,the minimal spanning tree problem for the digraph with the weights is not constant but random variables.Several algorithms are also developed to solve the models.Finally,a numerical demonstration is given. [WT5”HZ〗