运筹学最短路

附件2

《运筹学》最短路、最小费用最大流经典作品

关于钢管订购和运输的优化模型

队员：陈显健

陈瑜斌陈振松

2007

年6月5日

摘要：本文首先运用图论知识中的最短路算法求出Si到Aj的最优路径。然后将模型转化为最小费用最大流的网络优化问题，从而求出近似最优解。

在分析出求解该网络优化模型的解法后，运用Lingo软件包求出了该问题的近似最优解。对问题一而言，求出了较优的订购和运输计划（见表三），其最小费用为1291630万元。对于第二个问题而言，可得出钢厂S6的钢管销价的变化对购运计划和总费用的影响最大；钢管厂S1的钢管产量的上限的变化对总费用的影响最大，钢管厂S3的产量上限的变化对购运计划的影响最大。对问题三，给出了一般解，求出了较优的订购和运输计划（见表四），其最小费用为1396099万元，

最后对模型进行了综合评价并提出了改进方向。关键词：网络流最小费用最大流

一、问题重述

要铺设一条A1A2A15的输送天然气的主管道，如图一所示,经筛选后可以生产这种主管道的钢厂有S1,S2,,S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。

为了方便，1km主管道称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大生产数量为si个单位，钢厂出厂销价为pi万元，如下表：

表一

1单位钢管的铁路运价如下表：

（表二）

1000km以上每增加1至100km运价增加5万元。

公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。

管道可由铁路、公路运往铺设地点（不只是运到点A1A2A15，而是管道全线）。

要求：

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用。（2）请就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用

影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。

（3）如果要铺设的管道不是一条线，而是一个树形图。铁路、公路和管道购成网络，

请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出数学模型和结果。

二、基本假设

1．沿管道铺设路线上有公路，在计算运费时，与其它普通公路相同； 2．订购的钢管数量刚好等于需要铺设的钢管数量；

3．公路运输费用为1单位钢管每公里0.1万元（不足整公里的按整公里计算）； 4． 1km主管道钢管称为1单位钢管；

5．一个钢厂如果承担制造这种钢管，至少需要生产500个单位；

6． 1单位钢管的铁路运价如（表二）所示，1000km以上每增加1至100km运价增加

5万元； 7．管道可由铁路、公路运往铺设地点（不只是运到点A1,A2,,A15，而是管道全线）； 8．本问题只考虑在铁路和公路上运输的问题，而不考虑在其它路径上的情况； 9．每个钢管厂生产的钢管均满足铺设要求；

10．模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如转运费用等；

11．在公路上卸货,按铺路的要求卸车；

12．销售价和运输价不受市场价格变化的影响。

三、符号说明

第i钢管厂

表示Si的最大生产能力

Aj 表示需要铺设管道路径上的车站 xi, j

从所有Si运往Aj的钢管用于铺设Aj点前后侧的钢管数单位产品从Si到Aj地的运费

表示单位钢管从Si地运往Aj地的最小费用表示Aj和Aj1两车站之间需要铺设的管道长度从Si订购钢管的单位价格用于订购和运输的总费用

Fi, j fi, j Aj, j1 pi

四、模型的建立与求解

问题一

1、模型的建立

对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段。由本题的要求可以知道在铺设管道时必须经过

A1,A2,A15点。欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i地运

往j地的最优路线；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往j地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j为终点的钢管只铺到与j点相邻的两段管道上。因此，本问题可以按以下步骤求解。

第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。

设Si(i1,2,7)表示钢管厂，si(i1,2,7)表示Si的最大生产能力，

Aj(j1,2,,15)表示需要铺设钢管路径上的车站。假设从Si运往Aj的钢管用于铺设Aj

点前后侧的钢管数为xi, j单位，单位产品从Si到Aj地的运费为Fi, j万元，用fi, j表示单位钢管从Si地运往Aj地的最小费用，则：

fi, jminFi, j （1）

第二步：建立从Si厂运送xi, j单位钢管到Aj点的运费的模型：

用z1表示订购的所有钢管全部运到Aj点的总运费，则：

z1xi, jfi, j

j1i115

157

s.t. xi, jsi i

j1

xi, j500 i

j1

（2）

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1

xi, j0

其中： yj和yj分别表示运到Aj地钢管用于铺Aj点前边和后边的钢管长度；



Aj, j1表示Aj和Aj1之间需要铺设的管道长度

第三步：将运到Aj处的钢管铺到相邻两段路上的运输费用

根据假设，在铺设钢管时，dx单位钢管从第k点运到k1点的运费为：



k1

0.1 dx=0.1 （3）

由（3）式可得如下模型

（1）当yj和yj1均为整单位数时，设其运费用z21表示,则：





z210.1

j1



(1y)y(1y)yjjj1j1



（2）当yj和yj1均为非整单位数时，设其运费用z22表示,则：



z22



0.1



(1[y])[y]2(y[y])(1[yjjjjj])



[y])(1y)(2y[yjj1j1j1])}

0.1



(1y)[y]2(y[y])(1[yj1j1jj1j1])



