数学模型运输方式选择

《数学模型》课程设计报告书安徽工业大学数理学院论文题目：选择运输方式2014年6月25日姓名赵星宇专业信息与计算科学班级信111学号119084103指导教师侯为根目录一、课程设计题目..........................................................................1二、摘要..........................................................................................2三、问题分析..................................................................................3四、数学模型的表达..................................................................4-6五、模型实现................................................................................6-8六、计算结果...............................................................................8-9七、附件LINGO.......................................................................9-13第1页共13页一、课程设计题目选择运输方式题目：在法国西南部有一家公司，这家公司需要将180吨存放于仓库D1到D4中的化学产品运输到3个回收中心C1，C2和C3。仓库D1到D4分别储存有50，40，35，和65吨化学产品，总计为190吨。可以选用两种运输方式：公路运输和铁路运输。仓库D1只能通过公路向回收中心C1和C2进行运输，运费分别为12欧元/吨和14欧元/吨。仓库D2只能向回收中心C2运输，可以选择通过铁路或公路，运费分别为12欧元/吨和14欧元/吨。仓库D3可以通过公路向回收中心C2运输（9欧元/吨），或通过铁路或公路向回收中心C3运输，运费分别为4欧元/吨和5欧元/吨。仓库D4可以通过铁路或公路向回收中心C2运输，运费分别为11欧元/吨和14欧元/吨，或者通过铁路或公路向回收中心C3运输，运费分别为10欧元/吨和14欧元/吨。此公司与铁路公司签订的化学物品运输合同规定，每次运输量至少应为10吨，最多为50吨。除了标准的安全规章之外，对公路运输不存在其他特殊的限制。那么此公司应如何运输这190吨化学物品才能够使总运费最低？第2页共13页二、摘要运输费用最低化是我们在现代社会经常会遇到的一个问题。在社会的经济生产活动中，企业与客户都会想方设法合理调拨资源、降低运输费用，实现双方利益最大化，完成资源优化配置。本文以使物流运费成本最低为研究对象，在供应量，需求量和单位运费都已确定的情况下，可用线性规划方法来解决运输中的组织调拨问题。在本文中，我们主要解决的是化学物品配送最优的问题，即是使我们花费的总运费最少。我们运用系统的观点和方法，进行综合分析，发现问题，解决问题，使物流运输活动更加优化、物流运输成本更加合理化。根据题目中所给出的各约束条件，四个仓库、三个回收中心，每个仓库所能到达的回收中心及运费也不同。针对题目中所给信息，要使者190吨化学物品全部运输到回收中心，同时，每个仓库只能到达部分回收中心。基于这两个条件，我们建立了在运输目的地有限制情况下使用总运费最少的模型。我们依据此模型得出的最优运输方案最终要能符合双方要求，实现运输资源的合理优化使用。关键词：化学物品运输线性规划运输优化问题运费最少第3页共13页三、问题分析在本文中，我们主要解决的是化学物品最优的问题。在这里的最优即是使我们的总运费花费的最少。根据题目中所给出的条件是有四个在不同位置的仓库，每个仓库可到达的回收中心有限制。一共有三个回收中心，到达每个回收中心的方式有两种，铁路和公路且费用不同。在这次的建模中我们所需要解决的问题正是求解一个最优的运输方案，使得总运费最少。图形表达：图一运输网络图第4页共13页四、数学模型的表达我们将把此问题建模为一个具有固定总通过量的最小费用流问题（minimumcostflowproblem）。我们先来构造一幅图G=(NODES,ARCS)。首先向结点集合NODES中加入一组结点，代表各个仓库，然后再加入一组结点，代表回收中心（参照图10.1）。弧集合ARCS中包含了在所有仓库和回收中心之间可能存在的连接。运输方案即对应于图G中的一个流，即在每一条弧(i,j)上的流flowij。弧(i,j)具有一个最小通过量MINCAPij（除铁路运输其他均为0），一个最大通过量MAXCAPij（即运力上限，除铁路运输外均为无穷大），以及每吨的运输成本COSTij。从一个仓库到一个处理中心之间的两种运输方式需对应两条不同的弧。在这样的图中，两个结点之间至多有p条弧，称为p-图。这样的图无法编码为（二维）矩阵：例如费用矩阵中的元素COSTij只能表示一个费用。为将此图转化为两个结点之间至多有一条弧的图，可以为仓库i和处理中心j之间的每种运输方式都创建一个假想的结点。例如，在仓库D2（结点3）和处理中心C1（结点12）之间存在一条公路连接和一条铁路连接。为避免生成具有两条弧(3,12)的2-图，我们可以创建一个结点6对应于铁路运输，以及一个结点7对应于公路运输。则铁路运输即变为路径(3,6,12)，公路运输即变为(3,7,12)。只为弧(3,6)和(3,7)设置通过量和费用。在此图中未将仓库的存储量纳入考虑。为此，我们创建一个源结点（假想的结点1），此结点将用弧(1,d)连接到每个仓库结点d上，且此弧的通过量为MAXCAP1d，对应于仓库d处的存储量。因此离开仓库d的第5页共13页流不会超过此值。为方便数学模型的表达，我们也创建一个宿结点（假想的结点15），并且连接到每个处理中心结点上。这样最终得到的图即可以表示为图10.1，其中每条弧(i,j)都对应于一个三元组(MINCAP,MAXCAP,COST)。“-”表示通过量为无穷大。在此数学模型中包含了流守恒约束条件（10.2.2），也称为Kirchhoff定理：每个结点处的入流都等于此结点处的出流（除了源和宿结点之外）。每条弧上的流都至少取值为MINCAPij（约束条件（10.2.3）），且不超过最大通过量MAXCAPij（约束条件（10.2.4））。式（10.2.5）对总流量加以约束，即MINQ=180吨。这样就迫使离开源（结点1）的流总量等于MINQ。由于在此网络中流保持守恒，因此也可以使用宿结点的入流总量等于MINQ作为约束条件。在这个约束条件中，我们可以将等号替换为≥号，由于在最小化总成本时也将最小化总流量，因此此时总运输量将取此下界值。最后要解释一下目标函数（10.2.1）。COSTij是每吨的运费成本，因此通过弧(i,j)运输的流flowij的费用为COSTij⋅flowij。因此最小化总运费即最小化所有弧上的总费用。最终，通过定义这样的图，我们可以得到相当简洁的数学模型。注意，在约束条件（10.2.3）中也隐含给出了变量非负的约束条件。minimizeflowcostijarcsj,iij）（（10.2.1）∀i∈NODES,i≠SOURCE,SINK:ARCS）（j,ijiflow=ARCSj,iijflow）（(10.2.2)∀(i,j)∈ARCS,flowijmincapij(10.2.3)∀(i,j)∈ARCS,flowijmaxcapij(10.2.4)ARCSSOURCESOURCE）（，i,iflow=MINQ(10.2.5)第6页共13页除了这种基于图的问题数学表达之外，也可以将使用方式m从仓库d运输到目标c的运量表示为决策变量trasnportdcm，对每个可能出现的三元组(d,c,m)都建立这样的决策变量，从而得到另一种问题表达方式。这样总运量就可以表示为所有有定义的变量trasnportdcm的和，目标函数即所有可行的三元组(d,c,m)对应的COSTdcm⋅trasnportdcm的和。每种运输方式的最小和最大运力限制将表示为对应变量trasnportdcm的上界和下界约束条件，这一点与上述的（10.2.3）和（10.2.4）很相似。对于我们这个问题，这种表达方式可能比基于图的模型表达要容易一些。但在后面的模型实现和进一步的讨论中，我们仍然使用这种更一般的最小费用流模型，即（10.2.1）到（10.2.5）给出的模型。五、模型实现从这个问题可以引出一个经典的问题，即图的编码。可以将图定义为N×N的矩阵形式，其中N为结点总数，并为每对由弧相连的结点(i,j)都定义一个流变量。然而，对于稀疏图，如我们所使用的这个图，更常用（效率也更高）的方法是将图表示为弧的列表的形式。在下面的Mosel程序实现种就使用了这种表示方法。弧a=(i,j)将用标号a进行索引，而不是用对应的结点对(i,j)进行索引。弧的列表为二维数组A，其中Aa1=i，Aa2=i。在读入数据后（即弧集为已知）将定义流变量。注意在下面的实现中，未采用数字对结点进行编号，而是用名称“Source”，“D2”，“C4”等，这样能够能够方便对结果进行解释。第7页共13页modelE-2MinimumcostflowusesmmxprsdeclarationsNODES:setofstring!结点集合MINQ:integer!运输总量A:array(ARCS:range,1..2)ofstring!弧COST:array(ARCS)ofinteger!每条弧的运输成本MINCAP,MAXCAP:array(ARCS)ofinteger!弧的最小和最大通过量end-declarationsinitializationsfrom‘e2minflow.dat’AMINQMINCAPMAXCAPCOSTend-initializationsfinalize(ARCS)!计算结点集合NODES:=union(ainARCS){A(a,1),A(a,2)}declarationsflow:array(ARCS)ofmpvar!弧上的流end-declarations!目标函数：总运输成本Cost:=sum(ainARCS)COST(a)*flow(a)!流平衡：入流等于出流Forall(ninNODES|nSOURCEandnSINK)sum(ainARCS|A(a,2)=n)flow(a)=sum(ainARCS|A(a,1)=n)flow(a)!最小和最大流通过量第8页共13页Forall(ainARCS|MAXCAP(a)0)doflow(a)=MINCAP(a)flow(a)=MAXCAP(a)end-do!最小运输量sum(ainARCS|A(a,1)=SOURCE)flow(a)=MINQ!求解此问题minimize(Cost)end-model六、计算结果最低运输成本为1,715欧元。图10.2示意了此时的解决方案：在实际用于运输的弧上标出了运输量，未使用的弧用虚线表示。例如，仓库D1的所有50吨库存都将通过公路运输到回收中心2。第9页共13页上图最优运输方案应注意到，这种对弧上的流有最小约束的问题可能会无法找到可行解。在本例中，如果MINQ=9，则由于所有铁路运输的弧的最低通过量都是10吨，因此无法使用铁路运输。七、附件Lingo编写模型程序：model:!3Warehouse,4CustomerTransportationProblem;sets:Warehouse/1..3/:a;Customer/1..4/:b;Routes(warehouse,customer):c,x;Endsets!