表上作业法在货物运输组织中的应用分析课程设计

1、运 输 工 程 课 程 设 计题 目 表上作业法在货物运输组织中的应用分析 院 (部) 专 业 班 级 学生姓名 学 号 运 输 工 程 课 程 设 计 任 务 书摘要运输是人们借助于运输工具，在一定交通路线上实施运输对象空间位移的有目地的活动。现代化的运输不仅需要具备现代化的运输通路、港站和运载工具等设施设备，同时还必须用科学的方法和手段合理组织运输生产，充分发挥各种运输方式的运能和优势，提高运输效率，降低运输成本，以便更好的满足社会生产和人民生活的需要。企业的生产过程需要消耗一定的资源，而资源总是稀缺的，因此合理利用现有资源，并将其将行合理分配，是充分发挥企业资源效能、提高企业综合经济效益

2、的必由之路。本文利用表上作业法求得了货物运输组织中的最小费原理，解决了物流公司在货物运输中所存在的问题，为物流公司的货物运输提供了一种行之有效的方法。通过建立物流配送模型，利用表上作业法解出最小运输成本，解决了降低运输成本问题，提升了物流公司的市场竞争力。 关键词：货物运输，表上作业发，应用实例分析。目录1 绪论61.1 课题的提出61.1.1 课题背景61.1.2 课题意义62 表上作业发62.1 表上作业发的具体介绍62.2 确定初始基本可行解82.1.1 最小元素法82.2.2 西北角法112.2.3 伏格尔法（vogel）112.3 基本可行解的最优性检验162.3.1 位势法162.

3、3.2 闭回路法203 表上作业法在实际中的应用223.1 产销平衡问题223.1.1 平衡问题模型233.2.3 数学模型的建立233.2 产销不平衡问题244 总结24参考文献261 绪论1.1 课题的提出1.1.1 课题背景运输问题是当今社会经济生活中经常出现的问题，在经济建设中，经常出现物资的调运问题，如何制定调运方案，将物资运往指定地点，而且实现运输费用最小，即为运输问题。运输问题是特殊的线性规划问题，它是现行网络最优化的一个例子。与一般线性规划问题不同的是它的约束方程组的系数矩阵具有特殊结构，这就需要采用不同甚至更为简约的方法来解决这种实际工作中遇到的问题。运输问题代表了物资合理调

4、运、车辆合理调度等问题。其他类型问题经过一系列改变后也可归结为运输问题。1.1.2 课题意义物品运输问题在当今经济建设中是十分常见的问题，运输问题及运输成本的优化是运输企业制定调运方案时必须要考虑的内容，如何选择一个合理的运输方案使的运输费用最低是十分关键的。表上作业法可以较好的解决这类问题。本文主要目地便是系统全面的对表上作业法进行研究。2 表上作业发2.1 表上作业发的具体介绍表上作业发的单纯形法在求解运输问题的一种简化方法，其实质是单纯形法，但具体计算和术语有所不同。从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把

5、该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 这个方法的基本思想是就近供应，即从运价表中最小运价开始确定调运量，然后次小，一直到给出初始调运方案为止.可归纳为：（1）找出基本可行解。即在（m*n）产销平衡表上用西北角法或最小元素法，vogel法给出m+n.1个数字，称为数字格。它就是初始基变量的取值。（2）求各非基变量的检验数，即在表上记载空格的检验数，判断是否达到最优解。如以是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基本可行解，在表上用闭环回路法调整。（4）重复（2）（3）知道得到最优解为止。以下通过实际原始材料研究表上作业发：设有5个产地

6、a1、a2、a3、a4、a5和4个销地b1、b2、b3、b4的运输问题，他们的供应量和需求量及单位运费如下表。表2.1供应量和需求量及单位运费b1b2b3b4供应量a110205710a213912820a34157930a41471040a531251950需求量60602010150表2.2供应量和需求量b1b2b3b4供应量a110a220a330a440a550需求量606020101502.2 确定初始基本可行解确定初始基本可行解一般的方法是既简便，有尽可能接近最优解，下面介绍最小元素法和vogel法。2.1.1 最小元素法最小元素法的基本思想就是就近供应，即从最小的运价开始确定供销

