运输与指派模型问题

运筹学OperationsResearchChapter7运输与指派问题Transportation

andAssignmentProblem7.1运输模型

MathematicalModelofTransportationProblems7.2运输单纯形法TransportationSimplexMethod7.3运输模型的应用

Aplicationof

TransportationModel7.4

指派问题Assignmentproblem

3/2/20231运输与指派模型问题共30页，您现在浏览的是第1页!7.1运输模型

MathematicalModelofTransportationProblems3/2/20232运输与指派模型问题共30页，您现在浏览的是第2页!人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。7.1运输模型

ModelofTransportationProblems7.1.1数学模型产地销地A110A2

8A35B43B38B27B15354231682329图7.13/2/20233运输与指派模型问题共30页，您现在浏览的是第3页!设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，则运输费用为：地区产粮区B1B2B3B4产量A1326310A253828A341295需要量5783233/2/20234运输与指派模型问题共30页，您现在浏览的是第4页!运给需求地的量地区产粮区B1B2B3B4产量A1326310A253828A341295需要量5783233/2/20235运输与指派模型问题共30页，您现在浏览的是第5页!

有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型【例7.2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件(三种零件)，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如下表所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量7030501503/2/20236运输与指派模型问题共30页，您现在浏览的是第6页!则此问题的数学模型为3/2/20237运输与指派模型问题共30页，您现在浏览的是第7页!则数学模型为：3/2/20238运输与指派模型问题共30页，您现在浏览的是第8页!种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C′=（C′ij）m×n，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为3/2/20239运输与指派模型问题共30页，您现在浏览的是第9页!1.当产大于销时数学模型为即3/2/202310运输与指派模型问题共30页，您现在浏览的是第10页!bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可3/2/202311运输与指派模型问题共30页，您现在浏览的是第11页!2.当销大于产时,即数学模型为3/2/202312运输与指派模型问题共30页，您现在浏览的是第12页!销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。3/2/202313运输与指派模型问题共30页，您现在浏览的是第13页!先作如下分析：

（1）总产量为180，B1，…，B4的最低需求量20+50+35+45=150<180，这时属产大于销；（2）B1，…，B4的最高需求是60+70+35+45=210>180，这时属销大于产;B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/2/202314运输与指派模型问题共30页，您现在浏览的是第14页!（4）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj2040502035452103/2/202315运输与指派模型问题共30页，您现在浏览的是第15页!7.1.5中转问题产地销地

A120A230A350A920A815A720A645354231682329图5.2A4A522715中转地34133/2/202316运输与指派模型问题共30页，您现在浏览的是第16页!【例7.1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表7－1所示.问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表7－13/2/202317运输与指派模型问题共30页，您现在浏览的是第17页!地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323从产粮区运出去的量3/2/202318运输与指派模型问题共30页，您现在浏览的是第18页!运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：3/2/202319运输与指派模型问题共30页，您现在浏览的是第19页!

【解】设xij

(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，零件机床B1B2B3生产任务A152350A264160A373440需要量703050150则总的加工时间为3/2/202320运输与指派模型问题共30页，您现在浏览的是第20页!运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即

。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：3/2/202321运输与指派模型问题共30页，您现在浏览的是第21页!设数学模型为

7.1.2最大值问题3/2/202322运输与指派模型问题共30页，您现在浏览的是第22页!

当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即7.1.3不平衡运输问题

BjAiB1B2B3产量A1659120

A212107100A3698130销量100100803/2/202323运输与指派模型问题共30页，您现在浏览的是第23页!由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为3/2/202324运输与指派模型问题共30页，您现在浏览的是第24页!2.当销大于产时,即

BjAiB1B2B3产量A1659120

A212107100A3698130销量2001001503/2/202325运输与指派模型问题共30页，您现在浏览的是第25页!由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)3/2/202326运输与指派模型问题共30页，您现在浏览的是第26页!上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2107.1.4需求量不确定的运输问题3/2/202327运输与指派模型问题共30页，您现在浏览的是第27页!（3）虚设一个产地A5，产量是210－180=30，A5的产量只能供应B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/2/202328运输与指派模型问题共30页，您现在浏览的是第28页!（5）上述A5不能供应某需求地的运价用大M表示，A5到、的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM4