内容发布更新时间 : 2024/12/23 11:35:39星期一 下面是文章的全部内容请认真阅读。

化。

从起始点v1处，进行分析，用两辆小的货车配送货物，为了尽可能的减少两辆车的重复路线， v1到v5、v7的路程最短，让两辆车分开运货，先根据货物承载量50的限制让其中的一辆车走完路程，再让另一辆车走剩余城市的最短路线，这样走出两条运货路线： 第一种情况：

?v5???v2???v3???v4???v8???v9???v1，包含的客户有第一辆车：v1??5,2,3,4,8，从模型1可解得，从v8回到v1的最短路线是v8?v9?v1，运货总量为40单位，路程为145公里。

?v7???v6???v9???v10???v1，包含的客户有7,6,9,10，运第二辆车：v1??货总量为46，路程为135公里。这种情况下总路程为280公里。

第二种情况：

?v7???v6???v3???v4???v8???v9???v1，包含的客户有第一辆车：v1??7,6,3,4,8，从模型1可解得，从v8回到v1的最短路线是v8?v9?v1，运货总量为45单位，路程为150公里。

?v5???v2???v3???v8???v9???v10???v1，包含的客户第二辆车：v1??5,2,9,10，运货总量为41单位，路程为160。这种情况下总路程为310公里。

对这两种情况对比，分析，可以看出第一种情况优于第二种情况。因此选择第一种情况的路线。

问题四模型的建立与求解

题目要求我们运费最省，所以要考虑到需要的车最少，以及每辆车行驶的路程最短，而且还要保证送到每个客户手中。根据客户总需求量和货车的容量，所以，公司可派4辆货车去送货。在此，我们假设：

从提货点1到各客户点最短路为p1j(j?2,3?10) 从提货点1到各客户点的最短路程L1j(j?2,3?10)

提货点1到各客户点路径客户所需要货物量的总和G1j(j?2,3?10) 运用matlab程序（见附录4）可得：

从中可以发现：G1j?25，所以我们要继续对其进行分析：

首先为了保证送到每个客户手里，所以必须走p16和p110，那样就可以删除p17和p19；然后考虑到货车的路程最短，所以要走p12，删除p15和p18；最后，就只能走1-4-3-8路线。

图1 四辆货车路线图

经过计算可得下表：

表1：4辆车的情况表 每辆车的路线 每辆车的路程 每辆车所载的货物量 1-5-2 40 20 1-4-3-8 80 20 1-7-6 55 25 1-9-10 70 21 所以，可得到目标函数： 六、模型的评价与推广

模型的评价

（1）在整个模型的建立过程中，本文考虑的比较全面客观，使模型具有较强的说服力，结果更合理。

（2）根据问题的特点，综合运用了多个软件，如lingo、matlab等等，使得在解决问题的过程中，更方便简单。

这种寻路方法有其局限性，只适用于一些顶点较少的情况，顶点多，寻找起来较为麻烦。 模型的推广

模型的建立比较客观，在现实中也可以广泛的应用，与现实情况紧密相连；比如：最优路径问题与哈密顿回路问题，这些在现实中应用范围已经很广了。

七、参考文献

[1] 胡运权，运筹学教程第四版，北京：清华大学出版社，2012。 [2] 朱道元，数学建模案例精选，北京：科学出版社，2005。

[3] 姜启源，谢金星。叶俊．数学模型北京：高等教育出版杜，2004。 I4] 吴祈宗．运筹学与最优化方法fM．北京：机械工业出版社，2003。

附录

附录1：

clear; clc;

M=10000;%不能直接到达是将距离赋值给M a(1,:)=[0,50,M,40,25,M,30,M,50,M]; a(2,:)=[50,0,30,M,35,50,M,60,M,M]; a(3,:)=[M,30,0,15,M,30,50,25,M,60]; a(4,:)=[40,M,15,0,45,30,55,20,40,65]; a(5,:)=[25,15,M,45,0,60,10,30,M,55];

a(6,:)=[M,50,30,30,60,0,25,55,35,M]; a(7,:)=[30,M,50,M,10,25,0,30,45,60]; a(8,:)=[M,60,25,20,30,55,30,0,10,M]; a(9,:)=[20,M,M,40,M,15,25,45,0,20];

a(10,:)=[35,20,10,45,20,M,60,M,30,0];%建立a矩阵 path=zeros(length(a)); %建立一个与矩阵a同大小的全零矩阵 for i=1:10 for j=1:10

path(i,j)=j; %用path矩阵记录走过的点 end end for k=1:10 for i=1:10 for j=1:10

if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j);

path(i,j)=path(i,k); % floyd算法 end end end end a, path

i1=input('请输入起点'); i2=input('请输入终点'); disp(i1); while i1~=i2 i1=path(i1,i2); disp(i1); end;

附录2：

MODEL: SETS:

CUSTOMERS / 1.. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST =

0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0; ENDDATA

N = @SIZE( CUSTOMERS);

MIN = @SUM( LINK: DIST * X); @FOR( CUSTOMERS( K):

@SUM( CUSTOMERS( I)| I #NE# K: X( I, K)) = 1; @SUM( CUSTOMERS( J)| J #NE# K: X( K, J)) = 1; @FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) >= U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J)) + ( N - 3) * X( J, K) ); );

@FOR( LINK: @BIN( X));

@FOR( CUSTOMERS( K)| K #GT# 1:

U( K) <= N - 1 - ( N - 2) * X( 1, K); U( K) >= 1 + ( N - 2) * X( K, 1) ); END

Global optimal solution found.

Objective value: Objective bound: Infeasibilities:

Extended solver steps: 0 Total solver iterations: 86 Variable Value Reduced Cost N U( 1) U( 2) U( 3) U( 4) U( 5) U( 6) U( 7) U( 8) U( 9) U( 10) DIST( 1, 1) DIST( 1, 2) DIST( 1, 3) DIST( 1, 4) DIST( 1, 5) DIST( 1, 6) DIST( 1, 7) DIST( 1, 8) DIST( 1, 9) DIST( 1, 10) DIST( 2, 1) DIST( 2, 2) DIST( 2, 3) DIST( 2, 4) DIST( 2, 5) DIST( 2, 6) DIST( 2, 7) DIST( 2, 8) DIST( 2, 9) DIST( 2, 10) DIST( 3, 1)