第三章(运输问题)

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

2、资的运价为Cij，这些数据可，这些数据可 汇总于下表，在假设产销平衡的条件下，即汇总于下表，在假设产销平衡的条件下，即ai= bj，问该如，问该如 何调运物品使总运费最小？何调运物品使总运费最小？ B1B2Bn产量 A1C11C12C1na1 A2C21C22C2na2 AmCm1Cm2Cmnam 销量b1b2bn 建模：设建模：设xij表示从表示从Ai到到Bj的运量，则所求的的运量，则所求的 数学模型为：数学模型为： min =cijxij s.t. xij=ai i=1,m xij=bj j=1,n j=1 n i=1 m i=1 m j=1 n xij0 i=1,m,j=1,n 2.例如

3、例如：三个产地四个销地，用网络表示：三个产地四个销地，用网络表示 2 3 1 2 3 4 1b1=22 b2=13 b3=12 b4=13 a2=27 a3=19 a1=14 产地产地运价运价销地销地 6 7 5 3 4 8 2 7 5 9 10 6 产量产量 销量销量 总产量总产量60吨吨 总销量总销量60吨吨产销平衡的运输问题产销平衡的运输问题 0 13 12 13 22 19 27 14 6109572483576min 343332312423222114131211 342414 332313 322212 312111 34333231 24232221 14131211 3433

4、32312423222114131211 =+ =+ =+ =+ =+ =+ =+ += xxxxxxxxxxxx xxx xxx xxx xxx xxxx xxxx xxxxs.t. xxxxxxxxxxxxz 运输问题线性规划模型运输问题线性规划模型 产地约束产地约束 销地约束销地约束 运输问题的表格表示运输问题的表格表示 n j j m i i ba 11 3.2 表上作业法 n初始基可行解的确定初始基可行解的确定 n最优性检验最优性检验 n基变换基变换 运输问题基的表示运输问题基的表示 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1

5、 2 3 1234 1 2 3 基在运输表中的表示基在运输表中的表示 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 运输表中同行同列组成回路的变量运输表中同行同列组成回路的变量 一一. 初始基可行解的确定初始基可行解的确定 n西北角法西北角法 n最小元素法最小元素法 n沃格尔法沃格尔法 1.西北角法西北角法 8 13 13 14 6 6 方法：优先满足运输表中左上角空格的供销要求方法：优先满足运输表中左上角空格的供销要求 填一个数字只能划去一行或一列填一个数字只能划去一行或一列 2.最小元素法最小元素法 12

6、 0 15 13 0 1 13 0 2 19 3 0 1 2 0 2 0 0 方法：按单位运价的大小，决定供应的先后，优先方法：按单位运价的大小，决定供应的先后，优先 满足单位运价最小者的供销要求（就近供应）满足单位运价最小者的供销要求（就近供应） 3.沃格尔法沃格尔法 3 2 12 3 2 3 3 1 1 * 3 1 13 行罚数行罚数 列列 罚罚 数数 4 1 4 * 13 * 1 2 19 方法：计算出每一行及每一列中单位运价最小和次小的两个元素之方法：计算出每一行及每一列中单位运价最小和次小的两个元素之 间的差值，再从差值最大的行或列中找出单位运价最小者，优先满间的差值，再从差值最大的

7、行或列中找出单位运价最小者，优先满 足其供销关系。足其供销关系。 二二. 最优性检验求非基变量的检验数最优性检验求非基变量的检验数 n闭回路法闭回路法 n位势法位势法 1.闭回路法闭回路法 n方法方法 n意义：意义： 8 13 13 14 6 6 1.闭回路法闭回路法(1) 12 =c12-c22+c21-c11=7-4+8-6=5 5 8 13 13 14 6 6 1.闭回路法闭回路法(2) 5 13 =c13-c23+c21-c11=5-2+8-6=5 5 8 13 13 14 6 6 1. 闭回路法闭回路法(3) 55 14 =(c14-c34+ c33 - c23 + c21 -c11

8、)=3-6+10-2+8-6=7 7 8 13 13 14 6 6 1. 闭回路法闭回路法(4) 55 7 12 =c24-c34+ c33-c23=7-6+10-2=9 9 8 13 13 14 6 6 1. 闭回路法闭回路法(5) 55 7 9 32 =c32-c24+ c23-c33=9-4+2-10=-3 -3 8 13 13 14 6 6 1. 闭回路法闭回路法(6) 55 7 9 -3 31 =c31-c21+ c23-c32=5-8+2-10=-11 -11 2. 位势法位势法 该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为该法也称对偶变量法，我们知道一般标准运输问题的

9、对偶问题为 ： nj mi cvu vbuaMaxW ijji n j jj m i ii ,1 ,1 11 由由LP中中ij 的定义：的定义： ij =Cij-CBB-1Pij Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij = cij-(ui+vj) 对基变量而言：对基变量而言： 8 13 13 14 6 6 2. 位势法位势法(1) ui vj 0 6 2 20 10 -4 8 13 13 14 6 6 2. 位势法位势法(2) ui vj 0 6 2 20 10 -4 5 57 9 -13-3 0/min ijijlk 8 13 13 14 6 6 1.基变换基

10、变换-确定换入换出变量确定换入换出变量 55 7 9 -3-11-11 - - 6 8 13 13 14 6 6 1.基变换得新的基解基变换得新的基解 - - 6 212 13 13 14 1.基变换得新的基解基变换得新的基解 6 212 单纯形法与表上作业法比较单纯形法与表上作业法比较 单纯形法（单纯形法（Min）表上作业法表上作业法 确定初确定初 始基变始基变 量量XB +松驰变量松驰变量+（人工变量）（人工变量） XB系数矩阵为系数矩阵为I，m个个 其余其余XN 最小元素法、沃格尔法等最小元素法、沃格尔法等 XB数字格，数字格，m+n-1个个 XN 空格空格 检验数检验数 基变量基变量

