运输与指派模型问题.ppt

《运输与指派模型问题.ppt》由会员分享，可在线阅读，更多相关《运输与指派模型问题.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学运筹学OperationsResearchChapter7运输与指派问题运输与指派问题TransportationandAssignmentProblem7.1运输模型运输模型MathematicalModelofTransportationProblems7.2运输单纯形法运输单纯形法TransportationSimplexMethod7.3运输模型的应用运输模型的应用AplicationofTransportationModel7.4指派问题指派问题Assignmentproblem12/6/202217.1运输模型运输模型MathematicalModelofTransporta

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

3、s7.1.1数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图7.112/6/20223【例例7.1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应粮食分别为粮食分别为10，8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表71所示所示.问如何安排一个运输计划，使总的运输费用问如何安排一个运输计划，使总的运输费用最少。最少。地区地区产粮区产

4、粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表7112/6/20224设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，则运输费用为：则运输费用为：地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量57832312/6/20225地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323从产粮区运出去的量从产粮区运出去的量12/6/20226运给运

5、给需求地需求地的量的量地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量57832312/6/20227运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：12/6/20228有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型【例例7.2】有三台机床加工三种零件，有三台机床加工三种零件，计划第计划第i台的生产任务为台的生产任务为a i(i=1,2,3)个零件个零件(

6、三种零件三种零件)，第第j 种零件的需要量为种零件的需要量为bj (j=1,2,3)，第第i 台机床加工第台机床加工第j种零件需要的时间为种零件需要的时间为cij，如下表所示。如下表所示。问如何安排生产任务使总的加工时间最少？问如何安排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量70305015012/6/20229【解解】设设xi j (i=1,2,3；j=1,2,3,)为第为第i 台机床加工第台机床加工第j 种零种零件的数量，件的数量，零件零件机床机床B1B2B3生产生产任务任务A152350A264160A

7、373440需要需要量量703050150则总的加工时间为则总的加工时间为12/6/202210则此问题的数学模型为则此问题的数学模型为12/6/202211运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），），生产某种物资，其产生产某种物资，其产量分别为量分别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且且产销平衡产销平衡，即，即。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij，在满足各地需要的前提在满足各地需要的前提下，求总运输费用最

8、小的调运方案。下，求总运输费用最小的调运方案。设设xij (i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运个销地的运量，则数学模型为：量，则数学模型为：12/6/202212则数学模型为：则数学模型为：12/6/202213设数学模型为设数学模型为7.1.2最大值问题最大值问题12/6/202214第一种方法：第一种方法：将极大化问题转化为极小化问题。将极大化问题转化为极小化问题。设极大化问题的运价表为设极大化问题的运价表为C=（Cij）mn，用一个较大的数用一个较大的数M（MmaxCij）去减每一个）去减每一个Cij得到矩阵得到矩阵C=（Cij）mn，其中其中C

9、/ij=MCij0,将将C/作为极小化问题的运价表，用表上用业法求出最优解，作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为目标函数值为12/6/202215当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在这类运输问题在实际中常常碰到实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。平衡问题求解。1.当产大于销时当产大于销时,即即7.1.3不平衡运输问题不平衡运输问题 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量10

10、01008012/6/2022161.当产大于销时当产大于销时数学模型为数学模型为即即12/6/202217由于总产量大于总销量，由于总产量大于总销量，必有部分产地的产量不能全部必有部分产地的产量不能全部运送完运送完，必须就地库存，即每个产地设一个仓库，库存量，必须就地库存，即每个产地设一个仓库，库存量为为xi，n+1（i=1，2，m），），总的库存量为总的库存量为12/6/202218bn+1作为一个作为一个虚设的销地虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，的运价为零，即即Ci，n+1=0,（i=1，m）。）。则平衡问题的数学模型为：则平衡问题的数学模型为：

11、具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零运价为零,销量为销量为bn+1即可即可12/6/2022192.当销大于产时当销大于产时,即即 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量20010015012/6/2022202.当销大于产时当销大于产时,即即数学模型为数学模型为12/6/202221由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时这时虚虚设一个产地设一个产地Am+1，产量为产量为xm+1,j是是Am+1运到运到Bj的运量，也是的运量，也是

12、Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2,n)12/6/202222销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产运价为零。产量为量为am+1即可。即可。12/6/202223上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极小化问题的最优解。，试求极小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150

13、bj2060507035451801502107.1.4需求量不确定的运输问题需求量不确定的运输问题12/6/202224先作如下分析：先作如下分析：（1）总产量为总产量为180，B1，B4的最低需求量的最低需求量20+50+35+45=150180，这时属这时属销大于产销大于产;B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20605070354518015021012/6/202225（3）虚设一个产地虚设一个产地A5，产量是产量是210180=30，A5的产量只能供应的产量只能供应B1或或B2。B1B2B3B4aiA1592360A2-478

14、40A3364230A448101150bj20605070354518015021012/6/202226（4）将将B1与与B2各分成两部分各分成两部分的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此必须由必须由A1，A4供应，供应，可由可由A1、A5供应。供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521012/6/202227（5）上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到、的运价为零。

15、得到下表的产销平衡表。的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521012/6/2022287.1.5中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地341312/6/202229设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题则中转运输问题的数学模型为的数学模型为产大于销时将式产大于销时将式(5.3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5.3c)改为改为“”约束约束12/6/202230