网络流问题的病态网络分析

Ill-conditional networks for network flow problems

对供需运输系统中的网络流问题,由于供需约束或容量配置不合理,有时会出现一种反常现象:对一个最优运输方案来说,即使供需量或容量限制增加,多运了货物,运费反而下降.这种违背常理的现象反映出网络结构的失衡或畸形,迫使最优方案产生扭曲逆转,这种现象可称之为"病态".在运输问题的特殊情形(无容量约束的最小费用流问题),文献中已有过讨论,称为"运输问题悖论",对一般的网络流问题,研究三种类型的病态:供需约束、容量配置及结构上的病态,并给出判定条件和判别算法,最终引导到网络改造问题.

In a transportation system,due to the unsuitable distribution of sup-plies and demands,the network flow problem would cause a strange phenomenon:for an optimal transportation scheme,even the supplies and demands are increas-ing,more amounts of goods are transported,the transportation cost decreases instead.This unusual situation reflects the unbalanced and lopsided structure of the system,which twists the optimal scheme.This kind of structures may be called“ill-conditional”.In the case of transportation problem without capac-ity constraints,this strange phenomenon is called“the transportation paradox”,which has been discussed in the literature.In this paper,we investigate more ill-conditional structures in general network flow models and present corresponding recognition algorithms.This study will eventually lead to the area of the network improvement.