基于CPLEX的相关运输问题的分析及求解举例

基于CPLEX的相关运输问题的分析及求解举例1基于CPLEX的相关运输问题的分析及求解举例摘要：我们通常把货物从生产商到销售商的分配问题称为运输问题（TransportationProblem，简记TP），是一类非常典型的线性规划问题。在现代的生活中，运输可以说是实现经济贸易与文化交流的一种必不可少的手段，在物流系统中也是必不可少的重要环节。但是传统的产销地两者之间的货物转移已经很显然是最理想的情景。在物流系统中出现了越来越多的既不生产产品和既不消耗产品的中转地。本文主要就产地、中转地以及销地这三者之间的货物转移的运输问题进行分析，并简单的举以具体实例，借用CPLEX软件对案例进行建模求解。关键词：运输问题；产地；销地；中转地；CPLEX；建模求解1.案例说明某公司经销一种糖果。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往4个销售地。各销售地每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。除产、销地之外，中间还有4个转运站，分别是T1、T2、T3、T4。每个工厂生产的产品不一定直接发运到销售地，可以将几个产地集中一起运输；运往各销地的产品可以先运给其中几个销地，再转运给其它销地；产品也可以在产地、销地和转运站之间相互运输。已知各产地、销地和中间转运站及相互之间每吨产品的运价如表1所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将3个厂每天生产的产品运往销售地，使总的运费最小。表1两地之间的运价率元/吨项目产地中间转运站销地A1A2A3T1T2T3T4B1B2B3B4产地A10132143311310A210---35---21928A33---01---2374105中间转运站T123101322846T215---10114527T34---231021824T432321201---26销地B131724110142B21194858---1021B3321042224203B4108567462130注：表格中无数字的代表无法实现两地之间的运输。2.求解思路及步骤首先从表1可以看出，从A1到B2每吨的直接运费是11元，如从A1经A3运往B2，每吨运费为3+4=7元，从A1经T2运往B2只需1+5=6元，而从A1到B2运费最少的路径是从A1经A2，B1到B2，每吨的运费只需1+1+1=3元。可见这个问题中从每个产地到各个销地之间的运输方案是很多的。为了将这个问题转化成为一般的运输问题，可以做如下处理：(1)由于问题中所有产地、中间转运站、销地都可以看作产地，又可以看作销地。因此把这个问题当作是有11个产地和11个销地的扩大运输问题。(2)对扩大的运输问题建立单位运价表。方法是将表1中不可能的运输方案的运价用任意的正数M代替。基于CPLEX的相关运输问题的分析及求解举例2(3)所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运量不超过20吨。可以设定T1,T2,T3,T4的产量和销量均为20吨。(4)扩大的运输问题中原来的产地和销地因为也有转运站的作用，所以同样在原来产量和销量的数字上加20吨，即3个厂每天这种产品的产量改成27，24，29吨，销量均为20吨；4个销售点的每天销量改为23，26，25，26吨，产量均为20吨。最后扩大的运输问题的产销平衡表与单位运价表如下表2所示。表2扩大的运输问题的产销平衡表与单位运价表元/吨销地产地A1A2A3T1T2T3T4B1B2B3B4产量A1013214331131027A210M35M2192824A33M01M237410529T12311132284620T215MM011452720T34M22102182420T432331201M2620B13177411014220B21194458M102120B3321010222420320B410855746213020销地20202020202020232625262403.数学建模现有的已知条件：设有m个产地，n个销地（当然在此案例中m=n）;,,2,1;,,2,1;,,2,1jb;,,2,1ijiinjmiBACnjBmiAajiijj物资的调运数量，到从产地的需求量，个销地第的供应量，个产地第决策变量：;,,2,1;,,2,1njmiBAxjiij物资的调运数量，到从产地目标函数：ijminjijxCmin约束条件st;,,2,1;,,2,1,0;,,2,1,;,,2,1,njmixnjbxmiaxijjmiijinjij4.利用CPLEX编写代码进行求解在运用CPLEX求解问题的过程中由于M是一个非常大的数，所以设M=10000元，由此问题编写的CPLEX模型代码见附录1，数据代码见附录2。最后得出的运行结果如下表3所示。基于CPLEX的相关运输问题的分析及求解举例3表3CPLEX运行结果表吨销地产地A1A2A3T1T2T3T4B1B2B3B4产量A1202527A218624A320929T111920T22020T32020T42020B186620B22020B32020B42020销地2020202020202023262526240由此表可以得出各个产地的产品输送径路为：(1)产地A1生产的7吨产品有2吨运往A2，然后由A2转运至销地B1;另外5吨产品直接运往销地B3;所产生的运费为2ⅹ1+2ⅹ1+5ⅹ3=19元；(2)产地A2生产的4吨产品直接运往销地B1；所产生的运费为4ⅹ1=4元；(3)产地A3所生产的9吨产品先运至转运站T1，然后再由T1转运至B1;所产生的运费为9ⅹ1+9ⅹ2=27元；(4)聚集在销地B1的由各处运至的15吨产品除3吨用于在B1销售外，其余12吨分别转运至销地B2，B3各6吨；所产生的运费为6ⅹ1+6ⅹ2=18元；最后总的运费就是19+4+27+18=68元。5．结语通过对上述相关运输问题的分析建模与使用CPLEX求解的一系列过程，不仅使我们对已经学过运筹学的有关知识有了更深刻的了解，而且也提高了运用CPLEX这种新型软件求解复杂问题的能力，也体会到了这种软件给问题的求解过程带来的方便和快捷，为以后处理相关的一些问题积累了宝贵的经验，同时在做作业的过程中充分的锻炼了同学之间协作能力，使大家获益匪浅。基于CPLEX的相关运输问题的分析及求解举例4附录1：{string}Cities=...;{string}Products=...;tupleroute{stringp;stringo;stringd;}{route}Routes=...;tuplesupply{stringp;stringo;}{supply}Supplies={p,o|p,o,dinRoutes};floatSupply[Supplies]=...;tuplecustomer{stringp;stringd;}{customer}Customers={p,d|p,o,dinRoutes};floatDemand[Customers]=...;floatCost[Routes]=...;{string}Orig[pinProducts]={o|p,o,dinRoutes};{string}Dest[pinProducts]={d|p,o,dinRoutes};assertforall(pinProducts)sum(oinOrig[p])Supply[p,o]==sum(dinDest[p])Demand[p,d];dvarfloat+Trans[Routes];constraintctSupply[Products][Cities];constraintctDemand[Products][Cities];minimizesum(linRoutes)Cost[l]*Trans[l];subjectto{forall(pinProducts,oinOrig[p])ctSupply[p][o]:sum(dinDest[p])基于CPLEX的相关运输问题的分析及求解举例5Trans[p,o,d]==Supply[p,o];forall(pinProducts,dinDest[p])ctDemand[p][d]:sum(oinOrig[p])Trans[p,o,d]==Demand[p,d];}基于CPLEX的相关运输问题的分析及求解举例6附录2Cities={A1A2A3T1T2T3T4B1B2B3B4};Products={CANDY};Routes={CANDYA1A1,CANDYA1A2,CANDYA1A3,CANDYA1T1,CANDYA1T2,CANDYA1T3,CANDYA1T4,CANDYA1B1,CANDYA1B2,CANDYA1B3,CANDYA1B4,CANDYA2A1,CANDYA2A2,CANDYA2A3,CANDYA2T1,CANDYA2T2,CANDYA2T3,CANDYA2T4,CANDYA2B1,CANDYA2B2,CANDYA2B3,CANDYA2B4,CANDYA3A1,CANDYA3A2,CANDYA3A3,CANDYA3T1,CANDYA3T2,CANDYA3T3,CANDYA3T4,CANDYA3B1,CANDYA3B2,CANDYA3B3,CANDYA3B4,CANDYT1A1,CANDYT1A2,基于CPLEX的相关运输问题的分析及求解举例7CANDYT1A3,CANDYT1T1,CANDYT1T2,CANDYT1T3,CANDYT1T4,CANDYT1B1,CANDYT1B2,CANDYT1B3,CANDYT1B4,CANDYT2A1,CANDYT2A2,CANDYT2A3,CANDYT2T1,CANDYT2T2,CANDYT2T3,CANDYT2T4,CANDYT2B1,CANDYT2B2,CANDYT2B3,CANDYT2B4,CANDYT3A1,CANDYT3A2,CANDYT3A3,CANDYT3T1,CANDYT3T2,CANDYT3T3,CANDYT3T4,CANDYT3B1,CANDYT3B2,CANDYT3B3,CANDYT3B4,CANDYT4A1,CANDYT4A2,CANDYT4A3,CANDYT4T1,CANDYT4T2,CANDYT4T3,CANDYT4T4,CANDYT4B1,CANDYT4B2,CANDYT4B3,基于CPLEX的相关运输问题的分析及求解举例8CANDYT4B4,CANDYB1A1,CANDYB1A2,CANDYB1A3,CANDYB1T1,CANDYB1T2,CANDYB1T3,CANDYB1T4,CANDYB1B1,CANDYB1B2,CANDYB1B3,CANDYB1B4,CANDYB2A1,CANDYB2A2,CANDYB2A3,CANDYB2T1,CANDYB2T2,CANDYB2T3,CANDYB2T4,CANDYB2B1,CANDYB2B2,CANDYB2B3,CANDYB2B4,CANDYB3A1,CANDYB3A2,CANDYB3A3,CANDYB3T1,CANDYB3T2,CANDYB3T3,CANDYB3T4,CANDYB3B1,CANDYB3B2,CANDYB3B3,CANDYB3B4,CANDYB4A1,