运筹学管理运筹学讲义：运输问题

运筹帷幄之中决胜千里之外运筹学课件运输问题1第三章运输问题运输问题是线性规划问题的特例。产地：货物发出的地点。销地：货物接收的地点。产量：各产地的可供货量。销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。2第一节运输模型某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。

一、运输问题举例

销地产地B1B2B3B4产量A163255A275842A332973销量23143第一节运输模型(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件。产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束

xij≥0(i=1,2,3；j=1,2,3,4)

运输问题的LP模型

4第一节运输模型销地产地二、表式运输模型A1A2…Am产量a1a2…amB1B2…Bn销地b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn5第一节运输模型产销平衡三、运输问题的三种类型

6第一节运输模型产大于销7第一节运输模型产小于销8第二节表上作业法表上作业法适合于产销平衡的运输问题求解步骤：找出初始方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。

最优性检验：计算各非基变量的检验数，当ij0最优。方案调整与改进：确定进基变量和离基变量，找出新的基可行解。9第二节表上作业法最小元素法“就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量min{ai,bj}。最大差额法不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列差)。对最大差额处就采用最小运费调运。一、确定初始方案10第二节表上作业法从单位运价表中逐次挑选最小元素，安排运量min{ai,bj}。然后，划去该元素所在行或列：当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。最小元素法销地产地B1B2B3B4产量A163255A275842A332973销量2314130222初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=3811第二节表上作业法判别方法是计算非基变量的检验数：ij=cij–CBPij’=cij–CBB-1Pij运输问题的目标函数要求为最小，即当ij0视为最优。位势法计算检验数ij=cij–CBPij’=cij–CBB-1Pijij=cij–(ui+vj)

ui代表产地Ai的位势量，vj代表销地Bj的位势量。基变量的检验数为0，即ij=cij–ui–vj=0，并令u1=0，计算各行各列的位势量。二、最优性检验12第二节表上作业法基变量的检验数ij=cij–ui–vj=0，即cij=ui+vj，且令u1=0，计算位势量ui和vj位势法销地产地B1B2B3B4产量A162321525A2758422A33023973销量2314uivj0625-1-3513第二节表上作业法计算非基变量的检验数ij=cij–ui–vj位势法（续）销地产地B1B2B3B4产量uiA1623215250A2758422-1A33023973-3销量2314vj6525-2217105非基变量x12的检验数12=c12–u1–v2=-2，即让非基变量x12从0增到1，可使总运费减少2个单位。14第二节表上作业法确定进基变量检查非基变量xij的检验数ij，按min{ij|

ij<0}=lk确定xlk进基。确定离基变量非基变量xlk进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持产销平衡。保持产销平衡的方法是闭回路法。闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90º，继续前进，直到返回始点。奇偶点：始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量增加量；奇点标“-”，表示运量减少量。调整量：最小可减少的运量，即奇点运量的最小值。奇点运量的最小值所在格的基变量离基。三、改进的方法（闭回路调整法）15第二节表上作业法x12进基最小调整量为2，x11离基销地产地B1B2B3B4产量A1623x1221525A2758422A33023973销量2314+-+-16第二节表上作业法非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量；获得一个新的运输方案。销地产地B1B2B3B4产量A16

321525A2758422A33

2

973销量2314基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=342

03

22117第二节表上作业法基变量的检验数ij=cij–ui–vj=0，且令u1=0，计算位势量ui和vj四、最优性检验销地产地B1B2B3B4产量A163221525A2758422A33221973销量2314uivj04-1-1325所有非基变量xij的检验数ij=cij

–ui–vj≥0，即得最优解。18第三节产销不平衡问题产销平衡的运输问题采取表上作业法求解。产销不平衡的运输问题需划成产销平衡问题再求解。产大于销：虚设一个销地Bk(多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差bk=ai-bj。产小于销：虚设一个产地Al(不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差ak=bj

-

ai

。19第三节产销不平衡问题增加一个销地一、产大于销销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销量18121650-46B400045046505020第三节产销不平衡问题初始基可行解销地产地B1B2B3B4产量A1592015A2317018A3628017销量1812164121561214

初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=14021第三节产销不平衡问题最优性检验销地产地B1B2B3B4产量uiA159215015A2361127018A36122810417销量1812164vj0260-63-2511623-2非基变量x32的检验数32=-2，即让非基变量x32进基。22第三节产销不平衡问题闭回路调整x32进基最小调整量为12，x31离基销地产地B1B2B3B4产量A159215015A2361127018A36122x32810417销量1812164-+-+23第三节产销不平衡问题非最优方案的调整所有偶点的值都加上调整量；所有奇点的值都减去调整量。基可行解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34销地产地B1B2B3B4产量A159215015A2317018A362810417销量181216461212

180

1224第三节产销不平衡问题基变量的检验数ij=cij–ui–vj=0，且令u1=0，计算位势量ui和vj最优性检验所有非基变量xij的检验数ij=cij–ui–vj≥0，即得最优解。销地产地B1B2B3B4产量uiA159215015A231817018A360212810417销量1812164vj0260-4-63513623225第三节产销不平衡问题增加一个产地二、产小于销销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523-2200012223232326第三节产销不平衡问题初始基可行解销地产地B1B2B3产量A141210A234312A30001销量8105100571

初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=4627第三节产销不平衡问题最优性检验销地产地B1B2B3产量uiA141102010A23743512A301001销量8105vj01212-22210检验数ij≥0，得最优解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46由于非基变量x33的检验数33=0，为多最优解。让x33进基,x31离基,得另一最优解:x12=10,x13=0,x21=8,x23=4,x33=128第四节运输模型的应用短缺资源分配，“产小于销”，需注意产销配比问题。上例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，管理费45元/kt，引水费如下表：一、短缺资源的分配问题供区水库甲乙丙丁供水量kt/dA1613221750B1413191560C192023--50最低需求kt/d3070010最高需求kt/d507030不限如何分配供水量，保障各区最低需求，获利最大？29第四节运输模型的应用利润=收入-成本，收入最大，成本最小，则利润最大。收入：每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天总收入是常数，与水量分配无关，可以不与考虑。成本：各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到最小，总成本则最低。如何分配水量，既满足最低需求，又使总的引水费最低？最大需求量：供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。分析30第四节运输模型的应用产小于销的运输问题化为平衡问题，虚设水库D，供水量50。各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M>0。各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0。供区水库供水量A50B60C50甲1甲2乙丙丁1丁216161322171714141319151519192023MM销量302070301050DM0M0M05031第四节运输模型的应用用表上作业法求得最优方案供区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050销量302070301050最优分配方案：水库A向乙区供水50，水库B分别向乙区、丁区供水20和40，水库C向甲区供水50，不给丙区供水。最小引水费：1350+1320+15(10+30)+19(30+20)=2460引水管理费：45(50+60+50)=7200总成本：2460+7200=9600总收入：90(50+60+50)=14400最大获利：14400-9600=474032第四节运输模型的应用产地与销地之间存在转运站。面粉转运问题：三个面粉加工厂，两个糕点生产厂，两个中转站。二、资源转运问题终点始点面粉厂中转站糕点厂生产能力A1A2A3T1T2B1B2面粉厂A1323-683A242521374A3-2321143中转站T1352625T2-327-2糕点厂B