民营企业物流运输的最优化问题

CHANGZHOU INSTITUTE OF TECHNOLOGY

毕 业 论 文

题目：民营企业物流运输的最优化问题

二级学院（直属学部）： 理 学 院 专业： 数学与应用数学 班级： 08 数 学 学生姓名： 万冬琴 学号： 08090123 指导教师姓名： 陈 荣 军 职称： 副 教 授 评阅教师姓名： 高 枫 职称： 副 教 授

2012 年 6 月

摘要

面对金融危机，民营企业要在市场竞争中立足，就需要采取应对措施，降低企业生产成本、仓储成本、运输成本等来提高企业利润。本文首先阐述了目前物流系统中的运输现状以及存在的问题。第一部分主要介绍了选题的背景及意义，讲述了本文所用的方法，最小费用流的定义以及关于该方法的国内外研究动态，并且对本文的研究意义加以阐述。第二部分是在基于引言的基础上，对本文所研究的行业进行归纳总结，提出运输方面的问题，并根据某企业具体问题分析。第三部分建立最小费用流的数学模型，使用EXCEL、LINGO软件对模型求解，最后进行灵敏度分析。第四部分是对第二、第三部分进行总结得到关于最小费用流的结论。

关键词：运输成本控制 最大流 最小费用流 灵敏度分析

Optimization problem of the private enterprise logistics and

transport

Abstract

The face of financial crisis, private enterprises should be based on competition in market; you need to take response measures to reduce production costs, warehousing costs, transportation costs to improve profitability. This article first describes the current transport situation in the logistics system and the existence of the problem. The first part introduces the background and significance of the topics about the methods used in this article, the definition of the minimum cost flow and dynamic of the method at home and abroad, and to elaborate on the significance of this article. The second part, the conditions based on the foundation of the industries studied in this article summarizes the proposed transportation issues, and according to an enterprise specific problem analysis．The second part is in the Introduction, based on the basis of the industries studied in this paper summarizes the proposed transportation issues , and analysis based on a company specific issues ．The third part of the establishment of minimum cost flow mathematical model , using EXCEL , the LINGO software to solve the model , and finally carry out a sensitivity analysis ．The fourth part is the summary conclusions about the minimum cost flow of the second and third part.

Key words：transportation cost control maximum flow minimum cost flow problem

目 录

引言 .............................................................. 1

一、选题背景及意义 .................................................. 2

（一）最小费用流的介绍 ............................................. 2

（二）国内外研究动态 ............................................... 2

（三）本文的研究意义 ............................................... 4

二、问题的描述 ...................................................... 5

（一）问题的提出 ................................................... 5

（二）分析问题 ..................................................... 6

三、问题的求解 ...................................................... 7

（一）最小费用流的数学模型 ......................................... 7

（二）求出此网络系统的最大流量F ................................... 7

（三）求出此网络系统的最小费用 .................................... 11

（四）灵敏度分析 .................................................. 13

四、结论 ........................................................... 17

引言

随着中国经济的发展，民营企业在国民经济中发挥着越来越大的作用，但这些企业大部分是非高科技企业，利润微薄，且很多为进出口企业，金融危机来袭，对这些企业造成重大影响。在这种情况下，民营企业主如何有效的控制成本显得尤其重要。现在我国大多数中小企业的成本控制观念都很落后，企业主们认为单纯的通过提高产量就能降低成本，但在金融危机的情况下，还一味地提高产量必然导致产品积压严重亏损。而且传统的成本控制通常只注重对生产成本的控制，但是却忽略了对其他成本的控制，比如说管理成本、仓储成本、营销成本和物流运输成本。

运输是物流系统中的核心功能，是物品借助于运力在空间上所发生的位置转移。具体地讲，运输是使用运输工具对物品进行运送，以实现物流的空间效用。民营企业在运输过程中往往考虑物品转移和物品存储两大问题。运输利用的是时间资源、财务资源和环境资源，只有当运输确实提高了物品价值时，这种物品转移才是有效的。运输过程利用的时间资源是各种供应链管理方法，如准时制和快速响应等方法所要考虑的一个重要因素。运输过程中要使用的财务资源是指自营车队所必须的开支，或者商业或公共运输所需的开支。运输直接或间接地使用各种环境资源，直接如能源，间接如运输造成拥挤、空气污染等等。运输的主要目的就是以最少的时间、财务和环境资源成本，将物品从供应地转移到需要的地点。此外，物品的损失成本也必须最低。