0.05{(1[y])(2yjj



其中：[yj]表示yj的整数部分；



[yj1]表示yj1的整数部分;

综合上述两式可得：



z20.05{(1[y])(2y[y])(1y)(2y[yjjjj1j1j1])} （4）

j115

s.t. xi, jsi i

j1

xi, j500 i

j1

  1 当Si生产时i

 0 当Si不生产时7

y

yj

xi, j

i1

y

jyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

其中：z2表示运到Aj处的钢管铺到相邻两段路上的运输费用

第四步：建立订购费用的模型

设z3表示订购管道的总费用，则可建立如下模型：

715

z3pixi, j

（5）

i1j1

用z表示订购和运输的总费用，由（2）、（4）、（5）可得本问题的优化模型如下：

minzz1z2z3

即：

minz0.05{(1[y(2y

j])j[yj])(1yj1)(2yj1[yj1])}

j1

157715

xi, jfi, jpixi, j

j1i1

i1j1

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2、模型的求解（1）首先求解fi, j

此问题相当于求解最小费用流问题，即求出从Si点运送单位钢管到Aj点的最小费用。按常规，本问题可以按求最短路的常规方法求解。但由于本问题中沿铁路的单位运费由它前边经过的铁路长度而变化。根据问题的需要，我们不妨假设如果从Si点到Aj点的钢管经过铁路后，一旦走公路，那么，该钢管将不会再通过铁路运输。则假设沿铁路行走，直到走到与公路相连为止。那么，我们可以将已知图中铁路的费用直接表示出。因此从Si点到Aj点的通路如图三所示。

A（图三）

现在需要求出每个钢管厂Si到每条公路上的节点Aj的最优路径，即：如果需要从Si点运钢管到Aj点，则需要找出从该点到目的点间的最优路线。现在从每个钢厂出发，求出每个钢厂到需要铺设管道的路径上的每个节点的单位钢管量的最小费用。

那么，我们以Si，Aj以及铁路的端点等为点，以钢管的可能运输路线为边，以单位钢管的运输费用为权建立形如（图三）所示的加权图。（其中，边上的权的确定的具体方案参见文献[2]，本题中，以Si为起点，以需铺设管道的路上的节点为终点，那么从Si到Aj的路程中根据铁路和公路的运费特点不难得出形如图三所示的赋权图），根据Dijkstra标号法[2]可以求出每个钢管厂Si到各个节点Aj的最小单位运输费用。

现在我们以S2点为起点，以每个铺设管道的节点为终点，通过观察与简单运算得出图三的加权图，则以图三为基础，运用Lingo软件包中的求最短路问题的程序DYNAMB.LG4（见附录一）可求得单位钢管的最小运输费用如下：

其中：F(j)(j=1,…,15)表示从S2到Aj的最小单位钢管运费。

同理可得S1，S3，S4，S5，S6，S7各点到目的点的最优单位运费如下

S1点到需要铺设管道的路上的各节点的单位运输费

F( 1) 170.7000 F( 3) 140.2000 F( 5) 38.00000 F( 7) 3.100000 F( 9) 64.20000 F( 11) 96.00000 F( 13) 121.2000 F( 15) 142.0000

F( 2) 160.3000 F( 4) 98.60000 F( 6) 20.50000 F( 8) 21.20000 F( 10) 92.00000 F( 12) 106.0000 F( 14) 128.0000

S3点到需要铺设管道的路上的各节点的单位运输费

F( 1) 230.7000 F( 3) 200.2000 F( 5) 121.0000 F( 7) 96.00000 F( 9) 48.20000 F( 11) 86.00000 F( 2) 220.3000 F( 4) 181.6000 F( 6) 105.5000 F( 8) 86.20000 F( 10) 82.00000 F( 12) 96.00000 F( 13) 111.2000

F( 14) 118.0000

F( 15) 132.0000

S4点到需要铺设管道的路上的各节点的单位运输费

F( 1) 260.7000 F( 2) 250.3000 F( 3) 235.2000 F( 4) 216.6000 F( 5) 156.0000 F( 6) 140.5000 F( 7) 131.0000 F( 8) 116.2000 F( 9) 84.20000 F( 10) 62.00000 F( 11) 51.00000 F( 12) 61.00000 F( 13) 76.20000

F( 14) 83.00000

F( 15) 97.00000

S5点到需要铺设管道的路上的各节点的单位运输费

F( 1) 255.7000 F( 2) 245.3000 F( 3) 225.2000 F( 4) 206.6000 F( 5) 146.0000 F( 6) 130.5000 F( 7) 121.0000 F( 8) 111.2000 F( 9) 79.20000 F( 10) 57.00000 F( 11) 33.00000 F( 12) 51.00000 F( 13) 71.20000

F( 14) 73.00000

F( 15) 87.00000

S6点到需要铺设管道的路上的各节点的单位运输费

F( 1) 265.7000 F( 2) 255.3000 F( 3) 235.2000 F( 4) 216.6000 F( 5) 156.0000 F( 6) 140.5000 F( 7) 131.0000 F( 8) 121.2000 F( 9) 84.20000 F( 10) 62.00000 F( 11) 51.00000 F( 12) 45.00000 F( 13) 53.00000

F( 14) 11.00000

F( 15) 28.00000

S7点到需要铺设管道的路上的各节点的单位运输费

F( 1) 280.7000 F( 3) 250.2000 F( 5) 171.0000 F( 7) 146.0000 F( 9) 104.2000 F( 11) 66.00000 F( 13) 38.20000 F( 15) 2.000000

F( 2) 270.3000 F( 4) 231.6000 F( 6) 155.5000 F( 8) 136.2000 F( 10) 77.00000 F( 12) 56.00000 F( 14) 26.00000

(2)根据以上结果, 继续求解最小总费用的模型

原问题属于非线性规划问题的最优解，但针对我们现在的情况来说，不能找到较好的方法求解，我们可以根据线性（非线性）规划问题与网络流分析之间的密切联系，将原问题转化为下面的网络流问题进行求解。

本问题在求出Si点到Aj点的单位最小运费后，可以转化为有i个钢管厂给j个铺设公路点供钢管，然后第j个铺设点的钢管运往铺设处（管道全线）的网络流问题，假设用

si(i1,,7)表示第i个钢管厂的最大生产量，fi,j表示从i地运往j地的单位运价，每单

位钢管的成本为pi万元，运往j点后的每个点输出的管道数为dm运费为cm.。用xi表示第i地流出的钢管总数。我们可以构造源和汇, 可建立如下的网络流优化问题。其网络流如图四所示

该网络中每段弧上的两个数字，前者是该段弧的容量，后者是与该段弧相应的费用。符号表示该段弧容量无限制。

图中：si(i1,,S7)表示第i个钢厂的生产能力

pi(i1,,7)表示第i个钢厂生产钢管的销价

fi,j表示从i地运往j地的单位钢管的运费 cm表示运往Aj的钢管运往铺道上的费用 dm(m1,2,15) 表示运往Aj地的钢管数目

网络求解的具体方法如下:

（图四）

对网络G(N,A)的每一段弧(ni, nj)，除了容量c(ni, nj)之外，还附有另一非负实数l(ni, n总费用，及

)，称之为费用。要求构造一个从源到汇的最大网络流，同时使流的

l()

达到最小。

本问题的具体解法是

(ni, nj)A

l(n,n

)(ni,nj)

（1）任取一个取整数值的网络流，设流的值为v，要求在所有值为v的流中，的总费

用最小。显然l()0

（2）构造伴随增量网络G()，除容量外，对G()的每一段正向的弧，再按如下方式

定义一个费用，即：(i)对G()每一段正向的弧(ni, nj)，定义费用为

l'(ni, nj)l(ni, nj)。(ii)对G'()每一段正向的弧(ni, nj)，定义费用为l'(ni, nj)l(ni, nj)

（3）在G()上求出从源到汇的所有路径，定义每一条路径的费用为

l()

(ni, nj)

l(n,n

)

从中选出费用最小的路径，记为，如果G'()上不存在由源到汇的路径，转向步骤（5），否则继续。

（4）记为的最小弧容量，是G上与相应的链，在每段向前的弧上将流值增加，每段向后的弧上减少，得到一个新的流，它的值为v的最小费用，转向

步骤（2）

（5）判断最优解是否满足生产时至少生产500单位的条件，如果不满足，则将该厂的流

增加至500或减少到0，然后返回步骤（1），否则，此时所得到的流是最小费用最大流，算法结束。

在上述网络中必须知道cm，这样必须在上述求解网络的基础上加上枚举法。但是，在这样短的时间里不能编出求解此问题的全局最优解。现在只有运用求近似解的方法求解。否则不能求解。我们可以运用现成的软件，比如说Lingo数学软件，但是，在用它求解的过程中，不能将枚举法加在程序里，只有通过其他一些方法求出较好的初始值，然后求出前面一部分的最优解。我们可以在确定Aj处的钢管数后，运用将钢管铺到整段路上的运输费最小为目标确定出下一个局部的最优解。将上述两部分的解结合起来便可求出本问题的近似最优解。

首先，根据以下准则，确定出求图（四）的最优解的初始解。

在未给定初始值的情况下,为了使我们的解尽可能地解接近其最优解,我们根据自身的特点和工厂、铁路、公路以及铺设点分布情况，从而我们作出如下规则来确定模型的初始解域：

1）运输位置一旦离开铁路，而到达公路上后就不会再回到铁路上。 2）邻近原则：即将离工厂最近的铺设点为我们优先考虑定购点。 3）钢厂与铺设点之间的运输费用最少的优先考虑为我们的定购点。 4）一旦某工厂被定为定购点，它将尽最大的需求量去定购。大致根据以上规则和其分布特点，我们得到如下较优的初始值，即：Aj(j1,214,15)堆积点所定购的钢管量为0，261，482，515，571，153，373，212，574，330，317，170，257，655，141。

将上述数据作为我们的初始可行解，由后面的程序即可求出其最小费用为：1291630万元，其具体的订货、运输安排如下：

（表三）

问题二

1．模型的建立

针对本问题来说，我们可以用拉格郎日算子法求出灵敏度的大小求解非线性问题的灵敏度问题。同时也可转化为线性规划的方法求解，从而确定出该问题的灵敏度问题。

我们先根据其定义来求解。由灵敏度的定义可以知道，灵敏度是指系统中的参数或外扰的微小摄动对系统某特性的影响程度，关于参数摄动的灵敏度公式为：灵敏度=

参数变化引起系统特性变化的百分数

参数变化的百分数

由上述可以知道，当参数变化时，对应的最优解将会发生变化，那么每个参数发生变化的灵敏度就可以表示出来。对问题（1）的模型而言，当pi表示订购费用时，对应有一个最优解。

当pi变化pi时，对应的最优费用为ZZ，对应的最优解为xi, jxi, j，则：



zpi

piZZ/Z



pi/pipiZ

xi,j/xi,jpi/pi



pixi,j xi,jpi

xi,jpi



Z/ZSiZ

S

Si/SiSiZ

其中：

xi,jSj



xi,j/xi,jSj /Sj

Sixi,j xi,jSj

表示特性z关于参数pi的灵敏度 Spi

Spii,j表示特性xi,j关于参数pi的灵敏度

SSzi表示特性z关于参数pi的灵敏度

SSij,j表示特性xi,j关于参数pi的灵敏度

我们不妨仍以问题一中的模型作为本问题的模型，只是pi,si为变量而已。那么本问题的模型如下：



minz0.05{(1[yj])(2yj[yj])(1yj1)(2yj1[yj1])}

15x

j1

xi, jfi, jpixi, j

j1i1

i1j1

157715

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1

 i

当Si不生产时 0 yyxi, j



j

i17



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2．模型求解

当一些量变化时，我们可以运用问题一的解法求出变化后的最优解，然后运用上述灵敏度的定义求出其最优解。

我没不妨以每个量变化10%来求解，当然能够求出最小费用，但很难求出每个xi,j，因此，我们以参数变化后，以引起xi,j的变化的多少来确定参数变化后对订货运输计划的影响。

（1）我们不妨以上述两个变化来反映其变化的程度（单位：亿元），由附录中的程序可

由上述表格可以知道，第6个钢管厂钢管的销价对总费用的影响最大，对购运计划的影响也最大

（2）同理可得由于钢管厂生产能力发生变化对最优解的影响如下

由上可得：钢管厂S1的钢管产量的上限的变化对购运计划的总费用影响最大，钢管厂S3的产量上限的变化对购运计划影响最大。

问题三

1．模型建立

本问题比第一个问题更具有一般性，其主要目的与第一个问题相同。一种方案是找到最优生成树，找到需要管道的点所在的最小Steiner树。另一方面，我们也可以运用问题一的解决办法，先找出最优路径，然后求出所有费用的表达式，然后运用网络流的最小费用流的算法。运用穷举法便可求出最优解。

与问题一相同的方法可以建立以下模型：



minz0.05{(1[yj])(2yj[yj])(1yj1)(2yj1[yj1])}

j1

xi, jfi, jpixi, j

j1i1

i1j1

157715

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2．模型的求解

按问题一的方法，运用附录中的程序，求出单位钢管从Si运到Aj的最小费用f



i,j

，然

后运用与问题一一样的准则求出，建立如下网络模型，并用类似的方法求出本问题的最优解

（图四）

运用问题一的解法可以建立如下的网络流问题进行穷举求解。

S21

F( 1) 170.7000 F( 2) 160.3000 F( 3) 140.2000 F( 4) 98.60000 F( 5) 38.00000 F( 6) 20.50000 F( 7) 3.100000 F( 8) 21.20000 F( 9) 64.20000 F( 10) 92.00000 F( 11) 96.00000 F( 12) 106.0000 F( 13) 121.2000 F( 14) 128.0000 F( 15) 142.0000 F( 16) 60.00000 F( 17) 95.00000 F( 18) 100.0000 F( 19) 105.0000

F( 20) 115.0000

F( 21) 130.0000

S22

F( 1) 215.7000 F( 3) 190.2000 F( 5) 111.0000 F( 7) 86.00000 F( 9) 114.2000 F( 11) 146.0000 F( 13) 171.2000 F( 15) 192.0000 F( 17) 145.0000 F( 19) 145.0000

F( 21) 180.0000

S23

F( 1) 230.7000 F( 3) 200.2000 F( 5) 121.0000 F( 7) 96.00000 F( 9) 48.20000 F( 11) 86.00000 F( 13) 111.2000 F( 15) 132.0000 F( 17) 85.00000 F( 19) 100.0000

F( 21) 115.0000

S24

F( 1) 260.7000 F( 3) 235.2000 F( 5) 156.0000 F( 7) 131.0000 F( 9) 84.20000 F( 11) 51.00000 F( 13) 76.20000 F( 15) 97.00000 F( 17) 50.00000 F( 19) 70.00000

F( 21) 80.00000

S25

F( 2) 205.3000 F( 4) 171.6000 F( 6) 95.50000 F( 8) 71.20000 F( 10) 142.0000 F( 12) 146.0000 F( 14) 178.0000 F( 16) 110.0000 F( 18) 150.0000 F( 20) 165.0000

F( 2) 220.3000 F( 4) 181.6000 F( 6) 105.5000 F( 8) 86.20000 F( 10) 82.00000 F( 12) 101.0000 F( 14) 118.0000 F( 16) 44.00000 F( 18) 90.00000 F( 20) 105.0000

F( 2) 250.3000 F( 4) 216.6000 F( 6) 140.5000 F( 8) 116.2000 F( 10) 62.00000 F( 12) 71.00000 F( 14) 83.00000 F( 16) 80.00000 F( 18) 55.00000 F( 20) 70.00000

F( 1) 200.7000 F( 3) 170.2000 F( 5) 146.0000 F( 7) 121.0000 F( 9) 79.20000 F( 11) 33.00000 F( 13) 71.20000 F( 15) 87.00000 F( 17) 32.00000 F( 19) 50.00000 F( 21) 75.00000

F( 2) 190.3000 F( 4) 206.6000 F( 6) 130.5000 F( 8) 111.2000 F( 10) 57.00000 F( 12) 51.00000 F( 14) 73.00000 F( 16) 75.00000 F( 18) 50.00000 F( 20) 65.00000

S26

F( 1) 265.7000 F( 3) 235.2000 F( 5) 156.0000 F( 7) 131.0000 F( 9) 84.20000 F( 11) 51.00000 F( 13) 16.20000 F( 15) 28.00000 F( 17) 50.00000 F( 19) 36.00000 F( 21) 0.0000000

F( 2) 255.3000 F( 4) 216.6000 F( 6) 140.5000 F( 8) 121.2000 F( 10) 62.00000 F( 12) 37.00000 F( 14) 11.00000 F( 16) 80.00000 F( 18) 37.00000 F( 20) 10.00000

S27

F( 1) 280.7000 F( 3) 250.2000 F( 5) 166.0000 F( 7) 146.0000 F( 9) 104.2000 F( 11) 64.00000 F( 13) 38.20000 F( 15) 2.000000 F( 17) 63.00000 F( 19) 55.00000 F( 21) 26.00000

F( 2) 270.3000 F( 4) 226.6000 F( 6) 155.5000 F( 8) 136.2000 F( 10) 82.00000 F( 12) 56.00000 F( 14) 26.00000 F( 16) 100.0000 F( 18) 50.00000 F( 20) 32.00000

3．在确定出上述结果后，运用下列准则，确定下列初始解，再利用相同的方法编制附录中的程序。

从而可得到如下最优解：

总的最小费用为1396099万元，具体的订货和运输计划详细见下表

（表四）

五、结果分析

由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成。我们将其分段求出最优，然后综合考虑，这种解法不容易得到全局最优解，但经过我们多次的反复优化，使我们的结果趋于稳定。预想求出全局最优解，可以按我们在上面提出的非线性优化或网络最小费用最大流求解。

另外，我们借助于Lingo软件求解，同时进行了灵敏度分析（具体见附录中的程序结果）。

六、模型的评价及改进

1．优点：

1）本问题中运用了现代使用较广的网络流算法，同时又结合枚举法进行求解。这样模型的推广性较强，计算结果较为准确

2）问题将费用流转化为网络流，具有较强的推广性和准确性

3）本问题构造出的模型算法较简单，也可以运用手算的方法来得到比较满意的结果。

2．缺点：

1）由于本问题有现成的比较先进的解法，但由于缺乏基本的数学软件资料，不能将其准确求解。

2）于在求解最短路时，我们用人工计算容易将问题复杂化，同时，容易出错。

3）作为图论问题的技术而言，求解过程较难，且不易求出最优解

3．模型改进

本问题中需要用现成的先进的网络流求解，但本问题没有求解，将两部分分开来求解只有可能是原问题的一个可行解，实际上需要运用枚举法的网络解。在求解问题三时可用最小树求解，同时，我们可将本问题运用于时间的变化等范围的推广。

可以运用一些分类准则，将该图分类，也可以采用模糊聚类的方法分组

七、模型的运用及推广

由于网络技术已作为一种有效的科学管理方法,使其自身有其广泛的应用和推广在现实生活、生产和科研活动中，有很多问题具有网络的形式，都可以用本模型的思想和方法加以描述。例如：在生产管理和组织工作中，为有效完成某项生产任务，而对各工序之间衔接进行统筹安排问题；又如交通系统，供水管系统以及通信系统等的合理分布问题等等，具体我们可得如下表的一些典型的网络系统：

参考文献

[1] 许国志主编，《系统科学大词典》，云南科技出版社，云南，1994。

[2] 杜端甫，《运筹图论（图、网络理论中的运筹问题）》，北京航空航天大学出版社，北京，1990。

[3] 雷功炎，《数学模型讲义》，北京大学出版社，北京，1999。

附录

附录一

1．求解Si(i1,,7)到Aj(j1,,15)点的单位运费最小的最优路径，并将S2的数据代入求出其解的源程序清单

MODEL:

SETS:

CITIES /1..33/: F;

ROADS( CITIES, CITIES)/

1,2

2,3 2,16

3,4 3,17

4,5 4,18

5,6 5,19

6,7 6,20

7,8 7,21 7,22

8,9 8,23

9,10 9,24

10,11 10,25

11,12 11,26

12,13 12,27

13,14 13,28

14,15 14,29 14,30

15,31 15,32

16,33

17,33

18,33

19,33

20,33

21,33

22,33

23,33

24,33

25,33

26,33

27,33

29,33

30,33

31,33

32,33/: D;

! D( i, j) is the distance from city i to j;

ENDSETS

DATA:

! Here are the distances that correspond to the

above links;

D =

10.4

30.1 0.3

75.0 0.2

60.6 60

19.4 1

20.5 0.5

20.1 1.0 3.1

68.0 1.2

48.0 4.2

30.0 7.0

22.0 1.0

21.0 1.0

42.0 6.2

50.0 11.0 3.0

2.0 2.0

205.0

190.0

125.0

110.0

95.0

85.0

70.0

110.0

135.0

145.0

155.0

165.0

180.0

175.0

190.0

190.0;

F( @SIZE( CITIES)) = 0;

@FOR( CITIES( i)| i #LT# @SIZE( CITIES):

F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))

);

