1、17.064636.244916.283012.863121.04816.484911.41719.796223.365.38254.6122.0529.935011.857.763311.722.6814.33479.89111910.0812383.11358.19136.77273.9122.761410.86326.1167.984113.484210.2218368.7910.91218.86398.54016.1513.353.6811.33244.888.672820.87294.558.988.9427.7815.2217.3212.2111.0221.4116.2311.84
2、15.324416.422617.961513.33各乡镇的物资需求量如下表:人数76012814561155944676490728782420889526684882551590917565112412821030643884407120611791117560894322725612461478722394898770995999938333368619830954707111910181268数据处理:2、问题分析 本问题中为了得到最优解,需要求出最短加权(双权)路径,以三个火车站为终点求出最短路根-点图和路径权矩阵,在此基础上结合各点比重求权,得出能使花费最小而效益最大的路径。综上分
3、析,本问题中的最短加权路径选择所受的限制有:a.火车站总数有限且位置固定;b.各个乡镇存在邻接最短路径;C.各根点权重(与乡镇人数正相关)及各路径权重可求。3、变量定义 本问题过程中所涉及的变量有: a.各乡镇需求量; b.火车站货物运往的乡镇及途径路径; C.总路径长度;4、问题假设 在建模前假设: 不考虑运输车在不同路段的损耗情况; 外界潜在因素,如仓储,转运成本等不予考虑; 相邻乡镇间的需求量增减不存在相互作用; 不考虑运输量对火车的磨损情况。5、建模求解 首先调用trans函数(自编,功能为将已有的根-点图转化为点-点图),调用my_min2函数(已给,功能为将点-点图改写为最短情况下
4、的根-点-路径权值图),寻找到三个火车站所代表的点分别以这三个点为根点调用my_min1函数(已给,功能为导出以当前点为目的地的最短路根-点图以及路径权),调用comp函数(自编,功能为将my_min1得出的三个路径权数组分别乘以其各自的点的比重*,并进行比较,最终导出各点的双权路径最小时的根点选择方案),即可获得解。以下是各函数:trans函数functionM=trans(W,m)%trans函数功能为将原有的点-点图转化为根-点图%形参实参转化n=length(W);%初始化接受矩阵M=zeros(m,m);for i=1:m for j=1: if i=j M(i,j)=inf; en
5、dendfor j=1:n if W(j,1)W(j,2) M(W(j,1),W(j,2)=W(j,3); M(W(j,2),W(j,1)=W(j,3); elsemy_min2函数function L,z=my_min2(W)% 函数 my_min2(W)返回图中任意两个节点的最短路径 L 和关联的路径z%=初始化= L=W; z(:,j)=ones(n,1)*j;%=计算最短路=while 1 for i=1: u=L(i,:)+L(:,j); m,k=min(u); L1(i,j)=m; if mL(i,j) % 说明节点i到节点j之间过节点k z(i,j)=k; if L=L1,bre
6、ak,end L=L1;my_min1函数function L,z=my_min1(W,a)% 函数 my_min1(W,a)返回从点a出发到其它各点的最短路的长度 L 和对应的父节点标记 z% W 为图的权,z(i)=k 表示节点 i 的父节点为 k z=ones(1,n)*a;k=1; S(k)=a; u=a;flg=ones(1,n); flg(a)=inf; % flg 标记哪些节点已在集合S中,flg(k)=inf 表示节点k在S中%=优化计算=L=W(a,:);while kL(u)+W(u,v) & flg(v)inf % flg(v)z(j,i)*H(i) g(i)=z(j,i
7、)*H(i); Ans(i)=j;6、结论 本小组所用的编程环境为MATLAB 2012A,可能在数据导入等方面与MATLAB7.0有微小差异,敬请谅解!MATLAB实际操作过程的步骤和各结果如下:导入基本数据表:路径权.mat 和 比重权.mat ,分别进入矩阵W和矩阵H中。将程序trans.m,my_min2.m,my_min1.m,comp.m导入MATLAB库中。将数据my_min1(my_min2(trans(W,50),1)导入矩阵L1中,my_min1(my_min2(trans(W,50),2) 导入矩阵L2中,my_min1(my_min2(trans(W,50),3)导入矩
8、阵L3中。执行程序comp(L1,L2,L3,H),得到的数组命名为Ans,Ans所示即为最优解。(具体过程见附录)结论总结:最终结论为ANS数组所示,1-50乡镇的最近火车站安排为1 2 3 2 2 3 3 2 3 1 2 2 1 2 3 2 2 2 2 2 2 3 2 2 3 1 1 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 1 2 3 3 1 1 2 2 七附录附一:执行过程中用到的数据表(均以mat格式保存):路径权(根-点图)1 10 6.240000000000001 43 17.44000000000001 48 25.89000000000002 37 10.
9、83000000000002 5 6.430000000000002 23 7.370000000000002 20 18.35000000000003 34 10.85000000000003 45 12.14000000000003 7 17.06000000000003 46 36.24000000000004 9 16.28000000000004 30 12.86000000000004 31 21.04000000000004 8 16.48000000000005 49 11.40000000000005 17 19.79000000000006 22 3.36000000000
10、0007 22 5.380000000000007 25 4.610000000000007 43 22.05000000000007 48 29.93000000000008 50 11.85000000000008 9 7.760000000000008 33 11.70000000000009 46 22.68000000000009 34 14.330000000000010 47 9.8900000000000011 19 10.080000000000012 38 3.1100000000000012 35 8.1900000000000013 47 6.7700000000000
11、013 27 3.9100000000000013 48 22.760000000000014 38 10.860000000000014 32 6.1000000000000016 17 7.9800000000000016 41 13.480000000000017 42 10.220000000000018 36 8.7900000000000019 42 10.910000000000019 21 8.8600000000000020 39 8.5000000000000020 40 16.150*0021 30 13.350000000000023 50 3.680000000000
12、0023 40 11.330000000000024 14 4.8800000000000027 39 8.6700000000000028 49 20.870000000000029 32 4.5500000000000029 37 8.9800000000000029 18 8.9400000000000030 50 27.780000000000030 42 15.220000000000032 39 17.320000000000033 40 12.210000000000033 34.020*33 48 21.410000000000036 49 16.230000000000038
13、 39 11.840000000000040 48 15.320000000000041 44 16.420000000000043 26 17.960000000000046 15 13.3300000000000比重权附二:执行trans(W,50)的结果ans = Columns 1 through 13 0 Inf Inf Inf Inf Inf Inf Inf Inf 6.2400 Inf Inf Inf Inf 0 Inf Inf 6.4300 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf 17.0600 Inf Inf
14、 Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf 16.4800 16.2800 Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 7.7600 Inf Inf Inf Inf Inf Inf Inf Inf Inf In
15、f Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Columns 14 through 2
16、6 Inf Inf Inf Inf Inf Inf 18.3500 Inf Inf 7.3700 Inf Inf Inf Inf Inf Inf 19.7900 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 3.3600 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 5.3800 Inf Inf 4.6100 Inf Inf Inf Inf Inf Inf 10.0800 Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 4.8800 Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 7.9800 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf 8.8600 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf In
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2