运筹学课件第5章 运输问题.ppt

《运筹学课件第5章 运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第5章 运输问题.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 运输问题运输问题重庆三峡学院重庆三峡学院 关文忠关文忠http:/ n5.1 运输问题的数学模型运输问题的数学模型5.1.1 产销平衡的数学模型产销平衡的数学模型 5.1.2 产销不平衡的数学模型产销不平衡的数学模型5.1.3 非标准形式数学模型的标准化非标准形式数学模型的标准化n5.2 表上作业法表上作业法5.2.1 确定初始基本可行解确定初始基本可行解5.2.2 解的最优性检验解的最优性检验5.2.3 改进运输方案的办法改进运输方案的办法5.2.4 如何找多个最优方案如何找多个最优方案5.3 计算机求解运输问题（各节实验演示）计算机求解运输问题（各节实验演示）5.4 应用举例应

2、用举例n本章小结本章小结12/17/2022管理运筹学课件5.1.1 产销平衡的数学模型产销平衡的数学模型n一般情况一般情况:nm个产地，产量为个产地，产量为ainn个销地，销量为个销地，销量为bjn当当ai=bj时，称为产销平衡时，称为产销平衡nAi到到Bj的单位运价的单位运价cij,其数学模其数学模型如下。型如下。产地产地销地销地B1Bn产量产量A1Amc11c1mc1ncmna1am销量销量b1bnn容易看出，产销平衡运输模型具有以下特点：容易看出，产销平衡运输模型具有以下特点：n（1）它包含）它包含mn个变量，个变量，m+n个约束条件个约束条件n（2）因为有，）因为有，所以系数矩阵中所

3、以系数矩阵中线性独立的列向量的最大个数为（线性独立的列向量的最大个数为（mn1）个，即产销平衡运输问题的解中基变量的个数个，即产销平衡运输问题的解中基变量的个数为为(mn1)个。个。12/17/2022管理运筹学课件5.1.2 产销不平衡的数学模型产销不平衡的数学模型12/17/2022管理运筹学课件5.1.3 非标准形式数学模型的标准化非标准形式数学模型的标准化12/17/2022管理运筹学课件5.1.3 非标准形式数学模型的标准化非标准形式数学模型的标准化 销地销地产地产地B1B2B3最低最低产量产量最高最高产量产量A1A2A35362434432035不限不限3销量销量434【例例5.1

4、】将极大化运输问题标准化将极大化运输问题标准化12/17/2022管理运筹学课件5.1.3 非标准形式数学模型的标准化非标准形式数学模型的标准化12/17/2022管理运筹学课件5.1.3 非标准形式数学模型的标准化非标准形式数学模型的标准化12/17/2022管理运筹学课件5.3 表上作业法表上作业法n表上作业法计算过程如下。表上作业法计算过程如下。n(1)找出初始基本可行解。即在找出初始基本可行解。即在(mn)产销平衡表上给出产销平衡表上给出(m+n-1)个数字格，其相应的调运量就是基个数字格，其相应的调运量就是基变量，格子中所填写的值即为基变变量，格子中所填写的值即为基变量的解。量的解。

5、n(2)求各非基变量的检验数，即在求各非基变量的检验数，即在表上计算除了表上计算除了(m+n-1)个数字格以个数字格以外的空格的检验数，判别是否已得外的空格的检验数，判别是否已得到最优解。如已是最优解，则停止到最优解。如已是最优解，则停止计算，否则转到下一步。计算，否则转到下一步。n(3)确定入基变量与出基变量，找确定入基变量与出基变量，找出新的基本可行解，在表上用闭回出新的基本可行解，在表上用闭回路上进行调整。路上进行调整。n(4)重复重复2、3直到得到最优解为止。直到得到最优解为止。初始解如何给？检验数如何求？方案如何调整？三个关键环节：12/17/2022管理运筹学课件2.3.1 初始方