END

2．对求从S2到Aj的运行结果

Feasible solution found at step: 0

Variable Value

F( 1) 215.7000

F( 2) 205.3000

F( 3) 190.2000

F( 4) 171.6000

F( 5) 111.0000

F( 6) 95.50000

F( 7) 86.00000

F( 8) 71.20000

F( 9) 114.2000

F( 10) 142.0000

F( 11) 146.0000

F( 12) 156.0000

F( 13) 171.2000

F( 14) 178.0000

F( 15) 192.0000

F( 16) 205.0000

F( 17) 190.0000

F( 18) 125.0000

F( 19) 110.0000

F( 20) 95.00000

F( 21) 85.00000

F( 22) 85.00000

F( 23) 70.00000

F( 24) 110.0000

F( 25) 135.0000

F( 26) 145.0000

F( 27) 155.0000

F( 28) 165.0000

F( 29) 180.0000

F( 30) 175.0000

F( 31) 190.0000

F( 32) 190.0000

F( 33) 0.0000000

附录二，对问题一的订购和运输计划

1，Lingo源程序

MODEL:

! A 6 Warehouse 14 Vendor Transportation Problem;

SETS:

WAREHOUSES / S1 S2 S3 S4 S5 S6/: CAPACITY;

VENDORS/A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15/ : DEMAND; LINKS( WAREHOUSES, VENDORS): COST, VOLUME;

ENDSETS

! The objective;

MIN = @SUM( LINKS( I, J):

COST( I, J) * VOLUME( I, J));

! The demand constraints;

@FOR( VENDORS( J):

@SUM( WAREHOUSES( I): VOLUME( I, J)) =

DEMAND( J));

! The capacity constraints;

@FOR( WAREHOUSES( I):

@SUM( VENDORS( J): VOLUME( I, J))

CAPACITY( I));

! Here is the data;

DATA:

CAPACITY = 800 800 1000 2000 2000 2000;

DEMAND=261 482 515 571 153 373 212 734 330 317 170 257 655 141;

COST=320.3 300.0 258.6 198.0 180.5 163.1 181.2 224.2 252.0 256.0 266.0 281.2 288.0 302.0

360.3 345.2 326.6 266.0 250.5 241.0 226.2 269.2 297.0 301.0 311.0 326.2 333.0 347.0

375.3 355.2 336.6 276.0 260.5 251.0 241.2 203.2 237.0 241.0 251.0 266.2 273.0 287.0

410.3 395.2 376.6 316.0 300.5 291.0 276.2 244.2 222.0 211.0 221.0 236.2 243.0 257.0

