数学建模运输问题送货问题.docx
《数学建模运输问题送货问题.docx》由会员分享，可在线阅读，更多相关《数学建模运输问题送货问题.docx（19页珍藏版）》请在冰点文库上搜索。
数学建模运输问题送货问题
数学建模运输问题送货问题（总12页）
数学建模论文
题目:
送货问题
学院（直属系）:
数学与计算机学院
年级、专业:
2010级信息与计算科学
姓名:
杨尚安
刘洋
谭笑
指导教师:
蒲俊
完成时间:
2012年3月20日
摘要
本文讨论的是货运公司的运输问题，根据各公司需求和运输路线图，建立了线性规划模型和0-1规划模型，对货运公司的出车安排进行了分析和优化，得出运费最小的调度方案。
对于问题一，由于车辆在途中不能掉头，出车成本固定，要使得总成本最小，即要使在一定的车辆数下，既满足各公司的需求，又要尽量减小出车次数。
故以最小出车数为目标函数，建立线性规划模型，并通过lingo求解，得出最小出车数27次。
接着考虑车的方向问题，出车分为顺时针和逆时针，建立0-1模型，并求解，得出满足问题一的调度方案（见附录表1）。
对于问题二，车辆允许掉头，加上车辆装载货物和空装时运输费不同，，要使总成本最小，故可以通过修改原目标函数，建立线性规划模型和0-1规划模型，求解，得出最佳派出车辆3辆并列出满足问题二的调度方案。
对于问题三第一小问，增加了运输车辆的类型。
即装载材料的方法很多，在上述分析的基础上，通过增加约束条件，建立新的线性规划模型，并求解，得出满足问题三的调度方案。
在第二小问中，由于给出部分公司有道路相通，可采用运筹学中的最短路问题的解决方法加以解决。
关键字：
线性规划模型0-1规划模型调度
一、问题重述
某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。
路线是唯一的双向道路（如图１）。
货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。
每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。
运输车载重运费元/吨公里，运输车空载费用元/公里。
一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。
卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见表１）。
问题：
1、货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。
2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数应如何调度
3、
（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是元/吨公里，空载费用分别为，，元/公里，其他费用一样，又如何安排车辆数和调度方案
（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。
图１ 唯一的运输路线图和里程数
公司
材料
①
②
③
④
⑤
⑥
⑦
⑧
A
4
1
2
3
1
0
2
5
B
1
5
0
1
2
4
2
3
C
5
2
4
2
4
3
5
1
二、符号说明
表示为一个车装一单位A和两单位C；
表示为一个车装六单位C；
表示为一个车装两单位B；
表示为一个车装一单位B和三单位C；
表示最小运输次数；
表示为一个车装一单位A和一单位C；
表示为一个车装一单位A；
表示第i次运输装A的单位数；
表示第i次运输装B的单位数；
表示第i次运输装C的单位数；
表示第i次运输A到达目的地所走的路程；
表示第i次运输B到达目的地所走的路程；
表示第i次运输C到达目的地所走的路程；
表示运输车的方向（等于0按照顺时针即
；等于1按照逆时针即
）；
表示最小成本；
表示第i次运输j的所走单位路程的单位成本；
表示8个公司对A的总需求量；
表示8个公司对B的总需求量；
表示8个公司对C的总需求量；
三、模型假设
1．假设每辆车装载时发挥其最大的装载能力；
2．假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；
3．假设运输车行驶过程中不考虑塞车等各种抛锚现象，以保证每辆车每天可以达到最大的作业时间
四、问题分析
本题考虑从一个货源地往其余八个地运送货物，要求运输成本最少的运送方案。
由于运输问题中涉及到车量的限载重量（6吨）、车速的最大值（60km/h）、汽车每天最多的工作时间（8小时）、汽车每次上货时间（15min）、每次下货的时间（10min）以及ABC三种原材料每件的毛重和八个需货地分别所需ABC的件数等问题。
对于问题一，由于车不可以跳头，我们通过考虑每辆车的容量、卸货顺序、满足各公司需求按需分配，首先找到一个符合要求的解，然后将其优化算出最终结果。
如果假设一辆车在全程只装一次，也只卸一次，即用时最短，会花上85分钟，又因为一辆车工作时间不能超过8h，故一辆车最多跑5次，六辆车共30次。
所以我们可以首先考虑在满足各地所需货物的前提下，设计出车的运货方案，利用lingo软件从方案选择出出车次数最少的一种方案作为汽车的运送方案，经计算车次最少需要27车次，其中9车次运2B，8车次运1A2C，10车次运1A1C。
然后在利用这种方案向各地安排输送货物的方案。
由于运送B的车是单独的，所以我们可以首先将运送B的车单独考虑，然后在安排同时运送A和C的车次。
这里可以使用0、1规划模型，0表示顺时针（即⑨①②...）运送，1表示逆时针（即⑨⑧⑦...）运货。
对于问题二，解决方法和第一问中的解决方法是一样的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响模型中目标函数的中的价值系数的改变，其他和第一问的求解方法是一致的。
对于问题三，题中给出了三种不同的运输车，每辆车有不同的装载方式。
所以根据每个公司对A,B,C的需求，建立线性模型，使得8个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足要求，然后根据每辆车的工作时间，结合这些公司所选择的不同的运输方式，确定出在保证完成任务的情形下，所需要不同类型运输车的最少数目。
然后对不同类型运输车在运输途中的方案的分析，安排出合理的车辆数和调度方案。
五、模型建立与求解
问题一
数据分析
题中已经给出了固定的车辆数，6辆。
首先考虑满足各公司需求的最少出车次数，在此基础上安排调度车辆，使总成本最少。
一辆车在全程只装一次，只卸货一次的情况下所用时间最少，根据题中数据，全程会用85分钟，而一辆车的工作时间不能超过8小时，故一辆车最多只能跑5次，6辆车即最多只跑30次。
接着对车辆的装载情况进行分析。
一辆车最多只能装6吨货物，而一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，假设每辆车都能发挥最大装载力，故有装载情况
（1）一车装一单位A和两单位C，
（2）一车装六单位C，（3）一车装两单位B，（4）一车装一单位B和三单位C。
故可建立如下模型：
其中
表示为一个车装一单位A和两单位C，
表示为一个车装六单位C，
表示为一个车装两单位B，
表示为一个车装一单位B和三单位C，
表示最小运输次数
min=x1+x2+x3+x4;
x1=18;
2*x3+x4=18;
2*x1+6*x2+3*x4>=26;
求解得出满足各公司对于A和B的需求，却会多运C。
上面得出的模型显然不是最优模型，经分析后优化模型，考虑第五种情况：
一个车装一单位A和一单位C。
和第六种情况：
一个车装一单位A。
得出优化后的模型：
其中
表示为一个车装一单位A和一单位C，
表示为一个车装一单位A
min=x1+x2+x3+x4+x5+x6;
x1+x5+x
6=18;
2*x3+x4=18;
2*x1+3*x4+6*x2+x5=26;
x1+x2+x3+x4+x5+x6<=30;
解得最少出车次数为27次，其中9次装两单位B，8次装一单位A和两单位C，10次装一单位A和一单位C。
对于B，可单独考虑，27次中有9次装两单位的B，可先顺时针运两次给公司2，顺时针运1单位B给公司1,1单位B给公司2，以此类推。
对于A,C，由于需要考虑卸货时小件先卸，大件后卸，公司1可以运3次一单位A和一单位C，一次一单位A和一两单位C。
以此类推。
模型建立
最少出车次数为27次，通过分析题中数据和线路图可得到如下求解最小运费的模型：
其中
表示第i次运输装A的单位数，
表示第i次运输装B的单位数，
表示第i次运输装C的单位数，
表示第i次运输A到达目的地所走的路程，
表示第i次运输B到达目的地所走的路程，
表示第i次运输C到达目的地所走的路程，
表示运输车的方向（等于0按照顺时针即
；等于1按照逆时针即
），
表示最小成本，
表示第i次运输j的所走单位路程的单位成本，
表示8个公司对A的总需求量，
表示8个公司对B的总需求量，
表示8个公司对C的总需求量
每辆车的容量：
卸货顺序：
在
时，
在
时，
满足各公司需求：
其中：
模型求解
由于B的运输车次时单独的，故单独考虑B的运输。
我们考虑到车只能顺时针或逆时针运送以及载重运费大于空载运费，所以就近下货会节省运费。
又由于运B的车每次都是运2个单位的B，因此在就近下货的前提下在考虑八个需要地所需B件数的奇、偶问题求出运送B的最优方案。
设计出1-8地所需原材料数量简表，例如（415）表示需要4单位A，1单位B，5单位C。
12345678
（415）（152）（204）（312）（124）（043）（225）（531）
利用首先满足需要偶数单位原材料的原则分配可得:
顺时针往2送2*2B，逆时针往8送1*2B，7送1*2B，6送2*2B，5送1*2B
后得到：
12345678
（415）（112）（204）（312）（104）（003）（205）（511）
接着顺时针往1,2各送1*1B，逆时针往8,4各送1*1B。
这样正好9次将B的运送完成。
具体列表见[附录表1]：
故运送B所需的载重总费用为：
162+162+++54++162+162+=元
空车所需的总费用为：
（45+45+45+29+55+49+45+45+37）*=158元
运送B所需的总费用为：
+158=元
依次可得出运A,C的情况，见[附录表2]
即运送A和C总费用为:
元。
综上所述，六辆车的固定出车成本是120元，从港口固定出车的成本为270元。
完成任务所需全部总费用为：
++120+270=元。
问题二模型建立与求解
0-1表示顺时针出发，卸完货后掉头回去；1-0表示逆时针出发，卸完货后掉头回去。
方
向
方
案公司
车次
①
1
②
5
③
0
④
1
⑤
2
⑥
4
⑦
2
⑧
3
总运费（元）
最短时间（min）
0-1
2B
2
168
55
0-1
2B
2
168
55
0-1
2B
1
1
65
1
2B
1
1
206
95
1-0
2B
2
56
35
1-0
2B
2
47
1-0
2B
2
55
1-0
2B
2
55
1-0
2B
2
71
总计
1
5
0
1
2
4
2
3
533
故运送向各地运送B货物所需的总费用为：
168+168++206+56++++=元
方向
方
案公司
车次
①
4,5
②
1,2
③
2,4
④
3,2
⑤
1,4
⑥
0,3
⑦
2,5
3
5,1
总运费（元）
最短时间（min）
0-1
1A1C
1,1
41
0-1
1A1C
1,1
41
0-1
1A1C
1,1
41
0-1
1A1C
1,1
83
0-1
1A1C
1,1
83
1-0
1A1C
0,1
1,0
209
55
1-0
1A1C
0,1
1,0
209
55
1-0
1A1C
0,1
1,0
209
55
1-0
1A1C
0,1
1,0
81
1
1A1C
1,0
0,1
95
0-1
1A2C
1,2
41
0-1
1A2C
1,2
168
55
0-1
1A2C
1,2
73
0-1
1A2C
1,2
73
1-0
1A2C
1,2
47
1-0
1A2C
1,2
47
1-0
1A2C
0,1
1,1
57
1-0
1A2C
1,2
71
总计
4,5
1,2
2，4
3，2
1，4
0，3
2，5
5，1
3645
1094
即运送A和C总费用为:
3645元。
综上所述，四辆车的固定出车成本是80元，从港口固定出车的成本为270元。
完成任务所需全部总费用为：
+3645+80+270=元。
问题三
数据分析
以尽可能装满车为原则，题中所给出的三种不同的运输车4，6，8吨三种车型有以下装法由于卸货也需要时间，故可根据装载的方式，使每辆车尽可能一次性卸完货物分析出每个公司所需车次。
4吨（车型）
6吨
8吨
Y1=B+C
Y4=2B
Y9=2A
Y2=A
Y5=A+2C
Y10=A+4C
Y3=4C
X6=6C
X10=A+B+C
Y6=B+3C
Y11=8C
Y7=B+C
Y12=2B+2C
Y8=B+2C
Y13=B+5C
Y14=B+A
Y15=B+4C
模型建立
min=@sum（yi）
y2+y5+2*y9+y10+y14=18;
y1+2*y4+y6+y7+y8+2*y12+y13+y14+y15=18;
y1+4*y3+2*y5+3*y6+y7+2*y8+4*y10+8*y11+2*y12+5*y13+4*y15=26;
求解可以得出下表:
公司
（需求）
1．
（4，1，5）
2．
（1，5，2）
3．
（2，0，4）
4．
（3，1，2）
5．
（1，2，4）
6．
（0，4，3）
7．
（2，2，5）
8．
（5，3，1）
车次
2Y9+Y13
Y4+Y14+Y12
2Y5
Y2+Y5+Y14
Y4+Y10
Y4+Y7+Y8
Y10+Y14+Y7
Y9+Y7+2Y14
在考虑每辆车在规定的工作时间的前提下保证车辆尽量少。
由表求出：
4吨：
83分钟6吨：
567分钟8吨：
621分钟
而每辆车最多工作480分钟，故需要派出1+2+2=5辆车。
求出总费用没元。
六、模型评价与修正
本题采用建立线性约束条件的方法得到用车量数最少的数学模型，然后根据此模型按需分配车辆的运送方案，得到了比较满意的结果，能较为准确的计算及安排好出实际生活中遇到的相类似的关于在一定的约束条件下合理安排工作方案使得花费最少的问题，具有准确度高，可靠性好，实用性强的优点。
但在整个模型的建立过程中没有考虑到汽车自身条件等实际情况，使得模型的在实际适应中还不是特别的可靠。
若要在实际生产生活中使用此模型那么应有至少两辆汽车作为备用车。
七、参考文献
[1]景振毅，张泽兵，实用宝典，北京：
中国铁道出版社，2008
[2]姜启源，谢金星，数学建模（第三版），北京：
高等教育出版社，2003
[3]蒲俊，2010届信息与计算科学lingo软件使用方法教案，2011
八、附录
表1
方
向
方
案公司
车次
11
25
40
51
62
74
82
93
载重运费（元）
0
2B
2
162
0
2B
2
162
0
2B
1
1
1
2B
1
1
1
2B
2
54
1
2B
2
1
2B
2
162
1
2B
2
162
1
2B
2
表2
方
向
方
案公司
车次
①4,5
②1,2
③2,4
④3,2
⑤1,4
⑥0,3
⑦2,5
⑧5,1
运费（元）
0
1A2C
1,2
0
1A2C
1,2
180
0
1A2C
1,2
0
1A2C
1,2
1
1A2C
1,2
1
1A2C
1,2
1
1A2C
1,0
0,1
0,1
1
1A2C
1,0
0,2
288．8
0
1A1C
1,1
94
0
1A1C
1,1,
94
0
1A1C
1,1
94
0
1A1C
0,1
1,0
0
1A1C
0,1
1,0
0
1A1C
0,1
1,0
0
1A1C
0,1
1,0
1
1A1C
1,1
67
1
1A1C
1,0
0,1
1
1A1C
1,0
0,1
升级会员 