运输问题运筹学交大工商管理讲义PPT课件.ppt
《运输问题运筹学交大工商管理讲义PPT课件.ppt》由会员分享,可在线阅读,更多相关《运输问题运筹学交大工商管理讲义PPT课件.ppt(54页珍藏版)》请在咨信网上搜索。
1、第三章第三章 运输问题运输问题-TransportationProblem一、运输问题一、运输问题(TransportationProblem)以以知知有有m个个生生产产地地点点(source)Ai,i=1,m,可可供供应应某某种种物物资资,其其供供应应量量(产产量量)(supply)为为ai,i=1,m;有有n个个销销售售地地点点(destination)Bj,j=1,n,需需要要该该种种物物资资,其其需需要要量量(产产量量)(demand)为为bj,j=1,n;从从Ai到到Bj运运输输单单位位物物资资的的运运价价(单单价价)为为cij;设设ai=bj,这这些些数数据据可可汇汇总总于于如如下
2、下产产销销平平衡衡表表,现现要要制制定定一一个个使使总总运费最小的调运方案。运费最小的调运方案。第一节第一节运输问题及其数学模型运输问题及其数学模型销销地地产地产地B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量销量b1b2bnaibj产销平衡表产销平衡表(costandrequirementtable)若若用用xij表表示示从从Ai到到Bj的的运运量量,在在产产销销平平衡衡的的条条件件下下,要要求求得总运费最小的调运方案,其数学模型如下(模型得总运费最小的调运方案,其数学模型如下(模型Y)该该模模型型中中,包包含含了了mn个个变变量量,(
3、m+n)个个约约束束条条件,且有特殊结构的系数矩阵,即件,且有特殊结构的系数矩阵,即上述矩阵的列向量可用上述矩阵的列向量可用pij来描述,显然来描述,显然pij中除第中除第i个元素和第个元素和第m+j个元素为个元素为1以外,其余元素均为以外,其余元素均为0。一、运输问题数学模型的基本概念一、运输问题数学模型的基本概念对对于于运运输输问问题题的的数数学学模模型型(模模型型Y)有有如如下下定理。定理。定理定理3.1运输问题的数学模型必有最优解。运输问题的数学模型必有最优解。定定理理3.2运运输输问问题题约约束束方方程程系系数数矩矩阵阵A的的秩秩为为m+n1,即,即R(A)=m+n1。第二节第二节
4、表上作业法表上作业法-(TransportationSimplexMethod)定定义义3.1(闭闭回回路路的的定定义义)在在运运输输问问题题的的调调运运表表中中,凡凡能能排排成成xi1j1,xi1j2,xi2j3,xisjs,xisj1形形式式的的变变量量集集合合,称称为为一一个个闭闭回回路路(closedpath,stepping-stone-path),其其中中诸诸变变量量称称为为该该闭闭回回路路的的顶顶点点(corner)。闭回路有如下特点:闭回路有如下特点:每个顶点都是转角;每个顶点都是转角;每行或每列只有且仅有两个顶点;每行或每列只有且仅有两个顶点;每个顶点的连线都是水平的或垂直的
5、。每个顶点的连线都是水平的或垂直的。B1B2B3B4B5B6B7A1x11x12x13x14x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37定定理理3.3运运输输问问题题m+n1个个变变量量xi1j1,xi2j2,xisjs(s=m+n1)构构成成某某一一基基可可行行解解的的基基变变量量的的充充要要条条件件是是:不不包包含含以以这这些些变变量量为为顶顶点点的的闭闭回回路。路。该该定定理理能能帮帮助助我我们们简简便便地地求求出出基基可可行行解解或或判判别别某某一可行解是否为基可行解。一可行解是否为基可行解。表上作业法基本步骤表上作业法
6、基本步骤(1)确定初始基可行解)确定初始基可行解(2)最优解的判定;)最优解的判定;(3)基可行解的转换。)基可行解的转换。(一)初始基可行解的确定(一)初始基可行解的确定确确定定初初始始基基可可行行解解的的方方法法很很多多,如如最最小小元元素素法法、伏伏格格尔尔法法、西西北北角角法法等等。这这里里仅仅介介绍绍既既常常用用又又简简便便的的方法方法最小元素法最小元素法(minimumcostmethod)。这这种种方方法法的的基基本本思思想想就就是是就就近近供供应应,即即从从单单位位运运价价表表中中最最小小的的运运价价开开始始确确定定供供销销关关系系,然然后后次次小小。一一直到求出初始基可行解为
7、止。直到求出初始基可行解为止。二、表上作业法二、表上作业法最小元素法的步骤最小元素法的步骤1)列出如表列出如表36所示的调运表(包括单价、产量与销量);所示的调运表(包括单价、产量与销量);2)在在调调运运表表中中找找出出一一个个单单位位运运价价最最小小的的格格子子,在在相相应应的的运运量量位位置置上填上尽可能大的数(必须满足约束条件)。上填上尽可能大的数(必须满足约束条件)。3)在在填填有有数数字字的的格格子子所所在在行行或或者者列列运运量量应应该该为为0的的位位置置上上打打“”,(即即表表示示该该运运量量为为0,相相应应的的变变量量为为非非基基变变量量)且且只只能能在在行行或或列的方向上打
8、列的方向上打“”,不能同时在两个方向上打,不能同时在两个方向上打“”;4)在没有填数,也未打在没有填数,也未打“”的格子重复上述(的格子重复上述(2)、()、(3)步;)步;5)最后剩下的一行或列只能填数,不能打最后剩下的一行或列只能填数,不能打“”。例例3.2设设有有某某物物资资从从A1,A2,A3处处运运往往B1,B2,B3,B4四四个个地地方方,各各处处供供应应量量、需需求求量量及及单单位位运运价价见见下下表表。问问应应如如何何安安排排运运输输方方案案,才才能能使使总总运运费费最最少少?销销地地产地产地B1B2B3B4产量产量A1376450A2243320A3838930销量销量402
9、01525100100销销地产地地产地B1B2B3B4产量产量A120525503764A220202433A32010308389销量销量40201525(二)最优解的判定(二)最优解的判定(optimalitytesting)最优解的判定,通常有两种方法,即闭回路法和位势法。最优解的判定,通常有两种方法,即闭回路法和位势法。1闭回路法闭回路法(closedpathmethod)在在表表36所所描描述述的的调调运运表表中中,任任一一非非基基可可变变量量都都可可以以作作出出这这样样的的闭闭回回路路:该该闭闭回回路路以以选选定定的的非非基基变变量量为为第第一一个个顶顶点点,其其余余的的顶顶点点都
10、都是是基基变变量量。可可以以证证明明,对对于于任任一一非非基变量,这样的闭回路只有唯一一条。基变量,这样的闭回路只有唯一一条。在在这这样样的的闭闭回回路路上上,可可以以对对调调运运方方案案进进行行调调整整,而而能能使使调调运运方方案案仍仍然然满满足足所所有有约约束束条条件件,即即满满足足产产销销平平衡衡的的要要求。求。在在闭闭回回路路上上,进进行行一一个个单单位位的的运运量量调调整整所所得得目目标标函函数数的的变变化化即即为为该该非非基基变变量量的的检检验验数数。若若所所有有非非基基变变量量的的检检验验数均大等于零,则问题得到最优解数均大等于零,则问题得到最优解.对表对表36中,所有非基变量的
11、检验数计算如下:中,所有非基变量的检验数计算如下:x23的检验数的检验数23=2022=c22(u2+v2)=4(1+1)=2023=c23(u2+v3)=3(1+6)=2034=c34(u3+v4)=9(2+4)=30由于由于23=20,故表中基可行解不是最优解。,故表中基可行解不是最优解。v1=3v2=1v3=6v4=4(三)基可行解的转换(三)基可行解的转换(convertBFsolution)当当调调运运表表中中,仍仍然然有有非非基基变变量量的的检检验验数数为为负负,则则说说明明问问题题还还没没有有得得到到最最优优解解,需需要要进进行行基基可可行行解解的的转转换换。具具体体办法为:办法
12、为:(1)以以某某一一个个ij0(若若有有多多个个则则取取最最小小者者)对对应应的的变变量量xij作为进基变量;作为进基变量;(2)以以所所选选的的xij为为第第一一个个顶顶点点作作闭闭回回路路,该该闭闭回回路路除除xij外外,其余顶点都是基变量,并排序;其余顶点都是基变量,并排序;(3)以以顺顺序序为为偶偶数数的的顶顶点点的的基基变变量量最最小小值值min(xij)k|k为为偶偶数数作作为为调调整整量量,在在顺顺序序为为奇奇数数的的顶顶点点上上加加上上该该调调整整量量,在在顺顺序序为为偶偶数数的的顶顶点点上上减减去去该该调调整整量量,即即可可得得到到新的基可行解。新的基可行解。销销地地产地产
13、地B1B2B3B4产量产量A120255025503764A220155202433A32010308389销量销量40201525这里对表这里对表36中的基可行解进行转换。中的基可行解进行转换。由由于于23=2013=6(0+4)=2022=4(11)=6024=3(1+4)=031=8(4+3)=1034=9(4+4)=10u2+v1=2u2+v3=3u3+v2=3u3+v3=8v1=3v2=1v3=4v4=4由于所有非基变量的检验数均大等于零,故从表由于所有非基变量的检验数均大等于零,故从表311中中得到最优解为得到最优解为x11=25,x14=25,x21=15,x23=5,x32=2
14、0,x33=10,其它,其它xij=0f*=325+425+215+35+320+810=360此外,由于此外,由于24=0,故此问题有另一最优基可行解。具,故此问题有另一最优基可行解。具体求法是在表体求法是在表311中,以中,以x24为进基变量作闭回路,进为进基变量作闭回路,进行调整后得到。行调整后得到。由由上上面面分分析析可可知知,表表上上作作业业法法的的实实质质是是单单纯纯形形方方法法用用于于求求解解运运输输问问题题这这样样一一类类特特殊殊形形式式线线性性规规划划问问题题的简化,因而也称它为运输单纯形法。的简化,因而也称它为运输单纯形法。最后总结表上作业法的解题步骤最后总结表上作业法的解
15、题步骤。(1)编制调运表(包括产销平衡表及单位运价表);)编制调运表(包括产销平衡表及单位运价表);(2)正在调运表上求出初始基可行解;)正在调运表上求出初始基可行解;(3)用用位位势势法法或或闭闭回回路路法法计计算算非非基基变变量量的的检检验验数数。若若所所有有非非基基变变量量的的检检验验数数0,则则已已得得到到问问题题的的最最优优解解,停止计算。否则转下一步;停止计算。否则转下一步;(4)选选取取小小于于0的的检检验验数数中中的的最最小小者者对对应应的的变变量量作作为为进进基基变变量量,用用闭闭回回路路法法进进行行基基可可行行解解的的转转换换,得得到到新的基可行解,转(新的基可行解,转(3
16、)。)。第第三三节节产产销销不不平平衡衡的的运运输输问问题题及及其其求求解解-TotalSupplynotEqualtoTotalDemand一、产大于销一、产大于销(totalsupplyexceedstotaldemand)产大于销的运输问题的特征是产大于销的运输问题的特征是aibj,其数学模型为:,其数学模型为:解解此此类类问问题题可可假假想想一一个个销销地地Bn+1,其其需需要要量量为为:bn+1=aibj;若若用用xi,n+1表表示示从从Ai到到Bn+1的的运运量量,可可令令ci,n+1=0或或等等于于第第Ai产产地地储储存存单单位位物物资资的的费费用用。因因为为xi,n+1实实际际
17、上上表表示示Ai产产地地没没有有运运出出去去而而库库存存的的物物资资数数量量。经经处处理理后后,问问题题变变成成了了产产销销平平衡衡的的运运输输问问题,其数学模型为:题,其数学模型为:这样,这样,m个产地、个产地、n个销地的不平衡运输问题,转化成了个销地的不平衡运输问题,转化成了m个产地、个产地、n+1个销地的平衡运输问题,此时可用表上作业法求解。在用最小个销地的平衡运输问题,此时可用表上作业法求解。在用最小元素法求解该类问题初始基可行解时,若某列的运价全为零时,元素法求解该类问题初始基可行解时,若某列的运价全为零时,则该列最后考虑。则该列最后考虑。销销大大于于产产的的运运输输问问题题的的特特
18、征征是是aibj,其其数数学学模模型为:型为:二、销大于产二、销大于产(totaldemandexceedstotalsupply)解解此此问问题题可可假假想想一一个个产产地地Am+1,其其产产量量为为:am+1=bjai;若若用用xm+1,j表表示示从从Am+1到到Bj的的运运量量,可可令令cm+1,j=0或或等等于于第第Bj产产地地每每缺缺单单位位物物资资的的损损失失。因因为为xm+1,j实实际际上上表表示示Bj销销地地所所缺缺的的物物资资数数量量。经经处处理后,问题变成了产销平衡的运输问题,其数学模型为:理后,问题变成了产销平衡的运输问题,其数学模型为:此时,可用表上作业法求解。在用最小
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 问题 运筹学 交大 工商管理 讲义 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。