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

Ill-conditional networks for network flow problems

作　　者：林浩[1] 林澜[2] LIN Hao;LIN Lan(School of Science,Henan University of Technology,Zhengzhou 450001,China;School of Electronics and Information Engineering,Tongji University,Shanghai 200092,China)

机构地区：[1]河南工业大学理学院,郑州450001 [2]同济大学电子与信息工程学院,上海200092

出　　处：《应用数学与计算数学学报》2018年第4期715-724,共10页Communication on Applied Mathematics and Computation

基　　金：国家自然科学基金资助项目(11571323;61373106)

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

关 键 词：网络最优化 最小费用流 最大流 病态网络 判定算法 

分 类 号：O221.7[理学—运筹学与控制论]