管理运筹学运输问题.pptx

《管理运筹学运输问题.pptx》由会员分享，可在线阅读，更多相关《管理运筹学运输问题.pptx（119页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 运输问题运输问题TransportationProblem第第1页页/共共119页页本节内容提要本节内容提要3.1运输问题的数学模运输问题的数学模3.2表上作业法表上作业法第第2页页/共共119页页3.1运输问题的数学模型运输问题的数学模型A1AiAm产地产量销地B1BjBn销量第第3页页/共共119页页例：某运输问题的资料如下：例：某运输问题的资料如下：单位 销地 运价产地产量2910291342584257销量3846一、运输问题的数学模型一、运输问题的数学模型第第4页页/共共119页页第第5页页/共共119页页数学模型的一般形式数学模型的一般形式已知资料如下：已知资料如下：

2、单 销 产 量产地产量销 量运运价价供需平衡供需平衡第第6页页/共共119页页当产销平衡时，其模型如下：当产销平衡时，其模型如下：Ai的产品全部的产品全部供应出去供应出去Bj的需求全的需求全部得到满足部得到满足产销平衡的运输问题必定存最优解产销平衡的运输问题必定存最优解.第第7页页/共共119页页当产大于销时，其模型是：当产大于销时，其模型是：第第8页页/共共119页页当产小于销时，其模型是：当产小于销时，其模型是：第第9页页/共共119页页mn第第10页页/共共119页页平衡表、运价表和二为一：平衡表、运价表和二为一：第第11页页/共共119页页约束条件或解可用产销平衡表表示约束条件或解可用

3、产销平衡表表示:第第12页页/共共119页页 uivj无约束无约束（i=1,2,m;j=1,2,n)uivj设设u ui,v,vj为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为m个个n个个第第13页页/共共119页页 特征：特征：1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解；2 2、运输问题的基本可行解中应包、运输问题的基本可行解中应包括括 m+n1 个基变量。个基变量。第第14页页/共共119页页 .重复重复.，直到找到最优解为止。，直到找到最优解为止。步骤：步骤：.找出找出初始基本可行解初始基本可行解（初始调运方案，一（初始调运方案，一般般m+

4、n-1m+n-1个数字格），用西北角法、最小元素法；个数字格），用西北角法、最小元素法；.求出各非基变量的检验数，判别是否达到求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用最优解。如果是停止计算，否则转入下一步，用位势法计算；位势法计算；.改进当前的基本可行解（确定换入、换改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；出变量），用闭合回路法调整；二、表上作业法二、表上作业法确定确定m+n-1个基变量个基变量空格空格第第15页页/共共119页页3.2求解运输问题的算法求解运输问题的算法:表上作业法表上作业法开开始始求各非基变求各非基变量的检验数量的

5、检验数是否达到最优解是否达到最优解结束结束确定换入变量确定换入变量与换出变量与换出变量新的基可行解新的基可行解求初始基可行解求初始基可行解NNY Y最小元素最小元素最小元素最小元素法，法，法，法，伏格尔法伏格尔法伏格尔法伏格尔法闭回路闭回路闭回路闭回路法，法，法，法，位势法位势法位势法位势法闭回路闭回路闭回路闭回路调整法调整法调整法调整法第第16页页/共共119页页例一、某运输资料如下表所示：例一、某运输资料如下表所示：单位单位销地销地运价运价产地产地产量产量311310719284741059销量销量36561 1、求初始方案：、求初始方案：第第17页页/共共119页页初始基可行解的确定初始

6、基可行解的确定西北角法西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法.西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.第第18页页/共共119页页.西北角法西北角法(或左上角法或左上角法):):此法是纯粹的人为的规定此法是纯粹的人为的规定,没有理论依据和实际背没有理论依据和实际背景景,但它易操作但它易操作,特别适合在计算机上编程计算特别适合在计算机上编程计算,因而受因而受欢迎欢迎.方法如下：方法如下：总的运费总的运费(33)(33)(411)(411)(29)(29)(22)(

7、22)(310)(310)(65)(65)135135元元第第19页页/共共119页页B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633 .初始基可行解的确定初始基可行解的确定-最小元素法：最小元素法：基本思想是就近供应，即从运价最小的地方开始供基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。应（调运），然后次小，直到最后供完为止。总的运输费用（总的运输费用（3131）（）（6464）（4343）（）（1212）（）（310310）（）（3535）8686元元第第20页页/共共119页页分别计算各行、各列次