然而，如果在转移中的物品需要短时间存储，又将重新转移，这种储存就是必要的。因为将物品卸下来再装上去的成本可能会超过储存在运输工具上的成本。在准时制生产、敏捷制造等供应链管理方法中，可以利用运输的这种临时储存物品功能。例如为了节约生产时间，可将运输原材料直接转移到生产车间而不用进入仓库，当然这需要高效的运输系统或者物流系统作后盾。

为了降低运输成本，可以进行合理的运输网络优化，减少不必要的运输环节，选择最佳运输手段。因为运输路线的选择问题种类繁多，大致分为：起点和终点不同的单一路线选择；多个起点和终点的路线选择；起点和终点相同的路线选择。在具体解决路线优化问题上可选用组合优化和图论。

一、选题背景及意义

（一）最小费用流的介绍

最小费用流问题也叫最小费用最大流问题，是最为基本的网络流模型，传统的最小费用流问题它是指在一个给定的网络中求一个从发点到收点的流值为某一给定常数的流，使其费用最小。在这个网络中，每条弧的容量是固定不变的，流不能在中间点停留。这个问题的约束条件都是静止的，也叫静态最小费用流问题，已经有了单纯形解法[1]、原始对偶算法[2]等有效算法。最小费用流模型有着极为广泛的应用，例如将货物从加工工厂发送到仓库，或从仓库发送给零售商，在生产线上把原材料或中间产品制造出最终产品；电话系统中的电话线路的安排问题；以及一些看起来并不那么“直接”的应用等。

最小费用流问题是图论领域中的一个重要问题，是网络优化中的核心问题，在实际生活中的许多问题，诸如最短路问题、最大流问题、运输问题、指派问题等，都是最小费用流问题的特例，或者说都可以转化为最小费用流问题。迄今为止，最小费用流问题在许多生产实际中都有极强的应用背景，尤其与近年的物流管理、供应链研究等领域有比较密切的关系，并在通讯等其它许多领域有着十分广泛的应用。因次，最小费用流问题具有很大的研究价值。

（二）国内外研究动态

最小费用流是最为基本的网络流模型，因此对于该模型的研究已有丰富的成果。求解最小费用流的第一个多项式时间的算法是Edmonds和Karp[3]于1972年提出的，此后相继有多项式时间的算法提出。Tardos[4]求解最小费用流的第一个强多项式时间算法，紧接着有许多强多项式时间算法。第一个多项式时间的(原始)网络单纯形算法是由Orlin[5]于1997年给出的。另外，二十世纪80年代中期，许多研究者开始用内点法来求解一些网络流问题，包括最小费用流问题。对于广义最小费用流问题，目前己有不少多项式时间算法，但目前还没有求解此问题的强多项式时间算法。

现实生活中很多计划(Planning)问题都可以转化成最小费用流问题[6]。然而，实践中有很多跟网络有关的问题包含一些额外的线性约束条件，这些约束条件破

坏了问题系数矩阵的网络结构。对于这种带有嵌入网络(embedded network)的网络流问题，由于其本身是特殊的线性规划问题，因此可以用求解一般线性规划的方法得以解决。但是，当额外约束的个数不是很多时，问题仍具有一定的网络结构。若算法能充分利用问题的网络结构，则求解问题的效率会大大提高，目前己有不少这方面的研究。另外，还可用拉格朗日松弛法求解该类问题，对于一些特殊问题，这种方法是成功的，但是收敛速度却较慢。Cohen和Megiddon[7]对几类带额外约束的网络流问题的算法及其复杂性进行了分析，其研究结果表明，这些问题中的任何一个若存在强多项式时间算法，则意味着一般线性规划问题存在强多项式时间算法，并证明当额外约束的个数为一固定的数时，问题存在强多项式时间算法。

