运输与指派模型问题.pptx

运筹学运筹学OperationsResearchChapter7运输与指派问题运输与指派问题TransportationandAssignmentProblem7.1运输模型运输模型MathematicalModelofTransportationProblems7.2运输单纯形法运输单纯形法TransportationSimplexMethod7.3运输模型的应用运输模型的应用AplicationofTransportationModel7.4指派问题指派问题Assignmentproblem7.1运输模型运输模型MathematicalModelofTransportationProblems26 三月 20243人们在从事生产活动中，不可人们在从事生产活动中，不可避免地要进行物资调运工作。避免地要进行物资调运工作。如某时期内将生产基地的煤、如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别钢铁、粮食等各类物资，分别运到需要这些物资的地区，根运到需要这些物资的地区，根据各地的据各地的生产量生产量和和需要量需要量及各及各地之间的地之间的运输费用运输费用，如何制定，如何制定一个运输方案，使总的运输费一个运输方案，使总的运输费用最小。这样的问题称为用最小。这样的问题称为运运输问题输问题。7.1运输模型运输模型ModelofTransportationProblems7.1.1数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图7.126 三月 20244【例例7.1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应粮食分别为粮食分别为10，8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表71所示所示.问如何安排一个运输计划，使总的运输费用问如何安排一个运输计划，使总的运输费用最少。最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表7126 三月 20245设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，则运输费用为：则运输费用为：地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量57832326 三月 20246地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323从产粮区运出去的量从产粮区运出去的量26 三月 20247运给运给需求地需求地的量的量地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量57832326 三月 20248运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：26 三月 20249有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型【例例7.2】有三台机床加工三种零件，有三台机床加工三种零件，计划第计划第i台的生产任务为台的生产任务为a i(i=1,2,3)个零件个零件(三种零件三种零件)，第第j 种零件的需要量为种零件的需要量为bj (j=1,2,3)，第第i 台机床加工第台机床加工第j种零件需要的时间为种零件需要的时间为cij，如下表所示。如下表所示。问如何安排生产任务使总的加工时间最少？问如何安排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量70305015026 三月 202410【解解】设设xi j (i=1,2,3；j=1,2,3,)为第为第i 台机床加工第台机床加工第j 种零件种零件的数量，的数量，零件零件机床机床B1B2B3生产生产任务任务A152350A264160A373440需要需要量量703050150则总的加工时间为则总的加工时间为26 三月 202411则此问题的数学模型为则此问题的数学模型为26 三月 202412运输问题的一般数学模型运输问题的一般数学模型设有设有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个销地的运量，个销地的运量，则数学模型为：则数学模型为：26 三月 202413则数学模型为：则数学模型为：26 三月 202414设数学模型为设数学模型为7.1.2最大值问题最大值问题26 三月 202415第一种方法：第一种方法：将极大化问题转化为极小化问题。将极大化问题转化为极小化问题。设极大化问题的运价表为设极大化问题的运价表为C=（Cij）mn，用一个较大的数，用一个较大的数M（MmaxCij）去减每一个）去减每一个Cij得到矩阵得到矩阵C=（Cij）mn，其中，其中C/ij=MCij0,将将C/作为极小化问题的运价表，用表上用业法求出最优解，作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为目标函数值为26 三月 202416当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在这类运输问题在实际中常常碰到实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。衡问题求解。1.当产大于销时当产大于销时,即即7.1.3不平衡运输问题不平衡运输问题 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量1001008026 三月 2024171.当产大于销时当产大于销时数学模型为数学模型为即即26 三月 202418由于总产量大于总销量，由于总产量大于总销量，必有部分产地的产量不能全部必有部分产地的产量不能全部运送完运送完，必须就地库存，即每个产地设一个仓库，库存量，必须就地库存，即每个产地设一个仓库，库存量为为xi，n+1（i=1，2，m），总的库存量为），总的库存量为26 三月 202419bn+1作为一个作为一个虚设的销地虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，的运价为零，即即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可26 三月 2024202.当销大于产时当销大于产时,即即 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量20010015026 三月 2024212.当销大于产时当销大于产时,即即数学模型为数学模型为26 三月 202422由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时这时虚设虚设一个产地一个产地Am+1，产量为，产量为xm+1,j是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2,n)26 三月 202423销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。26 三月 202424上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极小化问题的最优解。，试求极小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502107.1.4需求量不确定的运输问题需求量不确定的运输问题26 三月 202425先作如下分析：先作如下分析：（1）总产量为总产量为180，B1，B4的最低需求量的最低需求量20+50+35+45=150180，这时属这时属销大于产销大于产;B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20605070354518015021026 三月 202426（3）虚设一个产地虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供应的产量只能供应B1或或B2。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20605070354518015021026 三月 202427（4）将将B1与与B2各分成两部分各分成两部分的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此必须由必须由A1，A4供应，供应，可由可由A1、A5供应。供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521026 三月 202428（5）上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到、的运价为零。得到下表的产销平衡表。的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521026 三月 2024297.1.5中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地341326 三月 202430设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题则中转运输问题的数学模型为的数学模型为产大于销时将式产大于销时将式(5.3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5.3c)改为改为“”约束约束