6、案的确定初始方案的确定n确定初始基本可行解的方法有西北角法、确定初始基本可行解的方法有西北角法、最小元素法最小元素法、Vogel法法等。由于等。由于Vogel法所给的初始方案最佳，最小元法所给的初始方案最佳，最小元素法次之，西北角法最差，故在这里仅介绍后两种方法。素法次之，西北角法最差，故在这里仅介绍后两种方法。无论采取哪一种方法，数字填充都要遵循以下原则。无论采取哪一种方法，数字填充都要遵循以下原则。n初始方案数字填充原则：初始方案数字填充原则：n(1)当需求量已满足，则划去该销地列，产地行的可供量当需求量已满足，则划去该销地列，产地行的可供量=原可供量原可供量-填充数字；填充数字；n(2)

7、若产量已供应完毕，则划去该产地行，销地列的需求若产量已供应完毕，则划去该产地行，销地列的需求量量=原需求量原需求量-填充数字；填充数字；n(3)若需求量与可供量刚好相等，则任选行（或列）划去，若需求量与可供量刚好相等，则任选行（或列）划去，未被划去的未被划去的ai或或bj剩余量为剩余量为0，此，此0视为可填充的数字，以视为可填充的数字，以保证原则保证原则(4)的满足；的满足；n(4)方案的有数字的格子数方案的有数字的格子数=行数行数+列数列数-1。12/17/2022管理运筹学课件1.最小元素法最小元素法n最小元素法的基本思想是就近供应，即从单位运价表中最小的最小元素法的基本思想是就近供应，即

8、从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为运价处开始确定供销关系，依次类推，一直到给出全部方案为止。止。n例（导入案例）例（导入案例）n最小元素最小元素2，为，为A2与与B1供销关系，供销关系，B1需要需要8，A2产产量量10，供应，供应8个，个，B1得到满足，划得到满足，划所该列，所该列，A2余余2。n余下的最小元素余下的最小元素3，为，为A2与与B3供销供销关系，关系，B3需要需要10，A2剩剩2，供应，供应2个，个，A2供应完毕，供应完毕，划所该行，划所该行，B3还还差差10。n余下的最小元素余下的最小元素4，为，为A1与与B3供销供销关系，关系，B3还需

9、还需10，A1产量产量16，供，供应应10个，个，B3得到得到满足，划所该列，满足，划所该列，A1余余6。n余下的最小元素余下的最小元素5，为，为A3与与B2供销供销关系，关系，B2需要需要14，A3产量产量22，供，供应应14个，个，B2得到得到满足，划所该列，满足，划所该列，A3余余8。n余下的最小元素余下的最小元素6，为，为A3与与B4供销供销关系，关系，B4需要需要14，A3余余8，供应，供应8个，个，A3供应完毕，供应完毕，划所该行，划所该行，B4还还差差6。n余下的元素只有余下的元素只有11，为，为A1与与B4供供销关系，销关系，B4还差还差6，A1余余6，供应，供应6个，个，A3

10、供应完毕，供应完毕，B4得到满足，任得到满足，任选一列或列划去。选一列或列划去。n有数字格子数有数字格子数(6)=行数行数(3)+列数列数(4)-1n得到了初始方案得到了初始方案 销地销地产地产地B1B2B3B4产量产量A1412411A221039A385116销量销量48488210614881412|1014|616|622|810|212/17/2022管理运筹学课件2.Vogel法法n用最小元素确定的初始方案只从局部观点考虑就近供应，可能造成总用最小元素确定的初始方案只从局部观点考虑就近供应，可能造成总体的不合理。体的不合理。Vogel法的步骤是从运价表上分别找出每行与每列的最法的步

11、骤是从运价表上分别找出每行与每列的最小元素和次小元素，求其差值，再从差值最大的行或列中找出最小运小元素和次小元素，求其差值，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。价确定供需关系和供应数量。销地销地产地产地B1B2B3B4产量产量最小最小差额差额A1412411 0A221039 1A385116 1销量销量4848最小最小差额差额 2 5 1 3821241488141214|616|422|810|2(1)求得最小元素差求得最小元素差额额,其中最大的是其中最大的是5,对应的是对应的是(A3,B2).由于由于mina3,b2=min22,14=14,将将(A3,B2)格填入

