数据模型与决策运输问题学习教案.pptx

《数据模型与决策运输问题学习教案.pptx》由会员分享，可在线阅读，更多相关《数据模型与决策运输问题学习教案.pptx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据模型与决策运输数据模型与决策运输(ynsh)问题问题第一页，共15页。学习学习(xux)目标目标n n运输问题属于一类特殊(tsh)的线性规划问题，由于其约束方程组的系数矩阵具有特殊(tsh)的结构，它有比单纯形法更为简便的求解方法表上作业法。n n要求：掌握产销平衡条件下的运输问题的表上作业法，以及通过最小元素法或Vogel法求解运输问题的初始基可行解，与如何通过最优性检验判别该解的目标函数值是否最优。第五章 运输(ynsh)问题第1页/共15页第二页，共15页。第五章第五章 运输运输(ynsh)问题问题n n5.1 运输(ynsh)问题的数学模型n n5.2 表上作业法第五章

2、运输(ynsh)问题第2页/共15页第三页，共15页。5.1 运输运输(ynsh)问题的数学模型问题的数学模型问题提出：公司是一家由家族经营的小公司，该公司收购生菜并在食品罐头厂中将生菜加工成罐头，然后再把这些罐头分销到各地去卖。这个公司的一个主要产品是一种(y zhn)豆类罐头，这些罐头在三个食品罐头厂加工，记为罐头厂一、罐头厂二、罐头厂三。然后用卡车把它们运送到美国西部的四个仓库，记为仓库一、仓库二、仓库三和仓库四。现在的问题是该公司采用怎样的运输策略才能使总运输成本最小。第五章 运输(ynsh)问题第3页/共15页第四页，共15页。5.1 运输运输(ynsh)问题的数学模型问题的数学模型

3、n n 运输问题(wnt)的概述n n 运输问题(wnt)的数学模型第五章 运输(ynsh)问题第4页/共15页第五页，共15页。运输问题运输问题(wnt)的概述的概述n n运输问题：要找到从来源到目的地之间运送货物的最佳路线，即经常(jngchng)遇到的从工厂到仓库之间的单一品种的物资调度问题。第五章 运输(ynsh)问题第5页/共15页第六页，共15页。运输问题运输问题(wnt)的概述的概述n n需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目

4、的地都有一个固定的需求量，整个需求量都必须由出发地满足。这个送出量正好等于接受量的假设意味着所有出发地都有一个固定的需求量，整个需求量都必须由出发地满足。这个送出量正好等于接受量的假设意味着所有出发地的总供应量与所有目的地的总需求量之间需要有一个平衡。地的总供应量与所有目的地的总需求量之间需要有一个平衡。n n可行解特性：当供应量的总和与需求量的总和相等时，运输问题才有可行解。可行解特性：当供应量的总和与需求量的总和相等时，运输问题才有可行解。n n成本假设：从任何一个出发地到目的地的货物配送成本和所配送的数量呈线性比例关系，因此这个成本等于从来成本假设：从任何一个出发地到目的地的货物配送成本

5、和所配送的数量呈线性比例关系，因此这个成本等于从来源所在地运送一个单位货物到目的地的费用。源所在地运送一个单位货物到目的地的费用。n n运输问题所需要的已知数据运输问题所需要的已知数据(shj)(shj)是供应量、需求量和单位成本，是供应量、需求量和单位成本，这些称之为模型参数。这些称之为模型参数。第五章 运输(ynsh)问题第6页/共15页第七页，共15页。运输运输(ynsh)问题的数学模型问题的数学模型n n经济生活中，存在着大量的这种物资调度问题。这种问题可描述为：经济生活中，存在着大量的这种物资调度问题。这种问题可描述为：已知有个产地已知有个产地(ch(ch nd)nd)可生产某种物资

6、，其产量分别为可生产某种物资，其产量分别为 （，），另有个销地，其销量分别为，），另有个销地，其销量分别为 （，）。又知从第个产地）。又知从第个产地(ch(ch nd)nd)到第个销地运输单位物资的运价到第个销地运输单位物资的运价为为 ，且个产地，且个产地(ch(ch nd)nd)的总量与个销地的总销量相等。试求产的总量与个销地的总销量相等。试求产销平衡条件下总运费最小的调运方案。销平衡条件下总运费最小的调运方案。第五章 运输(ynsh)问题第7页/共15页第八页，共15页。n n目标函数：目标函数：minz minz n n约束条件：约束条件：（，（，），）n n （，（，），）n n （，

7、（，；，；，）n n由于产销平衡由于产销平衡(pnghng)(pnghng)，因此有，因此有:n n=n n =第五章 运输(ynsh)问题第8页/共15页第九页，共15页。n n实例分析：n n已知公司从每个罐头厂到各仓库每车罐头的运价如表所示。问该公司应该如何调运才能(cinng)使总运输费用最低。一一二二三三四四合计（车）合计（车）一3113107二19284三741059合计（车）3656-第五章 运输(ynsh)问题第9页/共15页第十页，共15页。第五章第五章 运输运输(ynsh)问题问题n n5.1 运输问题(wnt)的数学模型n n5.2 表上作业法第五章 运输(ynsh)问题

8、第10页/共15页第十一页，共15页。5.2 表上作业表上作业(zuy)法法n n 表上作业法概述n n 最优检验与方案(fng n)的选择第五章 运输(ynsh)问题第11页/共15页第十二页，共15页。表上作业表上作业(zuy)法概述法概述表上作业法的计算方法 确定初始基可行解。即在个产销平衡表格中给出个数字格。求各非基变量（在表格中即为空格）的检验数，判别是否达到最优解。如果是，则停止计算，否则转到下一步。确定换入变量和换出变量，利用闭回路法进行(jnxng)调整，找出新的基可行解。重复上面两个步骤，直至找到最优解。第五章 运输(ynsh)问题第12页/共15页第十三页，共15页。n n

9、最小元素法：最小元素法的基本思想是就近运输，即从单位运价表中最小的运价处开始确定运输关系，依次类推，直到给出全部方案为止。n nVogel。法沃格尔逼近法（Vogel Approximation Method，）。这种方法得到(d do)的结果已经很接近最优解。第五章 运输(ynsh)问题第13页/共15页第十四页，共15页。最优检验最优检验(jinyn)与方案的调与方案的调整整n n闭回路是指调运方案中由一个空格和若干个数字闭回路是指调运方案中由一个空格和若干个数字(shz)(shz)格的水平和格的水平和垂直连线构成的封闭回路。它是以某空格为起点，用水平或垂直线往垂直连线构成的封闭回路。它是以某空格为起点，用水平或垂直线往前划，每碰到一数字前划，每碰到一数字(shz)(shz)格转格转，然后继续前进，直至回到起，然后继续前进，直至回到起点为止。点为止。n n构建闭回路的目的是为了计算各非基变量（对应空格）的检验数并对构建闭回路的目的是为了计算各非基变量（对应空格）的检验数并对可行解进行调整。可行解进行调整。第五章 运输(ynsh)问题第14页/共15页第十五页，共15页。