有供需要求运输问题的数学模型及算法

摘要

为满足不同用户对不同厂家、不同产品的数量要求,以运输总费用最小为目标,建立有供需要求运输问题的线性规划模型.将中转站顶点、用户顶点拆分后与厂家顶点、产品顶点分别关联,构建运输问题网络模型;推导出中转能力和直供能力一定条件下的中转站边和直供边容量约束方程;通过增设平行边,将容量有上下界约束的网络流问题转化为一般网络流问题;采用改进的最小费用最大流问题算法求出初始解.通过扩大直供边和中转站边的容量,使潜在的负回路显现,根据搜索的目的不同,有选择地切断部分直供边和配送边,从而在不同的范围内搜索负回路,并在负回路上调整流量,使初始解最终转化为最优解.通过算例分析,验证了模型和算法的可行性.