管理运筹学_第4章__运输问题(zy)

1、管管 理理 运运 筹筹 学学 1 第四章第四章 运运 输输 问问 题题 1 1运运 输输 模模 型型 2 2运输问题的计算机求解运输问题的计算机求解 3 3运输问题的应用运输问题的应用 管管 理理 运运 筹筹 学学 2 例例1、某公司从两个产地A1、A2将物品运往三个销 地B1、B2、B3，各产地的产量、各销地的销量和 各产地运往各销地每件物品的运费如下表所示， 问：应如何调运可使总运输费用最小？ B 1 B 2 B 3 产量 A 1 646200 A 2 655300 销量150150200 1 1运运 输输 模模 型型 管管 理理 运运 筹筹 学学 3 解：解： 产销平衡问题： 总产量 =

2、 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B 1 B 2 B 3 产量 A 1 x11x12x13200 A 2 x21x22x23300 销量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） 1 1运运 输输 模模 型型 管管 理理 运运 筹筹 学学 4 1 1运

3、运 输输 模模 型型 一般运输模型：一般运输模型：产销平衡 A1、 A2、 Am 表示某物资的m个产地； B1、 B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj 的单位运价。 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输 量问题的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 管管 理理 运运

4、 筹筹 学学 5 1 1运运 输输 模模 型型 变化：变化： 1）有时目标函数求最大。如求利润最大或营业额 最大等； 2）当某些运输线路上的能力有限制时，在模型中 直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产 时）或销地（产大于销时）。 管管 理理 运运 筹筹 学学 6 1 1运运 输输 模模 型型 例例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3，各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示，问：应如何调运可使总运输费 用最小？ 解：增加一个虚设的销地运输费用为0 B 1 B 2 B 3 产产 量量 A

5、1 6 4 6 300 A 2 6 5 5 300 销销 量量 150 150 200 600 500 B1 B2 B3 B4 产产量量 A1 6 4 6 0 300 A2 6 5 5 0 300 销销量量 150 150 200 100 600 600 管管 理理 运运 筹筹 学学 7 1 1运运 输输 模模 型型 例例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3，各产地的产量、各销地的销量和各产地运往各销地每 件物品的运费如下表所示，问：应如何调运可使总运输费 用最小？ 解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 B1 B2 B3 产产量量 A

6、1 6 4 6 200 A2 6 5 5 300 销销量量 250 200 200 500 650 B1 B2 B3 产产量量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销销量量 250 200 200 650 650 管管 理理 运运 筹筹 学学 8 2 2运输问题的计算机求解运输问题的计算机求解 管管 理理 运运 筹筹 学学 9 2 2运输问题的计算机求解运输问题的计算机求解 管管 理理 运运 筹筹 学学 10 2 2运输问题的计算机求解运输问题的计算机求解 管管 理理 运运 筹筹 学学 11 3 3运输问题的应用运输问题的应用 一、产销不平衡的运输问题

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

8、3 3 3运输问题的应用运输问题的应用 一、产销不平衡的运输问题一、产销不平衡的运输问题 例例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农 用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。 1234 产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需要量 507030 不限 管管 理理 运运 筹筹 学学 14 3 3运输问题的应用运输问题的应用 解：解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把 相应的虚设

9、产地运费取为 0 。对应 4”的销量 50 是考虑问题 本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 1 1” 2 3 4 4” 产 量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 销 量 30 20 70 30 10 50 210 210 管管 理理 运运 筹筹 学学 15 3 3运输问题的应用运输问题的应用 二、生产与储存问题二、生产与储存问题 例例6、某厂按合同规定须于当年每个季度末分别提供10、15、 25、20台同一规格的柴油机。已知该厂各季度的生

10、产能力 及生产每台柴油机的成本如右表。如果生产出来的柴油机 当季不交货，每台每积压一个季度需储存、维护等费用0.15 万元。试求在完成合同的情况下，使该厂全年生产总费用 为最小的决策方案。 生产能力（台） 单位成本（万元） 一季度2510.8 二季度3511.1 三季度3011.0 四季度1011.3 管管 理理 运运 筹筹 学学 16 3 3运输问题的应用运输问题的应用 解：解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24

11、 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交 货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作 运费。可构造下列产销平衡问题： 目标函数：目标函数：Min f = 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 第一季度 第二季度 第三季度 第四季

12、度 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 管管 理理 运运 筹筹 学学 17 3 3运输问题的应用运输问题的应用 二、生产与储存问题二、生产与储存问题 例例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生 产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货， 则需要运到

13、分厂库房，每台增加运输成本0.1万元,每台机器每月的平均 仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月，因 此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加 成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包括 运输、仓储、维护）最少？ 正常生产能力（台） 加班生产能力（台） 销量（台） 单台费用（万元） 1月份601010415 2月份50107514 3月份902011513.5 4月份1004016013 5月份1004010313 6月份80407013.5 管管 理理 运运 筹筹 学学 18 3 3运输问题的应用运输问题的应用 解：解：

14、 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产各月生产与交货分别视为产 地和销地地和销地 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设 一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为第0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为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 1

15、5 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 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

16、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 管管 理理 运运 筹筹 学学 19 3 3运输问题的应用运输问题的应用 用“管理运筹学”软件解得的结果是：1-6月最低生产费用为8307.5 万元，每月的销售安排如下表所示 管管 理理 运运 筹筹 学学 20 3 3运输问题的应用运输问题的应用 三、转运问题：三、转运问题： 在原运输问题上增加若干转运站。运输方式有：产地 转运站、转 运站 销地、产地 产地、产地 销地、销地 转运站、销地 产 地等。 例8、腾飞电子仪器公司在大连和广州

17、 有两个分厂生产同一种仪器，大连分厂 每月生产400台，广州分厂每月生产600 台。该公司在上海和天津有两个销售公 司负责对南京、济南、南昌、青岛四个 城市的仪器供应。另外因为大连距离青 岛较近，公司同意大连分厂向青岛直接 供货，运输费用如图，单位是百元。问应该如何调运仪器， 可使总运输费用最低？图中 1- 广州、2 - 大连、 3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛 管管 理理 运运 筹筹 学学 21 3 3运输问题的应用运输问题的应用 解：解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有

18、可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量 例8（续） 目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. x13+ x14 600 (广州分厂供应量限制） x23+ x24+ x28 400 (大连分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38

19、= 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 150 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （青岛的销量） xij 0 , i,j = 1,2,3,4,5,6,7,8 管管 理理 运运 筹筹 学学 22 3 3运输问题的应用运输问题的应用 用用“管理运筹学管理运筹学”软件求得结果：软件求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x2

20、8 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。 最小运输费用为：最小运输费用为：4600百元百元 管管 理理 运运 筹筹 学学 23 3 3运输问题的应用运输问题的应用 例例9、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表： 试求总费用为最少的调运方案。 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一 起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与 销地之间转运。 B 1 B 2 B 3 B 4 产量 A 1 3113107 A 2 19284 A 3 741059 销量3656和=20 管管 理理 运运 筹筹 学学 24 3 3运输问题的应用运输问题的应用 运价如下表： 解：解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20；