7、关系，然后次小。一直到给出初始基本可行解，以上述材料为例进行讨论。（1）从表2.1中找出最小运价为0，这表示先将a4的产品供应给b4，因为a4b4a4除满足b4的需求外，还可多余30的产品。在表2.2中的（a4,b4）的交叉处填上10，得表2.3。并将表2.1的b4列划去，得表2.4。表2.3计算过程表（1）b1b2b3b4供应量a110a220a330a41040a550需求量60602010150表2.4计算过程表（2）b1b2b3b4供应量a110205710a213912820a34157930a41471040a531251950需求量60602010150 （2）在表2.4中在找出

8、最小的运价1，确定a4中剩余30供应给b3，满足b3的需求量还多出10，并得出表2.5。并划去表2.1中的b3，得表2.6表2.5计算过程表（3）b1b2b3b4供应量a110a220a330a4201040a550需求量60602010150表2.6计算过程表（4）b1b2b3b4供应量a110205710a213912820a34157930a41471040a531251950需求量60602010150（3）在表2.6中找出最小运价为3。a5b1,所以a5里面的50全部供应给b1,还缺少10需求量，在从表中找出最小运价4，而b1只需求10，因此a3中止供应10给bi，还剩余20，由此的

9、表2.7。在表2.6中划去b1列，由于a5里的均已供应完，均划去，得表2.8。表2.7计算过程表（5）b1b2b3b4供应量a110a220a31030a4201040a55050需求量60602010150表2.8计算过程表（6）b1b2b3b4供应量a110205710a213912820a34157930a41471040a531251950需求量60602010150（4）现在只有b2的需求没有满足，所以a1,a2,a3,a4的全部供应给b2，刚好满足所有的供需量，由此的到表2.9。表2.9调运方案表b1b2b3b4供应量a11010a22020a3102030a410201040a5

10、5050需求量60602010150由表2.8可知，此方案的总费用为1o20+209+104+2015+107+201+0+503=960.2.2.2 西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 西北角法的基本思想是给产销平衡表左上角的变量分配运输量，以确定产销关系，依此类推，一直到给出初始可行方案为止。求解步骤如下：（1）先决定产销平衡表左上角变量 的值。令这个变量取尽可能大的值，即 ，在这个变量对应的数字格填上变量所取的值。（2）若，则

11、在第l行空格处打“”，这些空格不再赋值；若，则在第k列空格处打“”，这些空格不再赋值；若=，则在行的空格处打“”后，就不能在列的空格处打“”，反之，若在列的空格处打“”，就不在行空格处打“”。（3）对表上没有打“”的地方重复（1）， （2）步，直到所有格子都有标记止。 可以证明，用西北角法确定的初始方案是运输问题的一个初始基可行解，它也恰好包含m+n.1个数字格。2.2.3 伏格尔法（vogel）最大差额法是一行或一列的整体出发考虑，会更加合理。一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小费用调运时，运输量就会加多从而运费增加越多。因而对差额

12、最大处，要优先考虑，应当采用最小运费调运。最大差额法的具体步骤如下：（1）在表2.1中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表2.10。表2.10计算过程表（7）b1b2b3b4行差额a11020572a21391281a3415793a4147101a53125192列差额1247（2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表2.10中b4列是最大差额所在列。b4列最小元素为0，可确定a4产品先供应b4的需要。得表2.11。b4的需求量满足时，则在表2.11中划去b4，得表2.12。表2.11计算过程表（8）b1b2b3b4供应量a

13、110a220a330a41040a550需求量60602010150表2.12计算过程表（9）b1b2b3b4行差额a11020572a21391281a3415793a4147101a53125192列差额1247（3）在表2.12中，未划去的行和列中再分别计算出行差额和列差额，得表2.13。在表2.13中，a4为最大差额所在行，所对应的最小元素为b3列，则a4的成品供应给b3，a3里还有30个，b3需求30个，得表2.14。b3中的需求满足时，在表2.12中划去b3，得表2.15。2.13计算过程表（10）b1b2b3行差额a1102055a2139123a341573a414716a5

14、31252列差额124表2.14计算过程表（11）b1b2b3b4供应量a110a220a330a4201040a550需求量60602010150表2.15计算过程表（12）b1b2b3b4行差额a11020572a21391281a3415793a4147101a53125192列差额1247（4）在表2.15中，未划去的元素在进行计算出行差额和列差额，得表2.16.重复步骤（1），（2），可得表2.17。由于a1中的一全部供应完，则应划去，得表2.18。表2.16计算过程表（13）b1b2行差额a1102010a21394a34151a41477a53129列差额12表2.17计算过程表

