《运筹学》第三章-运输问题资料讲解

《运筹学》第三章运输问题23.1运输问题的典例和数学模型3.2运输问题的求解方法：表上作业法3.3几类特殊的运输问题3.4运输问题的应用3运输问题：根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。43.1运输问题的典例和数学模型一、典例某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨产地销地B1B2B3B4A1A2A33113101928741055调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x34产地销地6二、建立模型设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=67单位运价表产销平衡表8一般模型表示(ai=bj)9三、模型的特点1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量0110………10x11x12······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············································································································11关于运输模型的几个结论：(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n-1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路。12初始基可行解新的基可行解最优否？STOPYN3.2运输问题的求解方法：表上作业法单纯形法求解思路13表上作业法步骤:初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。143A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量311310192874105634133656749单位运价表产销平衡表最小元素法15例A1A2B1B215151020产量销量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法16A1A2A3B1B2B3B4749产量销量3656635213A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法产销平衡表17针对最小元素法和vogel法，需要说明的几点：(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；18例A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量273118469431052030251015201050单位运价表产销平衡表10251510019A1A2A3B1B2B3B4A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量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)单位运价表产销平衡表闭回路法20注:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。21A1A2A3B1B1B3B4位势法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)22A1A2A3B1B1B3B4749产量销量36566343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。23注:(1)对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。245例：A1A2A3B1B1B3B4749产量销量3656635213(0)(2)(2)(9)(1)(12)A1A2A3B1B1B3B4749产量销量365663312254(1)A1A2A3B1B2B3B4产量销量632233665659(2)(1)(-1)(10)(12)例：6A1A2A3B1B2B3B4产量销量63033665659226练习A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表27最小元素法A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表15515100028Vogel法A1A2A3B1B2B3B4A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表867792125-6119102-15-6-91013-10510029注:表上作业法适用于下列情形：(1)cij≥0；(2)minz；(3)产销平衡。表上作业法步骤303.3几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题31Minz=cij·xijni=1j=1mm)1,2,...,(i1ainjijxn)1,...,j;m...,1,(i0n),...,1,2(j1xijjmiijbx一、产销不平衡问题1产销(aibj)Minz=cij·xij+0xi,n+1ni=1j=1mm)1,2,...,(i11ainjijx1)nn,1,...,j;m...,1,(i01)nn,,...,1,2(j1xijjmiijbxi=1m32产地销地A1A2┊AmB1B2┈BnC11C12┈C1nC21C22┈C2n┆┊┈┊Cm1Cm2┈CmnBn+1００┆０产＞销问题单位运价表销量产量b1b2┈bna1a2┊amaibj33Minz=cij·xijni=1j=1mm)1,2,...,(i1ainjijxn)1,...,j;m...,1,(i0n),...,1,2(j1xijjmiijbx2销产(bjai)Minz=cij·xij+0xm+1,jni=1j=1m1)mm,1,2,...,(i1ainjijxn)1,...,j;1mm,...,1,(i0n),...,1,2(j11xijjmiijbxj=1n34产地销地A1A2┊AmB1B2┈BnC11C12┈C1nC21C22┈C2n┆┊┈┊Cm1Cm2┈CmnAm+1销＞产问题单位运价表00┈0销量产量b1b2┈bna1a2┊ambjai35例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。AⅠⅡⅢⅣ产量最低需求1613221714131915192023―单位运价表5060503070010单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求507030不限36ABCⅠⅠⅡⅢⅣⅣ16161322171714141319151519192023MMM0M0M0供应需求产量销量506050302070301050产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。37最优方案：需求产地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20103060C3020050D302050销量30207030105038练习AⅠⅡⅢ最高发量467-78单位运价表6040400BC销量708050D最低发量8040不限5054645-39三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。40A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表413.4运输问题的应用42例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