400.3 380.2 361.6 301.0 285.5 276.0 266.2 234.2 212.0 188.0 206.0 226.2 228.0 242.0 405.3 386.2

366.6 306.0 290.5 281.0 271.2 234.2 212.0 201.0 195.0 203.0 161.0 178.0;

ENDDATA

END

2．运行结果

Rows= 21 Vars= 84 No. integer vars= 0 ( all are linear) Nonzeros= 272 Constraint nonz= 168( 168 are +- 1) Density=0.152 Smallest and largest elements in abs value= 1.00000 2000.00 No. : 0, Obj=MIN, GUBs

Single cols= 0

Optimal solution found at step: 33

Objective value: 1220059.

Variable Value Reduced Cost

VOLUME( S1, A2) 0.0000000 28.00001 VOLUME( S1, A3) 0.0000000 22.79999 VOLUME( S1, A4) 274.0000 0.0000000 VOLUME( S1, A5) 0.0000000 0.0000000 VOLUME( S1, A6) 153.0000 0.0000000 VOLUME( S1, A7) 373.0000 0.0000000 VOLUME( S1, A8) 0.0000000 22.99999 VOLUME( S1, A9) 0.0000000 99.00000 VOLUME( S1, A10) 0.0000000 143.0000 VOLUME( S1, A11) 0.0000000 171.0000 VOLUME( S1, A12) 0.0000000 174.0000 VOLUME( S1, A13) 0.0000000 181.2000 VOLUME( S1, A14) 0.0000000 230.0000 VOLUME( S1, A15) 0.0000000 227.0000 VOLUME( S2, A2) 261.0000 0.0000000 VOLUME( S2, A3) 22.00000 0.0000000

VOLUME( S2, A4) 0.0000000 -0.6103516E-05 VOLUME( S2, A5) 305.0000 0.0000000 VOLUME( S2, A6) 0.0000000 2.000000 VOLUME( S2, A7) 0.0000000 9.899994 VOLUME( S2, A8) 212.0000 0.0000000 VOLUME( S2, A9) 0.0000000 76.00000 VOLUME( S2, A10) 0.0000000 120.0000 VOLUME( S2, A11) 0.0000000 148.0000 VOLUME( S2, A12) 0.0000000 151.0000 VOLUME( S2, A13) 0.0000000 158.2000 VOLUME( S2, A14) 0.0000000 207.0000 VOLUME( S2, A15) 0.0000000 204.0000 VOLUME( S3, A2) 0.0000000 5.000012

VOLUME( S3, A3) 0.0000000 -0.1220703E-04 VOLUME( S3, A4) 0.0000000 -0.6103516E-05

VOLUME( S3, A6) 0.0000000 2.000000 VOLUME( S3, A7) 0.0000000 9.899994 VOLUME( S3, A8) 0.0000000 4.999988 VOLUME( S3, A9) 734.0000 0.0000000 VOLUME( S3, A10) 0.0000000 50.00000 VOLUME( S3, A11) 0.0000000 78.00000 VOLUME( S3, A12) 0.0000000 81.00000 VOLUME( S3, A13) 0.0000000 88.20000 VOLUME( S3, A14) 0.0000000 137.0000 VOLUME( S3, A15) 0.0000000 134.0000 VOLUME( S4, A2) 0.0000000 15.00001 VOLUME( S4, A3) 0.0000000 14.99999 VOLUME( S4, A4) 0.0000000 14.99999 VOLUME( S4, A5) 0.0000000 15.00000 VOLUME( S4, A6) 0.0000000 17.00000 VOLUME( S4, A7) 0.0000000 24.89999 VOLUME( S4, A8) 0.0000000 14.99999 VOLUME( S4, A9) 0.0000000 16.00000 VOLUME( S4, A10) 0.0000000 10.00000 VOLUME( S4, A11) 0.0000000 23.00000 VOLUME( S4, A12) 0.0000000 26.00000 VOLUME( S4, A13) 0.0000000 33.20000 VOLUME( S4, A14) 0.0000000 82.00000 VOLUME( S4, A15) 0.0000000 79.00000 VOLUME( S5, A2) 0.0000000 5.000012 VOLUME( S5, A3) 460.0000 0.0000000 VOLUME( S5, A4) 241.0000 0.0000000 VOLUME( S5, A5) 0.0000000 0.0000000 VOLUME( S5, A6) 0.0000000 2.000000 VOLUME( S5, A7) 0.0000000 9.899994 VOLUME( S5, A8) 0.0000000 4.999988 VOLUME( S5, A9) 0.0000000 6.000003 VOLUME( S5, A10) 330.0000 0.0000000 VOLUME( S5, A11) 317.0000 0.0000000 VOLUME( S5, A12) 0.0000000 11.00000 VOLUME( S5, A13) 0.0000000 23.20000 VOLUME( S5, A14) 0.0000000 67.00000 VOLUME( S5, A15) 0.0000000 64.00000 VOLUME( S6, A2) 0.0000000 10.00001 VOLUME( S6, A3) 0.0000000 5.999988 VOLUME( S6, A4) 0.0000000 4.999994 VOLUME( S6, A5) 0.0000000 5.000000 VOLUME( S6, A6) 0.0000000 7.000000

VOLUME( S6, A8) 0.0000000 9.999988 VOLUME( S6, A9) 0.0000000 6.000003 VOLUME( S6, A10) 0.0000000 0.0000000 VOLUME( S6, A11) 0.0000000 13.00000 VOLUME( S6, A12) 170.0000 0.0000000 VOLUME( S6, A13) 257.0000 0.0000000 VOLUME( S6, A14) 655.0000 0.0000000 VOLUME( S6, A15) 141.0000 0.0000000

3．灵敏度分析

Ranges in which the basis is unchanged:

Objective Coefficient Ranges

Current Allowable Allowable Variable Coefficient Increase Decrease VOLUME( S1, A2) 320.3000 INFINITY 28.00001 VOLUME( S1, A3) 300.0000 INFINITY 22.79999 VOLUME( S1, A4) 258.6000 0.0 2.000000 VOLUME( S1, A5) 198.0000 INFINITY 0.0 VOLUME( S1, A6) 180.5000 2.000000 INFINITY VOLUME( S1, A7) 163.1000 9.899994 INFINITY VOLUME( S1, A8) 181.2000 INFINITY 22.99999 VOLUME( S1, A9) 224.2000 INFINITY 99.00000 VOLUME( S1, A10) 252.0000 INFINITY 143.0000 VOLUME( S1, A11) 256.0000 INFINITY 171.0000 VOLUME( S1, A12) 266.0000 INFINITY 174.0000 VOLUME( S1, A13) 281.2000 INFINITY 181.2000 VOLUME( S1, A14) 288.0000 INFINITY 230.0000 VOLUME( S1, A15) 302.0000 INFINITY 227.0000 VOLUME( S2, A2) 360.3000 5.000012 INFINITY VOLUME( S2, A3) 345.2000 0.0 0.0 VOLUME( S2, A4) 326.6000 INFINITY -0.6103516E-05 VOLUME( S2, A5) 266.0000 0.0 0.0 VOLUME( S2, A6) 250.5000 INFINITY 2.000000 VOLUME( S2, A7) 241.0000 INFINITY 9.899994 VOLUME( S2, A8) 226.2000 4.999988 INFINITY VOLUME( S2, A9) 269.2000 INFINITY 76.00000 VOLUME( S2, A10) 297.0000 INFINITY 120.0000 VOLUME( S2, A11) 301.0000 INFINITY 148.0000 VOLUME( S2, A12) 311.0000 INFINITY 151.0000 VOLUME( S2, A13) 326.2000 INFINITY 158.2000 VOLUME( S2, A14) 333.0000 INFINITY 207.0000 VOLUME( S2, A15) 347.0000 INFINITY 204.0000 VOLUME( S3, A2) 375.3000 INFINITY 5.000012

VOLUME( S3, A3) 355.2000 INFINITY -0.1220703E-04 VOLUME( S3, A4) 336.6000 INFINITY -0.6103516E-05 VOLUME( S3, A5) 276.0000 0.0 6.000003 VOLUME( S3, A6) 260.5000 INFINITY 2.000000 VOLUME( S3, A7) 251.0000 INFINITY 9.899994 VOLUME( S3, A8) 241.2000 INFINITY 4.999988 VOLUME( S3, A9) 203.2000 6.000003 INFINITY VOLUME( S3, A10) 237.0000 INFINITY 50.00000 VOLUME( S3, A11) 241.0000 INFINITY 78.00000 VOLUME( S3, A12) 251.0000 INFINITY 81.00000 VOLUME( S3, A13) 266.2000 INFINITY 88.20000 VOLUME( S3, A14) 273.0000 INFINITY 137.0000 VOLUME( S3, A15) 287.0000 INFINITY 134.0000 VOLUME( S4, A2) 410.3000 INFINITY 15.00001 VOLUME( S4, A3) 395.2000 INFINITY 14.99999 VOLUME( S4, A4) 376.6000 INFINITY 14.99999 VOLUME( S4, A5) 316.0000 INFINITY 15.00000 VOLUME( S4, A6) 300.5000 INFINITY 17.00000 VOLUME( S4, A7) 291.0000 INFINITY 24.89999 VOLUME( S4, A8) 276.2000 INFINITY 14.99999 VOLUME( S4, A9) 244.2000 INFINITY 16.00000 VOLUME( S4, A10) 222.0000 INFINITY 10.00000 VOLUME( S4, A11) 211.0000 INFINITY 23.00000 VOLUME( S4, A12) 221.0000 INFINITY 26.00000 VOLUME( S4, A13) 236.2000 INFINITY 33.20000 VOLUME( S4, A14) 243.0000 INFINITY 82.00000 VOLUME( S4, A15) 257.0000 INFINITY 79.00000 VOLUME( S5, A2) 400.3000 INFINITY 5.000012 VOLUME( S5, A3) 380.2000 0.0 0.0 VOLUME( S5, A4) 361.6000 0.0 0.0 VOLUME( S5, A5) 301.0000 INFINITY 0.0 VOLUME( S5, A6) 285.5000 INFINITY 2.000000 VOLUME( S5, A7) 276.0000 INFINITY 9.899994 VOLUME( S5, A8) 266.2000 INFINITY 4.999988 VOLUME( S5, A9) 234.2000 INFINITY 6.000003 VOLUME( S5, A10) 212.0000 0.0 INFINITY VOLUME( S5, A11) 188.0000 13.00000 INFINITY VOLUME( S5, A12) 206.0000 INFINITY 11.00000 VOLUME( S5, A13) 226.2000 INFINITY 23.20000 VOLUME( S5, A14) 228.0000 INFINITY 67.00000 VOLUME( S5, A15) 242.0000 INFINITY 64.00000 VOLUME( S6, A2) 405.3000 INFINITY 10.00001 VOLUME( S6, A3) 386.2000 INFINITY 5.999988 VOLUME( S6, A4) 366.6000 INFINITY 4.999994

