资源描述：
《数学建模：钢管订购和运输》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、钢管订购和运输摘要：本文运用线性规划理论建立了钢管订购和运输计划问题的数学模型。在求解时分别利用了图论中求最短路长的算法、整数规划中的0—1规划的解法及运输问题的表上作业法。关键词：线性规划,运输问题一、问题重述有一条从A1A2A15的天然气管道需要铺设，如图1。经筛选，只有7家厂商获得认可，分别记为S1，S2，，S7。图中粗线表示铁路，单细线表示公路，双细线表示管道（假设管道沿线有公路或建有施工公路）。圆圈表示公路，每段铁路公路和管道旁的数字表示管道的里程（单位km），记1km为一个单位。一个钢厂如果承担这种钢管的生产，则最少需要500个
2、单位。钢厂Si在制定期内最多能生产钢管的数量记为si个单位，钢管出场售价为每单位Pi万元，如下表。一单位钢管的铁路运价如下表：1000km每增加100km运费增加5万元公路运输费为每公里0.1万元（不足整公里部分按1公里计算）。1：制定一个主管道的订购和运输计划，市总费用最小（给出总费用）。2：就问题1的模型进行分析，那个钢管厂的钢管销售价格变化对够运计划和总费用影响最大；哪个钢管厂钢管的产量上限的变化对够运计划和总费用的影响最大，并给出相应的数字结果。3：如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，对这种更一般的
3、情形给出一种解决办法，并对图2按问题1的要求给出模型和结果。二、基本假设假设铺设钢管可从Aj向前后两个方向铺设或向同一方向铺设和不考虑火车运载与汽车运载的装卸费。三、符号说明1第Si个钢管厂承担制造钢管的任务。0-1变量Ri,Ri=0第Si个钢管厂不承担制造钢管的任务。ai表示向第Si个钢管厂订购的钢管的数量。xij表示从钢管厂Si沿着费用最小的路线运输到火车站Aj点的钢管的数量。bj表示从各个钢管厂运输到Aj点的钢管的总数。cij表示从钢管厂Si运输单位钢管到Aj的最小费用。Q表示铺设管道线路上的总运费。四、模型的建立与求解4.1(问题一
4、)：对所给问题进行分析,建立了如下线性规划模型：目标函数如下：约束条件如下：500RiaiRiSiaibi=5171xij≥0,ai≥0,bj≥0,且都为整数i=1,2,…,7j=1,2,..,15目标函数f中,aiRiPi项表示总订购费，cijxij表示从各钢管厂Si(i=1,2,…,7)将所订购钢管沿费用最小的路线运到Aj(j=1,2,…,15)的总运费,cij为从Si到Aj运输单位钢管的最小费用,其数值用求最短路的算法可求得。Q为铺设主管道线路上的总运费。约束条件:(1)表示各钢管厂生产量的限制条件。(2)表示从第Si个钢管厂运出去的
5、钢管总数应等于该钢管厂的生产量。(3)表示从各个钢管厂运到Aj的钢管总数。(4)表示铺设主管道所需钢管总数。求解上述线性规划模型,需分几个阶段进行。先求从钢管厂Si运输单位钢管到Aj的最小费用cij。将每条边上的表示距离的权换算成运费,铺设主管道的线路可不考虑,然后按图论中求最短路的Dijkstra算法,求出Si到Aj的最短路长Cij。该过程由计算机来实现。确定0-1变量Ri的取值,即确定哪些钢管厂承担制造钢管的任务。若用枚举法7个变量有128种可能情况。考虑到实际问题的要求,没有一个钢管厂来承担制造钢管的任务和只有一个钢管厂来承担都是不可
6、能的。实际上只有两个钢管厂来承担制造钢管的任务,其总费用也不可能是最小的。因而我们考虑用隐枚举法,得到最优解为R1=R2=R3=R5=R6=1,R4=R7=0,即S4和S7两个钢管厂不承担制造钢管的任务。假设铺设钢管的方向是从A15→A14→A13→…→A2→R1,据此来确定每个Aj所需的钢管数量bj,显然b1=0,即不需运输钢管到A1。根据铺设1km主管道需1单位钢管可知:b2=104,b3=301,b4=750,b5=606,b6=194,b7=205,b8=201,b9=680,b10=480,b11=300,b12=220,13=2
7、10,15=420,16=500。以各钢管厂Si为产地,Aj为销地,得到产销平衡表。这是一个产销不平衡的运输问题,总生产量6600大于总需要量5171,为求得平衡,在产销平衡表中增加一个假想的销地A0,其需要量为6600-5171=1429,并令各钢管厂到假想销地A0的单位运费为0,这样就把问题转化为产销平衡的运输问题。利用求解运输问题的表上作业法,由计算机运算求得结果:总订购费=797455(万元),铁路和公路上的总运费=378691.1(万元)。按从A15→A14→…→A1方向铺设时,从Aj(j=2,3,…,15)铺设至其邻点Ak(k=
8、1,2,…,14且j≠k)的运费q=0.1×a(a+1)/2万元(a为Aj至Ak的距离)。则Q=122904.3万元。由上面结果可得:minf=797455+378691.1+1
