第五章运输问题运筹学讲义

Chapter5运输问题与指派问题TransportationandAssignmentProblem,1运输模型TheTransportationmodel2运输问题表上作业法3运输问题网络模型TransportationNetwork4应用实例,物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）,运输问题TheTransportationProblem,如何分析这类问题,1运输问题模型实例ThePj=1,2,3,4),一般运输问题的提法：假设A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的需求量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果a1+a2+am=b1+b2+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡。,解：设xij为从产地Ai运往销地Bj的运输量对于产销平衡问题，可得到下列运输问题的模型：,这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。,该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即Pij=(0,1,0,0,1,0,0)T=ei+em+j,运输问题的特征CharacteristicsofTransportationProblems,运输问题的假定数学模型为：1、需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足2、可行解假定：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解，且有最优解3、成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4、整数解性质：当供应量和需求量都是整数，必存在决策变量均为整数的最优解,运输问题解中非零变量的个数不超过m+n-1个，因为m+n个约束中只有m+n-1个是独立的。基变量在迭代过程中保持为m+n-1个。,用单纯形来求解运输问题，需要加m+n个人工变量，产生一个变量数为mn+m+n的线性规划，求解比较复杂，需要寻求更简便的解法。,2运输问题求解表上作业法,基本步骤初始方案的确定（1）寻找初始方案的方法最小元素法（2）寻找初始方案的方法最大差值法最优解判定位势法非最优方案的改进闭回路调整法多最优解的判断及处理方法,一、初始基本可行解的确定,初始基本可行解的取值要满足下面条件：所得的变量均为非负，且变量总数恰好为m+n1个；得到了一个初始基本可行解。否则，在剩下的运输平衡表中选下一个变量，所有的约束条件均得到满足；,1.最小元素法最小元素法是就近供应，即对单位运价最小的变量分配运输量。假定运价表中cij最小,则分配运量xij,使xij取尽可能大的值xij=Minai,bj。即如果aibj，则取xijbj，删除运价表中第j列，修改剩余产量为aibj。否则若bjai，则取xijai,删除运价表中第i行，修改剩余需求量bjai,上述计算过程可用流程图描述如下,(42),例2(19)设有三座铁矿山Ai（i1，2，3），生产矿石，另有四个炼铁厂Bj（j1，2，3，4）需要矿石，各矿日产量为ai，各厂日需量为bj，以及对应的运价（单位物资的运输费用）为cij，cij由下面产销运价表给出，问：应怎样调运矿石才能使运费最小？P58,0,8,解,b150a242,最小元素法（续）,(30),0,18,(42),a348b230,最小元素法（续）,0,(30),(42),(18),7,b325a318,最小元素法（续）,(30),(42),(18),(7),(8),(45),由此可以得到初始可行解为：x21=42;x32=30;x33=18;x11=8;x14=45;x13=7初始方案的运输费用为：f1=68+127+745+142+130+318=573,2差值法Vogels法,计算运价表各行各列中最小两个运价之差值最小元素法可能导致其他供销点以更高的运费分配运量。次小运费和最小运费的差额越大，说明在该处如果不能以最小运费运送，按次小运费运送的费用将很大，因此次小运费和最小运费的差额为该供应地和需求地的罚数。若罚数的值不大，当不能以最小运费安排运输量时造成的运费损失不大；反之，如果罚数的值很大，不按最小运费安排运输量时造成的运费损失很大。差值法基于这种考虑，先计算所有行和列次小运费和最小运费的差值（称为行差值和列差值），找出最大的差值，然后根据其所在的行或列的最小运费来确定运量的分配。,差值法例P58,8,(42),b150a248,增加行差值和列差值,行差值,列差值,1,0,2,4,2,3,3,0,差值法例P58,23,(42),a348b325,增加行差值和列差值,行差值,列差值,1,2,1,8,9,3,0,(25),差值法例P58,7,(42),b230a323,增加行差值和列差值,行差值,列差值,1,3,1,8,3,0,(23),(25),(8),(7),(45),差值法例P58,(42),(23),(25),(8),(7),(45),由此可以得到初始可行解为：x11=8;x12=7；x14=45;x21=42;x32=23;x33=25;初始方案的运输费用为：f1=68+97+745+142+123+325=566,当我们取定xij的值之后，会出现Ai的产量与Bj的需求量都改为零的情况，这时应同时划去Ai行与Bj列。既在划去xij对应一行（列），填上一个数时，也应划去xij对应列（行），在任意被划去除xij以外任一格内填上0，这时出现退化解。,(30),0,0,(42),a330b230,(0),最优解的判别位势法也称对偶变量法,设,分别表示前m个约束等式相应的对偶变量，,分别表示后n个约束等式相应的对偶变量，既有对偶变量向量,符号不确定,对偶,线性规划问题变量的检验数，,最优解的判别位势法也称对偶变量法,所谓位势法，我们对运输表上的每一行赋予一个数值，分别表示前m个约束等式相应的对偶变量，对每一列赋予一个数值分别表示后n个约束等式相应的对偶变量，则变量xij的检验数它们的数值是由基变量xij的检验数所决定的，由于基变量为m+n-1个，而需要确定的值为m+n个，因此，首先令基变量最多那行的，从而可以根据基格确定所有的值。非基变量xij的检验数就可以用公式求出。如果非基变量xij的检验数：，则运输问题的当前分配方案为最优解，如果同时有某个非基格的检验数，则有无穷多最优解。否则，如果存在，需要（采用闭回路法）继续调整，寻找更好的解。下面以差值法得到的初始解（见PPT20）为例进行讨论,位势法进行最优解的判别,行位势ui,列位势vj,(42),(23),(25),(8),(7),(45),0,8,c116=u3v1;取u1=0,v16,c211=u2v1(6);u25,c129=u1(0)v2;c147=u3v4;v2=9,c333=u3(8)v3;v311,v47,6,9,7,5,c321=u3v2(9);8,11,计算非基变量的检验数,行位势ui,列位势vj,(42),(23),(25),(8),(7),(45),0,8,13c13u1v3=12011=1;,6,9,7,5,11,22c22u2v2=3(5)9=1,1,1,31c31u3v1=5(8)6=7;,7,23c23u2v3=6(5)11=0,0,24c24u2v4=1(5)7=1,1,34c34u3v4=4(8)7=5,5,最优解的判别闭回路法,对于每个非基变量单元格的检验数可以用闭回路法求得具体步骤如下：,(1)找闭回路：以每一个非基变量的单元格为起始顶点，以基变量的格为顶点，用水平和垂直线构造闭回路。这样的闭回路惟一,(2)对于找到的闭回路，起点格编号为1，对其它格以此编号,计算检验数：将所有奇数格的单位运价相加减去偶数格的单位运价，即得到非基变量的单元格的检验数。例如上例中,非最优方案的改进闭回路调整法,当存在有非基变量单元格的检验数时可以用闭回路法对解进行改进，具体步骤如下：,(1)找闭回路：以最小的负检验数对应非基变量的单元格为起始顶点，以基变量的格为顶点，用水平和垂直线构造闭回路。这样的闭回路惟一,(2)求调整量：闭回路上偶数次顶点运量的最小值为调整量，记作：,(3)调整：闭回路上的偶数次顶点的调运量减去；闭回路上的奇数次顶点的调运量加上；非闭回路顶点的其他变量调运量不变；再去掉闭回路上的一个零运量。,计算非基变量的检验数,行位势ui,列位势vj,(42),(23),(25),(8),(7),(45),0,8,6,9,7,5,11,1,1,7,0,1,调整量为闭回路所有偶数格中最小调运量：,5,调整，解的改进,行位势ui,列位势vj,(42),(23),(25),(8),(7),(45),0,8,6,9,7,5,11,1,1,7,0,1,闭回路中奇数格中调运量加42，偶数格调运量中减去42，得到运输问题的一个新的解：,5,(42),(3),(50),新的解和非基变量检验数,行位势ui,列位势vj,(42),(23),(25),(50),(7),(3),0,8,c116=u3v1;取u1=0,v16,c241=u2v4(7);u26,c129=u1(0)v2;c147=u3v4;v2=9,c333=u3(8)v3;v311,v47,6,9,7,6,c321=u3v2(9);8,11,1,1,0,1,7,5,最优解所有非基变量检验数均0,(42),(23),(25),(50),(7),(3),由此可以得到初始可行解为：x11=50;x12=7；x14=3;x24=42;x32=23;x33=25;初始方案的运输费用为：f*=650+97+73+142+123+325=524由于非基变量的检验数为0，有多最优解,各种运输问题变体：1）有时目标函数求最大。如求利润最大或营业额最大等；我们只需要将最小元素法改为最大元素法求初始解，判断是否所有的检验数当满足时，所得解为最优解，否则选最大检验数对应格为入基格求解2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)。如果不存在运输线路，则在运价表相应的格子中填上运价M（充分大正数）3）产销不平衡时，若产量大于需求量可增加一个虚拟的需求地，其需求量等于aibj，运价表中相应行的运价均为0；同样可用表上作业法求解若需求量产量大于产量，可增加一个虚拟的产地，其产量等于bjai，运价表中相应列的运价均为04）一个销地同时存在着最小需求和最大需求,例3（见书P64例21）已知一产销运价表如下所示，试求解最优运输方案。增加假想销地B5（实际上就是就地库存多余的产品），B5的销售量为（产量500）（销量440）60，因为是就地库存，所以所有产地到B5的运费均为0，由此得新的产销平衡运价表如下：,用表上作业法进行求解再删去假想销地所对应的变量（即x15、x25、x35）得最优方案为：x14120,x2220,x23130,x3180,x3270,x3420；其余xij0。最优运费为：f*=5250。注：求解可作为练习。,例4某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问应如何调运可使总运输费用最小？解：总产量为78+45=123；总销量为53+36+25=114。产销不平衡，增加一个虚设的销地，得到下表,计算过程如下：,15,36,0,9,1,11,11,45,25,7,16,12,2,行差值,列差值,以上运输方案已为最优方案,对于产大于销问题，可得到下列运输问题的模型：,当需求大于产量时，则需求地的需求不能全部满足，只能满足最低需求。如需求地Bj的最低需求为b0，则约束为：,对于销大于产问题，运输问题的模型约束变为：,3TransportationNetwork运输问题的网络表示,例5下表为运输问题的单位运价表和产量和需求量数据,TransportationNetwork运输问题的网络表示,每一个节点建立一个约束方程，目标函数为每一条箭线上的决策变量xij乘以单位运价cij之和,2,3,2,1,3,4,1,a2=27,a3=19,b1=22,b2=13,b3=12,b4=13,a1=14,供应量,sources,运价,需求量,Destinations需求地,6,7,5,3,8,4,2,7,5,9,10,6,x11,x12,x13,x14,A1,A2,A3,B1,B2,B3,B4,supplies,demands,供应地约束,需求地约束,LPModelofTransportationProblem运输问题线性规划模型,3网络模型的应用,转运问题：在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。产地为物质供应点，所有从产地运出的运量等于产量转运站为中间点，满足运量守衡，运入中间点的运量等于运出量需求地为接收点，运往需求地的运量等于需求量下面网络图表示两个供应点，三个中间点，两个需求点的运输问题和模型,运输网络,2,3,4,5,6,7,1,c14,c23,c24,c25,c15,s1,c36,c37,c46,c47,c56,c57,d1,d2,中间点Intermediatenodes,供应地Sources,需求地destinations,s2,需求量,供应量,c13,设xij表示从节点i到节点j的运输量Mincijxijijs.t.xij0对于所有i和j,线性规划模型,转运问题例,例6、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中产地：1-广州、2-大连、转运站3-上海、4-天津、销地：5-南京、6-济南、7-南昌、8-青岛,解：设xij为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量对转运站（中转点）：输入量-输出量=0对销地（收点）j：输入量-输出量=销量例8（续）目标函数：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48约束条件：s.t.x13+x14600(广州分厂供应量限制）x23+x24+x28400(大连分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）x35+x45=200（南京的销量）x36+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）xij0,i,j=1,2,3,4,5,6,7,8,用软件求得结果：x13=550；x14=50；x23=0；x24=100；x28=300；x35=200；x36=0；x37=350；x38=0；x45=0；x46=150 x47=0；x48=0,用Excel求解上述运输问题,转运问题产地、销地及中转站的有关数据、运价(百元/吨)表,A1和A2流出量总和为16吨，需求总和16吨,转运问题产地、销地及中转站的运价表,对中转点来说T1和T2，流入量=流出量=16,补充习题,某公司从三个产地A1、A2、A3将物品运往四个销地甲、乙、丙和丁，各产地的产量、各销地的销量和各产地运往各销地每件物品的单位运费如下表，问：应如何调运可使总运输费用最小？,4应用实例求佳公司分配工厂生产产品P199,求佳公司用3个有多余生产能力的工厂生产4种新产品，3个工厂的多余生产能力和4种产品的需求量以及每种产品在不同工厂的单位产品生产成本如下,Question:哪个工厂应生产何种产品及数量,电子表格模型,数学模型MinimizeCost=41x11+27x12+28x13+24x14+40 x21+29x22+23x24+37x31+30 x32+27x33+21x34S.T.工厂1：x11+x12x13+x1475工厂2:x21+x22+x23+x2475工厂3:x31+x32+x33+x3445产品1需求:x11+x21+x31=20产品2需求:x12+x22+x32=30产品3需求:x13+x23+x33=30产品4需求:x14+x24+x34=30 xij0(i=1,2,3;j=1,2,3,4),耐芙迪公司选择顾客NiftyCompanyP201,顾客1为最好顾客，需求必须满足，顾客2、3也是重要顾客，最低需满足其订单的1/3，顾客4的订单可以不考虑，问，在满足上述要求的前提下，需向每一位顾客供应多少产品数量，可使总利润最大?,电子表格模型P200,7000x11+x21+x3170003000x12+x22+x3290003000x13+x23+x336000 x14+x24+x348000,SUM（C11：F11）,一个获奖的应用宝洁公司重新设计制造和配送体系DistributionSystematProctorandGambleP197,ProctorandGambleneededtoconsolidate合并andre-designtheirNorthAmericandistributionsystemintheearly1990s.50productcategories50多个产品类别60plants60个工厂15distributioncenters15个配送中心1000customerzones超过1000个的顾客群体Solvedmanytransportationproblems(oneforeachproductcategory).Goal:findbestdistributionplan,whichplantstokeepopen,etc.Closedmanyplantsanddistributioncenters,andoptimizedtheirproductsourcinganddistributionlocation.工厂减少20%Implementedin1996.Saved$200millionperyear.Formoredetails,see1997Jan-FebInterfacesarticle,“BlendingOR/MS,Judgement,andGIS:RestructuringP&GsSupplyChain”,MetroWater米德罗水资源(DistributingNaturalResources),MetroWaterDistrictisanagencythatadministerswaterdistributioninalargegeographicregion.Theregionisarid干旱,sowatermustbebroughtinfromoutsidetheregion.Sourcesofimportedwater:克伦坡河Colombo,塞克隆Sacron,and卡路里Calorierivers.水源来自三条河Maincustomers:CitiesofBerdoo,LosDevils,SanGo,andHollyglass.供应四个城市,Question:从每条河流中引进多少水，在满足需求的前提下，使总成本最少,布都,洛斯戴维斯,圣哥,豪利格拉斯,P203,SpreadsheetFormulation,布都,洛斯戴维斯,圣哥,豪利格拉斯,克伦坡,塞克隆,卡路里,北方飞机公司NorthernAirplane(ProductionScheduling),北方飞机公司生产商业飞机，其中最重要的步骤是生产飞机发动机NorthernAirplaneCompanyproducescommercialairplanes.Thelaststageinproductionistoproducethejetenginesandinstallthem.公司必须满足第2列发动机安装量incolumn2.Productionandstoragecostsvaryfrommonthtomonth.,Question:制定一个生产计划，每月生产发动机的数量，使制造和存储成本最小Howmanyenginesshouldbeproducedineachofthefourmonthssothatthetotaloftheproductionandstoragecostswillbeminimized?,P205,SpreadsheetFormulation,最优生产计划OptimalProductionatNorthernAirplane,1月份生产20个发动机,其中当月装配10个,5个在2月份装配,另5个在4月份装配,2月份正常生产10个，用于当月装配，3月份正常生产25个，当月装配，3月加班生产10个用于4月分装配，4月正常生产5个用于当月装配。,米德尔城学生区域划分MiddletownSchoolDistrict,Middletown米德尔城SchoolDistrictis开办openingathirdhighschoolandthusneedstoredraw需要重新规划theboundariesfortheareaofthecitythatwillbeassignedtotherespectiveschools.Thecityhasbeendividedinto9tracts区域withapproximatelyequalpopulations.Eachschoolhasaminimumandmaximumnumberofstudentsthatshouldbeassigned.Theschooldistrictmanagementhasdecidedthattheappropriateobjectiveistominimizetheaveragedistancethatstudentsmusttraveltoschool.Question:Howmanystudentsfromeachtractshouldbea