龙源期刊网 http://www.qikan.com.cn
最小费用最大流模型在运输网络优化中的应用
作者：郭京生 刘璘
来源：《现代商贸工业》2015年第17期
摘要：运用图论的相关理论知识，针对物流系统中运输网络的特点，以最大限度的提高运输效率，同时以节约运输总成本为目标，提出了解决运输网络优化问题的最小费用最大流网络模型，并利用matlab编程实现，为优化物流运输网络路线提供了一种可行方法。 关键词：运输网络；最小费用最大流；网络流量；matlab
中图分类号：F25文献标识码：A文章编号：16723198（2015）17005302 0引言
运输作为现代物流过程的主要职能之一，是物流各项业务的中心活动。同时，运输产生的费用也是供应链和整个物流系统成本结构的重要组成部分。可以说，一个高效率、低成本和高反应能力的运输网络对一个成功的物流配送体系至关重要，这就使得运输网络的优化成为配送体系中一项重要的运营决策，关系到物流设计体系的成功与否。运输网络的优化主要是对运输路线的安排，即选择合理的配送路线，既能保证配送效率的最大化，又能同时使运输成本最低。
图论是运筹学中一个重要的分支，是用来描述运输网络的数学理论基础。本文基于图论的相关理论知识，针对物流运输中最小费用最大流问题，建立了基于matlab的优化数学模型，以求最大限度的提高运输效率，同时节约运输费用。 1最小费用最大流模型 1.1网络流量基本概念及定义
为了实现对网络流量最大流值和最低成本的优化，首先需明确几个基本定义：
定义1：容量—费用网络。给定一个有向图D=V，A，对任意的弧vi，vj∈A，设lij，uij为弧的运输容量上下界函数，其中0≤lij≤uij，也称uij为弧的容量；cij是弧vi，vj上单位流量的费用，称之为费用函数；对任意的节点vi∈V，称avi为节点vi的供应量或需求量，称之为供需函数，且满足vi∈Va（vi）=0。由此得到的网络称为容量—费用网络。
定义2：可行流及其总费用。设fij是给定网络N上的由节点vi到节点vj的一个流量，且满足：
龙源期刊网 http://www.qikan.com.cn
f+（vi）-f-（vi）=f（vi） lij≤fij≤uij （1）
式中，f+vi=vj∈Vfij，f-vi=vj∈Vfji，分别称为流出和流入节点vi的流量，fvi为该节点的净输出量。
当满足式（1）时，则称f=fij为网络N 上的一个可行流，且可行流f的总费用为 c（f）=（vi，vj）∈Acijfij （2） 1.2最小费用问题概念及数学模型
最小费用问题是物流运输网络优化的核心问题，目标是在满足供应条件的前提下，寻求供应网络总成本最小的最优解。
根据上述定义，最小费用问题属于线性规划问题。其数学模型如下： min z=c（f）=（vi，vj）∈Acijfij （3） 约束条件为式（1）。
其中，目标函数是通过网络N供应的总成本最小。决策变量fij指通过弧vi，vj的流量。约束条件有供应点的净流量（总流出量减去总流入量）为正，所有需求点的净流量为负，对于所有中转点（中间点）的净流量为0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量为非负。
1.3最大流问题概念及数学模型
最大流问题也与网络中的流有关，但是其优化目标与最小费用流不同，最大流问题是寻求一个可行流的方案，使得通过网络的流量最大。
根据最大流问题的概念，最大流问题也属于线性规划问题。其数学模型如下： max z=fvs （4）
除满足约束条件式（1）外，还应满足式（5）： f+（vi）-f-（vi）=fvs，i=s（源） -fvs，i=t（汇）
龙源期刊网 http://www.qikan.com.cn
0，i≠s，t（中转点）（5）
其中，目标函数是通过供应点vs的净流出量f（vs）（或需求点vt的净流入量f（vt））最大，决策变量是通过各个弧的流量fij，约束条件有所有中转点的净流量为0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量为非负。 1.4最小费用最大流问题概念及数学模型
前面小节中介绍的“最小费用流问题”的目标是在完成规定任务的条件下，使得网络供应的总成本最小，即解决流量一定成本最小的路线安排问题。“最大流问题”的目标是寻求一个可行流的方案，使得通过供应网络的流量最大，即不考虑成本的情况下，解决单纯的流量最大的路线安排问题。但是实际情况往往比较复杂，不仅考虑流量还需要兼顾费用。例如，物流系统中一个运输网络，不仅要争取网络中货运量最大，还要力求使总费用最小，即解决更贴合实际的流量最大成本最低的路线安排问题，这就是“最小费用最大流问题”。
因此，我们可以把“最小费用最大流问题”看成是“最小费用流问题”和“最大流问题”的结合。求解该问题自然可以分为两步：首先，按照“最大流量问题”的求解方法找到网络可通过的最大流量；其次，在保证该最大流量的前提下找到成本最小的线路。
根据最小费用最大流问题的概念，最小费用最大流问题也属于线性规划问题。其数学模型如下：
min z=（i，j）∈Acijfij （6） s.t.f+（vi）-f-（vi）=fvs，i=s（源） -fvs，i=t（汇） 0，i≠s，t（中转点）
0≤lij≤fij≤uij（（i，j）∈A） （7） 2算例
基于上述分析，本文以某公司链接产地到销地的物流运输体系为例进行说明。其中，产品运输网络如下图1所示，图中各弧表示运输道路。由于道路实际地质情况不同，使得每条道路上的运输费用也不同，因此优化该运输系统除考虑货物的最大流外，还需要考虑道路运输的最小费用，即可基于本文所提的最小费用最大流模型予以求解。
图1某公司产品运输网络图1中弧上括号内的数字分别表示对应运输道路的容量限制和单位运费。
最小费用最大流模型在运输网络优化中的应用