15、（14）b1b2b3b4供应量a11010a220a330a4201040a550需求量60602010150表2.18计算过程表（15）b1b2b3b4行差额a11020572a21391281a3415793a4147101a53125192列差额1247一直重复步骤（1），（2），可得最终结果，如表2.19。表2.19调运方案表b1b2b3b4供应量a11010a22020a330 30a410201040a5203050需求量60602010150由表2.17可知，此方案的最优解为：1010+209+304+107+201+0+203+3012=910。由以上可见：最大差额法和最小元素

16、法除在确定供求关系的原则上不同外，其余步骤基本相同。最大差额法给出的初始解比用最小元素法给出的初始解更接近最优解。本例题用最大差额法给出的初始解就是最优解继续判别。2.3 基本可行解的最优性检验最优解的检验的方法是查看空格（非基变量）的检验数是否有不符合最优性条件的。为此，介绍空格检验数的求法。基可行解是否最优的判别法有闭回路法、位势法。2.3.1 位势法位势法是一种检验数的简便方法，设是运输问题的m+n个约束条件对应的对偶变量，决策变量对应的列向量，对于一个基可行解，由单纯形法得知所有基变量（数字格）的检验数等于0，即,所以由m+n.1个数字格对应的及即可确定所有的值。 称分别为产销平衡表各

17、行与各列的位势。 因为非基变量（空格）检验数，所以，只要计算出所有位势值，就能求出各空格的检验数。首先根据最大差额法得到的初始方案并假设行位势为u，列位势为v得到表2.20。表2.20位势计算表（1）b1b2b3b4供应量uia110【10】【20】【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.10）a330【4】【15】【7】【9】30u3（.6）a4【14】10【7】20【1】10【0】40u4（.12）a520【3】30【12】【5】【19】50u5（.7）需求量60602010150viv1（10）v2（19）v3（13）v4（12）然后，计算位势。可先建立

18、方程组，并据此计算出运输表各行和各列的位势，填入表2.21中。u1+v1=10 u2+v2=9 u3+v1=4 u4+v2=7 u4+v3=1 u4+v4=0 u5+v1=3 u5+v2=12由于方程数量为m+n.1个，而位势的数量为m+n个，所以无法直接求它们的值，但由于我们想得到的只是它们的相对关系，因此我们可以假设其中一个的数值，一般为了方便计算我们可以假设u1=0.解得：u1=0 u2=.10 u3=.6 u4=.12 u5=.7 v1 =10 v2=19 v3=13 v4=12。最后计算检验数。有了位势之后，即可由公式计算出各空格的检验数，如表2.21所示。当所有的检验数都为非负时，

19、方案即为最优的调整方案。否则为非最优，则需要调整。表2.21检验数表（1）b1b2b3b4供应量uia10【10】1【20】.8【5】.5【7】10u1（0）a213【13】0【9】9【12】6【8】20u2（.10）a30【4】2【15】0【7】3【9】30u3（.6）a416【14】0【7】0【1】0【0】40u4（.12）a50【3】0【12】.1【5】14【19】50u5（.7）需求量60602010150viv1（10）v2（19）v3（13）v4（12）当表中空格处出现负检验数时，表明未得到最优解。若有两个或两个以上的负检验数，一般选择其中较小的负检验数，以它对应的空格为调入格，即

20、以它对应的非基变量为换入变量。由表2.21得（1，3）为调入格。以此格作为出发点，作一个闭合回路，调整后的运输方案见表2.19。表2.22计算过程表（16）b1b2b3b4供应量a12810a22020a33030a418121040a5282250需求量60602010150再进行位势法判断：表2.23位势计算表（2）b1b2b3b4供应量uia1【10】【20】10【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.2）a330【4】【15】【7】【9】30u3（2）a4【14】20【7】10【1】10【0】40u4（.4）a530【3】20【12】【5】【19】50

21、u5（1）需求量60602010150viv1（2）v2（11）v3（5）v4（4）求出检验数见表2.23。表2.24检验数表（1）b1b2b3b4供应量uia18【10】9【20】0【5】3【7】10u1（0）a213【13】0【9】9【12】6【8】20u2（.2）a30【4】2【15】0【7】3【9】30u3（2）a416【14】0【7】0【1】0【0】40u4（.4）a50【3】0【12】.1【5】14【19】50u5（1）需求量60602010150viv1（2）v2（11）v3（5）v4（4）当表中空格处出现负检验数时，表明未得到最优解。以此格作为出发点，作一个闭合回路，调整后的运

