数学建模运输问题

运输问题模型Transportation一．问题的提出门市部加工厂B1B2B3B4A1311310A21928A374105公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：B1—3吨，B2—6吨，B3—5吨，B4—6吨。A1—7吨，A2—4吨，A3—9吨。某食品公司主要经营糖果。它下面设有三个加工厂，每天的糖果生产量分别为：已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。二．问题的概述在线性规划中研究这样一类问题：有某种物资需要调运，这种物资的计量单位可以是重量，包装单位或其他。已知:有m个地点可以供应该种物资（统称产地，用i=1,…,m表示）；有n个地点需要该种物资（统称销地，用j=1,…,n表示）。n个销地的需要量（统称销量）为b1,b2,…,bn（统写为bj）。从第i个产地到第j个销地的单位物资运价为cij。又知m个产地的可供量（统称产量）为a1,a2,…,am（统写为ai）；上面这些数据通常用产销平衡表和单位运价表来表示。销地产地12…n产量12...ma1a2...am销量b1b2…bn销地产地12…n12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmn产销平衡表单位运价表有时候把两个表写在一起:销地产地12…n12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmn销地产地12…n产量12...ma1a2...am销量b1b2…bn销地产地12…n产量12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmna1a2...am销量b1b2…bn三．运输问题模型设xij代表从第i个产地调运给第j个销地的物资数量。在产销平衡的条件下，要求解运输问题使总的运费支出最小，则有如下的运输问题数学模型：0ijx),,1(1njbxjmiij),,1(1miaxinjijminjijijxcz11min销地产地12…n产量12...mx11x12…x1nx21x22…x2n.........xm1xm2…xmna1a2...am销量b1b2…bn销地产地12…n产量12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmna1a2...am销量b1b2…bn0),,1(),,1(min1111ijjmiijinjijminjijijxnjbxmiaxxcz如果用单纯形法求解，先要在每个约束条件左端加上一个人工变量，因此即使象食品公司调运糖果这样简单的数学问题，变量数就有3×4+3+4=19个之多，计算起来非常繁杂。运输问题的数学模型结构比较特殊，它的约束条件变量的系数矩阵具有如下的形式：运输问题的数学模型包含m×n个变量，(m+n)个约束条件。说明：0),,1(),,1(min1111ijjmiijinjijminjijijxnjbxmiaxxcz产销不平衡的运输问题minjjiba111．产大于销1）数学模型销地产地12…n产量12...mx11x12…x1nx21x22…x2n.........xm1xm2…xmna1a2...am销量b1b2…bnminjijijxcz11min0),,1(),,1(11ijmijijnjiijxnjbxmiaxs.t.产大于销时，增加一个假想的销地j=n+1（库存），2）求解方法:转化为产销平衡问题该销地的总需求量为minjjiba11而在单位运价表中从各产地到假想销地的单位运价为就转化为一个产销平衡的运输问题。具体做法如下：销地产地12…n产量12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmna1a2...am销量b1b2…bnn+100...0库存01,nicminjjiba112.销大于产销地产地12…n产量12...mx11x12…x1nx21x22…x2n.........xm1xm2…xmna1a2...am销量b1b2…bn0),,1(),,1(..min1111ijjmiijinjijminjijijxnjbxmiaxtsxcz1）数学模型miinjjab11销大于产时，在产销平衡表中增加一个假想的产地i=m+1，该地产量为在单位运价表中，从假想产地到各销地的单位运价为就转化为产销平衡的运输问题。具体做法如下：销地产地12…n产量12...mc11c12…c1nc21c22…c2n.........cm1cm2…cmna1a2...am销量b1b2…bnm+100…0短缺0,1jmc2）求解方法:转化为产销平衡问题应用实例设有A1、A2、A3三个产地生产某种物资，产量分别为7、5、7吨，B1、B2、B3、B4四个销地需要该物资，销量分别为2、3、4、6吨。又知各产销地之间的单位运价见下表，试决定总运费最少的调运方案。销地产地B1B2B3B4A1A2A321134103597812解：产地总产量为19吨，销地总销量为15吨，这是一个产大于销的运输问题。首先转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见下两表。销地产地B1B2B3B4库存产量A1A2A3757销量23464A1－7吨，A2－5吨，A3－7吨。B1－2吨，B2－3吨，B3－4吨，B4－6吨。销地产地B1B2B3B4A1A2A321134103597812销地产地B1B2B3B4库存A1A2A321134010359078120用表上作业法计算，求得最优调运方案为：销地产地B1B2B3B4库存产量A1A2A32323243757销量23464销地产地B1B2B3B4A1A2A321134103597812销地产地B1B2B3B4产量A1A2A3x11x12x13x14x21x22x23x24x31x32x33x34757销量234606432757..min3424143323133222123121113433323124232221141312113141ijijijijxxxxxxxxxxxxxxxxxxxxxxxxxtsxczLINGO求解Globaloptimalsolutionfoundatiteration:8Objectivevalue:35.00000设有三个电视机厂供应四个地区某种型号的电视机。各厂家的年产量、各地区的年销售量以及各地区的单位运价如右表，试求出总的运费最省的电视机调拨方案。销地厂家B1B2B3B4产量(万台)A1A2A363126439－9101310101210最低需求（万台）最高需求（万台）6140510146不限销地厂家B1’B1’’B2B3B4’B4’’产量（万台）A1A2A366312664439－－9910131010101210销量641465712A410MMM000MM销地厂家B1’B1’’B2B3B4’B4’’产量（万台）A1A2A3A4106242536410121010销量6414653+4总运价:172元Lingo求解销地厂家B1’B1’’B2B3B4’B4’’产量（万台）A1A2A3A4104442536410121010销量4614653+4Globaloptimalsolutionfoundatiteration:8Objectivevalue:172.00001014131211xxxx12232221xxx1034333231xxxx106312111xxx14322212xxx6332313xxx53414xx销地厂家B1B2B3B4产量(万台)A1A2A363126439－9101310101210最低需求（万台）最高需求（万台）6140510146不限销地厂家1234123x11x12x13x14x21x22x23x24x31x32x33x343433323124232221141312111013109100093461236minxxxxxxxxxxxxz05614106101210..1013109100093461236min34143323133222123121113433323123222114131211343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxzLingo求解Globaloptimalsolutionfoundatiteration:16Objectivevalue:172.0000销地厂家B1B2B3B4产量(万台)A1A2A363126439－9101310101210最低需求（万台）最高需求（万台）6140510146不限销地厂家B1B2B3B4产量(万台)A1A2A3108428101210最低需求（万台）最高需求（万台）6140510146不限中转调运问题1.已知甲、乙两处分别有100吨和85吨同种物资外运，A、B、C三处各需要物资55，60，70吨。物资可以直接运到目的地，也可以经某些中转点转运。已知各处之间的单位运价如下表，试确定一个最优的调运方案。甲乙甲乙010120ABC甲乙101514121218ABCABC0108140121140甲乙甲乙010120ABC甲乙101514121218ABCABC0108140121140ABC甲乙10151412121810085556070销地产地甲乙ABC产量甲乙ABC0101014121201512181015010814121401212181140销量甲乙ABC产量甲乙ABC8510055130851004525115185185130125115销量8510018518518518518513012511585100185185185用Lingo求解甲—A:55吨，甲—C:45吨;乙—B60吨25吨—CGlobaloptimalsolutionfoundatiteration:10Objectivevalue:2210.000进一步讨论：不考虑中转调运。ABC甲乙10151412121810085556070用Lingo求解Globaloptimalsolutionfoundatiteration:3Objectivevalue:2235.000ABC甲乙3025607010085556070门市部加工厂B1B2B3B4A1311310A21928A374105公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：B1—3吨，B2—6吨，B3—5吨，B4—6吨。A1—7吨，A2—4吨，A3—9吨。2.某食品公司主要经营糖果。它下面设有三个加工厂，每天的糖果生产量分别为：假设有四个中转站,每个加工厂生产的糖果在运往销地的过程中可以在产地、中转站和销地之间转运。已知各产地、销地和中转站之间的单位运价如表所示，试确定总运费最少的调运方案。产地中转地销地A1A2A3T1T2T3T4B1B2B3B4产地A1A2A301310-3-023115-4-2323317119432101085中转站T1T2T3T4214335-21-2301321011310221202411858-42226746销地B1B2B3B4311310192874105284645271