LR Ford 和 DR Fulkerson[8]提出了关于最小费用流问题求解方法Ford和Fulkerson迭加算法，其基本思路：把各条弧上单位流量的费用看成某种长度，用求解最短路问题的方法确定一条自v1至vn的最短路；在将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。X Cai[9]提出了随时间变化的一般最大流问题，并且用拟多项式算法对其求解。Jianzhong Zhang[10]提出了一个解决一般LP问题的方法，此方法基于LP问题的最优性条件，并且把最小费用流问题反问题作为这种方法的一个特例，通过一系列线性规划转换，把最小费用流问题反问题转换为最小费用循环流(minimum cost circulation)问题，得到了强多项式算法。

Ahuja和Orlin[11]的相关研究比较能够系统得到最小费用流的结果，结果显示L1模下的最小费用流问题反问题，在单位权重下可以转换为单位容量的最小费用流问题求解，在非单位权重下可以转换为最小费用流问题求解；L∞模下的最小费用流问题反问题，在单位权重下可以转换为最小平均圈问题求解，在非单位权重下可以转换为最小费用与时间比例圈问题求解。

Ahuja[12]等又用组合优化的方法，将L1模下的单位权重的最小费用流问题反问题转换为单位容量循环流问题(unit capacity circulation problem)，解单位容量循环流问题的最好算法的复杂性为O(m(m+nlogn))；L∞模下的单位权重的最小费用流问题反问题转换为最小平均圈问题。解最小平均圈问题的最好算法的复杂性为O(nm)；将L∞模下的赋权最小费用流问题反问题转换为最小费用与时间比例圈问

题，解最小费用与时间比例圈问题的最好算法的复杂性为O(n4logn)。

谢政和汤泽滢[13]首次提出了带模糊约束的最小费用流问题，建立了相应的数学模型并给出了求解这一模型的有关算法。文献提出并讨论了最小费用流的反问题：如何在有限的投资条件下，最有效地扩充容量参数，达到一个预定的流值，建立了反问题的数学模型，给出了最优参数配置的算法。在可扩充建弧的容量上限固定的情况下，以最大上限时的单位费用流作为扩充弧的单位费用，提供一个算法。

（三）本文的研究意义

近几十年，组合优化和图论，广义上来讲作为组合数学的完整研究领域，经历了飞速的发展[14]。网络理论是图论与数学规划相结合的产物，近二十年来发展十分迅速，应用也非常广泛。例如在生产--分配系统、交通运输系统、通讯系统、财贸系统、军事后勤系统、管道网络系统和电网系统中都得到了很好的应用，因此对它的研究有非常重要的意义[15]。

线性规划[16]的一类重要应用是网络最优化问题(或称网络规划)，网络流在生产和社会实践中有着广泛的应用，是组合优化及图论中被广泛研究的问题领域之一，横跨多个学科的研究，包括应用数学、计算机科学、工程学、管理学以及运筹学等等。最小费用流是最为基本的网络流模型，它是指在一个给定的网络中求一个从发点到收点的流值为某一给定常数的流，使其费用最小。

例如在一些实际系统模型利用网络规划时，有时因实际条件的变化，需要对网络进行调整，如：交通运输网有时需对一些路线或站点进行调整，油品输送网需要解决调线问题，等等。这些改变都有可能使整个网络规划的最优方案发生改变，如果对改变后的网络重新计算，就会造成时间、物力、财力的浪费。因此，希望在原网络最优方案的基础上进行调整以求到改变后的网络的最优方案。

有时一些数据并不是很精确的，有可能进行修改，也有可能增加(或减少)新的变量或新的约束条比如有时需要对一些边进行调整，以满足决策的要求，一些边的特性进行调整后，整个网络规划的最小费用流可能发生变化，因而就有可能涉及整个规划方案的修改，对于一些大型的交互式图上作业就不合适，我们希望在一个尽可能小的范围内，利用原有信息进行适当修正。这些调整是否对原网络

最优方案有影响，如果产生影响，变化后的最优方案又是什么，对这些问题的研究被称为灵敏度分析。

