煤矿应急物资储备运输问题的最优条件

最小费用流问题在网络流问题中增加了费用方面的指标,从而使网络流问题扩展到在费用、容量网络中求最佳的流量配置,使总流量达到预定值(或最大值)条件下总费用最低,这在现实生活中起着重要的作用。在求解最小费用流问题时,通过研究流分解性质、最短路问题的最优条件、对偶线性规划的互补松弛性等,给出三种不同但等价的最优条件:负圈最优条件、减少费用最优条件和互补松弛最优条件,由这三种最优条件分别给出三种对应的算法。将这三个算法分别应用于一个煤矿应急物资储备运输问题,说明三种最优条件在解决专项问题时可以根据实际情况选用构造最合适的算法求解问题。

Optimal Conditions of Coal Mines Emergency Reserve Transportation

The minimum cost flow problem adds the index of cost to expand the network flow problem to new field,where both of cost and capacity are researched,and both of fixed flow and minimum cost are desired.Thus,the minimum cost flow problem plays an important role in real life.When we solve this problem,nature of flow decomposition,optimality condition of shortest path problem and complementary slackness of dual linear programming will be researched.And,there are three different but equivalent optimal conditions,such as negative cycle optimality condition,reduced cost optimality condition and complementary slackness optimality condition.Also they can obtain three different but equivalent algorithms.At last,there is a case which is about coal mines emergency reserve transportation,and illuminates that how to use these optimality conditions after minimum cost flow problem reduction.In a word,the three optimality conditions can be used to build suitable algorithms to solve special problems according to the actual situation.