论文部分内容阅读
摘 要：运输问题的解决存在着多种的方法。本文主要介绍最小费用流理论在运输网络中的应用，通过建立最小费用流的运输网络模型，对运输网络进行了优化分析，从而得到了运输网络的优化算法，最后举例说明算法的运用。
关键词：运输网络;最小费用流;最优化;数学模型
前言
本文提出了典则型运输网络的概念，并在分析问题特性的基础上，通过构造典则型运输网络的办法，把运输问题转化为典则型运输网络中求最小费用流问题;再利用最小费用流的最短路算法将问题求解。
1基本概念和物资运输网络模型
1.1基本概念
1.1.1最小费用流问题的构成：
（1）节点：包括：
·供应点：节点产生的净流量（流出减去流入）是一个确定的正数。
·需求点：节點产生的净流量是一个确定的负数。
·转运点：节点产生的净流量恒为零。
（2）弧：网络中的带箭头的连线。
（3）容量：允许通过某一条弧的最大流量。
1.1.2最小费用流问题的假设：
（1）至少一个供应点一个需求点剩下都是转运点。
（2）通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量。
（3）网络中有足够的弧提供足够容量，使得所有在供点中产生的流都能够到达需求点。
（4）在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比。
1.1.3最小费用流问题解的特征：
（1）具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解。
（2）具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解。
1.2实际运输网络模型问题
1.2.1前提条件：
构造运输网络的目的是要使运输网络的整体费用最小。进行设计之前首先要收集如下一些信息：
（1）顾客、零售商、现有仓库、配送中心、制造机构和供应商的地理位置;
（2）所有产品，包括数量、特殊运输方式
（3）某区域范围内的顾客对于每一种商品的年需求量;
（4）每种运输方式的运输费率;
（5）各节点的库存成本以及数量函数;
（6）运输规模和配送频率;
（7）顾客服务需要和目标。
1.2.2原始实际问题：
铺设一条从站点A1到站点A15的电缆光纤电信网（见图1），选择了7个电缆光纤厂S1，S2，…，S7为网络主线电缆的货源地，已知电缆光纤的出厂价格和公路、铁路运输的费用情况，制订一个运输和采购方案，使总费用最小，同时分析货源地的价格和最大销售量的波动对最小总费用的影响.其中一个电缆厂如果承担制造这种钢管，至少需要生产500单位（为方便计，1km网络主线电缆称为1单位电缆光纤）。
2模型问题的分析与简化
整个铺设电缆光纤的工程看似错综复杂，如果用的运输量，运输单位管道所需的费用，则从电缆厂把电缆光纤运输到站点的运输费用为：
因此可简化第二步计算，把铁路与公路的混合运输费用转化为公路运输费用的SAP矩阵.求SAP矩阵的基本思路是图的最短路算法。
有关SAP矩阵的求解过程：（1）利用图的最短路算法，从铁路网络得出图中任意两个点之间的路径表T（如果两个点之间不连通，认为它们之间的最短路长度无限大）;（2）利用题中的铁路运价表将T中的每个元素（即最短距离）转化为运输费用，将运输费用记为C;（3）将公路长度换算为运输费用，由公路路程图得出公路费用图G，若不连通，则令为无限大;（4）对于任一组，如果较小，且小于，那么以铁路费用作为.利用图的标准最短路算法，求公路费用图中任一个S点到任一个A点的最小费用路径，得到SAP矩阵.如表1所列.
经过上述变换， 问题就大大简化了。 于是就可以建立以下的模型：
3问题的求解
基于分支定界搜索的求解过程：由于该问题给出的工厂产量范围不是一个区间，需要用分支界定搜索来求解。
下面以图1中的数据为例，分析分支界定搜索的求解过程：
1）将工厂产量的范围设定为，求得一个解;
2）费用为万元，生产方案为。由于第1节的解中第7个工厂的产量245属于，要将问题分解为两部分：范围1，解得费用为万元，生产方案为，这个方案是合理的，将其作为当前最优解;范围2，解得费用为万元，生产方案为费用大于当前最优解，舍弃当前节点。
所以最优解为：费用为万元，生产方案为。
4模型的扩展优化算法
4.1模型扩展
设想一般的运输网络的优化不如转化为典型的运输网络来优化。
定理1 任意运输网络都可化为与之等效的典则型运输网络。
证明：若运输网络不是典则型运输网络，则存在两个不同的顶点，使得弧都存在。在弧中增加一个虚顶点x，把弧变成两条弧，使得，。重复上述步骤，直到运输网络中任意两个不同顶点间最多存在一条弧为止，这时得到的网络就是典则型运输网络，并且它在运输功能上和N等效。
4.2算法
定理1的证明给出了任意运输网络化为与之等效的典则型运输网络的方法，根据理论依据直接给出优化的算法。因此，利用定理1和算法就能求任意运输网络的最小费用最大流。
5总结
通过将运输网络转换成最小费用流模型，利用优化了的算法求解最小费用，网络运输问题就变得相当简化和方便，还可以配合相应的编程语言对算法进行编译就可以在计算机上实现了。只是，要实现还必须解决关于编程和软件开发的其他方面很多的问题，比方数据库冗余，编程语言等，在这里就不作详细的分析了。
参考文献
[1]谢金星，邢文训，网络优化[M]，北京：清华大学出版社，2000.
[2]刘家壮，徐源，网络最优化[M]，北京：高等教育出版社，1991，191-245.
[3]李德，钱颂迪，运筹学[M]，清华大学出版社，1982，33-67。
关键词：运输网络;最小费用流;最优化;数学模型
前言
本文提出了典则型运输网络的概念，并在分析问题特性的基础上，通过构造典则型运输网络的办法，把运输问题转化为典则型运输网络中求最小费用流问题;再利用最小费用流的最短路算法将问题求解。
1基本概念和物资运输网络模型
1.1基本概念
1.1.1最小费用流问题的构成：
（1）节点：包括：
·供应点：节点产生的净流量（流出减去流入）是一个确定的正数。
·需求点：节點产生的净流量是一个确定的负数。
·转运点：节点产生的净流量恒为零。
（2）弧：网络中的带箭头的连线。
（3）容量：允许通过某一条弧的最大流量。
1.1.2最小费用流问题的假设：
（1）至少一个供应点一个需求点剩下都是转运点。
（2）通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量。
（3）网络中有足够的弧提供足够容量，使得所有在供点中产生的流都能够到达需求点。
（4）在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比。
1.1.3最小费用流问题解的特征：
（1）具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解。
（2）具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解。
1.2实际运输网络模型问题
1.2.1前提条件：
构造运输网络的目的是要使运输网络的整体费用最小。进行设计之前首先要收集如下一些信息：
（1）顾客、零售商、现有仓库、配送中心、制造机构和供应商的地理位置;
（2）所有产品，包括数量、特殊运输方式
（3）某区域范围内的顾客对于每一种商品的年需求量;
（4）每种运输方式的运输费率;
（5）各节点的库存成本以及数量函数;
（6）运输规模和配送频率;
（7）顾客服务需要和目标。
1.2.2原始实际问题：
铺设一条从站点A1到站点A15的电缆光纤电信网（见图1），选择了7个电缆光纤厂S1，S2，…，S7为网络主线电缆的货源地，已知电缆光纤的出厂价格和公路、铁路运输的费用情况，制订一个运输和采购方案，使总费用最小，同时分析货源地的价格和最大销售量的波动对最小总费用的影响.其中一个电缆厂如果承担制造这种钢管，至少需要生产500单位（为方便计，1km网络主线电缆称为1单位电缆光纤）。
2模型问题的分析与简化
整个铺设电缆光纤的工程看似错综复杂，如果用的运输量，运输单位管道所需的费用，则从电缆厂把电缆光纤运输到站点的运输费用为：
因此可简化第二步计算，把铁路与公路的混合运输费用转化为公路运输费用的SAP矩阵.求SAP矩阵的基本思路是图的最短路算法。
有关SAP矩阵的求解过程：（1）利用图的最短路算法，从铁路网络得出图中任意两个点之间的路径表T（如果两个点之间不连通，认为它们之间的最短路长度无限大）;（2）利用题中的铁路运价表将T中的每个元素（即最短距离）转化为运输费用，将运输费用记为C;（3）将公路长度换算为运输费用，由公路路程图得出公路费用图G，若不连通，则令为无限大;（4）对于任一组，如果较小，且小于，那么以铁路费用作为.利用图的标准最短路算法，求公路费用图中任一个S点到任一个A点的最小费用路径，得到SAP矩阵.如表1所列.
经过上述变换， 问题就大大简化了。 于是就可以建立以下的模型：
3问题的求解
基于分支定界搜索的求解过程：由于该问题给出的工厂产量范围不是一个区间，需要用分支界定搜索来求解。
下面以图1中的数据为例，分析分支界定搜索的求解过程：
1）将工厂产量的范围设定为，求得一个解;
2）费用为万元，生产方案为。由于第1节的解中第7个工厂的产量245属于，要将问题分解为两部分：范围1，解得费用为万元，生产方案为，这个方案是合理的，将其作为当前最优解;范围2，解得费用为万元，生产方案为费用大于当前最优解，舍弃当前节点。
所以最优解为：费用为万元，生产方案为。
4模型的扩展优化算法
4.1模型扩展
设想一般的运输网络的优化不如转化为典型的运输网络来优化。
定理1 任意运输网络都可化为与之等效的典则型运输网络。
证明：若运输网络不是典则型运输网络，则存在两个不同的顶点，使得弧都存在。在弧中增加一个虚顶点x，把弧变成两条弧，使得，。重复上述步骤，直到运输网络中任意两个不同顶点间最多存在一条弧为止，这时得到的网络就是典则型运输网络，并且它在运输功能上和N等效。
4.2算法
定理1的证明给出了任意运输网络化为与之等效的典则型运输网络的方法，根据理论依据直接给出优化的算法。因此，利用定理1和算法就能求任意运输网络的最小费用最大流。
5总结
通过将运输网络转换成最小费用流模型，利用优化了的算法求解最小费用，网络运输问题就变得相当简化和方便，还可以配合相应的编程语言对算法进行编译就可以在计算机上实现了。只是，要实现还必须解决关于编程和软件开发的其他方面很多的问题，比方数据库冗余，编程语言等，在这里就不作详细的分析了。
参考文献
[1]谢金星，邢文训，网络优化[M]，北京：清华大学出版社，2000.
[2]刘家壮，徐源，网络最优化[M]，北京：高等教育出版社，1991，191-245.
[3]李德，钱颂迪，运筹学[M]，清华大学出版社，1982，33-67。