运筹学-第3章运输问题.ppt
《运筹学-第3章运输问题.ppt》由会员分享,可在线阅读,更多相关《运筹学-第3章运输问题.ppt(47页珍藏版)》请在咨信网上搜索。
1、Chapter3 运输运输问题问题(Transportation Problem)运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用 本章主要内容:本章主要内容:本章主要内容:本章主要内容:1 从从m个发点个发点 向向n个收点个收点 发送某种货物发送某种货物.发点的发发点的发量为量为 ,收点的收量为收点的收量为 。由。由 运运往往 单位货物的运费为单位货物的运费为 ,问如何调配,问如何调配,才能使运费最省?才能使运费最省?问题的提出问题的提出2.表表1 产销平衡表产销平衡表 上述数据可以汇总于上述数据可以汇总于表格中表格中,如下如下:表表2 单位运价表单位运价
2、表 3.运输问题的数学模型 设设xij代表为从第代表为从第i个产地调运给第个产地调运给第j个销地的物资个销地的物资的数量的数量.在产销平衡的条件下,即在产销平衡的条件下,即 使总的运费支出最小,可以表为以下数学形式:使总的运费支出最小,可以表为以下数学形式:4.运输问题的约束方程组系数矩阵及特征运输问题的约束方程组系数矩阵及特征1.矩阵矩阵A是一个是一个m+n行行mn列的矩阵,它的秩为列的矩阵,它的秩为m+n-1。2.运输问题应该有运输问题应该有m+n-1个基变量。个基变量。3.3.xij的系数列向量为:的系数列向量为:m行n行5.表上作业法表上作业法6.表上作业法的基本思路:表上作业法的基本
3、思路:确定初始调运方案确定初始调运方案最优性检验最优性检验改进方案改进方案 7.1 确定初始基可行解确定初始基可行解 运输问题确定初始基可行解,就是求出运输问运输问题确定初始基可行解,就是求出运输问题的初始调运方案题的初始调运方案.确定初始基可行解的方法有确定初始基可行解的方法有最小元素法最小元素法伏格尔法伏格尔法8.【例例2-12-1】某公司经销甲产品某公司经销甲产品,下设下设3 3个加工厂个加工厂A A1 1、A A2 2、A A3 3,产品分别运往销售点,产品分别运往销售点B1、B2、B3、B4,各工厂,各工厂的日产量和各销售点的日需求量及各工厂到各销售点的日产量和各销售点的日需求量及各
4、工厂到各销售点的运价如下表所示的运价如下表所示:(:(运输问题供需平衡表和运价表运输问题供需平衡表和运价表如下),求总运费最少的调运方案。如下),求总运费最少的调运方案。销地产地B1B2B3B4发量(T)A13113107A219284A3741059收量(T)3656表3-39.思路:思路:为了减少运费,应优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地,以后将不再考虑。然后,在余下的供、销点的供销关系中,继续按上述方法安排调运,直至安排完所有供销任务,得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可
5、行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务,故称为最小元素法。1、最小元素法、最小元素法10.1.最小最小元素法元素法314633Z=43+310+31+12+64+35=86Z=43+310+31+12+64+35=86该方案总运费:该方案总运费:(思想:就近供应)(思想:就近供应)不不能能同同时时划划去去行行和和列列保证填保证填有运量有运量的格子的格子为为m+n-1表3-411.最小元素法,有时按某一最小单位运价优先安排物品调运时,却可能在其他供销点多花几倍的运费,从而使整个运输费用增加。55552.沃格尔法沃格尔法沃格尔法考虑到:一个产地的产品假如不能按
6、照最小运费就近供应,就考虑次小运费,这就有个差额。如果差额不大,当不能按最小单位运价安排运输时造成的运费损失不大;反之,如果差额很大,不按最小运价组织运输就会造成很大损失,故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。12.沃格尔法计算步骤:沃格尔法计算步骤:1)分别算出各行、各列的最小运费与次小运费的差额。2)从行、列中选出差额最大者,选择它所在行、列中的最小元素,进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。13.2.伏格尔法伏格尔法 2 5 1 3 0 1 1 表表3-66 2 1 3 0 1 2 3 2 1 2 0 1 3 1 2 7 6
7、521表3-5Z=8514.v1 若有两个以上相同的最大差值,可任取其一。v2 剩下一行或者一列有空格,填数字,不能划掉。v3 计算行差,列差时,已经划去的列或者行不再考虑。15.销产B1B2B3产量A151 812A224114A33 674销量 91011例例例例用用用用伏格尔法伏格尔法伏格尔法伏格尔法求初始调运方案求初始调运方案求初始调运方案求初始调运方案16.销产B1B2B3产量A1210 12A231114A34 4销量 91011初始调运方案初始调运方案17.2.2 最优解的判别最优解的判别 判别办法是计算判别办法是计算空格空格(非基变量非基变量)的检验数的检验数,因为运因为运输问
8、题的目标函数是实现最小化输问题的目标函数是实现最小化,所以当所有空格处所以当所有空格处的的检验数大于等于零检验数大于等于零时时,为最优解为最优解.下面分别介绍两种计算检验数的方法下面分别介绍两种计算检验数的方法:(1)闭回路法闭回路法(2)(2)位势法位势法18.闭回路法闭回路法 闭回路:从闭回路:从空格空格出发画出发画水平水平(或垂直或垂直)直线,遇到直线,遇到填有运量填有运量的方格(数字格)的方格(数字格)可转可转90,然后继续前进,然后继续前进,直到到达出发的空格所形成的闭合回路。直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。调运方案的任意空格一定存在唯一闭回
9、路。销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656表3-719.5 10 4 7A3 8 2 9 1A2 10 3 11 3A1B4B3B2B1 销地产地633431计算最小元素法得到的初始基可行解的检验数计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)3+(-1)3+(+1)2+(-1)1=1(+1)3+(-1)3+(+1)2+(-1)1=1调整后总运费增加:调整后总运费增加:空格处检验数为1表3-820.5 10 4 7A3 8 2 9 1A2 10 3 11 3A1B4B3B2B1 销地产地633431(+1)(
10、-1)(+1)(-1)7-5+10-3+2-1=107-5+10-3+2-1=10调整调整后总运费增加:后总运费增加:空格处检验数为10(-1)(+1)表3-921.检验数表检验数表110121-12 因为存在小于零的检验数因为存在小于零的检验数,所以最小元素法给出的所以最小元素法给出的方案不是最优方案方案不是最优方案.表3-1022.2.位势法位势位势:运输问题的对偶变量称为位势。:运输问题的对偶变量称为位势。因为因为m个供应点个供应点n个需求点的运输问题有个需求点的运输问题有m+n个约束,个约束,因此运输问题就有因此运输问题就有m+n个位势。个位势。行位势行位势:关于供应点关于供应点Ai的
11、约束对应的对偶变量,记为的约束对应的对偶变量,记为 ui,i=1,2,m。列位势列位势:关于需求点关于需求点Bj的约束对应的对偶变量,记为的约束对应的对偶变量,记为vj,j=1,2,n。23.定理定理:运输问题变量运输问题变量xij的检验数的检验数证明:证明:24.位势法位势法求检验数的步骤求检验数的步骤:1.1.在在表表中中下下面面和和右右面面增增加加一一行行和和一一列列,列列中中添添入入ui,行行中中添添入入vj,令令u1=0,按按照照 ,根根据据表表中中已已有有的数字确定所有的的数字确定所有的ui及及vj;2.2.计算所有空格处的检验数计算所有空格处的检验数.25.2 -1 3010-5
12、 9检检验验数数表表121-11012 24=-10,当前方案,当前方案 不是最优方案。不是最优方案。最最优优方方案案判判别别准准则则表3-1226.2.3 2.3 闭回路调整法改进方案闭回路调整法改进方案xpq为换入变量为换入变量 从从(p,qp,q)空格开始画闭回路,其它转角点都是空格开始画闭回路,其它转角点都是填有运量的方格,并从填有运量的方格,并从(p,qp,q)空格开始给闭回路上空格开始给闭回路上的点按的点按+1+1,-1-1,+1+1,-1-1编号,编号,-1-1格的最小运量格的最小运量为调为调整量。整量。表3-1327.找到最小调整量以后找到最小调整量以后,按照闭回路上的正、负按
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运输 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。