运输与指派模型问题幻灯片.ppt

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

1、运输与指派模型问题2023/4/161第1页，共30页，编辑于2022年，星期三7.1 运输模型运输模型 Mathematical Model of Transportation Problems第2页，共30页，编辑于2022年，星期三人们在从事生产活动中，不可避人们在从事生产活动中，不可避免地要进行物资调运工作。如某免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要粮食等各类物资，分别运到需要这些物资的地区，根据各地的这些物资的地区，根据各地的生生产量产量和和需要量需要量及各地之间的及各地之间的运输运输费用费用，如何制定一个运输

2、方案，如何制定一个运输方案，使总的运输费用最小。这样的问使总的运输费用最小。这样的问题称为题称为运输问题运输问题。7.1 运输模型运输模型 Model of Transportation Problems7.1.1 数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图7.12023/4/163第3页，共30页，编辑于2022年，星期三【例例7.1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别为粮食分别为10，8，5（万（万吨），现将粮食运往吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量

3、分别为四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表71所示所示.问如问如何安排一个运输计划，使总的运输费用最少。何安排一个运输计划，使总的运输费用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表712023/4/164第4页，共30页，编辑于2022年，星期三设设 xij(i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，则运输费用为：则运输费用为：地区地区产粮区

4、产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量5783232023/4/165第5页，共30页，编辑于2022年，星期三地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323从产粮区运出去的量从产粮区运出去的量2023/4/166第6页，共30页，编辑于2022年，星期三运给运给需求地需求地的量的量地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量5783232023/4/167第7页，共30页，编辑于2022年，星期三运量应大于或等于零（非负要求

5、），即运量应大于或等于零（非负要求），即 这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：2023/4/168第8页，共30页，编辑于2022年，星期三 有些问题表面上与运输问题没有多大关系，也可以建立与运输问题有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型形式相同的数学模型【例例7.2】有三台机床加工三种零件，有三台机床加工三种零件，计划第计划第i台的生产任务为台的生产任务为a i (i=1,2,3)个零件个零件(三种零件三种零件)，第第 j 种零件的需要量为种零件的需要量为 bj (j=1,2,3)，第第 i 台机床加工第台机床加工第j种零件需

6、要的时间为种零件需要的时间为 cij，如下表所示。如下表所示。问如何安排生产任务使总的加工时间最少？问如何安排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量7030501502023/4/169第9页，共30页，编辑于2022年，星期三 【解解】设设 xi j (i=1,2,3；j=1,2,3,)为第为第 i 台机床加工第台机床加工第 j 种零件的数种零件的数量，量，零件零件机床机床B1B2B3生产生产任务任务A152350A264160A373440需要需要量量703050150则总的加工时间为则总的加工时间为2

7、023/4/1610第10页，共30页，编辑于2022年，星期三则此问题的数学模型为则此问题的数学模型为2023/4/1611第11页，共30页，编辑于2022年，星期三运输问题的一般数学模型运输问题的一般数学模型设有设有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个销地的运量，个销地的运量，则数学模型为：则数学模型为：2023/4/1612第12页，共30页，编辑于2022年，星期三则数学模型为：则数学模型为：2023/4/1613第13页，共30页，编辑于2022年，星期三设数学模型为设数学模型为 7.1.2最大值问题最大值问题2023/4/1614第14页，共30页，编辑于2022年，星期三第一种方法：第一种方法：将极大化问题转化为极小化问题。将极大化问题转化为极小化问题。设极大化问题的运价表为设极大化问

9、题的运价表为C=（Cij）mn，用一个较大的数，用一个较大的数M（MmaxCij）去减每一个）去减每一个Cij得到矩阵得到矩阵C=（Cij）mn，其中，其中C/ij=MCij0,将将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为值为 2023/4/1615第15页，共30页，编辑于2022年，星期三 当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在实这类运输问题在实际中常常碰到际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题它的求解方法是将不平衡问题化

10、为平衡问题再按平衡问题求解。求解。1.当产大于销时当产大于销时,即即 7.1.3 不平衡运输问题不平衡运输问题 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量100100802023/4/1616第16页，共30页，编辑于2022年，星期三1.当产大于销时当产大于销时 数学模型为数学模型为 即即2023/4/1617第17页，共30页，编辑于2022年，星期三由于总产量大于总销量，由于总产量大于总销量，必有部分产地的产量不能全部必有部分产地的产量不能全部运送完运送完，必须就地库存，即每个产地设一个仓库，库存量，必须就地库存，即每个产地设一个仓库，

11、库存量为为xi，n+1（i=1，2，m），总的库存量为），总的库存量为 2023/4/1618第18页，共30页，编辑于2022年，星期三bn+1作为一个作为一个虚设的销地虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可2023/4/1619第19页，共30页，编辑于2022年，星期三2.当销大于产时当销大于产时,即即 BjAiB1B2B3产产

12、量量A1659120 A212107100A3698130销销 量量2001001502023/4/1620第20页，共30页，编辑于2022年，星期三2.当销大于产时当销大于产时,即即数学模型为数学模型为 2023/4/1621第21页，共30页，编辑于2022年，星期三由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时这时虚设一个产地虚设一个产地Am+1，产量为，产量为 xm+1,j 是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运的运价为零价为零,即即Cm+1,j=0(j=1

13、,2,n)2023/4/1622第22页，共30页，编辑于2022年，星期三销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为，运价为零。产量为am+1即可。即可。2023/4/1623第23页，共30页，编辑于2022年，星期三上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极，试求极小化问题的最优解。小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20605070

14、35451801502107.1.4需求量不确定的运输问题需求量不确定的运输问题2023/4/1624第24页，共30页，编辑于2022年，星期三先作如下分析：先作如下分析：（1）总产量为总产量为180，B1，B4的最低需求量的最低需求量 20+50+35+45=150 180，这时属这时属销大于产销大于产;B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502102023/4/1625第25页，共30页，编辑于2022年，星期三（3）虚设一个产地虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供应的

15、产量只能供应B1或或B2。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502102023/4/1626第26页，共30页，编辑于2022年，星期三（4）将将B1与与B2各分成两部分各分成两部分 的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此 必须由必须由A1，A4供应，供应，可由可由 A1、A5供应。供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521020

16、23/4/1627第27页，共30页，编辑于2022年，星期三（5）上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到 、的运价为的运价为零。得到下表的产销平衡表。零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj2040502035452102023/4/1628第28页，共30页，编辑于2022年，星期三7.1.5中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地34132023/4/1629第29页，共30页，编辑于2022年，星期三设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题的数学则中转运输问题的数学模型为模型为 产大于销时将式产大于销时将式(5.3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5.3c)改为改为“”约束约束 2023/4/1630第30页，共30页，编辑于2022年，星期三