首页 数学建模运输问题

数学建模运输问题

举报
开通vip

数学建模运输问题会计学1数学建模运输问题第四章运输问题运输问题(TransportationProblem,简记为TP)是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的,是物流优化管理的重要的内容之一。从理论上讲,运输问题也可用单纯形法来求解,但是由于运输问题数学模型具有特殊的结构,存在一种比单纯形法更简便的计算方法——表上作业法,用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法加速物资流转降低流通费用第1页/共41页§1运输问题及其数学模型§1运输问题及其数学模...

数学建模运输问题
会计学1数学建模运输问题第四章运输问题运输问题(TransportationProblem,简记为TP)是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的,是物流优化管理的重要的内容之一。从理论上讲,运输问题也可用单纯形法来求解,但是由于运输问题数学模型具有特殊的结构,存在一种比单纯形法更简便的计算 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ——表上作业法,用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法加速物资流转降低流通费用第1页/共41页§1运输问题及其数学模型§1运输问题及其数学模型设某种物资共有m个产地A1,A2,…,Am,各产地的产量分别是a1,a2,…,am;有n个销地B1,B2,…,Bn,各销地的销量分别为b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物资的运价是cij,问怎样调运才能使总运费最小?一、运输问题的数学模型第2页/共41页第四章运输问题销地产地B1B2…Bn产量A1c11c21…c1na1A2c21c22…c2na2ミミミミミAmcm1cm2…cmnam销量b1b2…bn运输表1、产销平衡问题即设xij表示产地Ai运往销地Bj(i=1,2,…,m;j=1,2,…,n)的运量.销地产地B1B2…Bn产量A1x11c11x12c12…x1nc1na1A2x21c21x22c22…x2nc2na2ミミミミミAmxm1cm1xm2cm2…xmncmnam销量b1b2…bnNote:cij在左下角xij在右上角第3页/共41页§1运输问题及其数学模型2、产销不平衡问题当当第4页/共41页第四章运输问题二、运输问题数学模型的特点讨论产销平衡问题定理1平衡运输问题必有可行解,也必有最优解. 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 定理2平衡运输问题的约束方程系数矩阵A和增广矩阵的秩相等,且等于m+n-1.即定理2说明:基可行解包含m+n-1个基变量.定理3平衡运输问题的约束方程系数矩阵A的所有各阶子式只取0,1或-1三个值.定理4如果平衡运输问题中的所有产量ai和销量bj都是整数,那么,它的任一基可行解都是整数解.证明noteGoon第5页/共41页定理1的证明Proof:则取显然有,又所以,是问题的一个可行解.又因为,对于任一可行解有目标函数值,对于求极小化问题,目标函数值有下界,则必有最优解.第6页/共41页§1运输问题及其数学模型Note:平衡运输问题有个变量,个约束条件,规模很大。Goback第7页/共41页定理4的证明Proof:设x是Ax=b的任一基可行解,B为对应的基矩阵,则其中Bt是用b中对应的m+n-1元素替换B的第t列元素得到的矩阵.显然,由定理3及ai、bj都是整数知,detBt是个整数,detB=,因此,都是整数.其基变量为第8页/共41页第四章运输问题定义1凡是能排列成(其中互不相同,互不相同)形式的变量集合,称为一个闭回路,其中诸变量称为这个闭回路的顶点.B1B2B3B4B5A1x11x12x13x14x15A2x21x22x23x24x25A3x31x32x33x34x35A4x41x42x43x44x45如:变量集合变量集合2、每一行(或列)若有闭回路的顶点,则有两个顶点;3、每两个顶点格子的连线都是水平的或垂直的;4、闭回路中顶点的个数必为偶数.闭回路的几何特征:1、每一个顶点格子都是90°转角点;第9页/共41页§1运输问题及其数学模型闭回路的代数性质:性质1构成闭回路的变量组对应的列向量组必线性相关.证明性质2分组构成闭回路,则该变量组对应的列向量组是线性相关的.推论1若变量组对应的列向量组线性无关,则该变量组一定不包含闭回路.若变量组中有一个部Goon第10页/共41页性质1的证明Proof:由直接计算可知故该向量组线性相关.第11页/共41页第四章运输问题在变量组中,若有某一个变量xij是它所在的行(第i行)或列(第j列)中出现于(*)中的唯一变量,则称该变量xij是该变量组的一个孤立点.定义2闭回路的特征性质3没有孤立点若一变量组中不包含任何闭回路,则该变量组必有孤立点.反证孤立点不会是闭回路上的点定理5变量组对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.证明第12页/共41页定理5的证明Proof:用反证法设变量组(*)对应的列向量组线性无关,但该变量组包含一个以其中某些变量为顶点的闭回路,则由性质2知,这些变量对应的列向量必线性相关,与假设矛盾.定理5变量组对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.设有一组数使得由于变量组(*)中不包含任何闭回路,由性质3可知其中必有孤立点,不妨设为孤立点,又不妨设是(*)在第i1行上唯一的变量,这时由pij的特征,(1)的左端第i1个分量和为k1,而右端为0,在第j1列上的唯一变量如何?但仍不包含闭回路,其中还有孤立点,与前面类似分析可证k2=0.同理得k3=k4=…=kr=0这就证明了向量组(*)线性无关.第13页/共41页§1运输问题及其数学模型推论2平衡运输问题中的一组m+n-1个变量能构成基变量的充要条件是它不包含任何闭回路.该推论给出了运输问题的基可行解中基变量的一个基本特征:基变量组不含闭回路.这就是基可行解在表上的一个表现,利用它来判断m+n–1个变量是否构成基变量组,就看它是否包含闭回路.这种方法简便易行,它比直接判断这些变量对应的列向量是否线性无关要简便得多.利用基变量的这个特征,将可以导出求平衡运输问题的初始基可行解的一些简便方法.第14页/共41页§2运输问题的表上作业法§2运输问题的表上作业法表上作业法(又称运输单纯形法)是根据单纯形法的原理和运输问题的特点, 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的一种在表上运算的求解运输问题的简便而有效的方法.主要步骤:1、求一个初始调运方案(初始基可行解);2、判别当前方案是否为最优,若是则迭代停止,否则转下一步;3、改进当前方案,得到新的方案(新的基可行解),再返回2。第15页/共41页第四章运输问题一、初始方案的确定1、西北角法BjAiB1B2B3B4aiA11052370A2431220A3563410bj50251015Ex.150已知某商品有三个产地A1、A2、A3和四个销地B1、B2、B3、B4,产量、销量及单位运价如表.问应如何调运,在满足各销地需要的情况下,使总的运费支出为最少?解:51010205规则:从运输表的西北角开始,优先安排编号小的产地和销地的运输任务.填了几个数字?Note:在填入一个数时,如果行和列同时饱和, 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 只划去一行或一列BjAiB1B2B3B4aiA11052350A2431220A3563410bj50251015500第16页/共41页§2运输问题的表上作业法2、最小元素法BjAiB1B2B3B4aiA11052370A2431220A3563410bj50251015规则:优先安排单位运价最小的产地与销地之间的运输任务.40102551010Note:在某行(或列)填入最后一个数时,如果行和列同时饱和,规定只划去该行(或列)BjAiB1B2B3B4aiA1153260A2412320A3561410bj502010100010102050填了几个数字?第17页/共41页第四章运输问题定理6用西北角法或最小元素法得到的初始解是平衡运输问题的基可行解,m+n-1个填入数字的格子对应的是基变量.Proof:首先,得到的初始解为可行解是显然的.其次,由于行列数共有m+n,而按填数字的方法,除填最后一个数时,划去一行一列外,每填一个数划去一行或一列.因此,共填m+n-1个数.最后,证明所填m+n-1个数对应的变量组不含闭回路.用反证法若含有闭回路不妨设此闭回路如右(其他情形同理可证)不妨设填后划去行,故必须较先填,且填后划去的是列,从而必须较先填,且填后划去的是行,而这又说明必须较先填,且填后划去的是列,这又得到必须较先填,且填后划去的是行,这样就得到了矛盾,所以,填数的m+n-1个格子对应的变量组不含闭回路,从而,证得了本定理.第18页/共41页§2运输问题的表上作业法关键1、填一个数字划去一行或一列不产生闭回路;2、填一个数字只划去一行或一列填满m+n-1个数.BjAiB1B2aiA1825A2314bj63差额62差额51315BjAiB1B2aiA1825A2314bj63按最小元素法3423、Vogel法(元素差额法)规则:计算各行各列的最小元素与次小元素的差额,优先安排差额最大的所在行或列的单位运价最小的产地与销地之间的运输任务这是最优解第19页/共41页第四章运输问题二、最优性检验BjAiB1B2B3B4aiA11052370A2431220A3563410bj5025101540102551010定理7设是平衡运输问题的一组基变量,是非基变量,则在变量组中存在唯一的闭回路.1、闭回路法+1-1+1-1检验数BjAiB1B2B3B4A1A2A3检验数表-5-10666第20页/共41页§2运输问题的表上作业法2、位势法(对偶变量法)求检验数的方法约束方程的系数矩阵的秩为m+n-1x0必为基变量,x0=0约束方程的系数矩阵的秩为m+n对任意的a0,与原问题等价由于xj的检验数  设:          为基变量,由于基变量的检验数等于零.一定有解,不唯一(a0可任取)ui称为行位势,vj称为列位势第21页/共41页第四章运输问题BjAiB1B2B3B4uiA1 4010255253A243101102A3105634vjBjAiB1B2B3B4A1A2A3检验数表-5-10666-2-120273见Ex.1最小元素法得到的初始基可行解10053-12-5若,则此时的运输方案为最优的第22页/共41页§2运输问题的表上作业法三、基可行解的改进BjAiB1B2B3B4aiA11052370A2431220A3563410bj5025101540102551010BjAiB1B2B3B4A1A2A3检验数表-5-10666选择进基变量则取非基变量xst为进基变量确定出基变量调整量则基变量xkl出基(运量擦去)调整方法:在该闭回路上,奇点运量加,偶点减去能转运多少?15301065420101-5652066456因为,所以此运输方案为最优方案Note:若在闭回路上有几个偶点处的运量等于,则可任取其中一个作为出基变量(运量擦去),其余几个点的值调整后变为0.(但应填入,说明这些变量还在基内,这时就出现了退化)620-50-50=520问:从A2到B4的单位运价c24在什么范围变化时,所得最优调运方案不变.c12在什么范围变化呢?第23页/共41页第四章运输问题补充:运输问题的图上作业法图上作业法是在交通图上进行物资调运方案编制和调整的一种科学方法。在铁路特别是公路运输中使用很多且有很好的效果。在交通图中,用Ο表示产地(发点),并将产量记在圆圈内;用□表示销地(收点),并将销量记在方框内。206040402463目标:吨公里数(费用)最小的调运方案.物资调运的流向用与交通线平行的箭线表示,规定画在前进方向的右边,调运量加括号记在箭线的右边。(20)(20)(40)第24页/共41页补充:运输问题的图上作业法20303020243对流:物资在同一线路上往返运输.(20)(20)(30)(30)(10)这是对流20303020243(20)(20)(30)(30)106030(10)(20)1、无圈的交通图2020502010对于无圈图,每条边都是割边,去掉它网络将不连通,所以,每条边上的运量是不得不只要每条边上不产生对流,即为最优方案第25页/共41页第四章运输问题206040402463(20)(20)(40)2、有一个圈的交通图圈长:圈上每一条边的长度之和(记为l)l=15先用“丢边破圈”方法,得到无圈图,再产生一个没有对流的方案。内圈长l内:流向在圈内的边的长度之和l内=8外圈长l外:流向在圈外的边的长度之和l外=4是最优解吗?称为迂回调整方案:对内圈各流量中最小调运量,进行反向调运(40)(20)(20)结论:内外圈长都小于圈长的一半的无对流的调运方案为最优方案第26页/共41页补充:运输问题的图上作业法3、有多个圈的交通图106030202050203020有几个圈?如有一个圈的情形,对每一个圈先用“丢边破圈”方法,得到无圈图,再产生一个没有对流的方案。再进行检查、调整。只需检查13个圈吗?会循环吗?一般不够!因为对一个圈进行调整后,会对已检查的圈有影响.不会!因为每次目标函数下降值大于一个固定值(如1)第27页/共41页第四章运输问题四、产销不平衡运输问题当Note:通常建立运输模型指的是平衡运输模型可以虚设一个产地Am+1,其产量为并假设产地Am+1运往各销地的单位运价为cm+1,j=0(j=1,2,…,n).则原问题可转化为平衡运输问题:产大于销,可通过虚设销地,类似建立平衡运输模型第28页/共41页§2运输问题的表上作业法Ex.2已知运输问题由表给出,试建立运输模型.BjAiB1B2B3aiA142510A263815bj8714解:BjAiB1B2B3aiA142510A263815A30004bj8714本题产量为25,销量为29,是销大于产问题虚设一个产地A3,由于并没有生产,所以运价为零,得运输模型.如果各销地不满足时,单位缺货费为4,3,7,则运输模型为437第29页/共41页第四章运输问题BjAiB1B2B3aiA142310A256415A334520最低需求量101010Ex.3已知运输问题由表给出,如果产地Ai的产量必须运走,试建立运输模型.BjAiB1B2B3B4aiA142310A256415A334520bj10101015解:这是一个产大于销的运输问题.234虚设一销地B4,销量b4=15.BjAiB1B2B3aiA142310A256415A334520最低需求量101010最高需求量2010不限BjAiB1B2B3aiA142310A256415A334520bj101010443B’3B’15351015A4M100MM0三个销地的最低需求为30,最高需求不限.根据现有产量,B3至多能得到25.建立运输模型.2说明什么?第30页/共41页第四章运输问题§3运输问题应用举例Ex.4(生产调度问题)某制冰厂每年1~4季度必须供应冰块15、20、25、10(千吨).已知该厂各季度冰块的生产能力及冰块的单位成本如表.如果生产出来的冰块不在当季度使用,每千吨冰块存储一个季度费用为4(千元).又设该制冰厂每年第3季度末对贮冰库进行清库维修.问应如何安排冰块的生产,可使该厂全年生产、存储费用最少?季度生产能力(千吨)单位成本(千元)1255218731684155第31页/共41页§3运输问题应用举例季度生产能力(千吨)单位成本(千元)1255218731684155BjAiB1B2B3B4aiA125A218A316A415bj15202510解:5B54913M0MMMMM0005118179137第32页/共41页第四章运输问题Ex.5(运量有界的运输问题)657bj10762A28453A1aiB3B2B1BjAi表1524A2334A1B3B2B1dij表2表1给出一个运输问题.现在规定产地Ai至销地Bj的运量不能超过dij,由表2给定.试建立运输问题.解:虚设Dij(i=1,2;j=1,2,3)6个点,Dij既作产地,又作销地,其产量、销量都为dij.产地Ai的物资只可运送给Dij,而Dij的物资只可运送给Bj,或送给自身.第33页/共41页§3运输问题应用举例BjAiD11D12D13D21D22D23B1B2B3aiA1D11D12D13A2D21D22D23bj657bj10762A28453A1aiB3B2B1BjAi表1524A2334A1B3B2B1dij表28104330000305040000206074334254257563321303124244214第34页/共41页第四章运输问题Ex.6(空车调度问题)某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务.已知各条航线的起点、终点城市及每天航班数见表1,假定各条航线使用相同型号的船只,又各城市间的航程天数见表2.又知每条船只每次装卸货的时间各需一天,则该航运公司至少应配备多少条船,才能满足所有航线的运货需求?航线起点城市终点城市每天航班数1ED32BC23AF14DB1表1到从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表2第35页/共41页§3运输问题应用举例解:该公司所需配备船只分两部分.1、载货航程需要的周转船只数航线起点城市终点城市每天航班数1ED32BC23AF14DB1表1到从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表2如航线1,在港口E装货1天,E至D航程17天,在D卸货1天,总计19天.每天3航班,故该航线周转船只需57条.航线装货天数航程天数卸货天数小计航班数需周转船只数11171193572131521031719194113115115累计共需周转船只数91条.第36页/共41页第四章运输问题2、各港口间调度所需船只数港口城市每天到达每天需求余缺数A01-1B12-1C202D312E03-3F101港口每天到达与需要的船只不同,如表.为使配备船只数最少,应做到周转的空船数为最少.建立运输模型,C、D、F为空船的产地,A、B、E为销地,单位运价为相应各港口之间的船只航程天数.港口ABE每天多余船只C2352D1413172F7831每天缺少船只11311111用表上作业法求出空船的最优调度方案.最少需周转的空船数为40条.所以,在不考虑维修、储备等情况下,该公司至少应配备131条船.第37页/共41页§3运输问题应用举例Ex.7(运输问题悖论)paradox在运输问题中,有一种在若干个产销地运价不变的情况下,当调运量增加了,总运费反而会下降的奇怪现象.BjAiB1B2B3B4B5aiA11415613147A216922131618A38511456A41241891015bj41112811746851510如下面的运输问题,总调运量46单位,最优总费用444单位.现在总产量和总销量各增加10单位,单位运价不变,总费用将如何?12112112468011150运量为56,最优总费用为409单位.怎么会产生呢?产生负费用路多品种物资运输问题、转运问题、车(船)调度问题等第38页/共41页第四章运输问题完第39页/共41页用表上作业法求如下运输问题的最优方案(初始方案由最小元素法得到)BjAiB1B2B3B4aiA13571110A2146313A37812718bj161285第40页/共41页
本文档为【数学建模运输问题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: ¥17.6 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
莉莉老师
暂无简介~
格式:ppt
大小:595KB
软件:PowerPoint
页数:0
分类:
上传时间:2021-10-18
浏览量:69