数学建模运输问题

运输问题模型Transportation,一问题的提出,公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：,B13吨，B26吨，B35吨，B46吨。,A17吨，A24吨，A39吨。,某食品公司主要经营糖果。它下面设有三个加工厂，每天的糖果生产量分别为：,已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，,该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。,二问题的概述,在线性规划中研究这样一类问题：有某种物资需要调运，这种物资的计量单位可以是重量，包装单位或其他。,已知:有m个地点可以供应该种物资（统称产地，用i=1,m表示）；,有n个地点需要该种物资（统称销地，用j=1,n表示）。,n个销地的需要量（统称销量）为b1,b2,bn（统写为bj）。,从第i个产地到第j个销地的单位物资运价为cij。,又知m个产地的可供量（统称产量）为a1,a2,am（统写为ai）；,上面这些数据通常用产销平衡表和单位运价表来表示。,有时候把两个表写在一起:,三运输问题模型,设xij代表从第i个产地调运给第j个销地的物资数量。,在产销平衡的条件下，要求解运输问题使总的运费支出最小，则有如下的运输问题数学模型：,如果用单纯形法求解，先要在每个约束条件左端加上一个人工变量，因此即使象食品公司调运糖果这样简单的数学问题，变量数就有34+3+4=19个之多，计算起来非常繁杂。,运输问题的数学模型结构比较特殊，它的约束条件变量的系数矩阵具有如下的形式：,运输问题的数学模型包含mn个变量，(m+n)个约束条件。,说明：,.,产销不平衡的运输问题,1产大于销,1）数学模型,s.t.,.,产大于销时，增加一个假想的销地j=n+1（库存），,2）求解方法:转化为产销平衡问题,该销地的总需求量为,而在单位运价表中从各产地到假想销地的单位运价为,就转化为一个产销平衡的运输问题。,具体做法如下：,.,2.销大于产,1）数学模型,.,销大于产时，在产销平衡表中增加一个假想的产地i=m+1，该地产量为,在单位运价表中，从假想产地到各销地的单位运价为,就转化为产销平衡的运输问题。,具体做法如下：,m+1000短缺,2）求解方法:转化为产销平衡问题,.,应用实例,设有A1、A2、A3三个产地生产某种物资，产量分别为7、5、7吨，B1、B2、B3、B4四个销地需要该物资，销量分别为2、3、4、6吨。又知各产销地之间的单位运价见下表，试决定总运费最少的调运方案。,解：产地总产量为19吨，销地总销量为15吨，这是一个产大于销的运输问题。首先转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见下两表。,.,A17吨，A25吨，A37吨。B12吨，B23吨，B34吨，B46吨。,用表上作业法计算，求得最优调运方案为：,.,LINGO求解,Globaloptimalsolutionfoundatiteration:8Objectivevalue:35.00000,.,设有三个电视机厂供应四个地区某种型号的电视机。各厂家的年产量、各地区的年销售量以及各地区的单位运价如右表，试求出总的运费最省的电视机调拨方案。,12,M,M,M,0,0,0,MM,.,总运价:172元,Lingo求解,Globaloptimalsolutionfoundatiteration:8Objectivevalue:172.0000,.,Lingo求解,.,Globaloptimalsolutionfoundatiteration:16Objectivevalue:172.0000,.,中转调运问题,1.已知甲、乙两处分别有100吨和85吨同种物资外运，A、B、C三处各需要物资55，60，70吨。物资可以直接运到目的地，也可以经某些中转点转运。已知各处之间的单位运价如下表，试确定一个最优的调运方案。,.,185185130125115,85100185185185,用Lingo求解,.,Globaloptimalsolutionfoundatiteration:10Objectivevalue:2210.000,进一步讨论：不考虑中转调运。,用Lingo求解,Globaloptimalsolutionfoundatiteration:3Objectivevalue:2235.000,.,公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：,B13吨，B26吨，B35吨，B46吨。,A17吨，A24吨，A39吨。,2.某食品公司主要经营糖果。它下面设有三个加工厂，每天的糖果生产量分别为：,假设有四个中转站,每个加工厂生产的糖果在运往销地的过程中可以在产地、中转站和销地之间转运。已知各产地、销地和中转站之间的单位运价如表所示，试确定总运费最少的调运方案。,.,.,B13吨，B26吨，B35吨，B46吨总销量：20吨,A17吨，A24吨，A39吨总产量：20吨,202020,20202020,17141514,131611,20202020,20202020,用Lingo求解,.,Globaloptimalsolutionfoundatiteration:41Objectivevalue:68.00000VariableValueReducedCostVOLUME(WH1,C1)13.000000.000000VOLUME(WH1,C2)7.0000000.000000VOLUME(WH2,C2)9.0000000.000000VOLUME(WH2,C8)11.000000.000000VOLUME(WH3,C3)11.000000.000000VOLUME(WH3,C6)9.0000000.000000VOLUME(WH4,C4)20.000000.000000VOLUME(WH5,C5)20.000000.000000VOLUME(WH6,C6)11.000000.000000VOLUME(WH6,C8)4.0000000.000000VOLUME(WH6,C10)5.0000000.000000VOLUME(WH7,C7)20.000000.000000VOLUME(WH8,C8)5.0000000.000000VOLUME(WH8,C9)6.0000000.000000VOLUME(WH8,C11)6.0000000.000000VOLUME(WH9,C9)14.000000.000000VOLUME(WH10,C10)15.000000.000000VOLUME(WH11,C11)14.000000.000000,.,202020,20202020,17141514,131611,20202020,20202020,Globaloptimalsolutionfoundatiteration:41Objectivevalue:68.00000,直接调运：85元,.,B13吨，B26吨，B35吨，B46吨,A17吨，A24吨，A39吨,.,（设备生产计划）某公司按照合同规定需要在当年每个季度末分别提供10、15、25、20台同一规格的某种机器设备。已知该公司各季度的生产能力以及生产每台设备的成本下表。如果生产的设备当季度不交货，则每台积压一个季度所需的存储、维护等费用为0.15万元。试确定在完成合同任务的条件下，使公司全年生产费用最小的设备生产计划。,.,每台