管理运筹学 第7章 运输问题ppt课件

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

2、A1646200A2655300销量150150200解：解： 产销平衡问题：产销平衡问题： 总产量总产量 = 总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到以下运输量表：的运输量，得到以下运输量表： B1B2B3产量A1x11x12x13200A2x21x22x23300销量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 =

3、 200 xij 0 ( i = 1、2；j = 1、2、3 1 1 运运 输输 模模 型型管管 理理 运运 筹筹 学学1 1 运运 输输 模模 型型普通运输模型：产销平衡普通运输模型：产销平衡 A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示某表示某物质的物质的n个销地；个销地；si 表示产地表示产地Ai的产量；的产量； dj 表示销地表示销地Bj 的销量；的销量； cij 表示把物表示把物资从产地资从产地Ai运往销地运往销地Bj的单位运价。的单位运价。设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到以下普通运输量问题的模型：的运输

4、量，得到以下普通运输量问题的模型： 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) 变化：变化： 1有时目的函数求最大。如求利润最大或营业额最大等；有时目的函数求最大。如求利润最大或营业额最大等； 2当某些运输线路上的才干有限制时，在模型中直接参与约束条件等式或当某些运输线路上的才干有限制时，在模型中直接参与约束条件等式或不等式约束不等式约束)； 3产销不平衡时，可参与假想的产地销大于产时或销地产大于销

5、时。产销不平衡时，可参与假想的产地销大于产时或销地产大于销时。管管 理理 运运 筹筹 学学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 B1 B2 B

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

7、1 B2 B3 产产量量 A1 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 解：添加一个解：添加一个虚设的产地虚设的产地运输费用为运输费用为0管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用一、产销不平衡的运输问题一、产销不平衡的运输问题例例4、石家庄北方研讨院有一、二、三三个区。每年分别需求用煤、石家庄北方研讨院有一、二、三三个区。每年分别需求用煤3000、1000、20

8、00吨，由河北临城、山西盂县两处煤矿担任供应，价钱、质量一样。供吨，由河北临城、山西盂县两处煤矿担任供应，价钱、质量一样。供应才干分别为应才干分别为1500、4000吨，运价为：吨，运价为： 由于需大于供，经院研讨决议一区供应量可减少由于需大于供，经院研讨决议一区供应量可减少0-300吨，二区必需满吨，二区必需满足需求量，三区供应量不少于足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。解：解： 根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：这里这里 M 代表一个很大的正数，其作用是强迫相应的代表一个很大的正数，其作用是强迫相应

9、的 x31、 x33、 x34取值为取值为0。管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用一、产销不平衡的运输问题一、产销不平衡的运输问题例例5、设有、设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4四个地域的农用化肥。假设效果一四个地域的农用化肥。假设效果一样，有关数据如下表：样，有关数据如下表： 试求总费用为最低的化肥调拨方案。试求总费用为最低的化肥调拨方案。解：解： 根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表： 最低要求必需满足，因此把相应的虚设产地运费取为最低要求必需满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低，而最高要求与

10、最低要求的差允许按需求安排，因此把相应的虚设产地运费取为要求的差允许按需求安排，因此把相应的虚设产地运费取为 0 。对应。对应 4的销量的销量 50 是思索问题本身适当取的数据，根据产销平衡要求确定是思索问题本身适当取的数据，根据产销平衡要求确定 D的产量为的产量为 50。 1234产量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限 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

11、50 销量 30 20 70 30 10 50 210 210 管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用二、消费与储存问题二、消费与储存问题例例6、某厂按合同规定须于当年每个季度末分别提供、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。知该厂各季度的消费才干及台同一规格的柴油机。知该厂各季度的消费才干及消费每台柴油机的本钱如右表。假设消费出来的柴油机当消费每台柴油机的本钱如右表。假设消费出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂

12、全年消费总费用万元。试求在完成合同的情况下，使该厂全年消费总费用为最小的决策方案。为最小的决策方案。生产能力（台） 单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用解：解： 设设 xij为第为第 i 季度消费的第季度消费的第 j 季度交货的柴油机数目，那么应满足：季度交货的柴油机数目，那么应满足： 交货：交货：x11 = 10 消费：消费：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 =

13、25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10目的函数：目的函数：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 第一季度 第二季度 第三季度 第四季度 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.3

