第四章运输问题.ppt
运运 输输 问问 题题4.1 运输问题及其数学模型 典型背景单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。mAAA,21nBBB,21maaa,21nbbb,21iABjijc 决策变量 表示由 到 的物品数量。iAjBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121销地产地销量产量 产销平衡问题总产量=总销量 即 产销不平衡问题总产量=总销量nijmiiba11总产量总销量 总产量销，即销，即 ， 只要增加一只要增加一个假想的销地个假想的销地j=n+1（实际上是贮存），该销（实际上是贮存），该销地总需要量为：地总需要量为： 。而在单位运价表中从。而在单位运价表中从各产地到假想销地的单位运价为各产地到假想销地的单位运价为0，就转化为，就转化为一个产销平衡运输问题。一个产销平衡运输问题。nijmiiba11nijmiiba11产销不平衡运输问题 当销大于产时，可以在产销平衡表中增加一个当销大于产时，可以在产销平衡表中增加一个假想的产地假想的产地i=m+1，该地产量为，该地产量为 ，在，在单位运价表上令从该假想产地到各销地的运价单位运价表上令从该假想产地到各销地的运价为为0，同样可以转化为一个产销平衡的运输问，同样可以转化为一个产销平衡的运输问题。题。niimijab11例例设有三个化肥厂供应四个地区的农用化肥。假定等设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。如下表所示，试求出总的运费最节省的化肥调运方案。 需求地区需求地区化肥厂化肥厂A1613221750B1413191560C19202350最低需求最低需求（万吨）（万吨）3070010最高需求最高需求（万吨）（万吨）507030不限不限产量产量（万吨）（万吨）IIIIIIIV三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量问：根据现有三个化肥厂的产量，地区IV 最高需求是否可以不限？最高需求是多少？160 3070060吨四个地区对化肥的最高需求为50703060 210吨需求地区需求地区产量产量运费单价运费单价（万吨）（万吨）化肥厂化肥厂A16161322171750B14141319151560C19192023MM50假想地假想地DM0M0M050销量销量210（万吨）（万吨）210IIIIIIVIV”302070301050II” 练习求下列运输问题：产地 销地B1 B2B3产量 A151710 A264680 A332515 销量752080五、运输问题的应用五、运输问题的应用（一）生产与储存的问题（一）生产与储存的问题 例例某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能台同一规格的柴油机。已知该厂各季度的生产能力及市场每台柴油机的成本如下表所示。又如果生产出来力及市场每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维的柴油机当季不交货的，每台每积压一个季度需储存、维护费用护费用0.15万元。要求在完成合同的情况下，做出使该厂全万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。年生产（包括储存、维护）费用最小的决策。 季度季度生产能力生产能力（台）（台）单位成本单位成本（万元）（万元）12510.823511.13301141011.3设设Xij为第为第i季度生产的用于第季度生产的用于第j季度交货的柴油机数季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用。实际的成本为该季度生产成本加上储存和维护费用。四个季度的生产能力为四个季度的生产能力为100台。而四个季度末共须提供柴台。而四个季度末共须提供柴油机油机70台台。 销地销地运费单价运费单价产地产地I10.810.9511.111.25025IIM11.111.2511.4035IIIMM1111.15030IVMMM11.3010100100IIIIVD产量产量（台）（台）销量销量1015252030III（二）调度问题（二）调度问题例某航运公司承担六个港口初始例某航运公司承担六个港口初始A、B、C、D、E、F的的四条固定航线的物资运输任务。已知各条航线的起点、终点四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表城市及每天航班数见下表1。假定各条航线使用相同型号的。假定各条航线使用相同型号的船只，又各城市间的航程天数见表船只，又各城市间的航程天数见表2。又知每条船只每次装卸货的时间各需又知每条船只每次装卸货的时间各需1天，则该航运公天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？司至少应配备多少条船，才能满足所有航线的运货需求？ 表表1 表2(1)载货航程需要的周转船只数：载货航程需要的周转船只数： 到到从从A0121477B1031388C2301555D14131501720E7851703F7852030EFABCD航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数周转船只数周转船只数11171193572131521031719194113115115 例如：航线例如：航线1，在港口，在港口E装货装货1天，天，ED航程航程17天，在天，在D卸货卸货1天，总计天，总计19天。每天天。每天3航班。故该航线需周转船航班。故该航线需周转船57条条以上共需周转船只数以上共需周转船只数91条。条。(2)各港口间调度所需船只数。有些港口每天到达船数多各港口间调度所需船只数。有些港口每天到达船数多于需要船数。例如，港口于需要船数。例如，港口D，每天到达，每天到达3条，需求条，需求1条。条。港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101 为使各港口间调度周转所需的为使各港口间调度周转所需的空船空船数最少，其产销平衡数最少，其产销平衡表如下。单位运价应为相应各港口之间的船只航程天数。表如下。单位运价应为相应各港口之间的船只航程天数。天数天数港口港口A港口港口B港口港口E每天多余船只每天多余船只港口港口C2352港口港口D1413172港口港口F7831每天缺少船只每天缺少船只113天数天数港口港口A港口港口B港口港口E每天多余船只每天多余船只港口港口C112港口港口D112港口港口F11每天缺少船只每天缺少船只113可求出空船的最优调度空船的最优调度方案如下： 由上表可计算得知最少周转的空船数为由上表可计算得知最少周转的空船数为40条。条。所以，在不考虑维修、储备等情况下，该公司至少应配备所以，在不考虑维修、储备等情况下，该公司至少应配备131条船。条船。（三）转运问题（三）转运问题例：某电子仪器公司在大连和广州有两个分厂，大连分厂例：某电子仪器公司在大连和广州有两个分厂，大连分厂每月生产每月生产400台某种仪器，广州分厂每月生产台某种仪器，广州分厂每月生产600台某种仪器。台某种仪器。该公司在上海与天津有两个销售公司负责对南京、济南、该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，公司同意大连分厂也可以向青岛直接供货。公司同意大连分厂也可以向青岛直接供货。这些城市间的每台仪器的运输费用我们标在两个城市间的这些城市间的每台仪器的运输费用我们标在两个城市间的弧上，单位为百元。问应该如何调运仪器，使得总的运输费最弧上，单位为百元。问应该如何调运仪器，使得总的运输费最低。低。 思路思路:将转运问题化为无转运问题。将转运问题化为无转运问题。中转地中转地3、4既可作为产地，也可作为销地。既可作为产地，也可作为销地。 到到运费运费从从123MMMM600231MMM440030M263610004M0446510003000300078产量产量销量销量100010002001503503003456例：例：某公司经销甲产品，它下设三个加工厂，每日的产量分某公司经销甲产品，它下设三个加工厂，每日的产量分别为别为A17吨，吨，A24吨，吨，A39吨。该公司把这些产品分吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为别运往四个销售点。各销售点每日销量为B13吨，吨，B26吨，吨，B35吨，吨，B46吨。已知从各工厂到各销售点的单位吨。已知从各工厂到各销售点的单位产品的运价如下表所示。产品的运价如下表所示。 销售点销售点加工厂加工厂A1311310A21928A374105B1B2B3B4如果假定如果假定1）每个工厂生产的产品不一定直接发运到销售点，可以）每个工厂生产的产品不一定直接发运到销售点，可以其中几个产地集中一起运；其中几个产地集中一起运；2）运往各销售点的产品可以先运给其中几个销售点，再）运往各销售点的产品可以先运给其中几个销售点，再转运给其它销售点；转运给其它销售点；3）除产地、销售点之外，中间还可以有几个转运站，在）除产地、销售点之外，中间还可以有几个转运站，在产地之间、销售点之间或产地与销售点之间转运。产地之间、销售点之间或产地与销售点之间转运。已知各产地、销售点、中间转运站及相互之间每吨产品的已知各产地、销售点、中间转运站及相互之间每吨产品的运价如下表所示，问在考虑到产销地之间直接运输和非直接运价如下表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往各个销售点，使总的运费最少。品运往各个销售点，使总的运费最少。A1A2A3T1T2T3T4B1B2B3B4A1132143311310A213521928A3312374105T12311322846T2151114527T3423121824T4323212126B13172411142B21194858121B332104222423B410856746213产地产地中间转运站中间转运站销地销地产产地地中中间间转转运运站站销销地地销量2020202020202023262526产量2724292020202020202020