VOLUME( S6, A5) 306.0000 INFINITY 5.000000 VOLUME( S6, A6) 290.5000 INFINITY 7.000000 VOLUME( S6, A7) 281.0000 INFINITY 14.89999 VOLUME( S6, A8) 271.2000 INFINITY 9.999988 VOLUME( S6, A9) 234.2000 INFINITY 6.000003 VOLUME( S6, A10) 212.0000 INFINITY 0.0 VOLUME( S6, A11) 201.0000 INFINITY 13.00000 VOLUME( S6, A12) 195.0000 11.00000 INFINITY VOLUME( S6, A13) 203.0000 23.20000 INFINITY VOLUME( S6, A14) 161.0000 67.00000 INFINITY VOLUME( S6, A15) 178.0000 64.00000 INFINITY

Righthand Side Ranges

Row Current Allowable Allowable RHS Increase Decrease 2 261.0000 22.00000 261.0000 3 482.0000 652.0000 460.0000 4 515.0000 652.0000 241.0000 5 571.0000 22.00000 305.0000 6 153.0000 274.0000 153.0000 7 373.0000 274.0000 241.0000 8 212.0000 22.00000 212.0000 9 734.0000 22.00000 305.0000 10 330.0000 652.0000 330.0000 11 317.0000 652.0000 317.0000 12 170.0000 777.0000 170.0000 13 257.0000 777.0000 257.0000 14 655.0000 777.0000 655.0000 15 141.0000 777.0000 141.0000 16 800.0000 241.0000 274.0000 17 800.0000 460.0000 22.00000 18 1000.000 305.0000 22.00000 19 2000.000 INFINITY 2000.000 20 2000.000 INFINITY 652.0000 21 2000.000 INFINITY 777.0000

附录三、对问题三最短路的求解

1．源程序清单

MODEL:

SETS:

CITIES /1..34/: F;

ROADS( CITIES, CITIES)/

1,2

3,4 3,23

4,5 4,24

5,6 5,25

6,7 6,26

7,8 7,27 7,28

8,9 8,29

9,10 9,16

10,11 10,30

11,12 11,17

12,13 12,19

13,14 13,20

14,15 14,21 14,31

15,32 15,33

16,34

17,18 17,19 17,34

18,34

19,20 19,34

20,21 20,34

21,34

22,34

23,34

24,34

25,34

26,34

27,34

28,34

29,34

30,34

31,34

32,34

33,34/: D;

! D( i, j) is the distance from city i to j;

ENDSETS

DATA:

! Here are the distances that correspond to the

above links;

D =

10.4

30.1 0.3

75.0 0.2

60.6 60

19.4 1

20.1 1.0 3.1

68.0 1.2

48.0 4.2

30.0 7.0

22.0 1.0

21.0 1.0

42.0 6.2

50.0 11.0 3.0

2.0 2.0

110.0

13.0 19.0 145.0

150.0

26.0 145.0

10.0 165.0

180.0

205.0

190.0

125.0

110.0

95.0

85.0

70.0

135.0

175.0

190.0

190.0;

ENDDATA

! If you are already in City 10, then the cost to

travel to City 10 is 0;

F( @SIZE( CITIES)) = 0;

@FOR( CITIES( i)| i #LT# @SIZE( CITIES):

F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))

);

END

2．运行结果

Variable Value

F( 1) 170.7000

F( 2) 160.3000

F( 3) 140.2000

F( 4) 98.60000

F( 5) 38.00000

F( 6) 20.50000

F( 7) 3.100000

F( 8) 21.20000

F( 9) 64.20000

F( 10) 92.00000

F( 11) 96.00000

F( 12) 106.0000

F( 13) 121.2000

F( 14) 128.0000

F( 15) 142.0000

F( 16) 60.00000

F( 17) 95.00000

F( 18) 100.0000

F( 19) 105.0000

F( 20) 115.0000

F( 21) 130.0000

附录四、确定问题三订购、运输计划及总费用的源程序

1．源程序清单

MODEL:

! A 6 Warehouse 8 Vendor Transportation Problem;

SETS:

WAREHOUSES / S1 S2 S3 S5 S6/: CAPACITY;

VENDORS/A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21/ : DEMAND;

LINKS( WAREHOUSES, VENDORS): COST, VOLUME;

ENDSETS

! The objective;

MIN = @SUM( LINKS( I, J):

COST( I, J) * VOLUME( I, J));

! The demand constraints;

@FOR( VENDORS( J):

@SUM( WAREHOUSES( I): VOLUME( I, J)) =

DEMAND( J));

! The capacity constraints;

@FOR( WAREHOUSES( I):

@SUM( VENDORS( J): VOLUME( I, J))

CAPACITY( I));

! Here is the data;

DATA:

CAPACITY = 800 800 1000 2000 2000;

DEMAND=261 482 515 571 153 373 212 754 330 322 170 257 655 141 22 185

60 161 179 100;

COST=320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302 220 255 260 265 275 290

360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 301 326.2 333 347 265 300 305 300 320 335

375.3 355.2 336.6 276 260.5 251 241.2 240 203.2 237 241 256 266.2 273 287 199 245 255 260 270

345.3 325.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 230 187 205 205 220 230

405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 187 166.2 161 178 230 200 187 186 160 150;

ENDDATA

END

2．运行结果

Rows= 26 Vars= 100 No. integer vars= 0 ( all are linear) Nonzeros= 325 Constraint nonz= 200( 200 are +- 1) Density=0.124 Smallest and largest elements in abs value= 1.00000 2000.00 No. : 0, Obj=MIN, GUBs

Single cols= 0

Optimal solution found at step: 36

Objective value: 1320666.

Variable Value Reduced Cost

VOLUME( S1, A2) 0.0000000 53.00001 VOLUME( S1, A3) 0.0000000 52.99999

VOLUME( S1, A4) 0.0000000 -0.6103516E-05 VOLUME( S1, A5) 274.0000 0.0000000 VOLUME( S1, A6) 153.0000 0.0000000 VOLUME( S1, A7) 373.0000 0.0000000 VOLUME( S1, A8) 0.0000000 23.00000 VOLUME( S1, A9) 0.0000000 68.00000 VOLUME( S1, A10) 0.0000000 126.8000 VOLUME( S1, A11) 0.0000000 146.0000 VOLUME( S1, A12) 0.0000000 157.0000 VOLUME( S1, A13) 0.0000000 193.0000 VOLUME( S1, A14) 0.0000000 205.0000 VOLUME( S1, A15) 0.0000000 202.0000 VOLUME( S1, A16) 0.0000000 68.00000 VOLUME( S1, A17) 0.0000000 146.0000 VOLUME( S1, A18) 0.0000000 151.0000

VOLUME( S1, A20) 0.0000000 193.0000 VOLUME( S1, A21) 0.0000000 218.0000 VOLUME( S2, A2) 0.0000000 25.00001 VOLUME( S2, A3) 0.0000000 29.99999 VOLUME( S2, A4) 515.0000 0.0000000 VOLUME( S2, A5) 73.00000 0.0000000 VOLUME( S2, A6) 0.0000000 2.000000 VOLUME( S2, A7) 0.0000000 9.899994 VOLUME( S2, A8) 212.0000 0.0000000 VOLUME( S2, A9) 0.0000000 45.00000 VOLUME( S2, A10) 0.0000000 103.8000 VOLUME( S2, A11) 0.0000000 123.0000 VOLUME( S2, A12) 0.0000000 124.0000 VOLUME( S2, A13) 0.0000000 170.0000 VOLUME( S2, A14) 0.0000000 182.0000 VOLUME( S2, A15) 0.0000000 179.0000 VOLUME( S2, A16) 0.0000000 45.00000 VOLUME( S2, A17) 0.0000000 123.0000 VOLUME( S2, A18) 0.0000000 128.0000 VOLUME( S2, A19) 0.0000000 124.0000 VOLUME( S2, A20) 0.0000000 170.0000 VOLUME( S2, A21) 0.0000000 195.0000 VOLUME( S3, A2) 0.0000000 30.00001 VOLUME( S3, A3) 0.0000000 29.99999

