1、22 仓库地址选择的图论模型摘要:仓库地址的选择是一个最优化问题,因此我们利用“图论的最短路”问题的思想，对模型作出了简化，提出了一般的解法，另外我们还了简单明了的物理模拟的方法确定了总费用最少的位置.对问题1，我们确定了建立仓库的最优位置在 E 点，运输的总费用最少为 =6593 元；对问题 2，最优位置也在5QE 点，运输的总费用与建库费之和最少为 =13213 元.5Q本文最后对所建模型的优缺点进行了分析.关键词：仓库选址；最短路；最少费用1 问题的提出某乡有十二村 A，B，C、 、 、 、 、 、L，如图，两村连线上数字表示两村间的距离（单位：千米）.各村上缴粮食数量依次为70、80、
2、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 I8 3 4 3 A 5 B D
3、 3 G 2 H J 3 L 6 55 5 F 2 E 8 K考虑的一般都为费用问题，如何建仓库才能使农民较容易上缴，不用花那么多费用上缴必须的粮食，为农民省点钱，这样农民也不会抱怨太大，所以考虑在什么位置建仓库，才能使各个村去缴粮食的路程最短，这样才能减少运费，使所有村上缴粮食的总费用最少，有时还要考虑建立仓库的费用.本问题的实质就是用图论的方法，在图中找一个位置建库，求出各村到建库点的最短路，并找出使总费用最少的建库点，显然这是一个最短路问题，图论中找最短路的方法很多，我们可以把几种方法结合起来，就可简单地找出最短路.，使得运输粮食的总费用最少.2 模型的假设（1） 不考虑在各村建的仓库的
4、经济寿命期相同.（2） 假设各村之间可以随意经过.（3） 假设建库费仅指建仓库的原材料费.（4） 不考虑各村之间可以随意经过.3 符号约定：从 A 村到 A 村的最短路距离.jiL,第一期（2002 年 10 月） 韶关学院学生数学建模论文集 No.123 ：各村上缴的粮食量.ix（i=112） ：分别表示十二各村 A，B，C，D，E，F，G，H，I，J，K，L.iAC ：整个公路上的运费（1.5 元/吨千米）.：从 A 村到 A 村的最少公路运费.（千米）.ij：各村的建库费.jW：运输粮食的总费用.jQW ：建库费也与总运费的总和.4 模型的建立与求解4.1 如果整个公路的运费相同，则确定
5、建库位置，使总运费最少.对此问题，我们采用分析法建立数学模型，粮食运输的总费用 应等于村jQ（ i=111）到村 粮食运费运输的费用之和.而村 到村 的粮食运费应该等于村iAjAiAj到村 的距离 ，村 上缴的粮食数量 和每吨千米的运费 C 的乘积.故此问题的目ijijLi ix标函数为： min （j=112）1iijjCLQ根据上面的表达式可知，因为 C, 均为常数，只有 为变量，所以要使运输粮食的总费ixIJL用 最少，必须使村 到村 的距离 最短，故我们现在要找最短路，由于本题的图jQiAjij形是比较简单的，所以我们采用了人工与计算机相结合的方法，寻找各个村到选定村的最短路.通过对它
6、们比较分析，我们找到了运输粮食的最少费用为 ，同时选出了需要最少5Q运费的位置在 E 点及相应的路线.找最短路的算法如下：（1）先定点 ，找出其他十一个点 ， 到 的最短路 , , .1A2A312A21L312（2）根据运输粮食的总费用 的表达式算出其他十一个点到点 的运费之和 . jQ（3）同理，算出到点 ， 的运费分别是 , ,23122Q312（4）对 , , , 进行比较，找出运费最少的，即为运输粮食的总费用的最优解1Q2315现在已经确定了建立仓库的位置在 E 点，运输的总费用（单位：元）最少为24 65931iiCxLQ各个点到点 E（ ）的最短线如下图：A（假如 E 村（ =0
7、）的粮食运费为零）5LC I3 3 G 2 J5 B D 4 LA 5 5 H 5 3F 2 E 8 K由图可知各个点到点的最短距离（单位：千米）分别如下=12， =7， =8， =5， =2， =815L2535L4565L75=10， =14， =13， =8， =168910112图中边的赋权表示两个村之间的距离.现设在任意两个村 ， 之间建仓库，它们需要上缴的粮食数量分别为 吨，如1y2 21,x图xy1 y2L设仓库位置距 的距离为 x 千米，两村的距离 L 为千米，则两村上缴粮食的总运费为：1w= + =xC12)(C)(21由上式可得当 时，x=0，W 达到最小值 CL（在 点）
8、21x1y当 时，x=L 时（在 点） ，W 达到最小值2y当 时，x 取任意值，W 都为 CL，故可取在两个端点21由上可知，无论什么情况，仓库都没有必要建在公路上，所以不用考虑它的总费用.只在村内建仓库就可以了.上述已经证明了，只在村内建仓库，所以我们还可以采用物理模拟法解此问题.如图所示.第一期（2002 年 10 月） 韶关学院学生数学建模论文集 No.125 先任意选定某一个点，比如选在 L 点，则可求出其他各个点到点 L 的最短距离，然后用模拟法，做一个带有坐标刻度的板面，在相应村所在的坐标位置处钻洞，通过每一个洞穿过一条绳子，一端垂在板下并吊一个砝码，其重量与村需上缴的粮食数量
9、相对应，另ix一端都在板面上，且与同一个小环相连，最后小环停留下来的平衡位置，就是使总费用最少的那个位置，即建立仓库的位置.4.2 若公路 BF，FE，ED，DG，GH 上的运费改变了，为 2 元/吨千米，运输总费用也发生了变化，由于这只是在局部路段的费用发生了变化，如果从某个村到建仓库的地点没有经过这些路段，则在整个路程中每千米每吨粮食的运费仍为 1.5 元，否则若经过了某个路段，则运费分为两部分，一部分是经过这个路段的运费，另一部分为经过的其它路段的费用.此问题还要考虑建库费，故我们的目标函数为：min )12.(1jwxCQWiijjjj此问题的关键也是求最短路问题，我们用类似问题 1
10、的方法找最短路.通过比较得出了使总费用最少的建库位置是在 E 点，运输粮食总费用与建库费的总和最少为： 5W各个村到点的最短路线如下图：C(60) I(30)4.5 57.5 B(80) D(30) G(20) 4 H(40) 4.5 L(20)A(70) 10 10 6 J(45)7.5F(80) 4 E 12 K(35)图中边的赋权即为此路段的路程与其每千米每吨的运费乘积，顶点的权为相应村所需上缴26 的粮食数量（单位：吨）.由上图可得各个村到村 E 的最少公路运费（单位：元）如下：4,10,5.8,4,5.216543CCC2,.9206 15987这里设村 E（ ）的粮食运费为 =0
11、元5A5所以粮食运输费与建库费的总和（单位：元）最少为：1324078515 wxCWiiI找各个点到点 E（ ）的最少公路费 （i=1.12）的算法如下：5A5iC（1） 把题目中的图的边赋权为经过这两点之间的公路运费，然后找出其它各点到点 A()的最少公路运费 (I=1.12)11i（2） 同理，找出其它各点的最少公路运费 .1232,ii（3） 比较十二个点的最少公路运费 , 与其相应的建库费的和，得出值1iCii最小的那个就是粮食运输费与建库费总和的最小值.（4） 最后得出粮食运费与建库费总和最少的为 ，即应该把仓库建在 E 点，才能使总5W费用最少.（5） 证明不必要把仓库建在公路上
12、的方法与问题 1 的方法一样，这里就不再证明了.所以只要考虑在村内建仓库的情况就可以了.5 模型的评价（1）模型的优点*运用了图论的建立寻优模型，建模的方法简单易懂，尽管建模过程中应用了图论的最短路理论，但仍可以用初等数学的方法解决问题.*所建模型利用了图的优点，使要解决的问题直观，清晰明了，便于理解.我们的建模的方法具有一定的通用性，对其它类似的问题也适用，并便于应用与实际.（2）模型的缺点*由于本题比较简单，所以我们重点是利用人工与计算机的方法建模求解，可以考虑用其它更一般的方法求解.6 模型的推广本文中村与村之间全部都是用公路连接的，在实际运用中，当各个村之间不仅仅是有公路相通，还有必须经过的桥或铁路时，可以设想，推广运用这一思想，按求最短路和最少运费的原则求解，但要想得到问题的最优解，还必须转化成明确的数学问题，并进行更深入的分析，进一步的探讨.参考文献：（略）
