答卷编号（参赛学校填写）：
答卷编号（竞赛组委会填写）：
论文题目： A 选址问题
组 别： 第六组
参赛队员信息(必填)：
姓 名 专业班级及学号
联系电话 参赛队员1 参赛队员2 参赛队员3
参赛学校：
矿物加工厂选址问题
摘要
本文针对工厂的采矿点的地理位置和产量进行综合分析. 使用图论中Dijkstra算法和线性规划及非线性规划对路线进行计算，设计出了一个使得总运输量最小的工厂选址方案.
针对问题一，我们根据图中采矿点的位置，利用Dijkstra算法分别求出了当工厂选址在1,2,3,4,5,6,7位置时各采矿点与其的最短距离，并算出总距离，并根据采矿点的产量，利用matlab软件对距离用产量进行加权，顺利解得总运输量：YSL1?1975，YSL2?1095，YSL3?995，YSL4?1115，YSL5?920，
YSL6?1060，YSL7?1510. 得到当工厂选址在5时总运输量最小，为920吨*
千米.
针对问题二，考虑经济，社会条件状况等我们设立了两种方案.
模型一：在采矿点周围允许建立工厂的范围内，不满足修公路的条件，即选址在原有的道路上，假设工厂分别位于所有的八条路线之一上，设其距某点距离为x，用带有x的表达式表示其距其他各点距离，利用LINGO软件加权求和取最小值后得出结论：工厂选址可以在任意路段的前提下，依然是选在采矿点5处，总运输量最小，为920千吨*千米.
模型二：自然条件完全满足的条件下，即为满足最小运输量允许随意修建公路，开设工厂. 在实际问题中，各各采矿点的地理位置为确定的值，故在本题中不妨假设出各采矿点的位置坐标，利用LINGO软件的非线性规划模型，求解出随机x，y（x<=110,y<=50）坐标点对各采矿点加权距离和的最小值，结论为：在点（88.7,15.4）建立工厂，有最小总运输量：831.9千吨*千米. 并通过查找资料，分析得到结论，若建四级公路，则有盈利可能的结论. 该模型可以根据实际问题作出更改，得出符合实际的结论，具有较高的普遍适用价值.
关键字：Dijkstra算法；非线性规划；最小运输量
1
一、问题重述
某工厂有7个采矿点，矿石在采矿点被采下后，须统一运输到工厂处理. 采矿点地理分布如图所示.
25 35 7 6 5 15 20 60 1 55 2 45 3 10 4 图中采矿点之间有直线相连表示他们之间有道路相通，直线上的数字表示他们之间的距离（单位：千米）.
表：各采矿点每天的产量（单位：千吨） 采矿点 1 2 3 4 5 6 7 产量 4 1 1 6 7 2 3 问题： 1、若工厂选在某个采矿点，请为工厂选址，使得总运输量最小.
2、若所有采矿点在一个110千米×50千米的范围内，这个区域内任意点都可以建设工厂，请重新为工厂选址. 若需要其他数据，可以在满足图中距离的前提下自行设置.
2
二、问题分析
1）对工厂地址选择的理解
模型一：由于重新架设公路会导致成本大大增加，而且后期节省的运费不足以满足增加的成本，工厂地址仅选择在现有的道路和采矿点上，不能在其它区域任意开设.
模型二：架设新公路的成本增加量，小于后期节省的总运费，工厂地址选择可在所有采矿点的一个110千米×50千米的范围内，这个区域内任意点都可以建设工厂，并且不影响工厂内的道路稳定和其它问题. 2）对运输量的理解
不考虑采矿的时间，即认为每天都需运送题中所给数据的量，而且都可以一次运完，不存在往返的问题，运输量即为距离乘以产量.
三、问题假设
1） 每个采矿点之间的单位重量的单位运费都相同. 2） 选址只考虑经济效应，不考虑对其它的影响. 3） 采矿点和工厂都当成点考虑，不考虑实际尺度. 4） 地形状况良好，条件允许可以修建公路.
四、符号说明
YSLi:工厂选址在iJLij:i
时的总运输量.
点与j点之间的最小距离. i点的产量.
Wi：第
xi:采矿点的代号.
V(G):任意采矿点，即xi?V(G). I:所指道路的开始出发矿点. (I?1,2?7)J:所指道路的终止矿点. (J?1,2?7)
YSL(x):道路在距离为x处的总运输量.
x:点J距离矿址点的路径长度.
3
五、问题一的解答
根据题中所述，若工厂选址在七个采矿点之一，则我们可以用图论中Dijkstra算法来求出当采矿点位于1到7时的每个采矿点到工厂的最短距离，记为JLij.
工厂选址在1点时：
设1为顶点x1，连接连个位置的公路为图的边，记为e,记w（e）为图的边e的长. 对任意的顶点xi? V(G)，寻求轨迹P（x1,x），使得
w?p?x1,x???min?w?p??，
即从x1到x的所有轨道长中寻求最小的一个. W（P）是轨道P上的各边长之和.
我们利用Dijkstra算法来进行求解，步骤如下： （1） 令l(x0)=0，l?x???,x?x0;JL11?{x0},i?0;
（2） 对每个x?JLi1,用min{l(x0),l(xi)?w(xi,x)}代替l(x)；设vi?1是l(x)使
取最小值的JLi1中的顶点（JLi1是JLi1的补集），令
JL(i?1)1?JLi1?{xi?1}(i?0,1,2…)；
（3） 若i?|V(G)|?1，则停止；若i?|V(G)|?1，令i?i?1转（2）. 由上述算法经过有限的步骤我们可以得出任意采矿点xi到所有采矿点的最小距离（千米），如表所示：
采矿点 1 2 3 1 2 3 4 5 6 7
4
4 110 55 10 0 30 65 90 5 105 50 20 30 0 35 60 6 70 15 55 65 35 0 25 7 95 40 80 90 60 25 0 0 55 100 110 105 70 95 55 0 45 55 50 15 40 100 45 0 10 20 55 80