另外由于在一些实际的最小费用流问题中，如在拥挤的运输网络中，车辆运行时间是时间变量，即其运行所需要的时间可能与运输所处的时段有关。所以，在求解最小费用的过程中，还需要考虑时间因素对于目标值的影响，我们将这样的最小费用问题称作动态最小费用流问题。由于在实际生活中，运输费用、运输能力等参数都与时间有关，随着时间的变化而变化，我们不得不考虑时间对这些因素的影响，因此对动态最小费用流的研究将有重要意义和应用价值。

二、问题的描述

（一）问题的提出

现今国内民营企业都或多或少的存在成本效益问题，比如某盐业企业，它有一个运输路线网络如图，使用这个网络图可以将盐从生产v1地运到销售地v6。因为每条运输路线不同，除了有不同的流量cij限制除外，还有不同的单位流量的费用bij。每条路线旁的括号内数值的意义为(cij, bij)。问：若使用网络系统，从采地到销地运送盐，怎样运送才能运送最多的盐并使得总的运送费用最小？(容量单位为千吨)

图1 某企业运输网络流

该企业在物流运输过程中，单位流的费用如下表(单位百元)：

表1 企业的单位费用

v1v 2v10 0

0 v216 0 0 0 0 v3 17 12 0 0 0 v40 13 7 0 15 v50 0 15 0 0 v6 0 0 0 10 8 合计 33 25 22 10 23 v3 v 4v5

（二）分析问题

最小费用流的基本概念如下：

1.最小费用流问题的构成（网络表示）[17]

①节点：包括供应点，需求点和转运点；

②弧：可行的运输路线(节点i →节点j)；

③弧容量：有最大流量（容量）限制。

2．最小费用流问题的假设

① 至少一个供应点；

② 至少一个需求点；

③ 其余均为转运点；

④ 通过弧的流只允许沿箭头方向流动，通过弧的最大流量取决于该弧的容量；

⑤ 网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点；

⑥ 在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比； ⑦ 最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小（或总利润最大）

3.最小费用流问题的解的特征[18]

① 具有可行解的特征：当且仅当供应点所提供的流量总和等于需求点所需的流量总和时（即平衡条件），最小费用流问题有可行解。

② 具有整数解的特征：只有其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流的问题的可行解就一定有所有流量都是整数的最优解（与运输问题和指派问题的解一样）；因此，没有必要加上所有变量都是整数的约束条件。

与运输问题一样，在配送网络中，由于运送量（流量）经常以卡车、集装箱为单位，若在运输过程中，不能满载就会导致经济效益降低。整数解就避免了配送方案为小数的麻烦。

三、问题的求解

（一）最小费用流的数学模型

最小费用流问题的数学模型为[19]：

1. 决策变量。设fij为通过弧(节点i 节点j)的流量。

2. 目标是使通过网络供应的总成本最小。

3. 约束条件。

① 供应点：净流量（总流出减总流入）为正；

② 转运点：净流量为零；

③ 需求点：净流量为负；

④ 弧的流量fij受到弧的容量限制；0 fij cij。

（二）求出此网络系统的最大流量F

首先需要定义有向路径的概念[20]，一条有向路径就是要考虑路径的有向边的方向的路径。例如，考虑下图。这个有向图G有顶点集合V(G) v1,v2,v3,v5,v4,v6 和弧集A(G) v12,v23,v35,v54,v46 。注意，v23 A(G)但是v32 A(G)，相应地，v1 v2 v3 v5 v6是v1到v6得一条有向路径，但是v1 v2 v3 v4 v6不是v1到v6得一条有向路径，因为v32 A(G)。该图还有在每条有向边上标注的有向流流量。

图2 某企业运输网络流

通过寻找从v1到v6得一条有向路径开始，可以有若干选择，挑选路径v1 v2 v4 v6，观察到在这条路径上的最低流量有向边是v24，它的流量为

u24 2，因此，创建一个表示余下的流量，或者说是在2个单位的流沿路径v1 v2 v4 v6被剔除后的剩余流量的一个新图。所做的一切就是对于路径上的

每条有向边去掉剩余流量为2之后的流。这样改变的的结果如图所示，此刻我们从v1到v6得到了2各单位的流，这就完成了最大流算法的第一次迭代。