8、小、最小运价的差值分别计算各行、各列次小、最小运价的差值,优先在优先在最大差值处进行供需搭配最大差值处进行供需搭配.差值差值=次小次小-最小最小 步骤：步骤：10计算未划去行、列的差额计算未划去行、列的差额;20找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配进行供需分配;30在未被划去的行、列重新计算差额在未被划去的行、列重新计算差额.(3)初始基可行解的确定初始基可行解的确定-最大差值法最大差值法(伏格尔法伏格尔法)Vogel第第21页页/共共119页页6 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656B1B2B3B4供量供量A13113107A

9、219284A3741059销量销量3656列差值列差值2513行差值行差值011第第22页页/共共119页页63 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656B1B2B3B4行差值行差值A13113100A219281A3741052列差值列差值213第第23页页/共共119页页363 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656B1B2B3B4行差值行差值A13113100A219281A374105列差值列差值212第第24页页/共共119页页51263B1B2B3B4差值差值A13113107A219286A374105差值差值12 销销

10、产产B1B2B3B4供量供量A17A24A3 39销量销量 3656第第25页页/共共119页页以上方法得到的初始解为基可行解每次行(需求)或列(供应)达到饱和每次必划掉一行或一列得到的元素个数必为m+n-1个西北角法 最小元素法 最大差值法第第26页页/共共119页页练习P97 3.1 3.2第第27页页/共共119页页 ijij0 0（因为目标函数要求最小化）（因为目标函数要求最小化）表格中有调运量的地方为基变量表格中有调运量的地方为基变量,空格处为非基变空格处为非基变 量量.基变量的检验数基变量的检验数ijij0,非基变量的检验数非基变量的检验数ijij0.0.ij0表示运费增加表示运费

11、增加.2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）：检验数检验数非基变量增加一个非基变量增加一个单位目标值的变化单位目标值的变化第第28页页/共共119页页（1）闭回路法）闭回路法闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或垂直或垂直)直线直线,遇到填有运量的方格遇到填有运量的方格可转可转90,然后继续前进然后继续前进,直到到达出发直到到达出发的空格所形成的闭合回路的空格所形成的闭合回路.调运方案的任意空格存在唯一闭回路调运方案的任意空格存在唯一闭回路.销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销

12、量 3656差差值值法法方方案案一、最优调运方案的判定一、最优调运方案的判定第第29页页/共共119页页314 633最最小小元元素素法法方方案案+-+-x11为换入变量，为换入变量，x11：01，运费的变化为，运费的变化为3-1+2-3=1。这个变化就是。这个变化就是x11的检验数，故的检验数，故 11=1第第30页页/共共119页页B1B2B3B4产量产量A17A24A39销量销量365631363124第第31页页/共共119页页B1B2B3B4产量产量A17A24A39销量销量36563136312-14第第32页页/共共119页页B1B2B3B4产量产量A17A24A39销量销量36

13、5631363121-14第第33页页/共共119页页B1B2B3B4产量产量A17A24A39销量销量365631363121-1124第第34页页/共共119页页B1B2B3B4产量产量A17A24A39销量销量365631363121-112104检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。第第35页页/共共119页页空格闭回路检验数(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32)-(22)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(2

14、3)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-11012检验数还存在检验数还存在负数负数,原方案不是最优方案原方案不是最优方案.第第36页页/共共119页页用闭回路求解检验数时,需要给每一个空格找一条闭回路.当产销点较多时,该方法较麻烦.第第37页页/共共119页页ui,vj自由变量自由变量（2）位势法位势法标准型运输问题的对偶问题是：标准型运输问题的对偶问题是：XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数检验数对偶变量值等于对偶变量值等于原问题的检验数原问

