07运输问题

1、管管 理理 运运 筹筹 学学 1 第七章第七章 运运 输输 问问 题题 1 1 运运 输输 模模 型型 2 2 运输问题的计算机求解运输问题的计算机求解 3 3 运输问题的应用运输问题的应用 管管 理理 运运 筹筹 学学 2 例例1、某公司从两个产地A1、A2将物品运往三 个销地B1、B2、B3，各产地的产量、各销地 的销量和各产地运往各销地每件物品的运费 如下表所示，问：应如何调运可使总运输费 用最小？ B1B2B3 产量 A1646200 A2655300 销量150150200 1 1 运运 输输 模模 型型 管管 理理 运运 筹筹 学学 3 解：解：设 xij 为从产地Ai运往销地Bj

2、的运输量，得到 下列运输量表： B1B2B3 产量 A1x11x12x13200 A2x21x22x23300 销量150150200 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3） 管管 理理 运运 筹筹 学学 4 某种物资有若某种物资有若 干产地和销地，现在需要把这种物资从各个干产地和销地，现在需要把这种物资从各

3、个 产地运到各个销地，产地运到各个销地，。 已知已知各产地的各产地的和各销地的和各销地的以及各产以及各产 地到各销地的地到各销地的，问应如，问应如 何组织调运，才能使何组织调运，才能使 ？ 管管 理理 运运 筹筹 学学 5 根据具体问题选择确定根据具体问题选择确定。 有关信息有关信息 单位单位 运价运价 销销 或运距或运距 地地 产地产地 B1 B2 Bn 产产 量量 A1 A2 Am c11 c12 c1 n c21 c22 c2n cm1 cm2 cm n s1 s2 sm 销销 量量 d1 d2 dn n j j m i i ds 11 管管 理理 运运 筹筹 学学 6 设设x ij为从

4、产地 为从产地A i运往销地 运往销地B j的物资数量 的物资数量 （i=1，m；j=1，n），由于从），由于从Ai运出的运出的 物资总量应等于物资总量应等于Ai的产量的产量si，因此，因此xij应满足：应满足： misx n j iij , 2 , 1 1 管管 理理 运运 筹筹 学学 7 同理，运到同理，运到Bj的物资总量应该等于的物资总量应该等于Bj 的销量的销量dj，所以，所以xij还应满足：还应满足： 总运费为：总运费为： m i jij njdx 1 , 1 m i n j ijij xcz 11 管管 理理 运运 筹筹 学学 8 njmix njdx misx ts xcMinZ

5、 ij m i jij n j iij m i n j ijij ,1;,1,0 ,1 ,1 . 1 1 11 m i n j ji ds 11 产销平衡条件 管管 理理 运运 筹筹 学学 9 1）有时目标函数求最大。如求利润最大或营业额 最大等； 2）当某些运输线路上的能力有限制时，在模型中 直接加入约束条件（等式或不等式约束)； 3）不可接受的路线：a.处理方法有删除弧（变 量）；b.赋予非常高的目标函数成本系数；c.或者， 增加一个约束条件。 4）产销不平衡时，可加入假想的产地（销大于产 时）或销地（产大于销时）。 管管 理理 运运 筹筹 学学 10 ？ 转化转化 管管 理理 运运 筹筹

6、 学学 11 2 2 运输问题的计算机求解运输问题的计算机求解 例例2、某公司从两个产地A1、A2将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表所示，问：应 如何调运可使总运输费用最小？ B1 B2 B3 产产量量 A1 6 4 6 300 A2 6 5 5 300 销销量量 150 150 200 600 500 管管 理理 运运 筹筹 学学 12 B1 B2 B3 B4 产产量量 A1 6 4 6 0 300 A2 6 5 5 0 300 销销量量 150 150 200 100 600 600 管管 理理 运运 筹筹 学学 13

7、2 2 运输问题的计算机求解运输问题的计算机求解 例例3、某公司从两个产地A1、A2将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表所示，问：应 如何调运可使总运输费用最小？ B1 B2 B3 产产量量 A1 6 4 6 200 A2 6 5 5 300 销销量量 250 200 200 500 650 管管 理理 运运 筹筹 学学 14 B1 B2 B3 产产量量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销销量量 250 200 200 650 650 管管 理理 运运 筹筹 学学 15 练习 计算

8、机求解 管管 理理 运运 筹筹 学学 16 3 3 运输问题的应用运输问题的应用 一、产销不平衡的运输问题一、产销不平衡的运输问题 例例4、石家庄北方研究院有一、二、三三个区。每年分 别需要用煤3000、1000、2000吨，由河北临城、山西 盂县两处煤矿负责供应，价格、质量相同。供应能力 分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0- -300吨，二区必须满足需求量，三区供应量不少于 1500吨，试求总费用为最低的调运方案。 管管 理理 运运 筹筹 学学 17 解：解： 根据题意，作出产销平衡与运价表 这里 M 代表一个很大的正数，其作用是强迫相应 的

9、x31、 x33、 x34取值为0 管管 理理 运运 筹筹 学学 18 3 3 运输问题的应用运输问题的应用 一、产销不平衡的运输问题一、产销不平衡的运输问题 例例5、设有A、B、C三个化肥厂供应1、2、3、4四个 地区的农用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。 1234产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需要量507030不限 管管 理理 运运 筹筹 学学 19 解： 根据题意，增加一个虚拟产地，并将地区按销根据题意，增加一个虚拟产地，并将地区按销 量进行分割，作出产销平衡与运价表：量进行