图3 第一次迭代后的最大流图例

现在准备第二次迭代，从上一次迭代得到的剩余图中寻找从v1到v6的一条有向路径。有向路径v1 v3 v5 v6是一种可能。在这个剩余图中，最小的有向边

流量u56 3，所有通过减去沿该路径所有这样的容量来创建另一个剩余图。在这次迭代中又从v1到v6剔除了3个单位的流，总的剔除的流为5个单位。结果展示在下图，从而结束了第二次迭代。

图4 第二次迭代后的最大流图例

类似的做第三次迭代。在上图剩余图中有最小流量为2个单位的流的有向路径v1 v3 v5 v4 v6。现在从v1到v6剔除了7个单位的流，得到下图

图5 第三次迭代后的最大流图例

此刻从v1到v6只有一条有向路径，即v1 v2 v3 v4 v6。因为u34 1。在剔除总数达到8个单位流。在有向路径的每条边的流量减去1后，得到下图所示

图6 最大流图例，最后的剩图

再从上图寻找从v1到v6有向路径，显然已经不存在这样的路径了，因此停止算法执行并断言在原来的图中，从v1到v6的最大流为8。尽管可以选择的路径有很多，但是不管怎样选择路径得到的最大流都是8。

下面建立模型求解：

设弧(vi,vj)上的流量为fij，则最大流问题的数学模型为

maxF f12 f13

(f23 f24) f12 0转运点v2 (f34 f35) (f13 f23) 0转运点v3

f46 (f24 f34) 0转运点v4 s..t f35 (f54 f56) 0转运点v5 fij cij容量限制 fij 0

在Excel中输入数据[19]，利用软件计算，过程如下：

本问题的决策变量用C4：H9（见附录1）中的单元格表示，它们是从各节点到其他节点的流量，也是流量在网络中各边上的分配量。例如单元格D4表示节点1流入节点2的流量，也是连接节点1与节点2的边上的流量。

计算各节点的总流入量，即所有流入该点的流量之和。用单元格C10表示节点1的总流入量，其计算公式如下：

=SUM(C4:C9)

将上述公式复制到单元格D10：H10，得到其他节点的总流入量。

计算各节点的总流出量，即该节点的所有流出量之和。用单元格I4表示节点1的总流出量，其计算公式如下：

=SUM(C4:H4)

将上述公式复制到单元格I5：I9，得到其他节点的总流入量。

计算各节点的净流出量，需要将I5：I9的总流出量写入单元格C11：H11。可以在单元格C11中输入：=I4。同理可得到C12：H12中的净流出量。（见附录）

用表格中的规划求解功能求出本问题的解，不管怎样选择路径得到的最大流都是8。

（三）求出此网络系统的最小费用

在最大流量F的所有解中，找出最小费用的解[21]。

仍然设弧(vi,vj)上的流量为fij，这时网络上的最大流量F已知道，只要在第

一步的约束条件上，加上发点的总流量必须等于F的约束条件：f12 f13 F，即得最小费用最大流问题的约束条件，其目标函数是求其流量的最小费用：minz fij bij。

最小费用最大流问题可以用整数规划模型求解[22]，根据题意可建立模型如下：

minz 16f12 17f13 13f24 12f23 7f34 15f35 15f54 8f56 10f46

f12 f13 8 (f23 f24) f12 0 (f13 f23) (f34 f35) 0 (f24 f34) f46 0 s..t f35 (f54 f56) 0 f13 4,f12 5,f23 2,f24 3,f34 1, f35 6,f54 2,f56 3,f46 7

为了方便计算，令：

f12=x1 ，f13=x2 ，f24=x3 ，f23=x4 ，f34=x5 ，f35=x6 ，f54=x7 ，f56=x8 ，f46=x9 minz 16x1 17x2 13x3 12x4 7x5 15x6 15x7 8x8 10x9

x1 x2 8 (x3 x4) x1 0 (x2 x4) (x5 x6) 0 (x3 x5) x9 0 s..t x5 (x7 x8) 0 x1 4,x2 5,x3 2,x4 3,x5 1, x6 6,x7 2,x8 3,x9 7

在LINGO中输入程序[22]：