14、0 0 10 销量 10 15 25 20 30 100 100 把第 i 季度消费的柴油机数目看作第 i 个消费厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；本钱加储存、维护等费用看作运费。可构造以下产销平衡问题：管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用二、消费与储存问题二、消费与储存问题例例7、光明仪器厂消费电脑绣花机是以产定销的。知、光明仪器厂消费电脑绣花机是以产定销的。知1至至6月份各月的消费月份各月的消费才干、合同销量和单台电脑绣花机平均消费费用见下表：才干、合同销量和单台电脑绣花机平均消费费用见下表： 知上年末库存知上年末库存103台绣

15、花机，假设当月消费出来的机器当月不交货，台绣花机，假设当月消费出来的机器当月不交货，那么需求运到分厂库房，每台添加运输本钱那么需求运到分厂库房，每台添加运输本钱0.1万元万元,每台机器每月的平均每台机器每月的平均仓仓储费、维护费为储费、维护费为0.2万元。在万元。在7-8月份销售淡季，全厂停产月份销售淡季，全厂停产1个月，因此在个月，因此在6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存80台。加班消费机器每台添加本钱台。加班消费机器每台添加本钱1万万元。问应如何安排元。问应如何安排1-6月份的消费，可使总的消费费用包括运输、仓月份的消费，可使总的消费费用包括运输、仓储、维护最少

16、？储、维护最少？正常生产能力（台） 加班生产能力（台） 销量（台）单台费用（万元）1 月份6010104152 月份501075143 月份902011513.54 月份10040160135 月份10040103136 月份80407013.5管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用解：解： 这个消费存储问题可化为运输问题来做。思索：各月消费与交货分别视为产这个消费存储问题可化为运输问题来做。思索：各月消费与交货分别视为产地和销地地和销地 11-6月份合计消费才干包括上年末储存量为月份合计消费才干包括上年末储存量为743台，销量为台，销量为707台。设台。设一假想销地

17、销量为一假想销地销量为36； 2上年末库存上年末库存103台，只需仓储费和运输费，把它列为第台，只需仓储费和运输费，把它列为第0行；行； 36月份的需求除月份的需求除70台销量外，还要台销量外，还要80台库存，其需求应为台库存，其需求应为70+80=150台；台； 41-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

18、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 6 M M M M M 13.5

19、0 80 6 M M M M M 14.5 0 40 销量 104 75 115 160 103 150 36 743 743 管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用 用“管理运筹学软件解得的结果是：1-6月最低消费费用为8307.5万元，每月的销售安排如下表所示管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用三、转运问题：三、转运问题： 在原运输问题上添加假设干转运站。运输方式有：产地在原运输问题上添加假设干转运站。运输方式有：产地 转运站、转运站、转转运站运站 销地、产地销地、产地 产地、产地产地、产地 销地、销地销地、销地 转运站、销地转运站、销

20、地 产产地等。地等。例例8、腾飞电子仪器公司在大连和广州、腾飞电子仪器公司在大连和广州有两个分厂消费同一种仪器，大连分厂有两个分厂消费同一种仪器，大连分厂每月消费每月消费400台，广州分厂每月消费台，广州分厂每月消费600台。该公司在上海和天津有两个销售公台。该公司在上海和天津有两个销售公司担任对南京、济南、南昌、青岛四个司担任对南京、济南、南昌、青岛四个城市的仪器供应。另外由于大连间隔青城市的仪器供应。另外由于大连间隔青岛较近，公司赞同大连分厂向青岛直接岛较近，公司赞同大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，供货，运输费用如图，单位是百元。问应该如何调运仪器，可

21、使总运输费用最低？图中可使总运输费用最低？图中 1- 广州、广州、2 - 大连、大连、3 - 上海、上海、4 - 天津、天津、5 - 南京、南京、6 - 济南、济南、7 - 南昌、南昌、8 - 青岛青岛管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用解：设解：设 xij xij 为从为从 i i 到到 j j 的运输量，可得到有以下的运输量，可得到有以下特点的线性规划模型：特点的线性规划模型：目的函数：目的函数：Min f = Min f = 一切能够的运输费用运输单一切能够的运输费用运输单价与运输量乘积之和价与运输量乘积之和约束条件：约束条件： 对产地发点对产地发点 i i

22、：输出量：输出量 - - 输入量输入量 = = 产产量量 对转运站中转点：输入量对转运站中转点：输入量 - - 输出量输出量 = 0= 0 对销地收点对销地收点 j j ：输入量：输入量 - - 输出量输出量 = = 销销量量管管 理理 运运 筹筹 学学目的函数： 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 +

23、 x36+ x37 + x38 上海销售公司，转运站 x14+ x24 = x45 + x46+ x47 + x48 天津销售公司，转运站 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管管 理理 运运 筹筹 学学用用“管理运筹学软件求得结果：管理运筹学软件求得结果： x13 = 550 x14 =50 x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 x23