15、题的检验数松弛变量松弛变量第第38页页/共共119页页基变量的检验数为零基变量的检验数为零(基变量基变量xij)，得得m+n-1个方程个方程,含含m+n个未知数个未知数,令某个令某个ui(或或vj)=0,可解出可解出m+n个个ui 和和vj;由此得非基变量的检验由此得非基变量的检验数数.第第39页页/共共119页页1.由基变量的检验数为0,ij=cij-(ui+vj)=0,u1=0(v1=0),得ui,vj2.利用 ij=cij-(ui+vj),求非基变量的检验数可令任意的行或列的位势为可令任意的行或列的位势为0(任意值均任意值均可可,为为0出于计算简单考虑出于计算简单考虑)第第40页页/共共

16、119页页314 633位位势势法法 令令v1=0,由由c21=1=u2+v1，得得u2=1第第41页页/共共119页页0112第第42页页/共共119页页01128-37位位势势表表2989-3-2检验数检验数第第43页页/共共119页页01128-37检检验验数数表表121-11012 24=-10，当前方案，当前方案不是最优方案。不是最优方案。第第44页页/共共119页页1.以以最小负检验数最小负检验数为出发点寻找一条闭回路为出发点寻找一条闭回路.2.确定调整量确定调整量,调出格中调出格中最小最小的运量的运量.2.3改进的方法改进的方法闭回路调整法闭回路调整法第第45页页/共共119页页

