运输与指派问题.pptx
《运输与指派问题.pptx》由会员分享,可在线阅读,更多相关《运输与指派问题.pptx(52页珍藏版)》请在咨信网上搜索。
1、运筹学运筹学OperationsResearch第三讲第三讲运输与指派问题运输与指派问题实际工作中常碰到很多线性规划问题,由于他们约束实际工作中常碰到很多线性规划问题,由于他们约束条件变量的系数矩阵具有特殊的结构,很可能找到比单纯条件变量的系数矩阵具有特殊的结构,很可能找到比单纯形法更为简便的方法进行求解,从而可节约时间和费用形法更为简便的方法进行求解,从而可节约时间和费用,运输问题就是其中之一。运输问题的一般提法是运输问题就是其中之一。运输问题的一般提法是:某种物资某种物资有若干个产地和销地,若已知各产地地产量、各销地的销有若干个产地和销地,若已知各产地地产量、各销地的销量,以及各产地到各销
2、地的单位运价量,以及各产地到各销地的单位运价(或运输距离或运输距离),问应,问应如何组织调运才能使总运费如何组织调运才能使总运费(或总运输量或总运输量)最省?最省?【例例1】现有现有A1,A2,A3三个产粮区,可供应三个产粮区,可供应粮食分别为粮食分别为10,8,5(万吨万吨),现将粮食运往,现将粮食运往B1,B2,B3,B4四个地区,其需要量四个地区,其需要量分别为分别为5,7,8,3(万吨万吨)。产粮地到需求地的运价。产粮地到需求地的运价(元元/吨吨)如表如表1所示,问如何安排一个运输计划,使总的运输费用最少。所示,问如何安排一个运输计划,使总的运输费用最少。地区地区产粮区产粮区B1B2B
3、3B4产量产量A1326310A253828A341295需要量需要量578323运价表运价表(元元/吨吨)表表1运输模型运输模型ModelofTransportationProblems设设xij(i=1,2,3;j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运个需求地的运量,这样得到下列运输问题的数学模型:量,这样得到下列运输问题的数学模型:【解解】运输模型运输模型ModelofTransportationProblems【例例2】有三台机床加工三种零件,计划第有三台机床加工三种零件,计划第i台的生产任务为台的生产任务为a i(i=1,2,3)个零件,第个零件,第j种零
4、件的需要量为种零件的需要量为bj (j=1,2,3),第,第i 台机床台机床加工第加工第j 种零件需要的时间为种零件需要的时间为cij,如表,如表2所示。问如何安排生产所示。问如何安排生产任务使总的加工时间最少?任务使总的加工时间最少?零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表2运输模型运输模型ModelofTransportationProblems【解解】设设xi j (i=1,2,3;j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的数种零件的数量,则此问题的数学模型为量,则此问题的数学模型为运输模
5、型运输模型ModelofTransportationProblems运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地生产某种物资个产地生产某种物资,记作记作A1,A2,A3,Am,其产量分别,其产量分别为为a1,a2,am;有;有n个销地个销地,记作记作B1,B2,Bn,其需要量分,其需要量分别为别为b1,b2,bn;且;且产销平衡产销平衡,即,即。从第。从第i个产地个产地到第到第j 个销地的单位运价为个销地的单位运价为cij,在满足各地需要的前提下,求总,在满足各地需要的前提下,求总运输费用最小的调运方案。运输费用最小的调运方案。设设xij(i=1,2,m;j=1,2,n)为第为
6、第i 个产地到第个产地到第j个销地的运量,则数学模型为:个销地的运量,则数学模型为:运输模型运输模型ModelofTransportationProblems设平衡运输问题设平衡运输问题的数学模型为:的数学模型为:模型特征模型特征:1.运输问题存在可行解,也一定存在最优解运输问题存在可行解,也一定存在最优解;2.当供应量和需求量都是整数时,则一定存在整数最优解当供应量和需求量都是整数时,则一定存在整数最优解;3.有有m+n个约束个约束,mn个变量个变量;4.有有m+n1个基变量个基变量;运输模型运输模型ModelofTransportationProblems为为一一个个闭闭回回路路,集集合合
7、中中的的变变量量称称为为回回路路的的顶顶点点,相相邻邻两两个个变变量量的连线为闭回路的边。的连线为闭回路的边。x25x23B1B2B3B4B5A1A2A3x35A4 x43x11 x12x31x42表表3表表3中闭回路的变量集合是中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有共有8个顶点,个顶点,这这8个顶点间用水平或垂直个顶点间用水平或垂直线段连接起来,组成一条线段连接起来,组成一条封闭的回路。封闭的回路。闭回路闭回路:运输模型运输模型ModelofTransportationProblemsx11x12x32x33x41B1B2B3A1A2A3A4x
8、43表表4表表4中闭回路是中闭回路是注:注:(1)(1)一条回路中的顶点数一定是偶数,回路遇到顶点必须一条回路中的顶点数一定是偶数,回路遇到顶点必须转转9090度与另一顶点连接。度与另一顶点连接。(2)有些变量组本身不构成回路,但其可能包含回路,例如:有些变量组本身不构成回路,但其可能包含回路,例如:表表3中变量组中变量组不能组成一条闭不能组成一条闭回路,但回路,但A中包含有中包含有 闭回路闭回路运输模型运输模型ModelofTransportationProblems设平衡运输问题的数学模型为:设平衡运输问题的数学模型为:运输单纯形法运输单纯形法TransportationSimplexMe
9、thod运输单纯形法基本思路:运输单纯形法基本思路:是是基可行解基可行解最优否最优否否否停停运运输输单单纯纯形形法法也也称称为为表表上上作作业业法法,是是直直接接在在运运价价表表上上求求最最优解的一种方法,它的步骤是:优解的一种方法,它的步骤是:Step1:求求初初始始基基可可行行解解(初初始始调调运运方方案案)。常常用用的的方方法法 有有最小元素法、元素差额法最小元素法、元素差额法(Vogel近似法近似法)、左上角法等。、左上角法等。Step2:求求检检验验数数并并判判断断是是否否得得到到最最优优解解。常常用用于于求求检检验验数数的的方方法法有有闭闭回回路路法法和和位位势势法法,当当非非基基
10、变变量量的的检检验验数数ij全全都都非非负负时时得得到到最最优优解解,若若存存在在检检验验数数lk0,说说明明还还没没有有达达到到最最优优,转第三步。转第三步。Step3:调调整整运运量量,即即换换基基。选选一一个个变变量量出出基基,对对原原运运量量进行调整得到新的基可行解,转入第二步。进行调整得到新的基可行解,转入第二步。注注:表上作业法的条件是表上作业法的条件是产销平衡和运价非负。产销平衡和运价非负。运输单纯形法运输单纯形法TransportationSimplexMethod初始基可行解的确定初始基可行解的确定最最小小元元素素法法:最最小小元元素素法法的的思思想想是是就就近近优优先先运运
11、送送,即即最最小小运运价价cij 对应的变量对应的变量xij 优先赋值优先赋值然然后后再再在在剩剩下下的的运运价价中中取取最最小小运运价价对对应应的的变变量量赋赋值值并并满满足足约约束束,依次下去,直到最后得到一个初始基可行解。依次下去,直到最后得到一个初始基可行解。【例例3】求表求表5所示的运输问题的初始基可行解。所示的运输问题的初始基可行解。表表5销销地地产地产地B1B2B3产产量量A1A2A3847634758304525销销量量603010100运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3产产量量A186730A243545A374
12、825销销量量603010100表表6【解解】3015102520运输单纯形法运输单纯形法TransportationSimplexMethod【例例4】求表求表7给出的运输问题的初始基本可行解给出的运输问题的初始基本可行解B1B2B3B4aiA14104420A2773815A31210615bj510251050表表7运输单纯形法运输单纯形法TransportationSimplexMethod表表8BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解解】5100151010运输单纯形法运输单纯形法TransportationSimpl
13、exMethod初始基本可行解可用下列矩阵表示初始基本可行解可用下列矩阵表示表表8中,基变量恰好是中,基变量恰好是3+41=6个且不包含闭回路,个且不包含闭回路,是一组基变量,其余标有符号是一组基变量,其余标有符号的变量是非基变量的变量是非基变量运输单纯形法运输单纯形法TransportationSimplexMethod求求出出一一组组基基可可行行解解后后,判判断断其其是是否否最最优优,仍仍然然是是用用检检验验数数来来判判断断,记记xij的的检检验验数数为为ij,由由第第一一章章知知,求求最最小小值值的的运运输输问问题题的的最最优优判判别准则是:别准则是:所有非基变量的检验数都非负,则运输方
14、案最优所有非基变量的检验数都非负,则运输方案最优(即为最优解即为最优解)。求检验数的方法有两种,求检验数的方法有两种,闭回路法和位势法。闭回路法和位势法。1 1闭闭回回路路法法求求某某一一非非基基变变量量的的检检验验数数的的方方法法是是:在在基基本本可可行行解解矩矩阵阵中中,以以该该非非基基变变量量为为起起点点,以以基基变变量量为为其其它它顶顶点点,找找一一条条闭闭回回路路,由由起起点点开开始始,分分别别在在顶顶点点上上交交替替标标上上代代数数符符号号+、-、+、-、,以以这这些些符符号号分分别别乘乘以以相相应应的的运运价价,其其代代数数和和就就是是这这个个非非基基变量的检验数。变量的检验数。
15、求检验数求检验数运输单纯形法运输单纯形法TransportationSimplexMethod【解解】用最小元素法得到下列一组基本可行解用最小元素法得到下列一组基本可行解【例例5】求求下下列列运运输输问问题题的的一一个个初初始始基基本本可可行行解解及及其其检检验验数数。矩矩阵阵中中的的元元素素为为运运价价Cij,矩矩阵阵右右边边的的元元素素为为产产量量ai,下下方方的的元元素为销量素为销量bj。运输单纯形法运输单纯形法TransportationSimplexMethod只求非基变量的检验数:只求非基变量的检验数:求求11,先找出,先找出x11的闭回路的闭回路,对应的运价为,对应的运价为再用正
16、负号分别交替乘以运价有再用正负号分别交替乘以运价有直接求代数和得直接求代数和得运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj1060403080966-32 2位位势势法法求求检检验验数数:位位势势法法求求检检验验数数是是根根据据对对偶偶理理论论推推导导出出来来的的一种方法。一种方法。设平衡运输问题为设平衡运输问题为设设前前m个个约约束束对对应应的的对对偶偶变变量量为为ui(i=1,2,m),后后n个个约约束束对对应的对偶变量为应的对偶变量为vj(j=1,2
17、,n),则运输问题的对偶问题是则运输问题的对偶问题是运输单纯形法运输单纯形法TransportationSimplexMethod加入松驰变量加入松驰变量ij将约束化为等式将约束化为等式:ui+vj+ij=cij记记原原问问题题基基变变量量XB的的下下标标集集为为I,由由第第二二章章对对偶偶性性质质知知,原原问问题题xij的的检检验验数数的的相相反反数数是是对对偶偶问问题题的的松松弛弛变变量量ij,当当(i,j)I时时ij=0,因而有,因而有解上面第一个方程,将解上面第一个方程,将ui、vj 代入第二个方程求出代入第二个方程求出ij运输单纯形法运输单纯形法TransportationSimpl
18、exMethod【例例6】用位势法求例用位势法求例7给出的初始基本可行解的检验数。给出的初始基本可行解的检验数。【解解】第一步求位势第一步求位势u1、u2、u3及及v1、v2、v3、v4。10604030令令u1=0得到位势的解为得到位势的解为运输单纯形法运输单纯形法TransportationSimplexMethod再再由由公公式式求求出出检检验验数数,其其中中cij是是非非基变量对应的运价。基变量对应的运价。计算结果与例计算结果与例7结果相同。结果相同。运输单纯形法运输单纯形法TransportationSimplexMethod用位势法求检验数通常可直接在表上进行计算:例如用位势法求检
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 指派 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。