VOLUME( S3, A4) 0.0000000 -0.6103516E-05 VOLUME( S3, A5) 224.0000 0.0000000 VOLUME( S3, A6) 0.0000000 2.000000 VOLUME( S3, A7) 0.0000000 9.899994 VOLUME( S3, A8) 0.0000000 5.000003 VOLUME( S3, A9) 0.0000000 5.800003 VOLUME( S3, A10) 330.0000 0.0000000 VOLUME( S3, A11) 0.0000000 49.00000 VOLUME( S3, A12) 0.0000000 54.00000 VOLUME( S3, A13) 0.0000000 89.80000 VOLUME( S3, A14) 0.0000000 105.2000 VOLUME( S3, A15) 0.0000000 95.00000 VOLUME( S3, A16) 0.0000000 57.00000 VOLUME( S3, A17) 0.0000000 12.00000 VOLUME( S3, A18) 0.0000000 58.00000 VOLUME( S3, A19) 0.0000000 69.00000 VOLUME( S3, A20) 0.0000000 100.0000 VOLUME( S3, A21) 0.0000000 120.0000 VOLUME( S5, A2) 261.0000 0.0000000

VOLUME( S5, A4) 0.0000000 24.99999 VOLUME( S5, A5) 0.0000000 25.00000 VOLUME( S5, A6) 0.0000000 27.00000 VOLUME( S5, A7) 0.0000000 34.89999 VOLUME( S5, A8) 0.0000000 30.00000 VOLUME( S5, A9) 728.0000 0.0000000 VOLUME( S5, A10) 0.0000000 8.800003 VOLUME( S5, A11) 322.0000 0.0000000 VOLUME( S5, A12) 0.0000000 19.00000 VOLUME( S5, A13) 0.0000000 60.00000 VOLUME( S5, A14) 0.0000000 67.00000 VOLUME( S5, A15) 0.0000000 64.00000 VOLUME( S5, A16) 22.00000 0.0000000 VOLUME( S5, A17) 185.0000 0.0000000 VOLUME( S5, A18) 0.0000000 18.00000 VOLUME( S5, A19) 0.0000000 19.00000 VOLUME( S5, A20) 0.0000000 60.00000 VOLUME( S5, A21) 0.0000000 80.00000 VOLUME( S6, A2) 0.0000000 60.00001 VOLUME( S6, A3) 0.0000000 59.99999 VOLUME( S6, A4) 0.0000000 29.99999 VOLUME( S6, A5) 0.0000000 30.00000 VOLUME( S6, A6) 0.0000000 32.00000 VOLUME( S6, A7) 0.0000000 39.89999 VOLUME( S6, A8) 0.0000000 35.00000 VOLUME( S6, A9) 26.00000 0.0000000 VOLUME( S6, A10) 0.0000000 8.800003 VOLUME( S6, A11) 0.0000000 13.00000 VOLUME( S6, A12) 170.0000 0.0000000 VOLUME( S6, A13) 257.0000 0.0000000 VOLUME( S6, A14) 655.0000 0.0000000 VOLUME( S6, A15) 141.0000 0.0000000 VOLUME( S6, A16) 0.0000000 0.0000000 VOLUME( S6, A17) 0.0000000 13.00000 VOLUME( S6, A18) 60.00000 0.0000000 VOLUME( S6, A19) 161.0000 0.0000000 VOLUME( S6, A20) 179.0000 0.0000000 VOLUME( S6, A21) 100.0000 0.0000000

附件2

《运筹学》最短路、最小费用最大流经典作品

关于钢管订购和运输的优化模型

队员：陈显健

陈瑜斌陈振松

2007

年6月5日

摘要：本文首先运用图论知识中的最短路算法求出Si到Aj的最优路径。然后将模型转化为最小费用最大流的网络优化问题，从而求出近似最优解。

最后对模型进行了综合评价并提出了改进方向。关键词：网络流最小费用最大流

一、问题重述

为了方便，1km主管道称为1单位钢管。

表一

1单位钢管的铁路运价如下表：

（表二）

1000km以上每增加1至100km运价增加5万元。

公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。

管道可由铁路、公路运往铺设地点（不只是运到点A1A2A15，而是管道全线）。

要求：

影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。

（3）如果要铺设的管道不是一条线，而是一个树形图。铁路、公路和管道购成网络，

请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出数学模型和结果。

二、基本假设

1．沿管道铺设路线上有公路，在计算运费时，与其它普通公路相同； 2．订购的钢管数量刚好等于需要铺设的钢管数量；

3．公路运输费用为1单位钢管每公里0.1万元（不足整公里的按整公里计算）； 4． 1km主管道钢管称为1单位钢管；

5．一个钢厂如果承担制造这种钢管，至少需要生产500个单位；

6． 1单位钢管的铁路运价如（表二）所示，1000km以上每增加1至100km运价增加

10．模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如转运费用等；

11．在公路上卸货,按铺路的要求卸车；

12．销售价和运输价不受市场价格变化的影响。

三、符号说明

第i钢管厂

表示Si的最大生产能力

Aj 表示需要铺设管道路径上的车站 xi, j

从所有Si运往Aj的钢管用于铺设Aj点前后侧的钢管数单位产品从Si到Aj地的运费

表示单位钢管从Si地运往Aj地的最小费用表示Aj和Aj1两车站之间需要铺设的管道长度从Si订购钢管的单位价格用于订购和运输的总费用

Fi, j fi, j Aj, j1 pi

四、模型的建立与求解

问题一

1、模型的建立

A1,A2,A15点。欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i地运

第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。

设Si(i1,2,7)表示钢管厂，si(i1,2,7)表示Si的最大生产能力，

Aj(j1,2,,15)表示需要铺设钢管路径上的车站。假设从Si运往Aj的钢管用于铺设Aj

点前后侧的钢管数为xi, j单位，单位产品从Si到Aj地的运费为Fi, j万元，用fi, j表示单位钢管从Si地运往Aj地的最小费用，则：

fi, jminFi, j （1）

第二步：建立从Si厂运送xi, j单位钢管到Aj点的运费的模型：

用z1表示订购的所有钢管全部运到Aj点的总运费，则：

z1xi, jfi, j

j1i115

157

s.t. xi, jsi i

j1

xi, j500 i

j1

（2）

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1

xi, j0

其中： yj和yj分别表示运到Aj地钢管用于铺Aj点前边和后边的钢管长度；



Aj, j1表示Aj和Aj1之间需要铺设的管道长度

第三步：将运到Aj处的钢管铺到相邻两段路上的运输费用

根据假设，在铺设钢管时，dx单位钢管从第k点运到k1点的运费为：



k1

0.1 dx=0.1 （3）

由（3）式可得如下模型

（1）当yj和yj1均为整单位数时，设其运费用z21表示,则：





z210.1

j1



(1y)y(1y)yjjj1j1



（2）当yj和yj1均为非整单位数时，设其运费用z22表示,则：



z22



0.1



(1[y])[y]2(y[y])(1[yjjjjj])



[y])(1y)(2y[yjj1j1j1])}

0.1



(1y)[y]2(y[y])(1[yj1j1jj1j1])



