《管理运筹学 运输问题.ppt》由会员分享，可在线阅读，更多相关《管理运筹学 运输问题.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、管理运筹学运输问题运输问题华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第五章第五章 运输问题运输问题运输问题是线性规划问题的特例。运输问题是线性规划问题的特例。产地产地产地产地：货物发出的地点。：货物发出的地点。销地销地销地销地：货物接收的地点。：货物接收的地点。产量产量产量产量：各产地的可供货量。：各产地的可供货量。销量销量销量销量：各销地的需求数量。：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。又使总运费最小。2华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节
2、运输模型运输模型 某某饮饮料料在在国国内内有有三三个个生生产产厂厂，分分布布在在城城市市A1、A2、A3,其其一一级级承承销销商商有有4个个，分分布布在在城城市市B1、B2、B3、B4，已已知知各各厂厂的的产产量量、各各承承销销商商的的销销售售量量及及从从Ai到到Bj的的每每吨吨饮饮料料运运费费为为Cij，为为发发挥挥集集团团优优势势，公公司司要统一筹划运销问题，求运费最小的调运方案。要统一筹划运销问题，求运费最小的调运方案。一、运输问题举例一、运输问题举例销地产地B1B2B3B4产量A1 63255A2 75842A3 32973销量 23143华东交大经济华东交大经济管理学院管理学院SHU
3、FESHUFE第一节第一节 运输模型运输模型(1)(1)决策变量决策变量决策变量决策变量。设从。设从Ai到到Bj的运输量为的运输量为xij，(2)(2)目标函数目标函数目标函数目标函数 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件约束条件约束条件。产量之和等于销量之和产量之和等于销量之和,故要满足故要满足：供应平衡条件供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件销售平衡条件x11+x21+x31=2x1
4、2+x22+x32=3x13+x23+x33=1x14+x24+x34=1非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)运输问题的运输问题的LPLP模型模型 4华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节 运输模型运输模型 销地销地产地产地二、表二、表式式运输模型运输模型A1A2Am产量产量a1a2amB1B2Bn销地销地b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1nx21 x22 x2n xm1 xm2 xmn5华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节 运输模型运
5、输模型产销平衡产销平衡三、运输问题的三种类型三、运输问题的三种类型 6华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节 运输模型运输模型产大于销产大于销7华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节 运输模型运输模型产小于销产小于销8华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第一节第一节 运输模型运输模型系数矩阵的结构如下：系数矩阵的结构如下：（决策变量（决策变量m n，约束方程约束方程m+n个）个）四、运输模型的特点四、运输模型的特点x11x12x1nx21x22x2n xm1xm2 xmnm行行n列列9华东交大经济华东交
6、大经济管理学院管理学院SHUFESHUFE五、运输问题的应用五、运输问题的应用产销不平衡的运输问题产销不平衡的运输问题增加一个销地增加一个销地产大于销产大于销销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销量18121650-46B400045046505010华东交大经济华东交大经济管理学院管理学院SHUFESHUFE增加一个产地增加一个产地产小于销产小于销销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523
7、-2200012223232311华东交大经济华东交大经济管理学院管理学院SHUFESHUFEP129P129页页:例例4 4 特别的特别的:由于供不应求由于供不应求,决定一区供应量可以减少决定一区供应量可以减少0至至200吨吨,二区需求全部满足二区需求全部满足,三区供应量不少于三区供应量不少于1700吨吨12华东交大经济华东交大经济管理学院管理学院SHUFESHUFE转运问题转运问题:P136P136页页:例例8 8产地产地 中转地中转地 销售地销售地13567842对于发点对于发点:产量产量=流出量流出量对于中转点对于中转点:流入量流入量=流出量流出量对于销售点对于销售点:流入量流入量=需
8、求量需求量令令x xijij表示两点间表示两点间的运量的运量,则有则有60040020015035030013华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法表上作业法适合于产销平衡的运输问题表上作业法适合于产销平衡的运输问题求解步骤：求解步骤：找出初始方案（初始基可行解）：在找出初始方案（初始基可行解）：在m n维维产销平衡表上给出产销平衡表上给出m+n-1个数字。个数字。最优性检验：计算各非基变量的检验数，当最优性检验：计算各非基变量的检验数，当 ij 0最优。最优。方案调整与改进：确定进基变量和离基变量，方案调整与改进：确定进基变量和离基变量
9、，找出新的基可行解。找出新的基可行解。14华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法最小元素法最小元素法“就近运给就近运给”，从单位运价表中最小运价开始确定供销关系，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量逐次挑选最小元素，安排运量minai,bj。最大差额法最大差额法不能按最小运费就近供应，就考虑次小运费。不能按最小运费就近供应，就考虑次小运费。各行各行(各列各列)的最小运费与次小运费之差称为行差的最小运费与次小运费之差称为行差(列查列查)。差额越大，说明不能按最小运费调运时，运费增差额越大，说明不能按最小运费调运
10、时，运费增加最多。加最多。对最大差额处就采用最小运费调运。对最大差额处就采用最小运费调运。一、确定初始方案一、确定初始方案15华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法从单位运价表中逐次挑选最小元素，安排运量从单位运价表中逐次挑选最小元素，安排运量 minai,bj。然后，划去该元素所在行或列：然后，划去该元素所在行或列：当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。最小元素法最小元素法销地产地B1B2B3B4产量A163255A275842A332973销量2314130222初始基可行解：初始基可行解：x11=2,x13=1
11、,x14=2,x24=2,x31=0,x32=3，Z=3816华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法判别方法是计算非基变量的检验数判别方法是计算非基变量的检验数：ij=cij CBPij=cij CBB-1Pij运输问题的目标函数要求为最小，即当运输问题的目标函数要求为最小，即当 ij 0视为最优。视为最优。位势法位势法计算检验数计算检验数(原理不做要求原理不做要求)ij=cij CBPij=cij CBB-1Pij ij=cij(ui+vj)ui代表产地代表产地Ai的位势量，的位势量，vj代表销地代表销地Bj的位势量。的位势量。基变量的
12、检验数为基变量的检验数为0，即，即 ij=cij ui vj=0，并令并令u1=0，计算各行各列的计算各行各列的位势量。位势量。二、最优性检验二、最优性检验17华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法基变量的检验数基变量的检验数 ij=cij ui vj=0，即即cij=ui+vj，且令且令u1=0，计算位势量计算位势量ui和和vj位势法位势法销地产地B1B2B3B4产量A162321525A2758422A33023973销量2314uivj0625-1-3518华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表
13、上作业法表上作业法计算非基变量的检验数计算非基变量的检验数 ij=cij ui vj位势法（续位势法（续）销地产地B1B2B3B4产量uiA162 321 52 50A2758422-1A330 23 973-3销量2314vj6525-2217105非基变量非基变量x12的检验数的检验数 12=c12 u1 v2=-2，即让非基变量即让非基变量x12从从0增增到到1，可使总运费减少，可使总运费减少2个单位。个单位。19华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法确定进基变量确定进基变量检查非基变量检查非基变量xij的检验数的检验数 ij，按按
14、 min ij|ij 0=lk 确定确定xlk进基。进基。确定离基变量确定离基变量非基变量非基变量xlk进基之后，能让它的运量增加多少呢？进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持就要求它所在行和列的运量保持产销平衡产销平衡产销平衡产销平衡。保持产销平衡的方法是保持产销平衡的方法是闭回路法闭回路法闭回路法闭回路法。闭回路法：闭回路法：闭回路法：闭回路法：以进基变量以进基变量xlk所在格为始点和终点，其余顶点均为基变量所在格为始点和终点，其余顶点均为基变量的封闭回路。的封闭回路。闭回路的画法闭回路的画法闭回路的画法闭回路的画法：从进基变量：从进基变量xlk所在格开始，用水平或
15、垂直线向前划，所在格开始，用水平或垂直线向前划，每碰到一个基变量格转每碰到一个基变量格转90，继续前进，直到返回始点。，继续前进，直到返回始点。奇偶点：奇偶点：奇偶点：奇偶点：始点是偶点，依次奇偶相间标注；偶点标始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量，表示运量增加量；奇点标增加量；奇点标“-”，表示运量减少量。，表示运量减少量。调整量：调整量：调整量：调整量：最小可减少的运量，即奇点运量的最小值。最小可减少的运量，即奇点运量的最小值。奇点运量的最小值所在格的基变量离基。奇点运量的最小值所在格的基变量离基。三、改进的方法（闭回路调整法）三、改进的方法（闭回路调整法）20华东交大经济
16、华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法x12 进基进基最小调整量为最小调整量为2，x11 离基离基销地产地B1B2B3B4产量A162 3 x1221 52 5A275842 2A330 23 973销量2314+-+-21华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法非最优方案的调整非最优方案的调整所有偶点的值都加上调整量；所有偶点的值都加上调整量；所有奇点的值都减去调整量；所有奇点的值都减去调整量；获得一个新的运输方案。获得一个新的运输方案。销地产地B1B2B3B4产量A16 3 21 52 5A2
17、75842 2A33 2 973销量2314 基可行解：基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34 2 0 3 22 1 22华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第二节第二节 表上作业法表上作业法基变量的检验数基变量的检验数 ij=cij ui vj=0，且令且令u1=0，计算位势量计算位势量ui和和vj四、最优性检验四、最优性检验销地产地B1B2B3B4产量A163 221525A2758422A33221973销量2314uivj04-1-1325所有非基变量所有非基变量xij的检验数的检验数 ij=cij ui vj
18、0，即得最优解。即得最优解。23华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题产销平衡的运输问题采取表上作业法求解。产销平衡的运输问题采取表上作业法求解。产销不平衡的运输问题需划成产销平衡问题再求解。产销不平衡的运输问题需划成产销平衡问题再求解。产大于销：产大于销：虚设一个销地虚设一个销地 Bk(多于物资在产地存储多于物资在产地存储)，其运价为，其运价为0，销量销量(存储量存储量)为产销量之差为产销量之差 bk=ai-bj。产小于销：产小于销：虚设一个产地虚设一个产地 Al(不足物资的脱销量不足物资的脱销量)，其运价为，其运价为0，产量，
19、产量(脱销量脱销量)为销产量之差为销产量之差 ak=bj-ai。24华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题增加一个销地增加一个销地一、产大于销一、产大于销销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销量18121650-46B400045046505025华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题初始基可行解初始基可行解销地产地B1B2B3B4产量A1592015A23
20、17018A3628017销量1812164121561214 初始基可行解：初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=14026华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题最优性检验最优性检验销地产地B1B2B3B4产量uiA159215015A2361127018A36122810417销量1812164vj0260-63-25 511116 62 23 3-2-2 非基变量非基变量x32的检验数的检验数 32=-2，即让非基变量即让非基变量x32进基。进基。27华东交大经济华东
21、交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题闭回路调整闭回路调整x32 进基进基最小调整量为最小调整量为12，x31 离基离基销地产地B1B2B3B4产量A159215015A2361127018A36122 x32 810417销量1812164-+-+28华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题非最优方案的调整非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量所有偶点的值都加上调整量；所有奇点的值都减去调整量。基可行解：基可行解：x13=15,x21=18,x31=0,x
22、32=12,x31=1,x34=4，Z=34销地产地B1B2B3B4产量A159215015A2317018A362810417销量181216461212 180 12 29华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题基变量的检验数基变量的检验数 ij=cij ui vj=0，且令且令u1=0，计算位势量计算位势量ui和和vj最优性检验最优性检验 所有非基变量所有非基变量xij的检验数的检验数 ij=cij ui vj0，即得最优解。即得最优解。销地产地B1B2B3B4产量uiA159215015A231817018A36021281
23、0417销量1812164vj0260-4-635 513136 62 23 32 230华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题增加一个产地增加一个产地二、产小于销二、产小于销销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523-2200012223232331华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题初始基可行初始基可行解解销地产地B1B2B3产量A141210A234312A30001
24、销量8105100571 初始基可行解：初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=4632华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第三节第三节 产销不平衡问题产销不平衡问题最优性检验最优性检验销地产地B1B2B3产量uiA141102010A23743512A301001销量8105vj01212-22 22 21 10 0检验数检验数 ij0，得最优解得最优解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46由于非基变量由于非基变量 x33 的检验数的检验数 33=0，为多最优解。为多最优解。让让x33进基进基,
25、x31离基离基,得另一最优解得另一最优解:x12=10,x13=0,x21=8,x23=4,x33=133华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用短缺资源分配，短缺资源分配，“产小于销产小于销”，需注意产销配比问题。，需注意产销配比问题。上例x12=10,x13=0,x21=7,x23=5,x31=1，表示销地B1脱销1个单位；然而x12=10,x13=0,x21=8,x23=4,x33=1，则表示销地B3 脱销1个单位；但销地B3 的销量为5，本身就很少，不允许脱销，如何处理呢？自来水分配问题：自来水分配问题：水价90元/kt，管
26、理费45元/kt，引水费如下表：一、短缺资源的分配问题一、短缺资源的分配问题供区供区水库水库甲甲乙乙丙丙丁丁供水量供水量kt/dA1613221750B1413191560C192023-50最低需求最低需求kt/d3070010最高需求最高需求kt/d507030不限不限如何分配供水量，保障各区最低需求，获利最大？34华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用 利润利润=收入收入-成本，收入最大，成本最小，则利润最大。成本，收入最大，成本最小，则利润最大。收入：收入：每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天供水
27、总量是一常数，水价也是常数，则每天总收入也是常数。每天供水总量若能全部售出，每天总收入则能达到最大。每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。丁区最高需求不限，每天总供水量能全售出。每天总收入是常数，与水量分配无关，可以不与考虑。每天总收入是常数，与水量分配无关，可以不与考虑。成本：成本：各区管理费相同各区管理费相同45元元/kt，每天售水总量是一常数，则管理费也是常数。每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到最小，总成本则最低。各区引水费不同，如果总的引水费达到最小，总成本则最低。如何分配水量，既满足最低需求，
28、又使总的引水费最低？如何分配水量，既满足最低需求，又使总的引水费最低？最大需求量：最大需求量：供水总量供水总量=50+60+50=160，四区最低需求量，四区最低需求量=30+70+10=110，故丁区最大需求，故丁区最大需求量量160-110+10=60。四区最大需求四区最大需求=50+70+30+60=210，比供水总量，比供水总量160多多50，则是一个产小于销的，则是一个产小于销的不平衡问题。不平衡问题。分析分析35华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用产小于销的运输问题化为平衡问题，虚设水库产小于销的运输问题化为平衡问题
29、，虚设水库D，供水量供水量50。各区的最低需求为基本需求，不允许脱销，不能由虚设水库各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引供水，故单位引水费（运费）为水费（运费）为M。各区的最大需求与最低需求的差为额外需求，可以由虚设水库各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位供水，故单位引水费（运费）为引水费（运费）为0。供区供区水库水库供水量供水量A50B60C50甲甲1甲甲2乙乙丙丙丁丁1丁丁216161322171714141319151519192023MM销量销量302070301050DM0M0M05036华东交大经济华东交大经济管理学院
30、管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用用表上作业法求得最优方案用表上作业法求得最优方案供区供区水库水库甲甲1甲甲2乙乙丙丙丁丁1丁丁2供水量供水量A5050B20103060C3020050D302050销量销量302070301050最优分配方案：水库最优分配方案：水库A向乙区供水向乙区供水50，水库，水库B分别向乙区、丁区供水分别向乙区、丁区供水20和和40，水库，水库C向甲区供水向甲区供水50，不给丙区供水。，不给丙区供水。最小引水费：最小引水费：13 50+13 20+15(10+30)+19(30+20)=2460 引水引水管理费：管理费：45(50+
31、60+50)=7200 总成本：总成本：2460+7200=9600 总收入：总收入：90(50+60+50)=14400 最大获利：最大获利：14400-9600=474037华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用产地与销地之间存在转运站。产地与销地之间存在转运站。面粉转运问题：面粉转运问题：三个面粉加工厂，两个糕点生产厂，两个中转站。二、资源转运问题二、资源转运问题终点终点始点始点面粉厂面粉厂中转站中转站糕点厂糕点厂生产生产能力能力A1A2A3T1T2B1B2面面粉粉厂厂A1323-683A242521374A3-232114
32、3中中转转站站T1352625T2-327-2糕糕点点厂厂B16-2-94B2-4-396如何调运，总运费最低？38华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用最小转运能力最小转运能力 t=max ai，bj=10销地销地产地产地面粉厂面粉厂中转站中转站糕点厂糕点厂产产 量量A1A2A3T1T2B1B2面面粉粉厂厂A1A2A3中中转转站站T1T2糕糕点点厂厂B1B2销量销量0323M6840252137M20321143520625M3270M26MM2M09MM4M39013141310101010面粉厂产量面粉厂产量:ai+t糕点厂
33、产量糕点厂产量:t转运站产量转运站产量:t面粉厂销量面粉厂销量:t糕点厂销量糕点厂销量:bj+t转运站销量转运站销量:t10101010101416323-68342521374-2321143352625-327-26-2-94-4-39639华东交大经济华东交大经济管理学院管理学院SHUFESHUFE第四节第四节 运输模型的应用运输模型的应用用表上作业法求得最优方案用表上作业法求得最优方案最优分配方案：最优分配方案：面粉厂面粉厂A3向糕点厂向糕点厂B2直接运输直接运输2吨，吨，A1、A2、A3向中转站向中转站T1和和T2运输运输3、4、1吨，中转站吨，中转站T1和和T2分别向糕点厂分别向糕点厂B1、B2运输运输4、4吨。吨。最小运费：最小运费：3 3+2 4+3 1+4 2+2 4+2 4=44销地销地产地产地面粉厂面粉厂中转站中转站糕点厂糕点厂产产 量量A1A2A3T1T2B1B2面面粉粉厂厂A1A2A3中中转转站站T1T2糕糕点点厂厂B1B2销量销量10313104141012136410641010101010101010101014163344123444640