11、j =0 非基变量非基变量 j =cj-cBB-1pj 基变量基变量 ij=0 非基变量非基变量 ij =cij-Ui-Vj 调整调整 进基：进基：min j j 0 出基：出基： minbi/aik，aik 0 进基：进基：min ij ijbj（产量（产量销量）所以要虚构一销销量）所以要虚构一销 地地B5，其销量，其销量b5=30，而，而ci5 =0，这样，就转化成了一个产销平衡问题。，这样，就转化成了一个产销平衡问题。 B1B2B3B4B5产量产量 A130508040030 A270408060050 A3100305020060 销量销量1510404530 B1B2B3B4产量产量

12、 A13113109 A219284 A3741057 销量销量136156 20 40 1）找出单位物资效益表（）找出单位物资效益表（cij）中的最大元素）中的最大元素M，即，即 M=maxcij 2)令令cij =M-cij，并视为运价。，并视为运价。 3）由）由cij构成单位运价表，按通常的表上作业法求解，求得构成单位运价表，按通常的表上作业法求解，求得 最优解后把所得结果转换为原问题的答案。最优解后把所得结果转换为原问题的答案。 （有最高需求和最低需求）（有最高需求和最低需求） 设销地设销地Bk的最低需求为的最低需求为bk，最高需求为，最高需求为bk” ，这时可把看作，这时可把看作 B

13、k和和Bk”两个销地，两个销地， Bk需求量需求量bk ，Bk”的需求量的需求量bk” - bk B1B2B3B4产量产量 A11613221750 A21413191560 A3192023M50 最低需求最低需求3070010 最高需求最高需求507030不限不限 B1B2B3B4产量产量 A11613221750 A21413191560 A3192023M50 最低需求最低需求3070010 最高需求最高需求507030不限不限 123 44 销量销量 30207030 A2 A3 A4 50 14 19 M 14 19 0 13 20 M 19 23 0 M 如下表，设销地如下表，设

14、销地1 1不允许缺货；销地不允许缺货；销地2 2缺货，单位损失费缺货，单位损失费3 3元；销地元；销地3 3缺货，缺货， 单位损失费单位损失费2 2元，问如何处理？元，问如何处理？ B1B2B3产量产量 A151710 A264680 A332515 销量销量655525 B1B2B3产量产量 A151710 A264680 A332515 销量销量655525 A440M32 如规定销地如规定销地1的需求量必须由产地的需求量必须由产地4供应，如何处理？供应，如何处理？ 1）直接令）直接令x41=b1 2)令令c41=-M，或者，或者c11=c21=c31=M这样销地这样销地1的需求量肯定是由

15、产地的需求量肯定是由产地1 供应了。供应了。 例：某厂按合同须于当年每个季度末分别提供例：某厂按合同须于当年每个季度末分别提供10、15、25、 20台同一规格的起重机，已知该厂各季度的生产能力及生产台同一规格的起重机，已知该厂各季度的生产能力及生产 每台起重机的成本如表所示，若生产出来的起重机当季不交每台起重机的成本如表所示，若生产出来的起重机当季不交 货，每台每积压一个季度工厂需支付保管及维护费货，每台每积压一个季度工厂需支付保管及维护费0.15万元，万元， 试问在按合同完成任务的情况下，工厂应如何安排生产计划试问在按合同完成任务的情况下，工厂应如何安排生产计划 才能使全年消耗的生产与存贮

16、费用的总和最少？才能使全年消耗的生产与存贮费用的总和最少？ 季度季度工厂生产能力（台工厂生产能力（台/季）季）成本（万元成本（万元/台）台）交货量（台）交货量（台） 12510.810 23511.1015 33011.0025 41011.3020 发货点：生产起重机的四个季度发货点：生产起重机的四个季度 发货量：生产能力发货量：生产能力 收货点：按合同交付起重机的四个季度收货点：按合同交付起重机的四个季度 收货量：按合同提供起重机的数量收货量：按合同提供起重机的数量 cij=第第i季度每台起重机的生产成本季度每台起重机的生产成本+（j-i）个季度每台起重）个季度每台起重 机的存贮费（机的存

17、贮费（ji） 12345发量（台）发量（台） 1 25 2 35 3 30 4 10 收量（台）收量（台） 10152520 30 10.8010.9511.1011.25 M11.1011.2511.40 MM11.0011.15 MMM11.30 0 0 0 0 1）产地：原产地、中间转运站、转运物资的销地）产地：原产地、中间转运站、转运物资的销地 2）销地：原销地、中间转运站、转运物资的产地）销地：原销地、中间转运站、转运物资的产地 3）设各转运站转运物资的数量均为）设各转运站转运物资的数量均为 ai 这样专职转运站的产量和销量均为这样专职转运站的产量和销量均为 ai 而原产地而原产地Ai的产量均为（的产量均为（ai+ ai） 原销地原销地Bj的销量均为（的销量均为（ bj+ ai） 4)将各条线路实际的运输单位列成单位运价表，其中不可能将各条线路实际的运输单位列成单位运价表，其中不可能 的运输其单位运价用的运输其单位运价用M表示。表示。 A、B两个化肥厂每年各生产磷肥两个化肥厂每年各生产磷肥900万吨、万吨、600万吨，这万吨，这 些化肥要通过公路运到三个港口，然后再装船运往其他各地，些化肥要通过公路运到三个港口，然后再装船运往其他各地， 已知三个港口已知三个港口C、D、E每年能承担的船运量分别为每年能承担的船运量分别为700、400、 300万吨，两