17、二、二、调运方案的调整调运方案的调整pqijj,i)(min =bj产小于销：产小于销：ai产量产量第第71页页/共共119页页第第72页页/共共119页页第第73页页/共共119页页二、转运问题二、转运问题出现下列问题：出现下列问题：1.产地与销地之间没有直达路线，货物由产地到销产地与销地之间没有直达路线，货物由产地到销地必须通过中转站转运；地必须通过中转站转运；2.某些产地可以输入货物，销地也可以输出货物，某些产地可以输入货物，销地也可以输出货物，3.产地与销地之间虽然有直达运输线，但直达运输产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。的费用（距离）比

18、经过某些中转站的还要高。解法：解法：无转运问题。无转运问题。1.根据问题求出最大可能周转量根据问题求出最大可能周转量Q；2.纯转运点纯转运点产地：输出量产地：输出量Q；销地：输入量销地：输入量Q；输入输入=输出输出第第74页页/共共119页页3.兼中转站的产地兼中转站的产地Ai=销地：输入量销地：输入量Q；产地：输出量产地：输出量Q+ai；4.兼中转站的销地兼中转站的销地Bj=销地：输入量销地：输入量bj+Q；产地：输出量产地：输出量Q；列出各产地的输出量和各销地的输入量及各产列出各产地的输出量和各销地的输入量及各产销地之间的运价表销地之间的运价表,用表上作业法求解用表上作业法求解.输出：产地

19、；中转站输出：产地；中转站(纯纯/兼兼)输入：销地；中转站输入：销地；中转站(纯纯/兼兼)第第75页页/共共119页页例例某货物某货物,其产地其产地A1的产量为的产量为10单位单位,A2的产量为的产量为2单单位位,销地销地A3、A4、A5的销量分别为的销量分别为3单位、单位、1单位和单位和8单位单位,其中产地其中产地A2、销、销A4又可作为中转站又可作为中转站.同时同时,货物货物可通过纯中转站可通过纯中转站A6进行运输进行运输.各产地、销地及中转站各产地、销地及中转站之间的单位物资运价如表所示之间的单位物资运价如表所示,试求一个使总运费最试求一个使总运费最省的调运方案省的调运方案.销地销地产地

20、产地A2A3A4A5A6A126312A203M24A4M2031A613270第第76页页/共共119页页最大可能周转量最大可能周转量Q=a1+a2=10+2=12A1纯产地纯产地,输出量输出量10;A2产地兼中转站产地兼中转站,输出量输出量2+12=14,输入量输入量12;A3纯销地纯销地,输入量输入量3;A4销地兼中转站销地兼中转站,输出量输出量12,输入量输入量1+12=13;A5纯销地纯销地,输入量输入量8;A6纯中转站纯中转站,输出量、输入量均为输出量、输入量均为12.根据以上情况列产销平衡表根据以上情况列产销平衡表.第第77页页/共共119页页 销地产地A2A3A4A5A6输出量

21、A12631210A203M2414A4M203112A61327012输入量1231381248第第78页页/共共119页页 销地产地A2A3A4A5A6输出量A118110A212214A41212A611112输入量1231381248不参加实际调运不参加实际调运第第79页页/共共119页页3.4应用举例应用举例搞清搞清“产地、销地产地、销地”、“运价运价”,“产量、需求产量、需求”,写出写出产销平衡产销平衡表表运输问题的要素运输问题的要素:未知数未知数如何设如何设虚设虚设产地与销地产地与销地;拆分拆分产地与销地产地与销地第第80页页/共共119页页例例3.某厂按合同规定须于每个季度末分

22、别提供某厂按合同规定须于每个季度末分别提供10,15,25,20台同一规格的柴油机台同一规格的柴油机.已知该厂各季度已知该厂各季度的生产能力及生产每台柴油机的成本如下表的生产能力及生产每台柴油机的成本如下表.如果如果生产出来的柴油机当季不交货生产出来的柴油机当季不交货,每台积压一个季度每台积压一个季度需储存、维护费用需储存、维护费用0.15万元万元.要求在完成合同的情要求在完成合同的情况下况下,做出该厂全年费用最小的决策做出该厂全年费用最小的决策.季度季度生产能力生产能力单位成本单位成本IIIIIIIV2535301010.811.111.011.3搞清搞清“产地、销地产地、销地”、“运价运价

23、”,“产量、需求产量、需求”,写出写出产销平产销平衡表衡表未知数未知数如何设如何设第第81页页/共共119页页设设xij为第为第i季度生产的用于第季度生产的用于第j季度交货的柴油机数季度交货的柴油机数.合同要求：合同要求：产量约束：产量约束：第第i季度生产的用于第季度生产的用于第j季度交货的柴油机的实际成本季度交货的柴油机的实际成本cij=生产成本生产成本+储存维护费用储存维护费用ijIIIIIIIVIIIIIIIV10.810.9511.1011.1011.2511.0011.2511.4011.1511.30目标函数：目标函数：目标函数：目标函数：第第82页页/共共119页页第第83页页/

24、共共119页页ijIIIIIIIV产量产量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3025353010销量销量10152520ijIIIIIIIVD产量产量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.30000025353010销量销量1015252030第第84页页/共共119页页第第85页页/共共119页页第第86页页/共共119页页第第87页页/共共119页页第第88页页/共共119页页第第89页页/共共119页页第第90页页/共

25、共119页页第第91页页/共共119页页第第92页页/共共119页页第第93页页/共共119页页第第94页页/共共119页页第第95页页/共共119页页第第96页页/共共119页页第第97页页/共共119页页第第98页页/共共119页页第第99页页/共共119页页第第100页页/共共119页页第第101页页/共共119页页第第102页页/共共119页页第第103页页/共共119页页 例:某玩具公司分别生产三种新型的玩具,每月可供应量分别为1000件,2000件,2000件，他们分别被送到甲乙丙三个百货商店销售,已知每月百货商店各类玩具预期销售量为1500件,由于经营原因,各百货商店销售不同玩具

26、的盈利额不同,又知丙百货商店要求至少供应C玩具1000件,而拒绝进入A种玩具,求满足上述条件下使总盈利额为最大的供销分配方案.甲乙丙可供量ABC516124810-911100020002000第第104页页/共共119页页C先满足丙1000件甲乙丙丁可供量ABC516124810-91100010002000100015001500500500甲乙丙丁可供量ABC11041286M7500010002000100015001500500500第第105页页/共共119页页 已知某运输问题的产销平衡表,最优调运方案及单位运价表分别如表所示,由于从产地2至销地B的道路因故暂时封闭,故需对调运方案

27、进行修正,试用尽可能简单的方法重新找出最优调运方案.ABCDE产量1233414513948销量35463ABCDE1231021201020510793010106410变为变为M,计算检验数进行调整计算检验数进行调整第第106页页/共共119页页已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/吨吨 试求出最优运输方案试求出最优运输方案.练习：练习：2、如将、如将A2的发量改为的发量改为1717

28、，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。第第107页页/共共119页页13A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费85元元/吨吨第第108页页/共共119页页已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费用为最小？用为最小？发电厂 发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表电力供需表B1B2B3B4A110523A24312A35634单位输电费用单位输电费用作业：作业：第第109页页/共共119页页B1B2B3B4uiA110

29、5230A24-1-4-3-6A350-3-2-5vj10523(ui+vj)B1B2B3B4uiA10000A20455A30666vjij-(ui+vj)=cijB1B2B3B4A1200250100150A2200A3100C=5200第第110页页/共共119页页运输问题习题第第111页页/共共119页页二、如下所示的运输问题中二、如下所示的运输问题中,如果某一产地有一如果某一产地有一个单位物资未运出个单位物资未运出,就将发生存储费用就将发生存储费用.假定三个假定三个产地单位物资存储费用分别为产地单位物资存储费用分别为2,2,1,请用最小元请用最小元素法求初始方案素法求初始方案,用位势

30、法调整出最优方案并计用位势法调整出最优方案并计算出最优方案的总费用算出最优方案的总费用.销地销地产地产地IIIIIIIV176550248830334520销量销量302040第第112页页/共共119页页三、某最小费用运输问题的调运方案如下(黑体字为运量):1.上述方案是否可作为表上作业法求解时的初始解?说明理由.2.如问题1的答案为是,请用用位势法进行检验并求出最优方案.单位单位运价运价发发点点收点收点发发量量B1B2B3B4A124515545A222430130A3401542535275收收量量40502535第第113页页/共共119页页四、某公司和供货商A、B、C签订了长期供货合

31、同,按月为位于不同地区的三个下属工厂供应某种原料,三个供货商提供的原料品质基本相同,但由于所处的地理位置、人工成本等导致其实际供货成本有所不同.由于一次生产事故，导致最大的供货商A下个月的供货量无法全部满足.下个月供货商的供应量、工厂的需求量和供货商与工厂之间的供货成本如下表所示.公司经紧急协商,在工厂1所在地筹措到100吨的货源,供货成本为23百元/吨;工厂2所在地货源充足,供货成本为25百元/吨.但由于运力紧张两处货源均无法调运到外地.鉴于此种情况公司决定要优先保证工厂1的全部需求,工厂3的需求至少要满足500吨.该公司面临的问题是应如何协调各供货商和工厂之间的供货关系,才能使总的供货成本

32、最小.请为本问题建立适合于应用于表上作业法的产销平衡表.(不必计算)工厂工厂供货成本供货成本（百元（百元/吨）吨）供货商供货商123供货量供货量（吨）（吨）A202119500B182220300C192021400需求量（吨）需求量（吨）400500700第第114页页/共共119页页五、已知某极小化运输问题的有关数据如下表所示:表中黑体字为运量。要求：用位势法计算表中方案的检验数并进行进一步调整。第第115页页/共共119页页第第116页页/共共119页页第第117页页/共共119页页教育部门认为：划分入学区域界限的适当目标是使学生到学校的平均路程最短。在这个初步计划中，他们要确定为了实现这一目标每一个区域内至少有多少学生要安排到哪一所学校，同时要满足表中最后两行规定的约束条件。(1)建立该问题的运输问题约束条件(2)按运输问题的最小元素法给出一个较好的初始分配方案。第第118页页/共共119页页感谢您的观看。感谢您的观看。第第119页页/共共119页页