min 16x1+17x2+13x3+12x4+7x5+15x6+15x7+8x8+10x9

s.t. x1+x2=8

x3+x4-x1=0

x2+x4-x5-x6=0

x3+x5-x9=0

x5-x7-x8=0

x1<=4 x2<=5 x3<=2 x4<=3 x5<=1

x6<=6 x7<=2 x8<=3 x9<=7

end

运行结果为：

Global optimal solution found.

Objective value: 281.0000

Infeasibilities: 0.000000

Total solver iterations: 0

Variable Value Reduced Cost X1 3.000000 0.000000

X2 5.000000 0.000000

X3 2.000000 0.000000

X4 1.000000 0.000000

X5 0.000000 0.000000

X6 6.000000 0.000000

X7 0.000000 17.00000

X8 0.000000 10.00000

X9 2.000000 0.000000

Row Slack or Surplus Dual Price 1 281.0000 -1.000000

2 0.000000 -43.00000

3 0.000000 -27.00000

4 0.000000 15.00000

5 0.000000 10.00000

6 0.000000 -2.000000

7 1.000000 0.000000

8 0.000000 11.00000

9 0.000000 4.000000

10 2.000000 0.000000

11 1.000000 0.000000

12 0.000000 0.000000

13 2.000000 0.000000

14 3.000000 0.000000

15 5.000000 0.000000

运行结果显示：z=281

x1= x2=5 x3=2 x4= x5=0

x6=6 x7=0 x8=0 x9=2.

（四）灵敏度分析

灵敏度分析(Sensitivity Analysis)[23]，就是分析LP模型各参数aij,bij,cj 的取值变化对最优解或最优基的影响，它在应用线性规划解决实际问题的过程中非常有用。因为在一些实际系统模型利用网络规划时，有时因实际条件的变化，需要对网络进行调整，如：交通运输网有时需对一些路线或者站点进行调整；油品输送网需要解决调线问题等等。这些改变都可能使整个网络规划的最优方案发生改变，如果对改变后的网络重新计算，就会造成时间、物力、财力的浪费。因此，希望在原网络最优方案的基础上进行调整以求到改变后的网络的最优方案，即讨论网络最小费用流灵敏度问题。有时一些数据并不是精确的，有可能进行修改，也可能增加(或减少)新的变量或者新的约束条件，比如有时需要对一些边进行调整，以满足决策的要求，一些边的特性进行调整后，整个网络规划的最小费用流可能发生变化，因而就有可能涉及整个规划方案的修改。对于一些大型的交互式图上作业就不适合，我们希望在一个尽可能小的范围内，利用原有信息进行适当修正。这些调整是否对原网络最优方案有影响，如果产生影响，变化后的最优方案又是什么，对这些问题的研究被称为灵敏度分析。

线性规划的灵敏度分析通常有两类问题：一是当c、b 、a（c为价值系数，b为资源系数，a为系数矩阵）中某部分数据发生给定的变化时，讨论最优解和最优值如何变化；二是分析c、b、a中数据在大范围内波动，原最优基仍保持不变，同时最优解和最优值如何变化。

引用上文中对最小费用流问题的模型表述：

minz fijbij

f12 f13 8 (f23 f24) f12 0 (f13 f23) (f34 f35) 0 (f24 f34) f46 0s..t f35 (f54 f56) 0 f13 4,f12 5,f23 2,f24 3,f34 1, f35 6,f54 2,f56 3,f46 7

考虑对弧vioj0上的费用系数bioj0发生变化，变化后的大小为bi ，变化大小用oj0

b=bi —bioj0表示。下面分情况讨论弧上费用系数的变化对最优解的影响： oj0

(1) 当 b 0时，此时分两种情况：

①原来经过弧(i0,j0)的最小费用不变

因为最小费用流经过弧(i0,j0)，所以xioj0 0，又因为bi bioj0，所以弧(i0,j0)的oj0

费用系数改变后此问题的总费用为

y fijbij fioj0bi fijbij fioj0bioj0 y oj0

所以这种情况最小费用流不会改变。

②原来不经过弧(i0,j0)的最小费用可能发生改变。