10、分割，作出产销平衡与运价表： 由于由于C不需要运到第不需要运到第4个地区，因此运费设为个地区，因此运费设为M。 同时，对应同时，对应 4”的销量的销量 50 是考虑问题本身适当取是考虑问题本身适当取 的数据，根据产销平衡要求确定的数据，根据产销平衡要求确定 D的产量为的产量为 50。 管管 理理 运运 筹筹 学学 20 解：解： 根据题意，作出产销平衡与运价表： 1.最低要求必须满足，因此把相应的虚设产地运费最低要求必须满足，因此把相应的虚设产地运费 取为取为 M。 2.最高要求与最低要求的差允许按需要安排，因此最高要求与最低要求的差允许按需要安排，因此 把相应的虚设产地运费取为把相应的虚设产

11、地运费取为 0 。 管管 理理 运运 筹筹 学学 21 3 3 运输问题的应用运输问题的应用 二、生产与储存问题二、生产与储存问题 例例6、某厂按合同规定须于当年每个季度末分别提供10、15、 25、20台同一规格的柴油机。已知该厂各季度的生产能力 及生产每台柴油机的成本如下表。如果生产出来的柴油机 当季不交货，每台每积压一个季度需储存、维护等费用0.15 万元。试求在完成合同的情况下，使该厂全年生产总费用 为最小的决策方案。 生产能力（台） 单位成本（万元） 一季度2510.8 二季度3511.1 三季度3011.0 四季度1011.3 管管 理理 运运 筹筹 学学 22 3 3 运输问题的

12、应用运输问题的应用 解：解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交 货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作 运费。可构造下列产销平衡问题： 目标函数：目标函数：Min f =

13、 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第一季度 第二季度 第三季度 第四季度 D 产量 第一季度 10.80 10.95 11.10 11.25 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 销量 10 15 25 20 30 100 100 管管 理理 运运 筹筹 学学 23 3 3 运输问题的应用运输问题

14、的应用 二、生产与储存问题二、生产与储存问题 例例7（不讲不讲）、）、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份 各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货， 则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓 储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月，因此在6 月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万 元。问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓 储、维护）最少？ 正常生产能力（台） 加班生产能力（台） 销量（台）单

15、台费用（万元） 1 月份601010415 2 月份50107514 3 月份902011513.5 4 月份1004016013 5 月份1004010313 6 月份80407013.5 管管 理理 运运 筹筹 学学 24 3 3 运输问题的应用运输问题的应用 解：解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产各月生产与交货分别视为产 地和销地地和销地 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设 一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为第0行； 3）6月份的需求除70台销量外，还要80台库存，其

16、需求应为70+80=150台； 4）1-6表示1-6月份正常生产情况， 1-6表示1-6月份加班生产情况。 产销平衡与运价表： 1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5 16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 14.9 0 50 2 M 15 15.3 15.5 15.7 15.9 0 10 3 M M 13.5 13.8 14.0 14.2 0 90 3

17、M M 14.5 14.8 15.0 15.2 0 20 4 M M M 13.0 13.3 13.5 0 100 4 M M M 14.0 14.3 14.5 0 40 5 M M M M 13.0 13.3 0 100 5 M M M M 14.0 14.3 0 40 6 M M M M M 13.5 0 80 6 M M M M M 14.5 0 40 销量 104 75 115 160 103 150 36 743 743 管管 理理 运运 筹筹 学学 25 3 3 运输问题的应用运输问题的应用 用“管理运筹学”软件解得的结果是：1-6月最低生产费用为8307.5 万元，每月的销售安排

18、如下表所示 管管 理理 运运 筹筹 学学 26 3 3 运输问题的应用运输问题的应用 三、转运问题：三、转运问题： 在原运输问题上增加若干转运站。运输方式有：产地 转运站、转 运站 销地、产地 产地、产地 销地、销地 转运站、销地 产 地等。 例8、腾飞电子仪器公司在大连和广州 有两个分厂生产同一种仪器，大连分厂 每月生产400台，广州分厂每月生产600 台。该公司在上海和天津有两个销售公 司负责对南京、济南、南昌、青岛四个 城市的仪器供应。另外因为大连距离青 岛较近，公司同意大连分厂向青岛直接 供货，运输费用如图，单位是百元。问应该如何调运仪器， 可使总运输费用最低？图中 1- 广州、2 -

19、 大连、 3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛 管管 理理 运运 筹筹 学学 27 3 3 运输问题的应用运输问题的应用 解：解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量 例8（续） 目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+

20、6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. x13+ x14 600 (广州分厂供应量限制） x23+ x24+ x28 400 (大连分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 150 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （青岛

21、的销量） xij 0 , i,j = 1,2,3,4,5,6,7,8 管管 理理 运运 筹筹 学学 28 3 3 运输问题的应用运输问题的应用 用用“管理运筹学管理运筹学”软件求得结果：软件求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。 最小运输费用为：最小运输费用为：4600百元百元 例例9（不讲不讲）、）、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B

22、3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表： 试求总费用为最少的调运方案。 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间 转运。 B1B2B3B4 产量 A13113107 A219284 A3741059 销量3656和=20 管管 理理 运运 筹筹 学学 29 3 3 运输问题的应用运输问题的应用 运价如下表： 解：解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3