表上作业法(共9页)

1、精选优质文档-倾情为你奉上表上作业法 什么是表上作业法表上作业法是指用列表的方法求解问题中的计算方法。是线性规划一种求解方法。当某些线性规划问题采用难以进行直观求解时，就可以将各元素列成，作为初始方案，然后采用检验数来验证这个方案，否则就要采用、等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。 表上作业法的步骤1、找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用、； （1）： 从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行

2、解。 （2）： 从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。 2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用计算； 问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，

3、据此： ij = cij (ui + vj) ,其中前m个计为,前n个计为 由可知，基变量的ij = 0 cij (ui + vj) = 0因此ui,vj可以求出。 3、改进当前的基本可行解（确定换入、换出变量），用调整； （因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数ij = 0，非基变量的检验数。ij < 0表示运费减少,ij > 0表示运费增加。 4、重复，直到找到最优解为止。 表上作业法计算中的问题1、无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的ij = 0，则该问题有无穷多最优解。 2、退化 表格中一般要有(m+

4、n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。 表上作业法案例分析 案例一:表上作业法在物流配送中的应用 是的一项十分重要的功能。随着的发展，迅速增加，各个物流公司之间的竞争日趋激烈。如何加强管理以减少成本问题成为各物流公司非常关注的话题。一般来说，数量减少，距离客户的距离就会越长，就越高;配送中心数量增多，配送中心距离客户的距离就会缩短，就越少，但是配送中心的管理成本随之增加。本文讨论利用现有的配送中心向客户的配送问题，寻求最小的配送成本。 一、配送模型的建立与求解 1.配送模型

5、的建立。物流公司常常在某个地区有多个配送中心来供应货物，每个都有一定的供应量。配送货物的客户也往往不止一个，多个客户更为常见。ai(i=1，2，3，m)表示不同的配送中心货物供应量，m表示配送中心的数量。bj(j=1，2，3,n)表示不同客户需求的货物量，n表示量客户的数量。从配送中心到客户的单位配送价格用c_ij表示。这些数据可用表1来表示。 若用xij表示从ai到bj的实际供应量，那么在供需平衡的条件下，要求得总运费最小的配送方案，可求解以下数学模型: 2.表上作业法对模型的求解。利用一般的求解方法很难求得上述数学模型的解，但是根据运筹学的相关内容来求解就相当容易了。求解的步骤分三步:首先

6、用最小元素法求出初始可行解，再采用闭合回路法判断是否最优，最后采用闭合回路调整法调整变量直至最优解。 以最小单位配送价格运价开始配送，从单位配送价格最小到最大顺序逐一使供需量平衡，配送中供需达到规定量的可以从表上划掉。根据表上求得的结果可以得到最小的配送成本。最小元素法的缺点是:为了节省某一配送中心的费用，可能造成其他配送中心几倍的配送成本，所以必须对上述的结果进行检验。 检验的方法采用闭合回路法，即从表上任一个空格出发，沿水平或垂直方向前进，每遇到一个适当数字(有利于回到原空格)转90°,继续前进直到回到原空格。当所有检验数，则就是最优解，否则还需要继续改进。 当有的空格检验数小于

7、0时，说明此空格应当使用。改进的方法采用闭合回路调整法，从检验数是负数的空格开始，沿闭回路前进取数字的最小值，使用闭回路转角的数加减这个数。然后再次使用闭合回路法检验所有空格的检验数，所有检验数大于0则就是最优解，否则再继续改进，直至最优。 二、物流公司配送实例 某物流公司给四个客户甲、乙、丙和丁配送货物，配送量分别为3吨、6吨、5吨和6吨。物流公司在该地区有三个配送中心，每个配送中心的货物供应量分别为7吨、4吨和9吨。由于各个配送中心距离客户的距离不一样，所以配送货物的也不同。需求量和供应量及价格数据如表2所示。其中价格单位为万元/吨。 1.最小元素法求出初始可行解。物流公司在配送货物时，除

8、了考虑准时、安全送达货物以外，尽可能减少配送成本。首先以最小开始配送，从单位价格最小到最大顺序逐一使供需平衡，配送中供需达到规定量的划掉。从上表中找到最低配送单位价格为2.1万元/吨，由于甲客户需求量为3吨，物流中心2的供应量为4吨，取min3 4=3填入表中，甲客户一栏需求量达到规定量，把甲客户一栏划去，如表3所示。 再从表中未划去的价格中找到最小价格开始配送，这时最小的单位价格为2.2万元/吨。由于丙客户需求量为5吨，而物流中心2的供应量仅为4吨且已经配给甲客户3吨，故配给丙客户只能1吨，取min5 1=1填入表中，物流中心2一行供应量达到规定量，把物流中心2一行划去，如表4所示。 同理:

9、按照上面的做法一直划下去，最后的结果如下表5所示。 最后可得到最小配送成本为: Zmin=4×2.3+3×3.0+3×2.1+1×2.26×2.43×2.5 (万元)。 2.闭合回路法判断最优解。上表中未填入数字的称之为空格，需要计算所有空格的检验数，若检验数全部大于等于0，则上述填入的数字为最优解，否则不是最优解，需要进一步计算。 图中的空格(11)闭合回路，可采取空格(11)空格(13)空格(23)空格(21)空格(11)组成回路。如下表6所示。 检验数： 同理,空格(12)、空格(22)、空格(24)、空格(31)和空格(33)

10、的检验数分别为:K12 = 0.2,K22 = 0.1,K24 = 0.1,K31 = 1和K33 = 1.2。 空格检验数K24 = 0.1为负数，所以上述不是最优解。 3.闭合回路调整法对上述变量进行调整。由于K24 = 0.1，故空格(24)必须要使用，先对(24)转角进行调整。取转角最小值min1，3，4=1填入空格(24)中，其空格(24)转角值相应做出如下调整，如表7所示。 调整后的空格检验数如下： K11 = 0,K12 = 0.2,K22 = 0.2,K23 = 0.1,K31 = 0.9,K33 = 1.2 所有空格检验数均为正数，说明上表中的解为最优解。即，物流中心1给丙客

11、户配送5吨货物，给丁客户配送2吨货物；物流公司2给甲客户配送3吨货物，给丁客户配送1吨货物。物流中心3给乙客户配送6吨货物，给丁客户配送3吨货物。此时物流公司的配送最小。 Zmin=5×2.32×3.0+3×2.11×2.86×2.43×2.5(万元)。 从计算结果可以看出，最优解比初始可行解又降低了0.1万元。 通过建立物流配送模型，利用表上作业法解出最小配送成本，解决了降低配送中心的配送成本问题，提升了物流公司的图上作业法什么是图上作业法图上作业法在运输图上求解线性规划运输模型的方法。它是在一张运输交通上通过一定步骤的规划和计算来

12、完成物资调运的编制工作，以便使运行的总吨公里数最小可使物资运费降低，并缩短了运输时间，所以，在一定条件下称这样的方案为最优方案。 图上作业法的步骤制定一个物资调运方案时： 1、首先要编制（如下图所示）。 图1：物资平衡表 在编制物资平衡表时需要做3件事。 (1)出需要调出的地点（即发点）及发量。 (2)出需要调进物资的地点（即收点）及收量。 (3)求：总发量=总收量。 2、第二步，根据物资平衡表和收点，发点间的相互位置绘制交通图。所谓交通图就是表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图上，用圆圈“”表示发点，将该发点的发量填入圆圈“”内。用方框“”表示收点，将该

13、收点的收量填入方框“”内。两点间的距离，记在交通线路的旁边。 3、第三步，交通图绘制好后，即可在其上面进行物资调运，找出初始调运方案(初始基可行解)，作物资调运流向图。 我们用箭头“”表示物资调运的方向即称流向，并规定：流向“”必须画在沿着线路前进的右侧。把运送物资的数量记在流向“”的旁边并加括号（ ），以区别于两点之间的距离数。 另一方面，为了保持图面的整洁，流向量最好不要通过收，发点以及交叉路口，如图1中，(a)，(b)是正确的。 图上作业法的注意事项在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨公里数是最小的调运方案。这就要注意在调运中不要发生和，因此

14、，我们在制定流向图时，就要避免它的出现。 （1）对流：所谓对流就是在一段线路上有同一种物资往返运输（同一段线路上，两各方向都有流向），如下图。 图2 图3 将某种物资10吨从A1运往B2，同时又有同样的物资10吨同时从A2运往B1，于是在A1A2之间就出现了对流现象.如果把流向图改成图3，即将A1的10吨运往B1，而将A2的10吨运往B2，就避免了A1A2的对流，从而可以节约运输量(吨公里)。 （2）迂回：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如下图4所示。 图4 图5 显然，它是一个迂回运输流向图，它的内圈长6大于整个圈长的一半5。如果把它改成图5，就避免了迂回现象，可节约运输量（吨公里）理论上可以证明，一个物资调运方案中，如果没有对流和，则该方案就是最优调运方案。即运输量最小的方案。 从以上讨论可以看到，图上作业法的实质就是在一张