运输问题的表上作业法.pptx
《运输问题的表上作业法.pptx》由会员分享,可在线阅读,更多相关《运输问题的表上作业法.pptx(49页珍藏版)》请在咨信网上搜索。
1、第3章运输问题(TP)学习目标了解运输问题模型的特点。掌握产销平衡运输问题的表上作业法。学会产销不平衡运输问题的转化。学习表上作业法在物流管理中的典型应用。3 运输问题(TP)2运输问题的模型运输问题的模型3.13.1运输问题的表上作业法运输问题的表上作业法3.23.2产销不平衡的运输问题产销不平衡的运输问题3.33.3运输问题的应用案例运输问题的应用案例3.43.4运输问题的运输问题的ExcelExcel处理处理3.53.53 运输问题(TP)33.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法4利用表上作业法求解运输问题时,与单纯形法类似,首先要求出一个初始方案(即线性规
2、划问题的初始基本可行解)。一般来讲这个方案不一定是最优的,因此需要给出一个判别准则,并对初始方案进行调整、改进。每进行一次调整,我们就得到一个新的方案(基本可行解),而这个新方案一般比前一个方案要合理些,也就是对应的目标函数z值比前一个方案要小些。经过若干次调整,我们就得到一个使目标函数达到最小值的方案最优方案(最优解),而这些过程都可在产销矩阵表(运输表)上进行,故称为表上作业法。其实质是单纯形法步骤步骤描述描述方法方法第一步第一步求初始基行可行解(初始调运方案)求初始基行可行解(初始调运方案)最小元素法、最小元素法、元素差额法、元素差额法、第二步第二步求检验数并判断是否得到最优解当非基变量
3、的求检验数并判断是否得到最优解当非基变量的检验数检验数 ij ij全都非负时得到最优解,若存在检验全都非负时得到最优解,若存在检验数数 ij ij 00,说明还没有达到最优,转第三步。,说明还没有达到最优,转第三步。闭回路法和闭回路法和位势法位势法第三步第三步调整运量,即换基,选一个变量出基,对原运调整运量,即换基,选一个变量出基,对原运量进行调整得到新的基可行解,转入第二步量进行调整得到新的基可行解,转入第二步3.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法5例3.1设有3个产煤基地A1、A2、A3,4个销煤基地B1、B2、B3、B4,产地的产量、销地的销量以及从各产地至
4、各销地煤炭的单位运价列于表3.4中,试求出使总运费最低的煤炭调拨方案。63.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法(1 1)列出运输问题的产销矩阵表。)列出运输问题的产销矩阵表。73.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法其中:xij为产地Ai到销地Bj的运量(i=1,2,3;j1,2,3,4),而将Ai到Bj的单位运价cij用小型字写在每格的右上角,以便直观地制定和修改调运方案。从表3.5的数据可知,例3.1是个满足产销平衡条件的产销平衡问题。(2)初始方案确定的方法)初始方案确定的方法最小元素法。最小元素法。最小元素法:就近供应,运价数小
5、的尽可能优先分配。83.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法93.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法这样,我们便得到这样问题的一个初始基本可行x11=0 x12=0 x13=4 x14=3 x21=3 x22=0 x23=1 x24=0 x31=0 x32=6 x33=0 x34=3它所对应的目标函数z值为z=30+110+34+103+13+90+21+80+70+46+100+53=86(万元)因此,在应用最小元素法确定初始方案时,必须注意以下两点。103.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法1.1.当选
6、定最小元素(不妨假定为cst)后,如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt(即as=bt),可在产销矩阵表上xst处填上一个数as,并画上圈。为了保证调运方案中画圈的数字为m+n1个,只能在s行的其他格子里都打上“”(或在t列的其他格子里都打上“”),不可以同时把s行和t列的其他格子里都打上“”。2 2.当最后只剩下一行(或一列)还存在没有填数和打“”的格子时,规定只允许填数,不允许打“”,其目的也是为了保证画圈数字的个数恰为m+n1个。3.在特殊情况下可填“0”并画上圈,这个“0”应与其他画圈的数字同样看待。(不限于最后一行或最后一列)。113.2 运输问题的表上
7、作业法3.2.1 产销平衡运输问题的表上作业法例在表3.7中,第一步最小元素为c31=1,在x31处填上数字min(13,19)=13,并在x11、x21处打上“”。123.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法3.2 运输问题的表上作业法3.2.1 产销平衡运输问题的表上作业法13第二步的最小元素为c32=2,可在x32处填上数字min(6,6)=6,并在x12、x22处打上“”(或在x33、x34处打上“”),由上面的注意(1)可知,不能同时在x12、x22、x33、x34处都打上“”。继续运用前面所述的方法,再经过两步计算,可得到表3.8。143.2 运输问题的
8、表上作业法3.2.4 确定初始方案的其他方法1.1.西北角法西北角法153.2 运输问题的表上作业法3.2.4 确定初始方案的其他方法2 2沃格尔法沃格尔法单位单位 销地销地 运价运价 产地产地产量产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量销量3 36 65 56 63.2 运输问题的表上作业法16方法方法1:最小元素法:最小元素法 基本思想是就近供应,即从运价最小的地方开始供应(调运),然后次小,直到最后供完为止。B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633总的运输费(31
9、)+(64)+(43)+(12)+(310)+(35)=86元3.2 运输问题的表上作业法17元素差额法对最小元素法进行了改进,考虑到产地到销地的最小运价和次小运价之间的差额,如果差额很大,就选最小运价先调运,否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是z=108+52+151=105最小元素法:3.2 运输问题的表上作业法85102120151551510后一种方案考虑到C11与C21之间的差额是82=6,如果不先调运x21,到后来就有可能x110,这样会使总运费增加较大,从而先调运x21,再是x22,其次是x12总运费z=105+152+51=85用元
10、素差额法求得的基本可行解更接近最优解,所以也称为近似方案。18最小元素法基本步骤:最小元素法基本步骤:1.在单位运价表中找出最小的运价cij,其对应的变量xij 优先赋值xij=min(ai,bj),2.使该行或列对应的供或求得到满足,在产销平衡表中填对应的供求数值,3.在单位运价表中划去该行或列,以示不需再予供应,4.在剩余的单位运价表中做同样的操作,直到单位运价表中所有的元素都被划去为止。表上作业法表上作业法要求要求:调运方案的数字格必须为m+n-1个,且有数字格不构成闭回路。一般用最小元素法给出的方案符合这要求。符合这要求。3.2 运输问题的表上作业法19方法2:Vogel法1)从运价表
11、中分别计算出各行和各列的最小运费和次最小运费的差额,并填入该表的最右列和最下行。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A2 41 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410583.2 运输问题的表上作业法20B1B2B3B4产量产量行差额行差额行差额行差额A177 7A2 41 1A3 91 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410585 52)再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时,划去运价表中
12、对应的行或列。重复1)和2),直到找出初始解为至。3.2 运输问题的表上作业法21单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额711352153.2 运输问题的表上作业法22单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额713527533.2 运输问题的表上作业法23单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额11351536312该方案的总运费:(13)(46)(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 问题 作业
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。