演示文稿运筹学第三章运输问题

演示文稿运筹学第三章运输问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 第一页，共四十七页。运筹学第三章运输问题ppt 课件 超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载 第二页，共四十七页。3.1运输问题的典例和数学模型3.2运输问题的求解方法：表上作业法3.3几类特殊的运输问题3.4运输问题的应用第三页，共四十七页。运输问题：根据已有的交通网，如何制定运输 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。第四页，共四十七页。3.1运输问题的典例和数学模型一、典例某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨产地单位运价销地B1B2B3B4A1A2A3311310192874105第五页，共四十七页。调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地第六页，共四十七页。二、建立模型设xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6第七页，共四十七页。单位运价表产销平衡表第八页，共四十七页。一般模型表示(ai=bj)第九页，共四十七页。三、模型的特点1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量0110………第十页，共四十七页。x11x12······x1nx21x22······x2n,············,xm1xm2······xmn11······100······0············00······000······011······1············00······000······000······0············11······110······010······0············10······001······001······0············01······000······100······1············00······1i=1i=2i=mj=1j=2j=n···························································································································································································第十一页，共四十七页。关于运输模型的几个结论：(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n-1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路。第十二页，共四十七页。初始基可行解新的基可行解最优否？STOPYN3.2运输问题的求解方法：表上作业法单纯形法求解思路第十三页，共四十七页。表上作业法步骤:初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。第十四页，共四十七页。3产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量311310192874105634133656749单位运价表产销平衡表最小元素法第十五页，共四十七页。例产地销地A1A2B1B215151020产量销量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法第十六页，共四十七页。产地销地A1A2A3B1B2B3B4749产量销量3656635213产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法产销平衡表第十七页，共四十七页。针对最小元素法和vogel法，需要说明的几点：(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；第十八页，共四十七页。例产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量273118469431052030251015201050单位运价表产销平衡表102515100第十九页，共四十七页。产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量31131019287410563431336567493656749产量销量363521(1)(2)(1)(-1)(10)(12)△z=c11-c13+c23-c21=1=11△z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表闭回路法第二十页，共四十七页。注:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。第二十一页，共四十七页。产地销地A1A2A3B1B1B3B4位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj计算各ui和vj3.计算空格处位势；ij=ui+vj行位势ui列位势vj110-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1A2A3B1B1B3B4311310192874105产地单位运价表位势表:2105(2)(9)(8)(9)(-3)(-2)第二十二页，共四十七页。产地销地A1A2A3B1B1B3B4749产量销量36566343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。第二十三页，共四十七页。注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。第二十四页，共四十七页。5例：产地销地A1A2A3B1B1B3B4749产量销量3656635213(0)(2)(2)(9)(1)(12)产地销地A1A2A3B1B1B3B4749产量销量365663312第二十五页，共四十七页。4(1)产地销地A1A2A3B1B2B3B4产量销量632233665659(2)(1)(-1)(10)(12)例：6产地销地A1A2A3B1B2B3B4产量销量630336656592第二十六页，共四十七页。练习产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表第二十七页，共四十七页。最小元素法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表155151000第二十八页，共四十七页。Vogel法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表867792125-6119102-15-6-91013-105100第二十九页，共四十七页。注:表上作业法适用于下列情形：cij≥0；minz；产销平衡。表上作业法步骤第三十页，共四十七页。3.3几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题第三十一页，共四十七页。Minz=cij·xijni=1j=1m一、产销不平衡问题1产销(ai>bj)Minz=cij·xij+0xi,n+1ni=1j=1mi=1m第三十二页，共四十七页。产地销地A1A2┊AmB1B2┈　BnC11C12┈C1nC21C22┈C2n┆┊┈┊Cm1Cm2┈CmnBn+1００┆０产＞销问题单位运价表销量产量b1b2┈　bna1a2┊amaibj第三十三页，共四十七页。Minz=cij·xijni=1j=1m2销产(bj>ai)Minz=cij·xij+0xm+1,jni=1j=1mj=1n第三十四页，共四十七页。产地销地A1A2┊AmB1B2┈　BnC11C12┈C1nC21C22┈C2n┆┊┈┊Cm1Cm2┈CmnAm+1销＞产问题单位运价表00┈0销量产量b1b2┈　bna1a2┊ambjai第三十五页，共四十七页。例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地AⅠⅡⅢⅣ产量最低需求1613221714131915192023―单位运价表5060503070010单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求507030不限第三十六页，共四十七页。ABCⅠⅠⅡⅢⅣⅣ16161322171714141319151519192023MMM0M0M0供应需求产量销量506050302070301050产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。第三十七页，共四十七页。最优方案：需求产地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20103060C3020050D302050销量302070301050第三十八页，共四十七页。练习产地销地AⅠⅡⅢ最高发量467-78单位运价表6040400BC销量708050D最低发量8040不限5054645-第三十九页，共四十七页。三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。第四十页，共四十七页。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表第四十一页，共四十七页。3.4运输问题的应用第四十二页，共四十七页。例：某工厂按 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ25353010第四十三页，共四十七页。模型：设xij第i季度生产，用于第j季度交货的数量。obj.minz=cijxiji=1j=144x11+x12+x13+x1425x22+x23+x2435x33+x3430x4410x11=10x12+x22=15x13+x23+x33=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供应：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：第四十四页，共四十七页。单位费用表：ⅠⅡⅢⅣⅠⅡⅢⅣ10.810.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.30单位：万元供应需求第四十五页，共四十七页。例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？第四十六页，共四十七页。建立模型：设xj—第j天使用新毛巾的数量；yij—第i天送第j天使用快洗餐巾的数量；zij—第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求约束供应约束新购餐巾：x1+x2+x3+x4+x55200第一天送洗：y12+z13+z14+z151000第二天送洗：y23+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200xj0，yij0，zij0，（i=1,┈,4；j=1,┈,5）Minz=∑xj+∑∑0.2yij+∑∑0.1zij第四十七页，共四十七页。