仓库地址选择的图论模型

由天下分享时间：2025/1/5 23:08:44 加入收藏我要投稿点赞

No.1 韶关学院学生数学建模论文集第一期（2002年10月）

仓库地址选择的图论模型

彭彩英⑴,刘枫⑵,黄春华⑶

(1) 韶关学院2000级数学系数学与应用数学本科1班 (2) 韶关学院2000级数学系数学与应用数学本科1班 (3) 韶关学院2000级计算机科学与技术本科2班

[摘要]:仓库地址的选择是一个最优化问题,因此我们利用“图论的最短路”问题的思想，对模型作出了简

化，提出了一般的解法，另外我们还了简单明了的物理模拟的方法确定了总费用最少的位置.对问题1，我们确定了建立仓库的最优位置在E点，运输的总费用最少为Q5=6593元；对问题2，最优位置也在E点，运输的总费用与建库费之和最少为Q5=13213元. 本文最后对所建模型的优缺点进行了分析.

关键词：仓库选址；最短路；最少费用

1 问题的提出

某乡有十二村A，B，C、、、、、、L，如图，两村连线上数字表示两村间的距离（单位：千米）.各村上缴粮食数量依次为70、80、60、30、65、100、20、40、30、45、35、20吨.现计划在村内或道路上建一仓库来储存这些粮食.现要求如下：（1），若整个公路上的运费为1.5元/吨*千米，确定建立仓库的位置，使运输的总费用最少. （2），若公路BF、FE、ED、DG、GH上的运费为2元/吨*千米，而其余公路上的运费为1.5元/吨*千米，各村的建库费分别为5100、5000、5200、5150、5400、5300、5200、5250、5400、5110、5010、5120元，而公路上的建库费与最近的村相同.设计确定使总费用之和最少的仓库位置的方案.

C 10 I

8 3 4 3

A 5 B D 3 G 2 H J 3 L 6 5 5 5

F 2 E 8 K 考虑的一般都为费用问题，如何建仓库才能使农民较容易上缴，不用花那么多费用上缴必须的粮食，为农民省点钱，这样农民也不会抱怨太大，所以考虑在什么位置建仓库，才能使各个村去缴粮食的路程最短，这样才能减少运费，使所有村上缴粮食的总费用最少，有时还要考虑建立仓库的费用.

本问题的实质就是用图论的方法，在图中找一个位置建库，求出各村到建库点的最短路，并找出使总费用最少的建库点，显然这是一个最短路问题，图论中找最短路的方法很多，我们可以把几种方法结合起来，就可简单地找出最短路.，使得运输粮食的总费用最少.

2 模型的假设

（1）不考虑在各村建的仓库的经济寿命期相同. （2）假设各村之间可以随意经过.

21A21A第一期（2002年10月）韶关学院学生数学建模论文集 No.1 （3）假设建库费仅指建仓库的原材料费. （4）不考虑各村之间可以随意经过.

3 符号约定

Li,j：从A 村到 A村的最短路距离. xi：各村上缴的粮食量.

Ai（i=1?12）：分别表示十二各村A，B，C，D，E，F，G，H，I，J，K，L.

C ：整个公路上的运费（1.5元/吨千米）.

Cij ：从A 村到 A村的最少公路运费.（千米）. Wj ：各村的建库费. Qj：运输粮食的总费用.

W ：建库费也与总运费的总和.

4 模型的建立与求解

4.1 如果整个公路的运费相同，则确定建库位置，使总运费最少.

对此问题，我们采用分析法建立数学模型，粮食运输的总费用Qj应等于村Ai（i=1?11）到村Aj粮食运费运输的费用之和.而村Ai到村Aj的粮食运费应该等于村Ai到村Aj的距离

Lij，村Ai上缴的粮食数量xi和每吨千米的运费C的乘积.故此问题的目标函数为：

min Qj??LCxiji?111i（j=1?12）

根据上面的表达式可知，因为C,xi均为常数，只有LIJ为变量，所以要使运输粮食的总费用Qj最少，必须使村Ai到村Aj的距离Lij最短，故我们现在要找最短路，由于本题的图形是比较简单的，所以我们采用了人工与计算机相结合的方法，寻找各个村到选定村的最短路.通过对它们比较分析，我们找到了运输粮食的最少费用为Q5，同时选出了需要最少运费的位置在E点及相应的路线.找最短路的算法如下：（1）先定点A1，找出其他十一个点A2，A3?

