浅析露天矿运输最小费用流问题
2022-06-08
煤炭工业是国家工业的基础之一，煤炭是世界上储量最多、分布最广的燃料资源。煤矿是煤炭的主要原料基地.提高大型设备的利用率是增加露天矿经济效益、促进安全有效开采的重中之重。优化车辆安排数量及具体车次安排将直接导致矿山运营效率的提高.
一、运费优化模型的数学语言分析
在假设条件下的运输网络 中，除给出每条运输线路的容量外，还给出了单位流量的运输费用 ，最小费用流问题就是要找出一个可行流x，它使得总的费用最小，其数学语言描述为：
显然这是一个线性规划问题，满足约束条件的x称为一个可行流，使总费用
最小的可行流称为最小费用流：若b（x）最小且流量f（x）为最大的问题称为最小费用最大流问题。下配介绍求解这个问题的网络方法。
求解最小费用最大流问题的基本思想是：先找一个最小费用流x。若 ，则x就已经是最小费用最大流；若 ，则对x进行调整，使其流量最大，而保证新的流即是最小费用流，一旦调整到了最大流，则它自然就是最小费用最大流了。
由于总有所有 ，于是零流（ ）便可取为初始的最小费用流，那么如何将初始的最小费用流f（x）调整成取值更大的最小费用流 ？若 不是最大流，便找一条增广链 ，计算出调整量后就可在 上将f调整成取值为 的新可行流 。可知新的可行流费用为：
＼移项得
由此得，从x调整成 沿 增加单位流量所需的费用为
；简称 为 的费用。
二、由增广链角度对最小费用的进一步求解
设x是最小费用流，而 是关于x的所有增广链中费用 最小的一条，则在 上对x进行调整后所得到的新流任是最小费用流（调整方法同最大流算法中的一样）。
如何寻找费用最少的增广链？设 是是关于x的一条增广链 的费用
若把 中的路线反向，并令它的权是（- ），而 的煤运输线路不变，并且令它的权是 则改变后的 就是一条以 为始点， 为终点的路，该路的权恰好就是增广链的费用。这样把求最小费用增广链的费用。这样就把求最小费用增广链的问题转化成一个求从 到 的最短路问题。
根据最广链的定义。可以判别哪些弧可能在某条增广链 的 中，哪些弧可能在 中，对于给定的可行流x，有如下判断：
（1） 若 =0，则 只能 在中。
（2）若 ，则（ ）只能在 中。
（3）若0< ，则（ ）既能在 中，也可能在 中。
因此为了求网络G=（V，E）的最小费用最大流，构建网络G的辅助网络W=（V， ），网络W的点集与D的点集相同，弧集 的构成及 中每条弧上的权 ，按下述规划确定：
对于E中任意一条弧（ ），弧上括号内数字分别表示容量与费用，而在 中分别表示容量与权重。
若 =0，则 （ ） ，并令
若 ，则（ ） ，并令
在G求关于x的最小费用增广链，就等价于在 中求 到 的最短路。
三、数学模型向矿山输运模型的转化及其应用
假设一虚拟现实的露天矿运输系统，网络的最小费用最大流均已知，在图中每条弧旁的数是
网络 从 到 的最短路，调整流量再根据得到的可行流构建网络 ，依前述规划，重复调整流量、构建辅助网络。由于辅助 中不存在从 到 的最短路，所以 已是最小费用最大流，弧旁数字加圈表示该弧为饱和弧。在 中有两条最短路，选取一条使调整量较大。
以上步骤即为对露天矿运输系统的数学理论分析及具体的应用步骤和实例，虽然实例中的相关数据是依据计算的简洁性而人为设定的，不可避免的与实际生产发生偏差，但是方法的应用仍具有重要的理论意义.小
参考文献
[1]王俊，刘淼.神经网络在露天矿运输系统中的应用.中国科技在线，2010.
[2]刘光伟，姜箭.基于遗传算法的神经网络在露天矿卡车调度系统优化中的应用研究.中国科技论文在线，2007.
[3] 北京科技大学；首钢矿业公司"大型 深凹露天矿高效运输系统及强化开采技术研究”， 2004
一、运费优化模型的数学语言分析
在假设条件下的运输网络 中，除给出每条运输线路的容量外，还给出了单位流量的运输费用 ，最小费用流问题就是要找出一个可行流x，它使得总的费用最小，其数学语言描述为：
显然这是一个线性规划问题，满足约束条件的x称为一个可行流，使总费用
最小的可行流称为最小费用流：若b（x）最小且流量f（x）为最大的问题称为最小费用最大流问题。下配介绍求解这个问题的网络方法。
求解最小费用最大流问题的基本思想是：先找一个最小费用流x。若 ，则x就已经是最小费用最大流；若 ，则对x进行调整，使其流量最大，而保证新的流即是最小费用流，一旦调整到了最大流，则它自然就是最小费用最大流了。
由于总有所有 ，于是零流（ ）便可取为初始的最小费用流，那么如何将初始的最小费用流f（x）调整成取值更大的最小费用流 ？若 不是最大流，便找一条增广链 ，计算出调整量后就可在 上将f调整成取值为 的新可行流 。可知新的可行流费用为：
＼移项得
由此得，从x调整成 沿 增加单位流量所需的费用为
；简称 为 的费用。
二、由增广链角度对最小费用的进一步求解
设x是最小费用流，而 是关于x的所有增广链中费用 最小的一条，则在 上对x进行调整后所得到的新流任是最小费用流（调整方法同最大流算法中的一样）。
如何寻找费用最少的增广链？设 是是关于x的一条增广链 的费用
若把 中的路线反向，并令它的权是（- ），而 的煤运输线路不变，并且令它的权是 则改变后的 就是一条以 为始点， 为终点的路，该路的权恰好就是增广链的费用。这样把求最小费用增广链的费用。这样就把求最小费用增广链的问题转化成一个求从 到 的最短路问题。
根据最广链的定义。可以判别哪些弧可能在某条增广链 的 中，哪些弧可能在 中，对于给定的可行流x，有如下判断：
（1） 若 =0，则 只能 在中。
（2）若 ，则（ ）只能在 中。
（3）若0< ，则（ ）既能在 中，也可能在 中。
因此为了求网络G=（V，E）的最小费用最大流，构建网络G的辅助网络W=（V， ），网络W的点集与D的点集相同，弧集 的构成及 中每条弧上的权 ，按下述规划确定：
对于E中任意一条弧（ ），弧上括号内数字分别表示容量与费用，而在 中分别表示容量与权重。
若 =0，则 （ ） ，并令
若 ，则（ ） ，并令
在G求关于x的最小费用增广链，就等价于在 中求 到 的最短路。
三、数学模型向矿山输运模型的转化及其应用
假设一虚拟现实的露天矿运输系统，网络的最小费用最大流均已知，在图中每条弧旁的数是
网络 从 到 的最短路，调整流量再根据得到的可行流构建网络 ，依前述规划，重复调整流量、构建辅助网络。由于辅助 中不存在从 到 的最短路，所以 已是最小费用最大流，弧旁数字加圈表示该弧为饱和弧。在 中有两条最短路，选取一条使调整量较大。
以上步骤即为对露天矿运输系统的数学理论分析及具体的应用步骤和实例，虽然实例中的相关数据是依据计算的简洁性而人为设定的，不可避免的与实际生产发生偏差，但是方法的应用仍具有重要的理论意义.小
参考文献
[1]王俊，刘淼.神经网络在露天矿运输系统中的应用.中国科技在线，2010.
[2]刘光伟，姜箭.基于遗传算法的神经网络在露天矿卡车调度系统优化中的应用研究.中国科技论文在线，2007.
[3] 北京科技大学；首钢矿业公司"大型 深凹露天矿高效运输系统及强化开采技术研究”， 2004