数学建模运输问题课件

运输问题模型运输问题模型 Transportation1.一问题的提出一问题的提出 门市部门市部加工厂加工厂B1B2B3B4A1311310A21928A374105公司把这些糖果分别运往四个地区的门市部销售，公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：各地区每天的销售量分别为：B1 133吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨。吨。A17 吨，吨，A24吨，吨，A39吨。吨。某食品公司主要经营糖果。某食品公司主要经营糖果。它下面设有三个加工厂，它下面设有三个加工厂，每天的糖果生产量分别为：每天的糖果生产量分别为：已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，该食品公司应如何调运，在满足各门市部销售需要的情况下，该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。使总的运费支出为最少。2.二问题的概述二问题的概述在线性规划中研究这样一类问题：在线性规划中研究这样一类问题：有某种物资需要调运，这种物资的计量单位可以是重量，有某种物资需要调运，这种物资的计量单位可以是重量，包装单位或其他。包装单位或其他。已知已知:有有m 个地点可以供应该种物资（统称产地，用个地点可以供应该种物资（统称产地，用 i=1,m 表示）；表示）；有有 n 个地点需要该种物资（统称销地，用个地点需要该种物资（统称销地，用 j=1,n 表示）。表示）。n 个销地的需要量（统称销量）为个销地的需要量（统称销量）为b1,b2,bn（统写为（统写为 b j ）。）。从第从第 i 个产地到第个产地到第 j 个销地的单位物资运价为个销地的单位物资运价为c i j。又知又知m 个产地的可供量（统称产量）为个产地的可供量（统称产量）为a1,a2,am（统写为（统写为a i ）；）；上面这些数据通常用产销平衡表和单位运价表来表示。上面这些数据通常用产销平衡表和单位运价表来表示。3.销地销地产地产地12n产量产量12.ma1a2.am销量销量b1b2bn 销地销地产地产地1 2 n12.mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmn产销平衡表产销平衡表单位运价表单位运价表有时候把两个表写在一起有时候把两个表写在一起:4.销地销地产地产地1 2 n12.mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmn 销地销地产地产地12n产产量量12.ma1a2.am销量销量b1b2bn 销地销地产地产地1 2 n产产量量12.mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmna1a2.am销量销量b1 b2 bn5.三运输问题模型三运输问题模型设设 xij 代表从第代表从第 i 个产地调运给个产地调运给第第 j 个销地的物资数量。个销地的物资数量。在产销平衡的条件下在产销平衡的条件下，要求解，要求解运输问题使总的运费支出最小，运输问题使总的运费支出最小，则有如下的运输问题数学模型：则有如下的运输问题数学模型：销地销地产地产地1 2 n产产量量12.mx11 x12 x1nx21 x22 x2n.xm1 xm2 xmna1a2.am销量销量b1 b2 bn 销地销地产地产地1 2 n产产量量12.mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmna1a2.am销量销量b1 b2 bn6.如果用单纯形法求解，如果用单纯形法求解，先要在每个约束条件左端加上一个人工变量，先要在每个约束条件左端加上一个人工变量，因此即使象食品公司调运糖果这样简单的数学问题，因此即使象食品公司调运糖果这样简单的数学问题，变量数就有变量数就有 34+3+4=19=19个之多，计算起来非常繁杂。个之多，计算起来非常繁杂。运输问题的数学模型结构比较特殊，运输问题的数学模型结构比较特殊，它的约束条件变量的系数矩阵具有如下的形式：它的约束条件变量的系数矩阵具有如下的形式：运输问题的数学模型包含运输问题的数学模型包含 mn个变量，个变量，(m+n)个约束条件。个约束条件。说明：说明：7.产销不平衡的运输问题产销不平衡的运输问题1 1产大于销产大于销1 1）数学模型）数学模型 销地销地产地产地1 2 n产产量量12.mx11 x12 x1nx21 x22 x2n.xm1 xm2 xmna1a2.am销量销量b1 b2 bns.t.8.产大于销时，增加一个假想的销地产大于销时，增加一个假想的销地 j=n+1+1（库存），（库存），2 2）求解方法）求解方法:转化为产销平衡问题转化为产销平衡问题该销地的总需求量为该销地的总需求量为而在单位运价表中从各产地到假想销地的单位运价为而在单位运价表中从各产地到假想销地的单位运价为就转化为一个产销平衡的运输问题。就转化为一个产销平衡的运输问题。具体做法如下：具体做法如下：销地销地产地产地 1 2 n产量产量12.m c11 c12 c1n c21 c22 c2n .cm1 cm2 cmna1a2.am销量销量 b1 b2 bnn+100.0库存库存9.2.2.销大于产销大于产 销地销地产地产地1 2 n产产量量12.mx11 x12 x1nx21 x22 x2n.xm1 xm2 xmna1a2.am销量销量b1 b2 bn1 1）数学模型）数学模型10.销大于产时，在产销平衡表中增加一个假想的产地销大于产时，在产销平衡表中增加一个假想的产地 i=m+1，该地产量为该地产量为在单位运价表中，在单位运价表中，从假想产地到各销地的单位运价为从假想产地到各销地的单位运价为 就转化为产销平衡的运输问题。就转化为产销平衡的运输问题。具体做法如下：具体做法如下：销地销地产地产地 1 2 n产量产量12.m c11 c12 c1n c21 c22 c2n .cm1 cm2 cmna1a2.am销量销量 b1 b2 bnm+1 0 0 0 短缺短缺 2 2）求解方法）求解方法:转化为产销平衡问题转化为产销平衡问题11.应用实例应用实例设有设有A1 1、A2 2、A3 3三个产地生产某种物资，产量分别为三个产地生产某种物资，产量分别为7 7、5 5、7 7吨，吨，B1 1、B2 2、B3 3、B4 4四个销地需要该物资，销量分别为四个销地需要该物资，销量分别为2 2、3 3、4 4、6 6吨。吨。又知各产销地之间的单位运价见下表，又知各产销地之间的单位运价见下表，试决定总运费最少的调运方案。试决定总运费最少的调运方案。销地销地产地产地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2解：解：产地总产量为产地总产量为1919吨，吨，销地总销量为销地总销量为1515吨，吨，这是一个产大于销的运输问题。这是一个产大于销的运输问题。首先转化为产销平衡的运输问题，首先转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见下两表。其产销平衡表和单位运价表分别见下两表。12.销地销地产地产地 B1 1 B2 2 B3 3 B4 4 库存库存产产量量A1 1A2 2A3 37 75 57 7销量销量 2 3 4 6 2 3 4 6 4 4A17吨，吨，A25吨，吨，A37 7吨。吨。B12吨，吨，B23吨，吨，B34吨，吨，B46 6吨。吨。销地销地产地产地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 销地销地产地产地 B1 1 B2 2 B3 3 B4 4 库存库存A1 1A2 2A3 3 2 2 11 11 3 3 4 4 0 0 10 10 3 3 5 5 9 9 0 0 7 7 8 8 1 1 2 2 0 0用表上作业法计算，用表上作业法计算，求得最优调运方案为：求得最优调运方案为：销地销地产地产地 B1 1 B2 2 B3 3 B4 4 库存库存产量产量A1 1A2 2A3 3 2 2 3 3 2 2 3 3 2 2 4 3 4 3 7 5 7销量销量 2 3 4 6 2 3 4 6 4 413.销地销地产地产地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 销地销地产地产地 B1 1 B2 2 B3 3 B4 4 产量产量A1 1A2 2A3 3 x11 11 x12 12 x13 13 x1414 x21 21 x22 22 x23 23 x2424 x31 31 x32 32 x33 33 x34347 75 57 7销量销量 2 3 4 6 2 3 4 6LINGOLINGO求解求解Global optimal solution found at iteration:8Objective value:35.0000014.设有三个电视机厂供应四个地区某种型号的电视机。设有三个电视机厂供应四个地区某种型号的电视机。各厂家的年产量、各厂家的年产量、各地区的年销售量以及各地区的年销售量以及各地区的单位运价各地区的单位运价如右表，如右表，试求出总的运费最省的试求出总的运费最省的电视机调拨方案。电视机调拨方案。销地销地厂家厂家 B1 B2 B3 B4 产量产量(万台万台)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（万台）最低需求（万台）最高需求（万台）最高需求（万台）6 14 0 5 10 14 6 不限不限 销地销地厂家厂家 B1 B1 B2 B3 B4 B4 产量产量（万台）（万台）A1A2A3 6 6 3 12 6 6 4 4 3 9 9 9 10 13 10 10 101210销量销量 6 4 14 6 5 712A410MMM000M M15.销地销地厂家厂家 B1 B1 B2 B3 B4 B4 产量产量（万台）（万台）A1A2A3A4 10 6 2 4 2 5 3 6 410121010销量销量 6 4 14 6 5 3+4总运价总运价:172元元LingoLingo求解求解 销地销地厂家厂家 B1 B1 B2 B3 B4 B4 产量产量（万台）（万台）A1A2A3A4 10 4 4 4 2 5 3 6 410121010销量销量 4 6 14 6 5 3+4Global optimal solution found at iteration:8Objective value:172.000016.销地销地厂家厂家 B1 B2 B3 B4 产量产量(万台万台)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（万台）最低需求（万台）最高需求（万台）最高需求（万台）6 14 0 5 10 14 6 不限不限销地销地厂家厂家1 2 3 4123x11 x12 x13 x14x21 x22 x23 x24x31 x32 x33 x34LingoLingo求解求解17.Global optimal solution found at iteration:16Objective value:172.0000 销地销地厂家厂家 B1 B2 B3 B4 产量产量(万台万台)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（万台）最低需求（万台）最高需求（万台）最高需求（万台）6 14 0 5 10 14 6 不限不限 销地销地厂家厂家 B1 B2 B3 B4 产量产量(万台万台)A1A2A3 10 8 4 2 8101210最低需求（万台）最低需求（万台）最高需求（万台）最高需求（万台）6 14 0 5 10 14 6 不限不限18.中转调运问题中转调运问题1.已知甲、乙两处分别有已知甲、乙两处分别有100吨和吨和85吨同种物资外运，吨同种物资外运，A、B、C三处各需要物资三处各需要物资55，60，70吨。吨。物资可以直接运到目的地，也可以经某些中转点转运。物资可以直接运到目的地，也可以经某些中转点转运。已知各处之间的单位运价如下表，试确定一个最优的调运方案。已知各处之间的单位运价如下表，试确定一个最优的调运方案。甲甲乙乙甲甲乙乙010120ABC甲甲乙乙101514121218ABCABC010814012114019.甲甲乙乙甲甲乙乙010120ABC甲甲乙乙101514121218ABCABC0108140121140ABC甲甲乙乙10151412121810085556070销地销地产地产地甲甲乙乙ABC产量产量甲甲乙乙ABC0101014121201512181015010814121401212181140销量销量甲甲乙乙ABC产量产量甲甲乙乙ABC8510055130851004525115185185130125115销量销量8510018518518518518513012511585 100 185185 185用用LingoLingo求解求解甲甲A:55吨，吨，甲甲C C:45:45吨吨;乙乙B6060吨吨2525吨吨C20.Global optimal solution found at iteration:10Objective value:2210.000进一步讨论：不考虑中转调运。进一步讨论：不考虑中转调运。ABC甲甲乙乙10151412121810085556070用用LingoLingo求解求解Global optimal solution found at iteration:3 Objective value:2235.000ABC甲甲乙乙302560701008555607021.门市部门市部加工厂加工厂B1B2B3B4A1311310A21928A374105公司把这些糖果分别运往四个地区公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：的门市部销售，各地区每天的销售量分别为：B1 133吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨。吨。A17 吨，吨，A24吨，吨，A39吨。吨。2.某食品公司主要经营糖果。某食品公司主要经营糖果。它下面设有三个加工厂，它下面设有三个加工厂，每天的糖果生产量分别为：每天的糖果生产量分别为：假设有四个中转站假设有四个中转站,每个加工厂生产的糖果在运往销地的过程中每个加工厂生产的糖果在运往销地的过程中可以在产地、中转站和销地之间转运。可以在产地、中转站和销地之间转运。已知各产地、销地和中转站之间的单位运价如表所示，已知各产地、销地和中转站之间的单位运价如表所示，试确定总运费最少的调运方案。试确定总运费最少的调运方案。22.产产 地地中中 转转 地地销销 地地A1A2A3T1T2T3T4B1B2B3B4产产地地A1A2A301310-3-023115-4-2323317119432101085中中转转站站T1T2T3T4214335-21-2301321011310221202411858-42226746销销地地B1B2B3B43113101928741052846452718241-26014210214203213023.B1 133吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨吨总销量：总销量：2020吨吨A17 吨，吨，A24吨，吨，A39吨吨总产量：总产量：2020吨吨销地销地产地产地A1A2A3T1T2T3T4B1B2B3B4产产量量A1A2A301310-3-023115-4-2323317119432101085T1T2T3T4214335-21-2301321011310221202411858-42226746B1B2B3B43113101928741052846452718241-260142102142032130销量销量202020202020201714151413 16 1120 20 20 2020 20 20 20用用LingoLingo求解求解24.Global optimal solution found at iteration:41 Objective value:68.00000 Variable Value Reduced CostVOLUME(WH1,C1)13.00000 0.000000VOLUME(WH1,C2)7.000000 0.000000VOLUME(WH2,C2)9.000000 0.000000VOLUME(WH2,C8)11.00000 0.000000VOLUME(WH3,C3)11.00000 0.000000VOLUME(WH3,C6)9.000000 0.000000VOLUME(WH4,C4)20.00000 0.000000VOLUME(WH5,C5)20.00000 0.000000VOLUME(WH6,C6)11.00000 0.000000VOLUME(WH6,C8)4.000000 0.000000VOLUME(WH6,C10)5.000000 0.000000VOLUME(WH7,C7)20.00000 0.000000VOLUME(WH8,C8)5.000000 0.000000VOLUME(WH8,C9)6.000000 0.000000VOLUME(WH8,C11)6.000000 0.000000VOLUME(WH9,C9)14.00000 0.000000VOLUME(WH10,C10)15.00000 0.000000VOLUME(WH11,C11)14.00000 0.00000025.销地销地产地产地A1A2A3T1T2T3T4B1B2B3B4产产量量A1A2A3131379-3-1123115-4-93233117119432101085T1T2T3T4214335-21-23201321201131112212202441858-42526746B1B2B3B43113101928741052846452718241-268142614214215361314销量销量202020202020201714151413 16 1120 20 20 2020 20 20 20 Global optimal solution found at iteration:41 Objective value:68.00000 直接调运：直接调运：8585元元26.614B4614B2155B320T420T2119T311A379A2B1T1A1B1B2B3B4T1T2T3T4A1A2A384201113销地销地产地产地B1 133吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨吨A17 吨，吨，A24吨，吨，A39吨吨667A1（7）A2（4+7）B1（11+4）11B2（6）B4（6）A3（9）T3（9）945B3（5）27.（设备生产计划）（设备生产计划）某公司按照合同规定需要在当年每个季度末分别提供某公司按照合同规定需要在当年每个季度末分别提供1010、1515、2525、2020台同一规格的某种机器设备。台同一规格的某种机器设备。已知该公司各季度的生产能力以及生产每台设备的成本下表。已知该公司各季度的生产能力以及生产每台设备的成本下表。如果生产的设备当季度不交货，如果生产的设备当季度不交货，则每台积压一个季度所需的存储、维护等费用为则每台积压一个季度所需的存储、维护等费用为0.150.15万元。万元。试确定在完成合同任务的条件下，试确定在完成合同任务的条件下，使公司全年生产费用最小的设备生产计划。使公司全年生产费用最小的设备生产计划。季度季度生产能力（万台）生产能力（万台）单位成本（万元）单位成本（万元）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.328.每台积压一个季度所需的存储、维护等费用为每台积压一个季度所需的存储、维护等费用为0.150.15万元万元季季度度生产能力生产能力（台）（台）单位成本单位成本（万元）（万元）需求需求（台）（台）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.310101515252520201 12 23 34 41 1 2 2 3 3 4 4交货季度交货季度生产季度生产季度交货季度交货季度生产季度生产季度 1 2 3 4 1 2 3 41 12 23 34 4 10.80 10.95 11.15 11.25 10.80 10.95 11.15 11.25 11.10 11.25 11.40 11.10 11.25 11.40 11.00 11.15 11.00 11.15 11.30 11.3029.季季度度生产能力生产能力（台）（台）单位成本单位成本（万元）（万元）需求需求（台）（台）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.310101515252520201 12 23 34 41 1 2 2 3 3 4 4交货季度交货季度生产季度生产季度30.练习练习下图是一个运输网络图，下图是一个运输网络图，A A1 1、A A2 2、A A3 3为厂家，供应量为为厂家，供应量为5050、4040、6565；B B1 1、B B2 2、B B3 3、B B4 4为销售部，需求量为为销售部，需求量为3030、2525、4040、4545。T T1 1、T T2 2为中转站，运输时允许在厂家、销售部和中转站之间转为中转站，运输时允许在厂家、销售部和中转站之间转运。边上的数据为两点间的单位运价。试建立求总运费最小的运。边上的数据为两点间的单位运价。试建立求总运费最小的数学模型。数学模型。A1A2A3T1T2B1B2B3B457555777111222299966831.