到A1 的最短路L21,L31,?L121.

（2）根据运输粮食的总费用Qj的表达式算出其他十一个点到点A1 的运费之和Q1. （3）同理，算出到点A2，A3?

的运费分别是Q2,Q3,?Q12

（4）对Q1,Q2,Q3,?Q12进行比较，找出运费最少的，即为运输粮食的总费用的最优解Q5

No.1 韶关学院学生数学建模论文集第一期（2002年10月）

现在已经确定了建立仓库的位置在E点，运输的总费用（单位：元）最少为

Q5??Li5xiCi?111

?6593各个点到点E（A5）的最短线如下图：（假如E村（L55=0）的粮食运费为零）

C I 3 3 G 2 J 5 B D 4 L A 5 5 H 5 3 F 2 E 8 K

由图可知各个点到点的最短距离（单位：千米）分别如下

L15=12，L25=7，L35=8，L45=5，L65=2，L75=8 L85=10，L95 =14，L105=13，L115=8，L125=16

图中边的赋权表示两个村之间的距离.

现设在任意两个村y1，y2之间建仓库，它们需要上缴的粮食数量分别为x1,x2吨，如图

y1 y2 L

设仓库位置距x1的距离为x千米，两村的距离L 为千米，则两村上缴粮食的总运费为：

w=Cx1x+C(L?x)x2=Cx(x1?x2)?CL

由上式可得

当x1?x2时，x=0，W达到最小值CL（在y1点）当x1?x2 时，x=L时（在y2点），W达到最小值

当x1?x2 时，x取任意值，W都为CL，故可取在两个端点

由上可知，无论什么情况，仓库都没有必要建在公路上，所以不用考虑它的总费用.只在村内建仓库就可以了.

上述已经证明了，只在村内建仓库，所以我们还可以采用物理模拟法解此问题.如图所示.

第一期（2002年10月）韶关学院学生数学建模论文集 No.1

先任意选定某一个点，比如选在L点，则可求出其他各个点到点L的最短距离，然后用模拟法，做一个带有坐标刻度的板面，在相应村所在的坐标位置处钻洞，通过每一个洞穿过一条绳子，一端垂在板下并吊一个砝码，其重量与村需上缴的粮食数量xi相对应，另一端都在板面上，且与同一个小环相连，最后小环停留下来的平衡位置，就是使总费用最少的那个位置，即建立仓库的位置.

4.2 若公路BF，FE，ED，DG，GH上的运费改变了，为2元/吨千米，运输总费用也发生了变化，由于这只是在局部路段的费用发生了变化，如果从某个村到建仓库的地点没有经过这些路段，则在整个路程中每千米每吨粮食的运费仍为1.5元，否则若经过了某个路段，则运费分为两部分，一部分是经过这个路段的运费，另一部分为经过的其它路段的费用.此问题还要考虑建库费，故我们的目标函数为： minWj?Qj?wj??Ci?111ijxi?wj(j?1..12)

此问题的关键也是求最短路问题，我们用类似问题1的方法找最短路.通过比较得出了使总费用最少的建库位置是在E点，运输粮食总费用与建库费的总和最少为：W5 各个村到点的最短路线如下图：

C(60) I(30) 4.5 5

7.5 B(80) D(30) G(20) 4 H(40) 4.5 L(20) A(70) 10 10 6 J(45) 7.5 F(80) 4 E 12 K(35)

图中边的赋权即为此路段的路程与其每千米每吨的运费乘积，顶点的权为相应村所需上缴的

No.1 韶关学院学生数学建模论文集第一期（2002年10月）粮食数量（单位：吨）.

由上图可得各个村到村E的最少公路运费（单位：元）如下： C15?21.5,C25?4,C35?18.5,C45?10,C65?4

C75?16,C85?20,C95?24,C105?19.5,C115?12,C125?24 这里设村E（A5）的粮食运费为 C55=0元

所以粮食运输费与建库费的总和（单位：元）最少为： W5??Ci?111I5ix?w5?7813?5400?13213

找各个点到点E（A5 ）的最少公路费 Ci5（i=1..12）的算法如下：

（1）把题目中的图的边赋权为经过这两点之间的公路运费，然后找出其它各点到点A(A1)

的最少公路运费Ci1 (I=1..12)

（2）同理，找出其它各点的最少公路运费Ci2,Ci3,..Ci12.