0.05{(1[y])(2yjj



其中：[yj]表示yj的整数部分；



[yj1]表示yj1的整数部分;

综合上述两式可得：



z20.05{(1[y])(2y[y])(1y)(2y[yjjjj1j1j1])} （4）

j115

s.t. xi, jsi i

j1

xi, j500 i

j1

  1 当Si生产时i

 0 当Si不生产时7

y

yj

xi, j

i1

y

jyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

其中：z2表示运到Aj处的钢管铺到相邻两段路上的运输费用

第四步：建立订购费用的模型

设z3表示订购管道的总费用，则可建立如下模型：

715

z3pixi, j

（5）

i1j1

用z表示订购和运输的总费用，由（2）、（4）、（5）可得本问题的优化模型如下：

minzz1z2z3

即：

minz0.05{(1[y(2y

j])j[yj])(1yj1)(2yj1[yj1])}

j1

157715

xi, jfi, jpixi, j

j1i1

i1j1

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2、模型的求解（1）首先求解fi, j

A（图三）

其中：F(j)(j=1,…,15)表示从S2到Aj的最小单位钢管运费。

同理可得S1，S3，S4，S5，S6，S7各点到目的点的最优单位运费如下

S1点到需要铺设管道的路上的各节点的单位运输费

F( 1) 170.7000 F( 3) 140.2000 F( 5) 38.00000 F( 7) 3.100000 F( 9) 64.20000 F( 11) 96.00000 F( 13) 121.2000 F( 15) 142.0000

F( 2) 160.3000 F( 4) 98.60000 F( 6) 20.50000 F( 8) 21.20000 F( 10) 92.00000 F( 12) 106.0000 F( 14) 128.0000

S3点到需要铺设管道的路上的各节点的单位运输费

F( 1) 230.7000 F( 3) 200.2000 F( 5) 121.0000 F( 7) 96.00000 F( 9) 48.20000 F( 11) 86.00000 F( 2) 220.3000 F( 4) 181.6000 F( 6) 105.5000 F( 8) 86.20000 F( 10) 82.00000 F( 12) 96.00000 F( 13) 111.2000

F( 14) 118.0000

F( 15) 132.0000

S4点到需要铺设管道的路上的各节点的单位运输费

F( 1) 260.7000 F( 2) 250.3000 F( 3) 235.2000 F( 4) 216.6000 F( 5) 156.0000 F( 6) 140.5000 F( 7) 131.0000 F( 8) 116.2000 F( 9) 84.20000 F( 10) 62.00000 F( 11) 51.00000 F( 12) 61.00000 F( 13) 76.20000

F( 14) 83.00000

F( 15) 97.00000

S5点到需要铺设管道的路上的各节点的单位运输费

F( 1) 255.7000 F( 2) 245.3000 F( 3) 225.2000 F( 4) 206.6000 F( 5) 146.0000 F( 6) 130.5000 F( 7) 121.0000 F( 8) 111.2000 F( 9) 79.20000 F( 10) 57.00000 F( 11) 33.00000 F( 12) 51.00000 F( 13) 71.20000

F( 14) 73.00000

F( 15) 87.00000

S6点到需要铺设管道的路上的各节点的单位运输费

F( 1) 265.7000 F( 2) 255.3000 F( 3) 235.2000 F( 4) 216.6000 F( 5) 156.0000 F( 6) 140.5000 F( 7) 131.0000 F( 8) 121.2000 F( 9) 84.20000 F( 10) 62.00000 F( 11) 51.00000 F( 12) 45.00000 F( 13) 53.00000

F( 14) 11.00000

F( 15) 28.00000

S7点到需要铺设管道的路上的各节点的单位运输费

F( 1) 280.7000 F( 3) 250.2000 F( 5) 171.0000 F( 7) 146.0000 F( 9) 104.2000 F( 11) 66.00000 F( 13) 38.20000 F( 15) 2.000000

F( 2) 270.3000 F( 4) 231.6000 F( 6) 155.5000 F( 8) 136.2000 F( 10) 77.00000 F( 12) 56.00000 F( 14) 26.00000

(2)根据以上结果, 继续求解最小总费用的模型

si(i1,,7)表示第i个钢管厂的最大生产量，fi,j表示从i地运往j地的单位运价，每单

该网络中每段弧上的两个数字，前者是该段弧的容量，后者是与该段弧相应的费用。符号表示该段弧容量无限制。

图中：si(i1,,S7)表示第i个钢厂的生产能力

pi(i1,,7)表示第i个钢厂生产钢管的销价

fi,j表示从i地运往j地的单位钢管的运费 cm表示运往Aj的钢管运往铺道上的费用 dm(m1,2,15) 表示运往Aj地的钢管数目

网络求解的具体方法如下:

（图四）

对网络G(N,A)的每一段弧(ni, nj)，除了容量c(ni, nj)之外，还附有另一非负实数l(ni, n总费用，及

)，称之为费用。要求构造一个从源到汇的最大网络流，同时使流的

l()

达到最小。

本问题的具体解法是

(ni, nj)A

l(n,n

)(ni,nj)

（1）任取一个取整数值的网络流，设流的值为v，要求在所有值为v的流中，的总费

用最小。显然l()0

（2）构造伴随增量网络G()，除容量外，对G()的每一段正向的弧，再按如下方式

定义一个费用，即：(i)对G()每一段正向的弧(ni, nj)，定义费用为

l'(ni, nj)l(ni, nj)。(ii)对G'()每一段正向的弧(ni, nj)，定义费用为l'(ni, nj)l(ni, nj)

（3）在G()上求出从源到汇的所有路径，定义每一条路径的费用为

l()

(ni, nj)

l(n,n

)

从中选出费用最小的路径，记为，如果G'()上不存在由源到汇的路径，转向步骤（5），否则继续。

步骤（2）

（5）判断最优解是否满足生产时至少生产500单位的条件，如果不满足，则将该厂的流

增加至500或减少到0，然后返回步骤（1），否则，此时所得到的流是最小费用最大流，算法结束。

首先，根据以下准则，确定出求图（四）的最优解的初始解。

将上述数据作为我们的初始可行解，由后面的程序即可求出其最小费用为：1291630万元，其具体的订货、运输安排如下：

（表三）

问题二

1．模型的建立

参数变化引起系统特性变化的百分数

参数变化的百分数

当pi变化pi时，对应的最优费用为ZZ，对应的最优解为xi, jxi, j，则：



zpi

piZZ/Z



pi/pipiZ

xi,j/xi,jpi/pi



pixi,j xi,jpi

xi,jpi



Z/ZSiZ

S

Si/SiSiZ

其中：

xi,jSj



xi,j/xi,jSj /Sj

Sixi,j xi,jSj

表示特性z关于参数pi的灵敏度 Spi

Spii,j表示特性xi,j关于参数pi的灵敏度

SSzi表示特性z关于参数pi的灵敏度

SSij,j表示特性xi,j关于参数pi的灵敏度

我们不妨仍以问题一中的模型作为本问题的模型，只是pi,si为变量而已。那么本问题的模型如下：



minz0.05{(1[yj])(2yj[yj])(1yj1)(2yj1[yj1])}

15x

j1

xi, jfi, jpixi, j

j1i1

i1j1

157715

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1

 i

当Si不生产时 0 yyxi, j



j

i17



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2．模型求解

当一些量变化时，我们可以运用问题一的解法求出变化后的最优解，然后运用上述灵敏度的定义求出其最优解。

（1）我们不妨以上述两个变化来反映其变化的程度（单位：亿元），由附录中的程序可

由上述表格可以知道，第6个钢管厂钢管的销价对总费用的影响最大，对购运计划的影响也最大

（2）同理可得由于钢管厂生产能力发生变化对最优解的影响如下

由上可得：钢管厂S1的钢管产量的上限的变化对购运计划的总费用影响最大，钢管厂S3的产量上限的变化对购运计划影响最大。

问题三

1．模型建立

与问题一相同的方法可以建立以下模型：



minz0.05{(1[yj])(2yj[yj])(1yj1)(2yj1[yj1])}

j1

xi, jfi, jpixi, j

j1i1

i1j1

157715

s.t. xi, jSi i

j1

xi, j500 i

j1

当Si生产时 1  i

当Si不生产时 0 yyxi, j



j

i1



yjyj1Aj, j1 [yj][yj1]Aj, j11

xi, j0

2．模型的求解

按问题一的方法，运用附录中的程序，求出单位钢管从Si运到Aj的最小费用f



i,j

，然

后运用与问题一一样的准则求出，建立如下网络模型，并用类似的方法求出本问题的最优解

（图四）

运用问题一的解法可以建立如下的网络流问题进行穷举求解。

S21

F( 20) 115.0000

F( 21) 130.0000

S22

F( 1) 215.7000 F( 3) 190.2000 F( 5) 111.0000 F( 7) 86.00000 F( 9) 114.2000 F( 11) 146.0000 F( 13) 171.2000 F( 15) 192.0000 F( 17) 145.0000 F( 19) 145.0000

F( 21) 180.0000

S23

F( 1) 230.7000 F( 3) 200.2000 F( 5) 121.0000 F( 7) 96.00000 F( 9) 48.20000 F( 11) 86.00000 F( 13) 111.2000 F( 15) 132.0000 F( 17) 85.00000 F( 19) 100.0000

F( 21) 115.0000

S24

F( 1) 260.7000 F( 3) 235.2000 F( 5) 156.0000 F( 7) 131.0000 F( 9) 84.20000 F( 11) 51.00000 F( 13) 76.20000 F( 15) 97.00000 F( 17) 50.00000 F( 19) 70.00000

F( 21) 80.00000

S25

F( 2) 205.3000 F( 4) 171.6000 F( 6) 95.50000 F( 8) 71.20000 F( 10) 142.0000 F( 12) 146.0000 F( 14) 178.0000 F( 16) 110.0000 F( 18) 150.0000 F( 20) 165.0000

F( 2) 220.3000 F( 4) 181.6000 F( 6) 105.5000 F( 8) 86.20000 F( 10) 82.00000 F( 12) 101.0000 F( 14) 118.0000 F( 16) 44.00000 F( 18) 90.00000 F( 20) 105.0000

F( 2) 250.3000 F( 4) 216.6000 F( 6) 140.5000 F( 8) 116.2000 F( 10) 62.00000 F( 12) 71.00000 F( 14) 83.00000 F( 16) 80.00000 F( 18) 55.00000 F( 20) 70.00000

F( 1) 200.7000 F( 3) 170.2000 F( 5) 146.0000 F( 7) 121.0000 F( 9) 79.20000 F( 11) 33.00000 F( 13) 71.20000 F( 15) 87.00000 F( 17) 32.00000 F( 19) 50.00000 F( 21) 75.00000

F( 2) 190.3000 F( 4) 206.6000 F( 6) 130.5000 F( 8) 111.2000 F( 10) 57.00000 F( 12) 51.00000 F( 14) 73.00000 F( 16) 75.00000 F( 18) 50.00000 F( 20) 65.00000

S26

F( 1) 265.7000 F( 3) 235.2000 F( 5) 156.0000 F( 7) 131.0000 F( 9) 84.20000 F( 11) 51.00000 F( 13) 16.20000 F( 15) 28.00000 F( 17) 50.00000 F( 19) 36.00000 F( 21) 0.0000000

F( 2) 255.3000 F( 4) 216.6000 F( 6) 140.5000 F( 8) 121.2000 F( 10) 62.00000 F( 12) 37.00000 F( 14) 11.00000 F( 16) 80.00000 F( 18) 37.00000 F( 20) 10.00000

S27

F( 1) 280.7000 F( 3) 250.2000 F( 5) 166.0000 F( 7) 146.0000 F( 9) 104.2000 F( 11) 64.00000 F( 13) 38.20000 F( 15) 2.000000 F( 17) 63.00000 F( 19) 55.00000 F( 21) 26.00000

F( 2) 270.3000 F( 4) 226.6000 F( 6) 155.5000 F( 8) 136.2000 F( 10) 82.00000 F( 12) 56.00000 F( 14) 26.00000 F( 16) 100.0000 F( 18) 50.00000 F( 20) 32.00000

3．在确定出上述结果后，运用下列准则，确定下列初始解，再利用相同的方法编制附录中的程序。

从而可得到如下最优解：

总的最小费用为1396099万元，具体的订货和运输计划详细见下表

（表四）

五、结果分析

另外，我们借助于Lingo软件求解，同时进行了灵敏度分析（具体见附录中的程序结果）。

六、模型的评价及改进

1．优点：

1）本问题中运用了现代使用较广的网络流算法，同时又结合枚举法进行求解。这样模型的推广性较强，计算结果较为准确

2）问题将费用流转化为网络流，具有较强的推广性和准确性

3）本问题构造出的模型算法较简单，也可以运用手算的方法来得到比较满意的结果。

2．缺点：

1）由于本问题有现成的比较先进的解法，但由于缺乏基本的数学软件资料，不能将其准确求解。

2）于在求解最短路时，我们用人工计算容易将问题复杂化，同时，容易出错。

3）作为图论问题的技术而言，求解过程较难，且不易求出最优解

3．模型改进

可以运用一些分类准则，将该图分类，也可以采用模糊聚类的方法分组

七、模型的运用及推广

参考文献

[1] 许国志主编，《系统科学大词典》，云南科技出版社，云南，1994。

[2] 杜端甫，《运筹图论（图、网络理论中的运筹问题）》，北京航空航天大学出版社，北京，1990。

[3] 雷功炎，《数学模型讲义》，北京大学出版社，北京，1999。

附录

附录一

1．求解Si(i1,,7)到Aj(j1,,15)点的单位运费最小的最优路径，并将S2的数据代入求出其解的源程序清单

MODEL:

SETS:

CITIES /1..33/: F;

ROADS( CITIES, CITIES)/

1,2

2,3 2,16

3,4 3,17

4,5 4,18

5,6 5,19

6,7 6,20

7,8 7,21 7,22

8,9 8,23

9,10 9,24

10,11 10,25

11,12 11,26

12,13 12,27

13,14 13,28

14,15 14,29 14,30

15,31 15,32

16,33

17,33

18,33

19,33

20,33

21,33

22,33

23,33

24,33

25,33

26,33

27,33

29,33

30,33

31,33

32,33/: D;

! D( i, j) is the distance from city i to j;

ENDSETS

DATA:

! Here are the distances that correspond to the

above links;

D =

10.4

30.1 0.3

75.0 0.2

60.6 60

19.4 1

20.5 0.5

20.1 1.0 3.1

68.0 1.2

48.0 4.2

30.0 7.0

22.0 1.0

21.0 1.0

42.0 6.2

50.0 11.0 3.0

2.0 2.0

205.0

190.0

125.0

110.0

95.0

85.0

70.0

110.0

135.0

145.0

155.0

165.0

180.0

175.0

190.0

190.0;

F( @SIZE( CITIES)) = 0;

@FOR( CITIES( i)| i #LT# @SIZE( CITIES):

F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))

);