24、 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 x45 = 0 x46 = 150 x47 = 0 x48 = 0 。最小运输费用为：最小运输费用为：46004600百元百元管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用例例9、某公司有、某公司有A1、 A2、 A3三个分厂消费某种物资，分别供应三个分厂消费某种物资，分别供应B1、 B2、 B3、 B4四个地

25、域的销售公司销售。假设质量一样，有关数据如下表：四个地域的销售公司销售。假设质量一样，有关数据如下表： 试求总费用为最少的调运方案。试求总费用为最少的调运方案。假设：假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一同运；同运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。销地之间转运。B1B2B3B

26、4产量A13113107A219284A3741059销量3656和=20管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用运价如下表：解：把此转运问题转化为普通运输问题： 1、把一切产地、销地、转运站都同时看作产地和销地； 2、运输表中不能够方案的运费取作M，本身对本身的运费为0； 3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20； Bi： 产量为 20， 销量为 20 +原销量，其中20为各点能够变化的最大流量； 4、对于最优方案，其中 xi i 为本身对本身的运量，实践上不进展运作。A1A2A3T1T2T3T4B1B2B3B4A113214

27、3311310A21-35-21928A33-1-2374105T12311322846T215-1114527T34-23121824T43232121-2621194858-121B332104222423B410856746213管管 理理 运运 筹筹 学学3 3 运输问题的运用运输问题的运用 扩展的运输问题产销平衡与运价表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5

28、 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 26 25 26 240 管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作

29、业法运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法，其本质是单纯形法。 运输问题都存在最优解。 计算过程假设产销平衡： 1.找出初始根本可行解。对于有m个产地n个销地的产销平衡问题，那么有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只需m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在mn的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。 2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别能否到达最优解，假设已是最优，停顿计算，否那么转到下一步。 3.确定入基变量和出基变量，找出新的根本

30、可行解。在表上用闭回路法调整。 4.反复2、3直到得到最优解。管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法例10.喜庆食品公司有三个消费面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？这是一个产销平衡的运输问题，因此不需求再设假想产地和销地了。 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656 2020管管

31、理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法一、确定初始根本可行解 为了把初始根本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始根本可行解调运量。 1.西北角法：先从表的左上角即西北角的变量x11开场分配运输量，并使x11取尽能够大的值，即x11=min(7,3)=3,那么x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。 销地产地 B1 B2 B3 B4 产量 A1 3 47 4 0 A2 2 24 2 0 A3 3 69 6 0 销量 3 0 6 2 0 5

32、 3 0 6 0 2020311310851029471管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法2.最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽能够大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的33矩阵中再找最小运价，同理可得其他的根本可行解。 普通来说用最小元素法求得的初始根本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始根本可行解出发求最优解的迭代次数能够少一些。 销地产

33、地 B1 B2 B3 B4 产量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 销量 3 0 6 0 5 4 0 6 3 0 2020311310851029471管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法 在求初始根本可行解时要留意的两个问题： 1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。 2.用最小元素法时，能够会出现只剩下一行或一列的一切格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可

34、以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法二、最优解的判别1.闭回路法 所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿程度或垂直方向前进，只需遇到代表基变量的填入数字的格才干向左或右转90度当然也可以不改动方向继续前进，这样继续下去，直至回到出发的那个空格，由此构成的封锁折线叫做闭回路。一个空格存在独一的闭回路。 所谓闭回路法，就是对于代表非基变量的空格其调运量为零，把它的调运量调整为1，由于产销平衡的要求,我们必需对这个空格的闭回路的顶点的调运量加上或减少1

35、。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。假设一切代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，那么已求得最优解，否那么继续迭代找出最优解。管管 理理 运运 筹筹 学学4 4* * 运输问题的表上作业法运输问题的表上作业法从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其他都为基变量。如今把x11的调运量从零添加为1吨，运费也添加了3元，为了使A1产量平衡，x13必需减少1吨，运费减少3元。为了B3的销量平衡，x23必需添加1吨，运费添加2元。同理把x21减少1吨，运费减少1元。调整后，总运费添加了3-3+2-1=1元。阐明假设让x11为基变量，运费就会添加，其添加值1作为x11的检验数，为了区别调整量，我们把1加圈。用同样的方法可以找出一切空格即非基变量的检验数。 销地产地 B1 B2 B3 B4 产量 A1 1 4 7 A2 3 1 4 A3 9 销量 3 6 5 6 20203113108510294