矿厂选址--数学建模

矿厂选址摘要本文针对采矿场的采矿点的地理位置和产量进行综合分析。使用图论中迪克斯特拉（Dijkstra）算法和线性规划对路线进行计算，设计出了一个使得总运输量最小的矿厂选址方案。针对问题一，我们根据图中采矿点的位置，利用迪克斯特拉（Dijkstra）算法分别求出了当矿场选址在1,2,3,4,5,6,7位置时采矿点与其的总距离，并根据采矿点的产量，利用matlab软件对距离进行加权，顺利解得总运输量：19751YSL，10952YSL，9953YSL，11154YSL，9205YSL，10606YSL，15107YSL。得到当矿厂选址在5时总运输量最小。针对问题二，我们考虑两种方案。方案一：由于经济条件制约，矿厂的地址选择仅限于建在现有的公路和和采矿点上。方案二：随意开设矿厂，矿厂的选择在所有采矿点在一个110千米×50千米的范围内任意一点。一、问题重述某采矿场有7个采矿点，矿石在采矿点被采下后，须统一运输到工厂处理。采矿点地理分布如图所示。图中采矿点之间有直线相连表示他们之间有道路相通，直线上的数字表示他们之间的距离（单位：千米）。表：各采矿点每天的产量（单位：千吨）采矿点1234567产量4116723问题：1、若工厂选在某个采矿点，请为工厂选址，使得总运输量最小。2、若所有采矿点在一个110千米×50千米的范围内，这个区域内任意点都可以建设工厂，请重新为工厂选址。若需要其他数据，可以在满足图中距离的前提下自行设置。76512432535551545206010二、问题分析1）对矿厂地址选择的理解模式一：由于重新架设公路会导致成本大大增加，而且后期节省的运费不足以满足增加的成本，矿厂地址选择仅在现有的道路和采矿点上，不能在其它区域任意开设。模式二：架设新公路的成本增加量，小于后期后期节省的总运费，矿厂地址选择可在所有采矿点的一个110千米×50千米的范围内，这个区域内任意点都可以建设工厂，并且不影响矿场内的道路稳定和其它问题。2）对运输量的理解不考虑采矿的时间，即认为每天都需运送题中所给数据的量，而且跟都可以一次运完，不存在往返的问题，运输量即为距离乘以产量。三、问题假设1）每个采矿点之间的单位重量的单位运费都相同。为方便起见，我们假定为1.2）选址只考虑经济效应，不考虑对其它的影响。3）采矿点和工厂都当成点考虑，不考虑实际尺度。四、符号说明iYSL:工厂选址在i时的总运输量。ijJL:i点与j点之间的最小距离。iW：第i点的产量。ix:采矿点的代号。)(GV:任意采矿点，即ix)(GV。:I所指道路的开始出发矿点。)72,1(I:J所指道路的终止矿点。)72,1(J:)(xYSL道路在距离为x处的总运输量。:x点J距离矿址点的路径长度。五、问题一得解答根据题中所述，若工厂选址在七个采矿点之一，则我们可以用图论和迪克斯特拉（Dijkstra）算法来求出当采矿点位于1到7时的每个采矿点到工厂的最短距离，记为ijJL。工厂选址在1点时：设1为顶点1x，连接连个位置的公路为图的边，记为e,记w（e）为图的边e的长。对任意的顶点ixV(G)，寻求轨迹P（1,xx），使得W（P（1,xx））={()}minpWP，即从1x到x的所有轨道长中寻求最小的一个。W（P）是轨道P上的各边长之和。我们利用迪克斯特拉（Dijkstra）算法来进行求解，步骤如下：（1）令0()=0lx，(x)l=,0110;{},0;xxJLxi（2）对每个x1iJL,用0min{(),()(,)}iilxlxwxx代替()lx；设1iv是(x)l使取最小值的1iJL中的顶点（1iJL是1iJL的补集），令(1)111{}(0,1,2)iiiJLJLxi…；（3）若|()|1iVG，则停止；若|()|1iVG，令1ii转（2）。由上述算法经过有限的步骤我们可以得出任意采矿点ix到采矿点1的最小距离，如表所示：采矿点123456710551001101057095这样，即可求出当矿厂设在采矿点1时各采矿点到矿厂的总运量之和，即：7111(1,2,)iiiYSLWJLi…,7=1975。（用matlab编程求解，程序见附录）同理，可求得矿厂设在其它采矿点时各采矿点到矿厂的总运量之和，结果如下表所示：矿厂地址1234567总运量19751095995111592010601510由上表可知，当矿厂设在采矿点5的时候，总运量最小，为920。六、问题二的解答模式一：考虑最初资金问题，假设最初达不到修建公路的条件，只在现有的道路和采矿点建立矿厂，为以后矿石的运输提供条件。若矿厂建立在道路上（与问题一做比较），设在道路IJ矿厂到各矿点的距离为ix，这样有关各矿点到矿厂的最短路径是与x有关的表达式，经分析当矿点设在道路上，矿点到矿厂的最短路径是线性函数。12345671-255-xx45+x55+x50+x15+x40+x3-4110-x55-x10-xx30-x65-x90-x6-760+x15-x55+x65+x35+xx25-x3-5xx125,100minxx70,45minx10+x20-x55-x80-x5-6105-x50-x20+x30+x35-x60-x2-655+xx45+x55+x50-x15-x40-x2-355+xx45-x55-x15+x40+x4-5xx165,110minxx110,55min10+xx60-xxx95,65min上述表中，均选择与后一个采矿点的距离为x，矿厂与各矿点的距离即为总运输量，在各条道路上设立的最优矿址点):min(JIxx，在ix在I到J移动的范围内，最短距离时该址点的运输量JIYSL:。如果矿厂建在这些道路中,则总运费是x的分段线性函数(定义域为一个有界闭区间),由于有界闭区间上的分段线性函数的最值在关节点或区间端点处达到,而区间端点对应问题一中的情形,因此只需要考虑关节点的总运输量既可。采矿点1-23-46-73-55-62-62-34-5):min(JIxx010020,00045,060,0):(JIYSL109510201020920,99592010951020,10951150,1325采矿点1234567产量4116723模型二:若所有采矿点允许的范围内，这个区域内任意点都可以建设工厂，满足最初的资金周转良好可任意建立公路的条件下，只考虑运输量的最大值，为取得最优解，即现实中七个确定采矿点看为点坐标。在不考虑地形地貌，所满足的路径均为直线的情况下，设立二维坐标系（以1矿点作为坐标原点）确定各矿点的坐标分别为1（0，0）、2（55，0），3（100，0），4（110，0），5（90，17），6（55，15），7（30，15）。