运输与指派模型问题

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

andAssignmentProblem7.1运输模型

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

Aplicationof

TransportationModel7.4

指派问题Assignmentproblem

7.1运输模型

MathematicalModelofTransportationProblems02九月20233人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。7.1运输模型

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

8A35B43B38B27B15354231682329图7.102九月20234【例7.1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表7－1所示.问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表7－102九月20235设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，则运输费用为：地区产粮区B1B2B3B4产量A1326310A253828A341295需要量57832302九月20236地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323从产粮区运出去的量02九月20237运给需求地的量地区产粮区B1B2B3B4产量A1326310A253828A341295需要量57832302九月20238运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：02九月20239

有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型【例7.2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件(三种零件)，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如下表所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量70305015002九月202310

【解】设xij

(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，零件机床B1B2B3生产任务A152350A264160A373440需要量703050150则总的加工时间为02九月202311则此问题的数学模型为02九月202312运输问题的一般数学模型设有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个销地的运量，则数学模型为：02九月202313则数学模型为：02九月202314设数学模型为

7.1.2最大值问题02九月202315第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C′=（C′ij）m×n

，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为02九月202316

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

BjAiB1B2B3产量A1659120

A212107100A3698130销量1001008002九月2023171.当产大于销时数学模型为即02九月202318由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为02九月202319bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可02九月2023202.当销大于产时,即

BjAiB1B2B3产量A1659120

A212107100A3698130销量20010015002九月2023212.当销大于产时,即数学模型为02九月202322由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)02九月202323销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。02九月202324上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2107.1.4需求量不确定的运输问题02九月202325先作如下分析：

（1）总产量为180，B1，…，B4的最低需求量

20+50+35+45=150<180，这时属产大于销；

（2）B1，…，B4的最高需求是60+70+35+45=210>180，这时属销大于产;B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～21002九月202326（3）虚设一个产地A5，产量是210－180=30，

A5的产量只能供应B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～21002九月202327（4）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521002九月202328（5）上述A5不能供应某需求地的运价用大M表示，A5到、的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521002九月2023297.1.5中转问题产地销地

A120A230