运筹学胡运权第五版课件(第3章)分析

第三章运输问题TransportationProblem§3.1运输问题的典例和数学模型例某食品公司经营糖果业务，公司下设三个加工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位糖果的运输费用等情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨加工厂门市部B1B2B3B4A1A2A3311310192874105单位：元/吨解：用cij表示从第i个加工厂到第j个门市部的单位糖果的运价，设xij表示第i个加工厂到第j个门市部调运糖果的数量，（i=1，2，3；j=1，2，3，4）则总费用为：minz=cijxij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,3；j=1,2,3,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6s.t.1、运输问题•产地提供物资的地点用A1,A2,…Am表示，或用i=1，2，…,m表示；•销地需要物资的地点用B1,B2,…,Bn表示，或用j=1,2,…,n表示；•产量每个产地提供物资的数量，用a1,a2,…,am表示；•销量每个销地需要物资的数量，用b1,b2,…,bn表示；•单位物资运价从产地i到销地j单位物资的运价为cij一般满足产销平衡：与物资调运有关的问题。2、已知条件11mnijijab已知条件的表格形式单销价地产地产量销量平衡nBB1mAA1maa1nbb1mnmncccc1111产销平衡表单位运价表销地3113101928741052065964A1A2bjB13产地A3aiB2B37B4本例中：,,2,1,,2,10)(,,2,1)(,,2,1..min1111njmixnjbxmiaxtsxczijjmiijnjiijminjijij，，销量约束产量约束对于m产n销运输问题，设xij表示产地i运往销地j的物资数量，则其数学模型如下：3、运输问题的数学模型注：运输问题是特殊的线性规划问题。4、模型的特点已知运输问题有m个产地、n个销地，（1）决策变量的个数：mn（2）约束方程的个数：m+n其中线性独立方程的个数：m+n-1基变量的个数：m+n-1非基变量的个数：m×n-(m+n-1)5、运输问题解的情况运输问题有最优解运输问题有可行解产销平衡§3.2表上作业法初始调运方案的确定是否最优？结束Y调整方案使目标函数值更小N基本原理：2-1初始方案的确定1、最小元素法销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③例用最小元素法确定初始方案。865310334214613Z就近供应————“找便宜”有多少要多少运多少销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③得到初始调运方案表：（1）有数字格（基格）填写了调运量的格子，对应解中的基变量。（用白圈表示）（2）空格未填写调运量的格子，对应解中的非基变量，其对应变量在该方案中取值为0。（用蓝圈表示）在调运方案表中，12个格子分成两类：销地3114577381210620aiB2B37B4A1A2bjB13产地A365964例用最小元素法确定初始方案。注意：在调运方案表中，每次填入一个数字，都在满足供需关系下划去相应的一列或一行。若填入的一个数字既满足产量要求又满足销量要求，则应同时划去这一列和这一行，并在划去的所在列或行的任一个空格内填入一个0，以保持有数字格的总数不变（即基变量的个数不变）。2.沃格尔法（Vogel）销地31131019287410520aiB2B37B4A1A2bjB13产地A3659640110122513⑥2-13③01-2-12③01-2-1-①②⑤85538335461132Z例每行两个最小元素之差每列两个最小元素之差“找大差”注意：由沃格尔法得出的解比最小元素法得出的解更接近最优解。2-2最优性检验与方案的调整1、闭回路的概念在调运方案表中以一个空格和若干个有数字格作为顶点，以及水平、垂直连线围成的封闭回路，称为该空格对应的闭回路。销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③例如分别找出下列空格的闭回路。销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③销地3113101928741052065964A1A2bjB13产地A3aiB2B37B4③④①⑥③③空格（A1,B1）的闭回路销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③⑥③③③④①⑥空格（A2,B2）的闭回路③④①⑥③③③④①⑥③③销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③④①⑥③③空格（A1,B2）的闭回路销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③③④①⑥③空格（A2,B4）的闭回路销地31131019287410520aiB2B37B4A1A2bjB13产地A365964④⑥③③③④①⑥③空格（A3,B1）的闭回路销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③③④①⑥③③空格（A3,B3）的闭回路注意：调运表中每个空格有且只有一个闭回路。2、利用闭回路计算检验数令空格（Ai,Bj）对应的非基变量的值为1，沿着闭回路，相应顶点的基变量的值依次-1，+1，-1，+1…，得到新可行解。将新可行解与原可行解相比，得到的运费变化量称为该空格处的检验数，记做λij。即偶奇ijijijcc例求下列调运方案表中各个空格的检验数。销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③1)31()23(11销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③销地3113101928741052065964A1A2bjB13产地A3aiB2B37B4③④①⑥③③空格（A1,B1）的闭回路表示新方案的费用要增加1元销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③⑥③③③④①⑥空格（A2,B2）的闭回路1)2104()359(22表示新方案的费用要增加1元③④①⑥③③③④①⑥③③销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③④①⑥③③空格（A1,B2）的闭回路2)104()511(12表示新方案的费用要增加2元销地31131019287410520aiB2B37B4A1A2bjB13产地A365964④⑥③③③④①⑥③空格（A3,B1）的闭回路10)135()2107(31表示新方案的费用要增加10元销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③③④①⑥③③空格（A3,B3）的闭回路12)35()1010(33表示新方案的费用要增加12元销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③④①⑥③③③④①⑥③空格（A2,B4）的闭回路1)102()38(24表示新方案的费用要减少1元综上，得到检验数表如下：B1B2B3B4A11200A2010－1A3100120注意：有数字格（基变量）的检验数为0。B1B2B3B4A10200A20210A390120销地31131019287410520aiB2B37B4A1A2bjB13产地A365964⑥③③⑤②①例已知运输问题的调运方案如下，用闭回路法求检验数表。解：检验数表为3、利用检验数表判断最优性解。时，运输问题达到最优当所有最优性判别准则：0ij（1）若有负检验数，则该方案需要改进；（2）若空格的检验数全为正数，则该问题有唯一最优方案；（3）若检验数全非负，且有空格的检验数为0，则该问题有无穷多最优解。在检验数表中，确定绝对值最大的负检验数对应的空格，利用该空格的闭回路在满足供需关系下调整各顶点的运量，得到费用更小的调运方案。4、改进方案的方法------闭回路法例调整方法：销地311310192874105A1A2A3B1产地B2B3B4③④①⑥③③121-11012（1）找出绝对值最大的负检验数对应的闭回路（2）使所对应的空格达到最大的调整量1②⑤①242313141,0,5,2xxxx此时x23=0，可看成非基变量。注：格子右上角数字为单位物资运价，左下角数字为检验数，圆圈内数字为调运物资数量。销地31131019287410520aiB2B37B4A1A2bjB13产地A365964③⑤①⑥③②得到新的调运方案：该方案就是用沃格尔法得到的初始方案。B1B2B3B4A10200A20210A390120其检验数表为故该方案为最优方案，且有无穷多最优方案，Zmin=85元。5、用位势法求检验数（2）计算行位势ui和列位势vj不妨令u1=1，则依cij=ui+vj计算各ui和vj（3）计算空格处位势和ui+vj（4）计算空格处检验数λij=cij-（ui+vj）（1）列一张只含有数字格单位运价cij的表；注意：行位势、列位势可能不唯一，但检验数是相同的。A1A2A3B1B1B3B43101845(3)(9)(7)(-2)(1)(-2)行位势列位势12-1-4289A1A2A3B1B1B3B4311310192874105单位运价表位势表A1A2A3B1B1B3B4749产量销量3656635213调运方案表A1A2A3B1B1B3B40229112检验数表λijB1B2B3B4A10200A20210A390120检验数表：故该方案为最优方案，且该问题有无穷多最优方案。总费用Zmin=85元。2-3小结（1）分析问题，列出产销平衡表和单位运价表。（2）利用最小元素法或沃格尔法求初始调运方案。注：沃格尔法是近似最优解。（3）用闭回路法或位势法求检验数表。注：位势法比较简单。（4）判断最优性若无负检验数，则该方案为最优方案，计算相应的总运费，结束；否则，利用绝对值最大的负检验数对应的闭回路调整方案，并转入（3）。1、表上作业法的前提：产销平衡2、表上作业法的步骤已知某运输问题的资料如下表：B1B2B3B4发量A1265315A2132112A3327413收量1013125表中的发量、收量单位为：吨，运价单位为：元/吨，试求出最优运输方案。练习解：1、用最小元素法求初始方案B1B2B3B4发量A1012315A210212A31313收量1013125用沃格尔法求初始方案B1B2B3B4发量A1100515A21212A301313收量1013125总费用z=107元总费用z=85元B1B2B3B4A15A2251A3102、用位势法求由沃格尔法得到的方案的检验数3、结论：表中无负检验数且有非基变量的检验数为0，本问题有无穷多最优方案。一个最优调运方案为：B1B2B3B4发量A1100515A21212A301313收量1013125综上所述，总费用Zmin=85元。§3.3产销不平衡的运输问题及其应用一、原理njjmiiijjmiijinjijbanjm