12、格填入数字数字14,B2需求已需求已满足满足,或去所在列或去所在列;A3剩余供应量剩余供应量22-14=8(2)第第3行最小元素差行最小元素差额变为额变为2,其余未变其余未变.差额最大的是差额最大的是3,位位于第于第4列列,最小元素最小元素6,对应的是对应的是(A3,B4).由于由于mina3,b4=min8,14=8,将将(A3,B4)格填入数字格填入数字8,A3产量供应完毕产量供应完毕,或去所在行或去所在行;B4还需还需14-8=6|2(3)第第4列最小元素差列最小元素差额变为额变为2,其余未变其余未变.差额最大的是差额最大的是2,位位于第于第1、4列列,任选第任选第1列列,最小元素最小元

13、素2,对对应的是应的是(A2,B1).由由于于mina2,b1=min10,8=8,将将(A2,B1)格填入数字格填入数字8,B1需求满足需求满足,划去划去所在列所在列;A2余余10-8=2|2(4)第第1行最小元素差行最小元素差额变为额变为7,第第2行变为行变为6,其余未变其余未变.差额最差额最大的是大的是7,位于第位于第1行行,最小元素最小元素4,对应的对应的是是(A1,B3).由于由于mina1,b3=min12,16=12,将将(A1,B3)格填入数字格填入数字12,B3需求满足需求满足,划划去所在列去所在列;A1余余16-12=4|7|6(5)余下的只有第余下的只有第4列列了由于产销

14、平衡了由于产销平衡,剩剩余供应量全部供应余供应量全部供应给销地给销地B4,有数字的有数字的格子格子=6=3+4-1.于是于是得初始方案得初始方案.总运费总运费=412+114+28+92+514+68=244|4|0|012/17/2022管理运筹学课件5.2.2 解的最优性检验解的最优性检验位势法位势法B1 B2 B3 B4A1 4 12 4 11A2 2 10 39A3 85 11 6B1 B2 B3 B4 产量产量A116A2810A314822销量销量 8 14 12 14B1 B2 B3 B4uiA1(4)(11)A2(2)A3(5)(6)vj例例5.4求最小元素法所给方案的检验数求

15、最小元素法所给方案的检验数单位运价表单位运价表初始方案初始方案位势法检验数表位势法检验数表0411-1-5310121-1104(3)210 6存在负检验数，存在负检验数，非最优解非最优解12/17/2022管理运筹学课件5.2.3 方案的改进方案的改进闭回路法闭回路法B1 B2 B3 B4A1 4 12 4 11A2 2 10 39A3 85 11 6B1 B2 B3 B4 产量产量A116A2810A314822销量销量 8 14 12 14B1 B2 B3 B4uiA1(4)(11)A2(2)A3(5)(6)vj例例5.4求最小元素法所给方案的检验数求最小元素法所给方案的检验数单位运价表

16、单位运价表方案调整方案调整位势法检验数表位势法检验数表0411-2-5410022(9)9121210 612 4最优方案最优方案12/17/2022管理运筹学课件5.2.4 如何找多个最优方案如何找多个最优方案12/17/2022管理运筹学课件5.4 应用举例应用举例n由于运输问题模型简捷，求解方便，可将一由于运输问题模型简捷，求解方便，可将一些非地理问题转换为地理问题。些非地理问题转换为地理问题。n案例案例5-1 生产计划问题生产计划问题n案例案例5-2 空车调度问题空车调度问题n案例案例5-3 转运问题转运问题12/17/2022管理运筹学课件案例案例5-1 生产计划问题生产计划问题季度

17、季度需求量需求量(万吨万吨)生产能力生产能力(万吨万吨)生产成本生产成本(万元万元/万吨万吨)12341025251020252520250280300250存储成本：存储成本：10万元万元/万吨万吨*季季I IIIIIIIIIIIIVIV产量产量生产成本生产成本I I2020250IIII2525280IIIIII2525300IVIV2020250销量销量1010252525251010250280300250260270280290300310MMMMMM（1）当季生产当季销售，单）当季生产当季销售，单位运价位运价=生产成本生产成本（2）前季生产后季销售，单）前季生产后季销售，单位运价位

18、运价=生产成本生产成本+存储成本存储成本（3）后季生产前季销售为不）后季生产前季销售为不可能，运价为可能，运价为M解：生产能力看作产地，需求解：生产能力看作产地，需求看作销地，建立产销平衡表与看作销地，建立产销平衡表与单位运价表单位运价表最优方案：最优方案：总成本总成本1920012/17/2022管理运筹学课件运输任务运输任务案例案例5-2 空车调度问题空车调度问题线路线路从工地从工地到工地到工地需车次数需车次数1ED82BC63AF34DB4ABCDEFA0122.523B101.51.21.53C21.502.522D2.51.22.502.53E21.522.501.5F33231.5