22、输方案见表2.25，并算出位势数。表2.25 位势计算表（3）b1b2b3b4供应量uia1【10】【20】10【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.3）a330【4】【15】【7】【9】30u3（1）a4【14】30【7】【1】10【0】40u4（.5）a530【3】10【12】10【5】【19】50u5（0）需求量60602010150viv1（3）v2（12）v3（5）v4（5）求出检验数，见表2.26表2.26检验数表（3）b1b2b3b4供应量uia17【10】8【20】0【5】2【7】10u1（0）a213【13】0【9】10【12】6【8】20

23、u2（.3）a30【4】2【15】1【7】3【9】30u3（1）a416【14】0【7】1【1】0【0】40u4（.5）a50【3】0【12】0【5】14【19】50u5（0）需求量60602010150viv1（3）v2（12）v3（5）v4（5）检验数均为非负数，所以此为最佳方案。得最小运费为：820。2.3.2 闭回路法为了确定空格（i,j）的检验数，可以先找出以该空格为一个顶点，其余顶点全是数字格的闭回路。所谓闭回路，就是从该空格出发，沿水平方向或垂直方向前进，遇到合适的数字格后转90，继续前进，如果能够回到出发点，则称这个封闭折线为闭回路。该顶点通常记为第一个顶点，为奇数位，它的下一

24、个顶点为偶数位，下面的顶点依次奇偶相同，奇数位取正值，偶数位取负值，各数累加的和就等于（i,j）格的检验数。 可以证明，在任何可行方案中，以空格（i,j）为一个顶点，其余顶点全是数字格的闭回路存在而且唯一。下面以最大差额法的结果为例，对表2.19所有的非基变量的检验数计算过程如表2.27表2.27闭合回路检验过程非基变量闭合回路检验数x12x12x52x51x11x121x21x21x22x52x51x2113x32x32x52x51x31x322x41x41x42x52x51x4116x13x13x11x51x52x42x43x13.8x14x14x11x51x52x42x44x14.5x2

25、3x23x22x42x43x239x24x24x22x42x44x246x33x33x31x51x52x42x43x330x34x34x31x51x52x42x44x343x53x53x43x42x52x53.1x54x54x44x42x52x54 14 按上述做法，可计算出表2.27中的所有非基变量的检验数，把它们填入相应位置的方括号内，如表2.28所示：表2.28非基变量检验数b1b2b3b4供应量a110205710101.8.5a213912820132096a3415793030203a4147104016102010a5312519502030.114需求量60602010150表

26、格中所有的检验数不均为非负，这表明该方案不是最优，仍能调整，下面会介绍到。3 表上作业法在实际中的应用3.1 产销平衡问题产销平衡是指生产量与销售量相同，即ai=bi。公路货运企业时常会遇到若干货源地向若干需求地的货物运输问题，供货量与需求量不尽相同，怎样合理组织运输，满足货主的运输要求，同时使完成运输计划的运输费用最低，这是运输业制定计划时优先考虑的问题。显然，调运方案可以有很多个，但最优方案只有一个，表上作业法可以找到这个最优方案。表上作业法求解线性规划问题也是取迭代选优的办法，即给出一个初始可行方案，经过反复迭代，每次迭代使目标函数有所降低（以成本为目标函数），最后取得最优方案。3.1.

27、1 平衡问题模型已知有m个供应地点，ai，i=1，2，3，,m。可供应某种物资，其供应量分别为ai，i=1，2，3m,有n个销地bj，j=1，2，3，,n，其需求量分别为bj，j=1，2，3，,n。从ai到bj运输单位物资的运价为cij这些问题可以汇总到产销平衡表（3.1）和单位运价表（3.2）中。表3.1产销平衡表123n产量1a12a23a3mam销量b1b2b3bn表3.2单位运价表123n1c11c12c13c1n2c21c22c23c2n3c31c32c33c3nmcm1cm2cm3cmn3.2.3 数学模型的建立若用xij表示从ai到bj的用量，那么供需平衡的条件下，要求得总费用最小的调运方案，可求解一下数学模型：目标函数： 约束条