数学建模论文集 最小费用流算法在运输问题中的应用.pdf

最小费用流算法在运输问题中的应用 摘要 本文主要是引用运筹学中的一个算法——最小费用流算法来解决运输问题 的。由于该企业的产销是平衡的，于是我们可先写出运输问题的线性规划形式， 接着根据最小费用流算法的需要，把此线性规划问题的对偶规划写出来，再由题 意写出相对应的松紧条件，根据线性规划的对偶理论，如果{xij }是原始规划的 一个可行解并且它与对偶规划的一组解{u ， }一起满足松紧条件，那么只要调 v i j 整对偶解，使其逐步达到可行，则它们就分别达到最优。 我们可依据上述过程，先任给原始规划一个可行解 ，然后对于原始规 { }x ij 划的可行解 ，计算出对偶规划的一个解 ，再利用计算公式 { }x { , u }v ij i j wij wij u i −v j − 计算出在对偶规划的解解出的条件下的检验数，判断所 有检验数的正负性，若所有检验数都是非负的，则这时得到的{ }和 就 {x , u }v ij i j 分别为原始规划和对偶规划的最优解，运输所需的最小费用也就相应解出。若并 非所有的检验数都是非负的，则需调整原始可行解，具体方法为：令 min{ | wst 0}wij wij i j , 即选择x 进入基。对应于网络中，即在支撑树上加入弧 ，从而得到一 st ( ,s)t θ θ 个回路。并选择其流量 x st θ ，使这个回路上