《运输与指派模型问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《运输与指派模型问题精品文稿.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运输与指派模型问题2022/10/241第1页，本讲稿共30页7.1 运输模型运输模型 Mathematical Model of Transportation Problems第2页，本讲稿共30页人们在从事生产活动中，不可避人们在从事生产活动中，不可避免地要进行物资调运工作。如某免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要粮食等各类物资，分别运到需要这些物资的地区，根据各地的这些物资的地区，根据各地的生生产量产量和和需要量需要量及各地之间的及各地之间的运输费运输费用用，如何制定一个运输方案，使总，如何制定一个运输方案，使总
2、的运输费用最小。这样的问题称为的运输费用最小。这样的问题称为运输问题运输问题。7.1 运输模型运输模型 Model of Transportation Problems7.1.1 数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图7.12022/10/243第3页，本讲稿共30页【例例7.1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别为粮食分别为10，8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为四个地区，其需要量分别为5，7，8，3（万吨）。
3、产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表71所示所示.问问如何安排一个运输计划，使总的运输费用最少。如何安排一个运输计划，使总的运输费用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表712022/10/244第4页，本讲稿共30页设设 xij(i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，则运输费用为：则运输费用为：地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A34129
4、5需要量需要量5783232022/10/245第5页，本讲稿共30页地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323从产粮区运出去的量从产粮区运出去的量2022/10/246第6页，本讲稿共30页运给运给需求地的量需求地的量地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量5783232022/10/247第7页，本讲稿共30页运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：2022/10/24
5、8第8页，本讲稿共30页 有些问题表面上与运输问题没有多大关系，也可以建立与运输问题有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型形式相同的数学模型【例例7.2】有三台机床加工三种零件，有三台机床加工三种零件，计划第计划第i台的生产任务为台的生产任务为a i (i=1,2,3)个零件个零件(三种零件三种零件)，第第 j 种零件的需要量为种零件的需要量为 bj (j=1,2,3)，第第 i 台机床加工第台机床加工第j种零件需要的时间为种零件需要的时间为 cij，如下表所示。如下表所示。问如何安排生产任务使总的加工时间最少？问如何安排生产任务使总的加工时间最少？零件零
6、件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量7030501502022/10/249第9页，本讲稿共30页 【解解】设设 xi j (i=1,2,3；j=1,2,3,)为第为第 i 台机床加工第台机床加工第 j 种零件的数种零件的数量，量，零件零件机床机床B1B2B3生产生产任务任务A152350A264160A373440需要需要量量703050150则总的加工时间为则总的加工时间为2022/10/2410第10页，本讲稿共30页则此问题的数学模型为则此问题的数学模型为2022/10/2411第11页，本讲稿共30页运输问题的一般数学模型运输问
7、题的一般数学模型设有设有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个销地的运量，个销地的运量，则数学模型为：则数学模型
8、为：2022/10/2412第12页，本讲稿共30页则数学模型为：则数学模型为：2022/10/2413第13页，本讲稿共30页设数学模型为设数学模型为 7.1.2最大值问题最大值问题2022/10/2414第14页，本讲稿共30页第一种方法：第一种方法：将极大化问题转化为极小化问题。将极大化问题转化为极小化问题。设极大化问题的运价表为设极大化问题的运价表为C=（Cij）mn，用一个较大的数，用一个较大的数M（MmaxCij）去减每一个）去减每一个Cij得到矩阵得到矩阵C=（Cij）mn，其中，其中C/ij=MCij0,将将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为作为极
9、小化问题的运价表，用表上用业法求出最优解，目标函数值为 2022/10/2415第15页，本讲稿共30页 当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在实际中常常这类运输问题在实际中常常碰到碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时当产大于销时,即即 7.1.3 不平衡运输问题不平衡运输问题 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量100100802022/10/2416第16页，本讲稿共30页
10、1.当产大于销时当产大于销时 数学模型为数学模型为 即即2022/10/2417第17页，本讲稿共30页由于总产量大于总销量，由于总产量大于总销量，必有部分产地的产量不能全部必有部分产地的产量不能全部运送完运送完，必须就地库存，即每个产地设一个仓库，库存量，必须就地库存，即每个产地设一个仓库，库存量为为xi，n+1（i=1，2，m），总的库存量为），总的库存量为 2022/10/2418第18页，本讲稿共30页bn+1作为一个作为一个虚设的销地虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：）。
11、则平衡问题的数学模型为：具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可2022/10/2419第19页，本讲稿共30页2.当销大于产时当销大于产时,即即 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量2001001502022/10/2420第20页，本讲稿共30页2.当销大于产时当销大于产时,即即数学模型为数学模型为 2022/10/2421第21页，本讲稿共30页由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时这时
12、虚设一个虚设一个产地产地Am+1，产量为，产量为 xm+1,j 是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运的运价为零价为零,即即Cm+1,j=0(j=1,2,n)2022/10/2422第22页，本讲稿共30页销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为，运价为零。产量为am+1即可。即可。2022/10/2423第23页，本讲稿共30页上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要
13、量是的需要量是50到到70，试求极，试求极小化问题的最优解。小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502107.1.4需求量不确定的运输问题需求量不确定的运输问题2022/10/2424第24页，本讲稿共30页先作如下分析：先作如下分析：（1）总产量为总产量为180，B1，B4的最低需求量的最低需求量 20+50+35+45=150 180，这时属这时属销大于产销大于产;B1B2B3B4aiA1592360A2-47840A3364230A448101150bj206050703545180
14、1502102022/10/2425第25页，本讲稿共30页（3）虚设一个产地虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供应的产量只能供应B1或或B2。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502102022/10/2426第26页，本讲稿共30页（4）将将B1与与B2各分成两部分各分成两部分 的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此 必须由必须由A1，A4供应，供应，可由可由 A1、A5供应。供应。B3B4aiA1559
15、92360A2MM447840A333664230A44488101150A5M0M0MM30bj2040502035452102022/10/2427第27页，本讲稿共30页（5）上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到 、的运价为的运价为零。得到下表的产销平衡表。零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj2040502035452102022/10/2428第28页，本讲稿共30页7.1.5中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地34132022/10/2429第29页，本讲稿共30页设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题的数则中转运输问题的数学模型为学模型为 产大于销时将式产大于销时将式(5.3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5.3c)改为改为“”约束约束 2022/10/2430第30页，本讲稿共30页