END

2．对求从S2到Aj的运行结果

Feasible solution found at step: 0

Variable Value

F( 1) 215.7000

F( 2) 205.3000

F( 3) 190.2000

F( 4) 171.6000

F( 5) 111.0000

F( 6) 95.50000

F( 7) 86.00000

F( 8) 71.20000

F( 9) 114.2000

F( 10) 142.0000

F( 11) 146.0000

F( 12) 156.0000

F( 13) 171.2000

F( 14) 178.0000

F( 15) 192.0000

F( 16) 205.0000

F( 17) 190.0000

F( 18) 125.0000

F( 19) 110.0000

F( 20) 95.00000

F( 21) 85.00000

F( 22) 85.00000

F( 23) 70.00000

F( 24) 110.0000

F( 25) 135.0000

F( 26) 145.0000

F( 27) 155.0000

F( 28) 165.0000

F( 29) 180.0000

F( 30) 175.0000

F( 31) 190.0000

F( 32) 190.0000

F( 33) 0.0000000

附录二，对问题一的订购和运输计划

1，Lingo源程序

MODEL:

! A 6 Warehouse 14 Vendor Transportation Problem;

SETS:

WAREHOUSES / S1 S2 S3 S4 S5 S6/: CAPACITY;

VENDORS/A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15/ : DEMAND; LINKS( WAREHOUSES, VENDORS): COST, VOLUME;

ENDSETS

! The objective;

MIN = @SUM( LINKS( I, J):

COST( I, J) * VOLUME( I, J));

! The demand constraints;

@FOR( VENDORS( J):

@SUM( WAREHOUSES( I): VOLUME( I, J)) =

DEMAND( J));

! The capacity constraints;

@FOR( WAREHOUSES( I):

@SUM( VENDORS( J): VOLUME( I, J))

CAPACITY( I));

! Here is the data;

DATA:

CAPACITY = 800 800 1000 2000 2000 2000;

DEMAND=261 482 515 571 153 373 212 734 330 317 170 257 655 141;

COST=320.3 300.0 258.6 198.0 180.5 163.1 181.2 224.2 252.0 256.0 266.0 281.2 288.0 302.0

360.3 345.2 326.6 266.0 250.5 241.0 226.2 269.2 297.0 301.0 311.0 326.2 333.0 347.0

375.3 355.2 336.6 276.0 260.5 251.0 241.2 203.2 237.0 241.0 251.0 266.2 273.0 287.0

410.3 395.2 376.6 316.0 300.5 291.0 276.2 244.2 222.0 211.0 221.0 236.2 243.0 257.0

400.3 380.2 361.6 301.0 285.5 276.0 266.2 234.2 212.0 188.0 206.0 226.2 228.0 242.0 405.3 386.2

366.6 306.0 290.5 281.0 271.2 234.2 212.0 201.0 195.0 203.0 161.0 178.0;

ENDDATA

END

2．运行结果

Single cols= 0

Optimal solution found at step: 33

Objective value: 1220059.

Variable Value Reduced Cost

VOLUME( S3, A3) 0.0000000 -0.1220703E-04 VOLUME( S3, A4) 0.0000000 -0.6103516E-05

3．灵敏度分析

Ranges in which the basis is unchanged:

Objective Coefficient Ranges

Righthand Side Ranges

附录三、对问题三最短路的求解

1．源程序清单

MODEL:

SETS:

CITIES /1..34/: F;

ROADS( CITIES, CITIES)/

1,2

3,4 3,23

4,5 4,24

5,6 5,25

6,7 6,26

7,8 7,27 7,28

8,9 8,29

9,10 9,16

10,11 10,30

11,12 11,17

12,13 12,19

13,14 13,20

14,15 14,21 14,31

15,32 15,33

16,34

17,18 17,19 17,34

18,34

19,20 19,34

20,21 20,34

21,34

22,34

23,34

24,34

25,34

26,34

27,34

28,34

29,34

30,34

31,34

32,34

33,34/: D;

! D( i, j) is the distance from city i to j;

ENDSETS

DATA:

! Here are the distances that correspond to the

above links;

D =

10.4

30.1 0.3

75.0 0.2

60.6 60

19.4 1

20.1 1.0 3.1

68.0 1.2

48.0 4.2

30.0 7.0

22.0 1.0

21.0 1.0

42.0 6.2

50.0 11.0 3.0

2.0 2.0

110.0

13.0 19.0 145.0

150.0

26.0 145.0

10.0 165.0

180.0

205.0

190.0

125.0

110.0

95.0

85.0

70.0

135.0

175.0

190.0

190.0;

ENDDATA

! If you are already in City 10, then the cost to

travel to City 10 is 0;

F( @SIZE( CITIES)) = 0;

@FOR( CITIES( i)| i #LT# @SIZE( CITIES):

F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))

);

END

2．运行结果

Variable Value

F( 1) 170.7000

F( 2) 160.3000

F( 3) 140.2000

F( 4) 98.60000

F( 5) 38.00000

F( 6) 20.50000

F( 7) 3.100000

F( 8) 21.20000

F( 9) 64.20000

F( 10) 92.00000

F( 11) 96.00000

F( 12) 106.0000

F( 13) 121.2000

F( 14) 128.0000

F( 15) 142.0000

F( 16) 60.00000

F( 17) 95.00000

F( 18) 100.0000

F( 19) 105.0000

F( 20) 115.0000

F( 21) 130.0000

附录四、确定问题三订购、运输计划及总费用的源程序

1．源程序清单

MODEL:

! A 6 Warehouse 8 Vendor Transportation Problem;

SETS:

WAREHOUSES / S1 S2 S3 S5 S6/: CAPACITY;

VENDORS/A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21/ : DEMAND;

LINKS( WAREHOUSES, VENDORS): COST, VOLUME;

ENDSETS

! The objective;

MIN = @SUM( LINKS( I, J):

COST( I, J) * VOLUME( I, J));

! The demand constraints;

@FOR( VENDORS( J):

@SUM( WAREHOUSES( I): VOLUME( I, J)) =

DEMAND( J));

! The capacity constraints;

@FOR( WAREHOUSES( I):

@SUM( VENDORS( J): VOLUME( I, J))

CAPACITY( I));

! Here is the data;

DATA:

CAPACITY = 800 800 1000 2000 2000;

DEMAND=261 482 515 571 153 373 212 754 330 322 170 257 655 141 22 185

60 161 179 100;

COST=320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302 220 255 260 265 275 290

360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 301 326.2 333 347 265 300 305 300 320 335

375.3 355.2 336.6 276 260.5 251 241.2 240 203.2 237 241 256 266.2 273 287 199 245 255 260 270

345.3 325.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 230 187 205 205 220 230

405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 187 166.2 161 178 230 200 187 186 160 150;

ENDDATA

END

2．运行结果

Single cols= 0

Optimal solution found at step: 36

Objective value: 1320666.

Variable Value Reduced Cost

VOLUME( S1, A2) 0.0000000 53.00001 VOLUME( S1, A3) 0.0000000 52.99999

相关文章