韩伯棠管理运筹学(第三版)-第七章-运输问题分析ppt课件.ppt

PERSIL30C40C60C95CNeuJaPERSIL30C40C60C95CNeuJaREWE运运运运 筹筹筹筹 学学学学第七章第七章 运输问题运输问题统筹安排成本最低1在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第五章第五章 运运 输输 问问 题题1 运运 输输 模模 型型2 运输问题的计算机求解运输问题的计算机求解3 运输问题的应用运输问题的应用4*运输问题的表上作业法运输问题的表上作业法2在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么例例1、某某公公司司从从两两个个产产地地A1、A2将将物物品品运运往往三三个个销销地地B1、B2、B3，各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每件件物物品品的的运运费费如如下下表表所所示示，问问：应应如如何何调调运运可可使使总总运运输输费费用用最小？最小？1 1 运运 输输 模模 型型3解：解：产销平衡问题：产销平衡问题：总产量总产量=总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到的运输量，得到下列运输量表：下列运输量表：4 Min f=6x11+4x12+6x13+6x21+5x22+5x23 5产地产地A1运出的运输量等于其产量：运出的运输量等于其产量：x11+x12+x13=200产地产地A2运出的运输量等于其产量：运出的运输量等于其产量：x21+x22+x23=300运到销地运到销地B1的运输量等于其需求量：的运输量等于其需求量：x11+x21=150运到销地运到销地B2的运输量等于其需求量：的运输量等于其需求量：x12+x22=150运到销地运到销地B3的运输量等于其需求量：的运输量等于其需求量：x13+x23=200运输量非负：运输量非负：xij 0(i=1,2；j=1,2,3)6在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么整理得：整理得：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 运运 输输 模模 型型7在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1 1 运运 输输 模模 型型一般运输模型：一般运输模型：产销平衡产销平衡 A1、A2、Am 表表示示某某物物资资的的m个个产产地地；B1、B2、Bn 表表示示某某物物质质的的n个个销销地地；ai 表表示示产产地地Ai的的产产量量；bj 表表示示销销地地Bj 的的销销量量；cij 表表示示把把物物资资从从产产地地Ai运运往往销销地地Bj的单位运价。的单位运价。设设 xij 为为从从产产地地Ai运运往往销销地地Bj的的运运输输量量，得得到下列一般运输量问题的模型：到下列一般运输量问题的模型：8在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么运输问题及其数学模型运输问题及其数学模型bnb2b1销量销量 BnB2B1 销地销地产地产地AmA2A1ama2a1产量产量 产产销销平衡平衡运价运价1 1 运运 输输 模模 型型9在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么bnb2b1销量销量BnB2B1 销地销地产地产地AmA2A1ama2a1产量产量cmncm2cm1c2nc22c21c1nc12c11求使总的运输费用最小的调运方案？求使总的运输费用最小的调运方案？产产销销 平平衡衡表表运输问题及其数学模型运输问题及其数学模型1 1 运运 输输 模模 型型10在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么产产地地Ai发发量量之之和和等等于其产量于其产量销销地地Bj收收量量之之和和等等于其销量于其销量运量不能为负数运量不能为负数 运输问题线性规划模型运输问题线性规划模型总费用最小总费用最小1 1 运运 输输 模模 型型11在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2321341运输问题网络图运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供供应应量量供应地供应地运价运价需需求求量量需求地需求地67538427591061 1 运运 输输 模模 型型12在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么运输问题线性规划模型运输问题线性规划模型供供应应地地约约束束需需求求地地约约束束1 1 运运 输输 模模 型型13在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解将上述问题用以下运价表：将上述问题用以下运价表：14在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解运行管理运筹学计算机软件：运行管理运筹学计算机软件：点击运输问题模块点击运输问题模块15在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解点击新建点击新建输入输入3输入输入4选择选择Min点击确定点击确定16在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解17在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解点击解决点击解决18在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解19思考题：思考题：运输问题的特点是什么？运输问题的特点是什么？既既然然运运输输问问题题是是线线性性规规划划的的一一种种特特殊殊情情况况，为为什什么么不不用用线线性性规规划划的的方方法法求求解解？要求：要求：对对以以上上例例子子分分别别应应用用计计算算机机软软件件的的线线性性规规划划模模块块和和运运输输问问题题的的模模块块进进行行计算、分析后回答。计算、分析后回答。20在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解例例2、某某公公司司从从两两个个产产地地A1、A2将将物物品品运运往往三三个个销销地地B1、B2、B3，各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每件件物物品品的的运运费费如如下下表表所所示示，问问：应应如如何何调调运运可可使使总总运运输输费费用最小？用最小？21解解：增增加加一一个个虚虚设设的的销销地地运运输输费费用用为为0.0.22在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么23在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解例例3、某某公公司司从从两两个个产产地地A1、A2将将物物品品运运往往三三个个销销地地B1、B2、B3，各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每件件物物品品的的运运费费如如下下表表所示，问：应如何调运可使总运输费用最小？所示，问：应如何调运可使总运输费用最小？24解解：增增加加一一个个虚虚设设的的产产地地运运输输费费用用为为025在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么26思考题思考题在在例例3中中，即即某某公公司司从从两两个个产产地地A1、A2将将物物品品运运往往三三个个销销地地B1、B2、B3，各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每件件物物品品的的运运费费如如下下表表所所示示，如如果果增增加加条条件件：B3的的需需求求不不能能满满足足则则需需以以高高价价（每每单单位位10元元）在在本本地地购购买买，问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？27思考题思考题在在例例3中中，即即某某公公司司从从两两个个产产地地A1、A2将将物物品品运运往往三三个个销销地地B1、B2、B3，各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每件件物物品品的的运运费费如如下下表表所所示示，如如果果增增加加条条件件：B3的的需需求求不不能能满满足足则则需需以以高高价价（每每单单位位10元元）在在本本地地购购买买，问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？28在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解29在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 2 运输问题的计算机求解运输问题的计算机求解30在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3 3 运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输问题例例4、石石家家庄庄北北方方研研究究院院有有一一、二二、三三三三个个区区。每每年年分分别别需需要要用用煤煤3000、1000、2000吨吨，由由河河北北临临城城、山山西西盂盂县县两两处处煤煤矿矿负负责责供供应应，价价格格、质质量量相相同。供应能力分别为同。供应能力分别为1500、4000吨，运价为：吨，运价为：由由于于需需大大于于供供，经经院院研研究究决决定定一一区区供供应应量量可可减减少少0-300吨吨，二二区区必必须须满满足足需需求求量量，三三区区供供应应量不少于量不少于1500吨吨,试求总费用为最低的调运方案。试求总费用为最低的调运方案。31解：解：根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：这里这里 M 代表一个很大的正数，其作用是强迫代表一个很大的正数，其作用是强迫相应的相应的 x31、x33、x34取值为取值为0。32在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么应用运筹学软件计算得：应用运筹学软件计算得：3 3 运输问题的应用运输问题的应用33在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3 3 运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输问题例例5、设设有有A、B、C三三个个化化肥肥厂厂供供应应1、2、3、4四四个个地地区区的的农农用用化化肥肥。假假设设效效果果相相同同，有有关关数据如下表：数据如下表：试求总费用为最低的化肥调拨方案。试求总费用为最低的化肥调拨方案。34解：解：根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：最最低低要要求求必必须须满满足足，因因此此把把相相应应的的虚虚设设产产地地运运费费取取为为M,而而最最高高要要求求与与最最低低要要求求的的差差允允许许按按需需要要安安排排，因因此此把把相相应应的的虚虚设设产产地地运运费费取取为为 0。对对应应 4”的的销销量量 50 是是考考虑虑问问题题本本身身适适当当取取的的数据数据,根据产销平衡要求确定根据产销平衡要求确定D的产量为的产量为 50.35在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么思考题思考题考考虑虑一一运运输输问问题题，有有关关产产品品的的单单位位运运价价（元元/千千克克）如如下下表表所所示示，假假设设A1、A2处处产产品品要要求求全全部部运运走走,A3处处产产品品就就地地储储存存的的费费用用为为每每千克千克16元，试写出该问题的产销平衡表。元，试写出该问题的产销平衡表。3 3 运输问题的应用运输问题的应用36在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么思考题思考题该问题的产销平衡表为：该问题的产销平衡表为：3 3 运输问题的应用运输问题的应用37在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3 3 运输问题的应用运输问题的应用二、生产与储存问题二、生产与储存问题例例6、某某厂厂按按合合同同规规定定须须于于当当年年每每个个季季度度末末分分别别提提供供10、15、25、20台台同同一一规规格格的的柴柴油油机机。已已知知该该厂厂各各季季度度的的生生产产能能力力及及生生产产每每台台柴柴油油机机的的成成本本如如右右表表。如如果果生生产产出出来来的的柴柴油油机机当当季季不不交交货货，每每台台每每积积压压一一个个季季度度需需储储存存、维维护护等等费费用用0.15万万元元。试试求求在在完完成成合合同同的的情情况况下下，使使该该厂厂全全年年生生产产总总费费用用为为最最小小的的决策方案。决策方案。38解解：把把第第 i 季季度度生生产产的的柴柴油油机机数数目目看看作作第第 i 个个生生产产厂厂的的产产量量；把把第第j季季度度交交货货的的柴柴油油机机数数目目看看作作第第j个个销销售售点点的的销销量量；成成本本加加储储存存、维维护护等费用看作运费。可构造下列产销平衡问题等费用看作运费。可构造下列产销平衡问题:39设设 xij为第为第i季度生产的第季度生产的第j季度交货的柴油机数目，则季度交货的柴油机数目，则交货交货:x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20生产生产:目标函数目标函数:Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0 x33+11.15x34+11.3x4440在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、转运问题：三、转运问题：在在原原运运输输问问题题上上增增加加若若干干转转运运站站。运运输输方方式式有有:产产地地 转转运运站站、转转运运站站 销销地地、产产地地 产产地地、产产地地 销销地地、销销地地 转转运运站站、销地销地 产地等产地等。3 3 运输问题的应用运输问题的应用41例例8、腾腾飞飞电电子子仪仪器器公公司司在在大大连连和和广广州州有有两两个个分分厂厂生生产产同同一一种种仪仪器器，大大连连分分厂厂每每月月生生产产400台台，广广州州分分厂厂每每月月生生产产600台台。该该公公司司在在上上海海和和天天津津有有两两个个销销售售公公司司负负责责对对南南京京、济济南南、南南昌昌、青青岛岛四四个个城城市市的的仪仪器器供供应应。另另外外因因为为大大连连距距离离青青岛岛较较近近，公公司司同同意意大大连连分分厂厂向向青青岛岛直直接接供供货货，运运输输费费用用如如图图，单单位位是是百百元元。问问应应该该如如何何调调运运仪仪器器，可可使使总总运运输输费费用用最最低低？图图中中1-广广州州、2-大大连连、3-上上海海、4-天天津、津、5-南京、南京、6-济南、济南、7-南昌、南昌、8-青岛。青岛。42在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么应应该该如如何何调调运运仪仪器器，可可使使总总运运输输费费用用最最低低？图图中中1-广广州州、2-大大连连、3-上上海海、4-天天津津、5-南南京京、6-济南、济南、7-南昌、南昌、8-青岛。青岛。43在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么260040010001000100010002001503503003MMMM31MMM40M2636M0广州广州济济南南大连大连上海上海天津天津南南京京南南昌昌青青岛岛44在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么45在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么46在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么47在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3 3 运输问题的应用运输问题的应用例例9、某某公公司司有有A1、A2、A3三三个个分分厂厂生生产产某某种种物物资资，分分别别供供应应B1、B2、B3、B4四四个个地地区区的的销销售售公公司司销销售售。假假设设质质量量相相同同，有有关关数数据如下表，据如下表，试求总费用为最少的调运方案。试求总费用为最少的调运方案。48在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么假设：假设：1.每每个个分分厂厂的的物物资资不不一一定定直直接接发发运运到到销销地地，可以从其中几个产地集中一起运；可以从其中几个产地集中一起运；2.运运往往各各销销地地的的物物资资可可以以先先运运给给其其中中几几个个销地，再转运给其他销地；销地，再转运给其他销地；3.除除产产销销地地之之外外，还还有有几几个个中中转转站站，在在产产地之间、销地之间或在产地与销地之间转运。地之间、销地之间或在产地与销地之间转运。3 3 运输问题的应用运输问题的应用49运价如下表：运价如下表：50解：把此转运问题转化为一般运输问题：解：把此转运问题转化为一般运输问题：1.把把所所有有产产地地、销销地地、转转运运站站都都同同时时看看作作产产地和销地；地和销地；2.运运输输表表中中不不可可能能方方案案的的运运费费取取作作M,自自身身对对自身的运费为自身的运费为0；3.Ai:产产量量为为20+原原产产量量,销销量量为为20;Ti:产产量量、销销量量均均为为20；Bi:产产量量为为20,销销量量为为20+原原销销量量,其中其中20为各点可能变化的最大流量为各点可能变化的最大流量;4.对对于于最最优优方方案案,其其中中xii为为自自身身对对自自身身的的运运量量,实际上不进行运作。实际上不进行运作。51扩大的运输问题产销平衡与运价表：扩大的运输问题产销平衡与运价表：52谢谢谢谢大大家家返返回回首首页页53