第三章(运输问题)

1、第三章 运输问题3.1 运输问题及其数学模型运输问题及其数学模型3.2 表上作业法表上作业法3.3 运输问题的进一步讨论运输问题的进一步讨论本章学习要求n掌握表上作业法及其在产销平衡运输问题求解中的应用n掌握产销不平衡运输问题的求解方法：假设有假设有m个生产地点，可以供应某个生产地点，可以供应某种物资（以后称为产地），用种物资（以后称为产地），用Ai来表示，来表示，i=1,m,有有n个销地，个销地，用用Bj来表示，来表示，j=1,n，产地的产量和销地的销量分别为，产地的产量和销地的销量分别为ai,bj，从产地从产地Ai到销地到销地Bj运输一个单位物资的运价为运输一个单位物资的运价为Cij，这些

2、数据可，这些数据可汇总于下表，在假设产销平衡的条件下，即汇总于下表，在假设产销平衡的条件下，即ai= bj，问该如，问该如何调运物品使总运费最小？何调运物品使总运费最小？B1B2Bn产量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam销量b1b2bn建模：设建模：设xij表示从表示从Ai到到Bj的运量，则所求的的运量，则所求的数学模型为：数学模型为：min =cijxij s.t. xij=ai i=1,mxij=bj j=1,nj=1ni=1mi=1mj=1nxij0 i=1,m,j=1,n2.例如例如：三个产地四个销地，用网络表示：三个产地四个销地，用网络表示

3、2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14产地产地运价运价销地销地6753482759106产量产量销量销量总产量总产量60吨吨总销量总销量60吨吨产销平衡的运输问题产销平衡的运输问题0131213221927146109572483576min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211=+=+=+=+=+=+=+=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxx

4、xxxxxxxz运输问题线性规划模型运输问题线性规划模型产地约束产地约束销地约束销地约束运输问题的表格表示运输问题的表格表示njjmiiba113.2 表上作业法n初始基可行解的确定初始基可行解的确定n最优性检验最优性检验n基变换基变换运输问题基的表示运输问题基的表示 123412312341231234123123412312341231234123基在运输表中的表示基在运输表中的表示123412312341231234123123412312341231234123运输表中同行同列组成回路的变量运输表中同行同列组成回路的变量一一. 初始基可行解的确定初始基可行解的确定n西北角法西北角法n最

5、小元素法最小元素法n沃格尔法沃格尔法1.西北角法西北角法813131466方法：优先满足运输表中左上角空格的供销要求方法：优先满足运输表中左上角空格的供销要求填一个数字只能划去一行或一列填一个数字只能划去一行或一列2.最小元素法最小元素法12015130113021930120200方法：按单位运价的大小，决定供应的先后，优先方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）满足单位运价最小者的供销要求（就近供应）3.沃格尔法沃格尔法3212323311*3113行罚数行罚数列列罚罚数数414*13*1219方法：计算出每一行及每一列中单位运价最小和次小的两个

6、元素之方法：计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。足其供销关系。二二. 最优性检验求非基变量的检验数最优性检验求非基变量的检验数n闭回路法闭回路法n位势法位势法1.闭回路法闭回路法n方法方法n意义：意义：8131314661.闭回路法闭回路法(1)12 =c12-c22+c21-c11=7-4+8-6=558131314661.闭回路法闭回路法(2)513 =c13-c23+c21-c11=5-2+8-6=558131314661. 闭回路法闭回路法(

7、3)5514 =(c14-c34+ c33 - c23 + c21 -c11)=3-6+10-2+8-6=778131314661. 闭回路法闭回路法(4)55712 =c24-c34+ c33-c23=7-6+10-2=998131314661. 闭回路法闭回路法(5)557932 =c32-c24+ c23-c33=9-4+2-10=-3-38131314661. 闭回路法闭回路法(6)5579-331 =c31-c21+ c23-c32=5-8+2-10=-11-112. 位势法位势法该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为该法也称对偶变量法，我们知道一般标准运输问题的对

8、偶问题为：njmicvuvbuaMaxWijjinjjjmiii,1,111由由LP中中ij 的定义：的定义： ij =Cij-CBB-1Pij Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij= cij-(ui+vj)对基变量而言：对基变量而言： 8131314662. 位势法位势法(1)uivj0622010-48131314662. 位势法位势法(2)uivj0622010-45579-13-30/minijijlk8131314661.基变换基变换-确定换入换出变量确定换入换出变量5579-3-11-11-68131314661.基变换得新的基解基变换得新的基解-