此情况下若要维持原最小费用流不变，只需在弧(i0,j0)上的费用系数bioj0改变后保持其检验数 i 此时需要考虑i0和j0的每一个邻节点，看他们直接按的弧是属于 0即可。0j0

基变量还是非基变量，可以用简单圈的做如下分析：

图7 中实线代表基变量，虚线代表非基变量

图中，由联圈法可得弧(i0,j0)的检验数为 i bi bjok biok。要维持最0j0oj0

小费用流不变，只需使得 bi bjok biok 0即可。所以，bi bjok biok，即oj0oj0

bioj0 b bjok biok，则 b bioj0 bjok biok i0j0。

因此，若要维持原最小费用流不变，只需 b i0j0即可。

(2) 当 b 0时，此时分两种情况：

① 原来经过弧(i0,j0)的最小费用流可能发生改变。

此时若要维持原最小费用流不变，只需在弧(i0,j0)上的费用系数bioj0改变后保持与

其在同一圈上的非变量检验系数 i 0即可。 0j0

由下图用联圈法可得弧(i0,j0)的检验数 j0k bjok bioj0 biok，因此只需使需使

得 bi bjok biok 0即可。所以，bi bjok biok，即bioj0 b bjok biok，oj0oj0

则 b bioj0 bjok biok i0j0。

图8 中实线代表基变量，虚线代表非基变量

因此，若要维持原最小费用流不变，只需 b i0j0即可。

由下图用联圈法可得弧(i0,j0)的检验数 j0k bjok biok bioj0，因此只需使需使

得 biok bjok bi 0即可。即bi bjok biok，所以，bjok b biok bioj0，则oj0oj0

b bioj0 bjok biok j0k。

图9 中实线代表基变量，虚线代表非基变量

因此，若要维持原最小费用流不变，只需 b i0j0即可。

② 原来不经过弧(i0,j0)的最小费用不变。与(1)中①的方法类似可得出。所以这种情况下最小费用流不会改变。

上诉分析给出了一个分析网络中各边费用系数在一定范围内变化，不会影响原最小费用流问题最优解变化的一个算法。另外，最小费用流其他几个方面的灵敏度分析也可以进一步讨论，例如，去掉网络中的一条弧，添加一条弧，转移一条弧，去掉一个节点，修改一条弧上的容量等。下面根据本文例题修改其中一条弧的容量，所引起的最小费用流的变化。

图10 某企业运输网络流

则原来的最大流为9，路径有v1 v2 v3 v4 ，vv1 v2 v4 v6，v1 v3 v5 v4 v6，v1 v3 v5 v6。

原最小费用流在LINGO中运行结果为：

Global optimal solution found.

Objective value: 334.0000

Infeasibilities: 0.000000

Total solver iterations: 0

Variable Value Reduced Cost

X1 4.000000 0.000000

X2 5.000000 0.000000

X3 2.000000 0.000000

X4 2.000000 0.000000

X5 1.000000 0.000000

X6 6.000000 0.000000

X7 0.000000 7.000000

X8 1.000000 0.000000

X9 3.000000 0.000000

Row Slack or Surplus Dual Price

1 334.0000 -1.000000

2 0.000000 -53.00000

3 0.000000 -37.00000

4 0.000000 25.00000

5 0.000000 10.00000

6 0.000000 8.000000

7 0.000000 0.000000

8 0.000000 11.00000

9 0.000000 14.00000

10 1.000000 0.000000

11 0.000000 0.000000

12 0.000000 10.00000

13 2.000000 0.000000

14 2.000000 0.000000

15 4.000000 0.000000

四、结论

在一个运输网络流中，可以根据边容量、费用来确定最优的路线，使得企业获得低成本高效益。本文根据具体情况提出用最小费用流方法建立模型求解最优值，确定最大流路线，据以用来改善民营企业的成本效益。同时在文章的最后给出了灵敏度分析，成功地给出一个分析网络中各边费用系数在一定范围内变化，不会影响原最小费用流问题最优解变化的一个算法。当然，对于超出这个范围，最小费用流最优解将怎样变化，还有待进一步研究。

本文来源：https://www.bwwdw.com/article/nazm.html