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

摘要

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