9、62121313141.基变换得新的基解基变换得新的基解6212单纯形法与表上作业法比较单纯形法与表上作业法比较单纯形法（单纯形法（Min）表上作业法表上作业法确定初确定初始基变始基变量量XB+松驰变量松驰变量+（人工变量）（人工变量）XB系数矩阵为系数矩阵为I，m个个其余其余XN最小元素法、沃格尔法等最小元素法、沃格尔法等XB数字格，数字格，m+n-1个个XN 空格空格检验数检验数基变量基变量 j =0非基变量非基变量 j =cj-cBB-1pj基变量基变量 ij=0非基变量非基变量 ij =cij-Ui-Vj调整调整进基：进基：min j j 0出基：出基： minbi/aik，aik0进

10、基：进基：min ij ijbj（产量（产量销量）所以要虚构一销销量）所以要虚构一销地地B5，其销量，其销量b5=30，而，而ci5 =0，这样，就转化成了一个产销平衡问题。，这样，就转化成了一个产销平衡问题。B1B2B3B4B5产量产量A130508040030 A270408060050A3100305020060销量销量1510404530B1B2B3B4产量产量A13113109 A219284A3741057销量销找出单位物资效益表（）找出单位物资效益表（cij）中的最大元素）中的最大元素M，即，即M=maxcij2)令令cij =M-cij，并视为运价。，

11、并视为运价。3）由）由cij构成单位运价表，按通常的表上作业法求解，求得构成单位运价表，按通常的表上作业法求解，求得最优解后把所得结果转换为原问题的答案。最优解后把所得结果转换为原问题的答案。（有最高需求和最低需求）（有最高需求和最低需求）设销地设销地Bk的最低需求为的最低需求为bk，最高需求为，最高需求为bk” ，这时可把看作，这时可把看作Bk和和Bk”两个销地，两个销地， Bk需求量需求量bk ，Bk”的需求量的需求量bk” - bkB1B2B3B4产量产量A11613221750 A21413191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限

12、不限B1B2B3B4产量产量A11613221750 A21413191560A3192023M50最低需求最低需求3070010最高需求最高需求507030不限不限12344销量销量30207030A2A3A4501419M141901320M19230M如下表，设销地如下表，设销地1 1不允许缺货；销地不允许缺货；销地2 2缺货，单位损失费缺货，单位损失费3 3元；销地元；销地3 3缺货，缺货，单位损失费单位损失费2 2元，问如何处理？元，问如何处理？B1B2B3产量产量A151710 A264680A332515销量销量655525B1B2B3产量产量A151710 A264680A33

13、2515销量销量655525A440M32如规定销地如规定销地1的需求量必须由产地的需求量必须由产地4供应，如何处理？供应，如何处理？1）直接令）直接令x41=b12)令令c41=-M，或者，或者c11=c21=c31=M这样销地这样销地1的需求量肯定是由产地的需求量肯定是由产地1供应了。供应了。例：某厂按合同须于当年每个季度末分别提供例：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交每台起重机的成本如表所示，若生产出来的起重机当季

14、不交货，每台每积压一个季度工厂需支付保管及维护费货，每台每积压一个季度工厂需支付保管及维护费0.15万元，万元，试问在按合同完成任务的情况下，工厂应如何安排生产计划试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？才能使全年消耗的生产与存贮费用的总和最少？季度季度工厂生产能力（台工厂生产能力（台/季）季）成本（万元成本（万元/台）台）交货量（台）交货量（台）12510.81023511.101533011.002541011.3020发货点：生产起重机的四个季度发货点：生产起重机的四个季度发货量：生产能力发货量：生产能力收货点：按合同交付起重机的四个

15、季度收货点：按合同交付起重机的四个季度收货量：按合同提供起重机的数量收货量：按合同提供起重机的数量cij=第第i季度每台起重机的生产成本季度每台起重机的生产成本+（j-i）个季度每台起重）个季度每台起重机的存贮费（机的存贮费（ji）12345发量（台）发量（台）125235330410收量（台）收量（台）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.3000001）产地：原产地、中间转运站、转运物资的销地）产地：原产地、中间转运站、转运物资的销地2）销地：原销地、中间转运站、转运物资的产地）销地：原销地、中间转运

16、站、转运物资的产地3）设各转运站转运物资的数量均为）设各转运站转运物资的数量均为 ai这样专职转运站的产量和销量均为这样专职转运站的产量和销量均为 ai而原产地而原产地Ai的产量均为（的产量均为（ai+ ai）原销地原销地Bj的销量均为（的销量均为（ bj+ ai）4)将各条线路实际的运输单位列成单位运价表，其中不可能将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用的运输其单位运价用M表示。表示。A、B两个化肥厂每年各生产磷肥两个化肥厂每年各生产磷肥900万吨、万吨、600万吨，这万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口已知三个港口C、D、E每年能承担的船运量分别为每年能承担的船运量分别为700、400、300万吨，