19、0A AB BE E余余C C2 21.51.52 26 6D D2.52.51.21.22.52.54 4F F3 33 31.51.53 3缺缺3 32 28 8行驶时间表行驶时间表余缺表余缺表以余缺为供需的运输问题以余缺为供需的运输问题A AB BE E余余C C336 6D D224 4F F33 3缺缺3 32 28 8最优调度方案最优调度方案行驶里程行驶里程:23.9公里公里工地工地出发出发到达到达余缺余缺ABCDEF306406430880-3-2 634-812/17/2022管理运筹学课件案例案例5-3 转运问题转运问题某公司有两个工厂、两个仓库、两个销某公司有两个工厂、两个

20、仓库、两个销地。工厂生产的产品可以直接运往销地，地。工厂生产的产品可以直接运往销地，也可通过其他工厂或仓库中转运往销地，也可通过其他工厂或仓库中转运往销地，还可以在销地之间转运。工厂还可以在销地之间转运。工厂1的产量的产量为为7t，工厂，工厂2的产量为的产量为3t；销地；销地1和销地和销地2的需求均为的需求均为5t。工厂、仓库、销地之。工厂、仓库、销地之间的单位运价如表间的单位运价如表5-30所示，试确定运所示，试确定运费最小的调运计划费最小的调运计划 151515151010101010101010101010101010101013131717101010103 37 75 55 53 3

21、10102 25 51010101013131717销销量量C C2 2C C1 1销销地地B B2 2B B1 1仓库仓库A A2 2A A1 1工厂工厂C C2 2C C1 1B B2 2B B1 1A A2 2A A1 1产产量量销销地地仓库仓库工厂工厂销销地地产产地地解：将产地、仓库、销地既作为产地又解：将产地、仓库、销地既作为产地又作为销地。两工厂产量之和为作为销地。两工厂产量之和为10，即最，即最大转运量，作为转运点的产量和销量；大转运量，作为转运点的产量和销量；作为产地的工厂，除作为转运点外，还作为产地的工厂，除作为转运点外，还承担生产任务，其产量为最大转运量加承担生产任务，其产

22、量为最大转运量加上各自的产量；作为销地的销地，除作上各自的产量；作为销地的销地，除作为转运点外，还有销售需求，其销量等为转运点外，还有销售需求，其销量等于最大转运量加上各自的销量。于最大转运量加上各自的销量。求得最优方案：求得最优方案：12/17/2022管理运筹学课件本章小结本章小结n本本章章介介绍绍了了一一种种特特殊殊类类型型的的线线性性规规划划运运输输问问题题。运运输输问问题题LPLP建模的关键是建立一个产销平衡表和一个单位运价表。建模的关键是建立一个产销平衡表和一个单位运价表。n利利用用表表上上作作业业法法求求解解运运输输问问题题时时，需需要要标标准准化化为为：目目标标minmin，产

23、产量量=销量；销量；n表表上上作作业业法法的的有有三三个个关关键键环环节节：给给初初始始方方案案、求求检检验验数数、方方案案调整。调整。n西西北北角角法法最最为为简简单单，但但给给出出的的初初始始方方案案最最差差，故故不不建建议议采采用用；最最小小元元素素法法相相对对简简单单，给给出出的的初初始始方方案案相相对对较较好好，建建议议使使用用；VogelVogel法法较较复复杂杂，但但给给出出的的初初始始方方案案是是三三者者中中最最好好的的，建建议议使使用用。本本章章介介绍绍了了后后两两种种方方法法。求求检检验验数数用用位位势势法法，调调整整方方案案用用闭闭回路法。回路法。n运运输输问问题题不不但但可可以以解解决决货货物物配配送送方方案案优优化化问问题题，也也可可以以解解决决管管理理中中的的一一些些其其他他问问题题，如如转转运运问问题题、空空车车调调度度问问题题、生生产产计计划划问题等等。问题等等。12/17/2022管理运筹学课件