运输问题_表上作业法

4.2表上作业法表上作业法表上作业法与单纯形法的关系表上作业法的基本步骤确定初始基可行解最小元素法的基本步骤伏格尔法三、运输问题的求解运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。1.表上作业法2.表上作业法与单纯形法的关系表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；表上作业法中的“位势法”实质上是在求单纯形表中的检验数；调运方案表中数字格的数实质上就是单纯形法中基变量的值；调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。（1）找出初始基可行解：m+n-1个数字格（基变量）；（2）求各非基变量（空格）的检验数。,那么选取xij为入基变量；（3）确定入基变量，若min{|0}ijijlk3.表上作业法的基本步骤（4）确定出基变量，找出入基变量的闭合回路；（5）在表上用闭合回路法调整运输方案；（6）重复2、3、4、5步骤，直到得到最优解。4、确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解）。最小元素法（theleastcostrule）和伏格尔法（Vogel’sapproximationmethod）。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止.最小元素法找出最小运价，确定供求关系，最大量的供应；划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；在剩余的运价表中重复1、2两步，直到得到初始基可行解。5、最小元素法的基本步骤最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。表4-1甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656最小元素法的应用（以引例4-1为例）第一步：从表4-1中找出最小运价“1”，最小运价所确定的供应关系为（B，甲），在（B，甲）的交叉格处填上“3”，形成表4-2；将运价表的甲列运价划去得表4-3.甲乙丙丁产量（ai）A7B4C9销量（bj）3656甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-2表4-33第二步：在表4-3的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（B，丙），即将B余下的1个单位产品供应给丙，表4-2转换成表4-4。划去B行的运价，划去B行表明B所生产的产品已全部运出，表4-3转换成表4-5。甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-3甲乙丙丁产量（ai）A7B4C9销量（bj）3656甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-4表4-531甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-5第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。表4-7甲乙丙丁产量（ai）A7B4C9销量（bj）3656表4-6甲乙丙丁产量（ai）A311107B1984C7109销量（bj）36563213446533最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。在供需关系格（i，j）处填入一数字，刚好使第i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。6.应注意的问题为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。表4-7甲乙丙丁产量（ai）A3113104B19284C7410512销量（bj）3656表4-8甲乙丙丁产量（ai）A4B4C12销量（bj）36563147.举例将例4-1的各工厂的产量做适当调整（调整结果见表4-7），就会出现上述特殊情况。066每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。8.伏格法尔法伏格尔法的基本步骤：8.伏格尔法1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。表4-1甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-12甲乙丙丁两最小元素之差A311310B1928C7105两最小元素之差13011254表4-13甲乙丙丁产量（ai）A7B4C9销量（bj）3656表4-14甲乙丙丁两最小元素之差A311310B1928C7410两最小元素之差562130125表4-15甲乙丙丁产量（ai）A7B4C9销量（bj）365663表4-16甲乙丙丁两最小元素之差A311310B928C74105两最小元素之差212011表4-17甲乙丙丁产量（ai）A7B4C9销量（bj）3656633表4-18甲乙丙丁两最小元素之差A31110B1928C74105两最小元素之差12673表4-19甲乙丙丁产量（ai）A7B4C9销量（bj）3656表4-20甲乙丙丁两最小元素之差A311310B192C74105两最小元素之差63352812总运费为85由以上可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤是完全相同的。伏格尔法给出的初始解比最小元素法给出的初始解一般来讲会更接近于最优解。表4-23甲乙丙丁产量（ai）A7B4C9销量（bj）36566335124.2.2基可行解的最优性检验对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个空格存在唯一的闭回路。所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。1.闭合回路下面就以表4-6中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论闭合回路法。表4-24甲乙丙丁产量（ai）A437B314C639销量（bj）3656（+3）（-3）（+2）（-1）从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对于空格（A，甲）在初始方案的基础上将A生产的产品调运一个单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数字格（基变量）组成的闭合回路。表4-24中用虚线画出了这条闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。对应这样的方案调整，运费会有什么变化呢？可以看出（A，甲）处增加一个单位，运费增加3个单位；在（A，丙）处减少一个单位，运费减少3个单位；在（B，丙）处增加一个单位，运费增加2个单位；在（B，甲）处减少一个单位，运费减少1个单位。增减相抵后，总的运费增加了1个单位。由检验数的经济含义可以知道，（A，甲）处单位运量调整所引起的运费增量就是（A，甲）的检验数，即σ11=1。表4-24甲乙丙丁产量（ai）A437B314C639销量（bj）3656（+3）（-3）（+2）（-1）仿照此步骤可以计算初始方案中所有空格的检验数，表4-25～表4-30展示了各检验数的计算过程，表4-30给出了最终结果。可以证明，对初始方案中的每一个空格来说“闭合回路存在且唯一”。表4-25甲乙丙丁产量（ai）A11=1（+11）43（-10）7B314C6（-4）3（+5）9销量（bj）3656表4-26甲乙丙丁产量（ai）A11=112=24（+3）3（-10）7B3（+9）1（-2）4C6（-4）3（+5）9销量（bj）3656表4-27甲乙丙丁产量（ai）A11=112=24（+3）3（-10）7B322=11（-2）（+8）4C639销量（bj）3656表4-28甲乙丙丁产量（ai）A11=112=24（-3）3（+10）7B322=1124=-14C6（+10）3（-5）9销量（bj）3656表4-29甲乙丙丁产量（ai）A11=112=24（-3）3（+10）7B3（-1）22=11（+2）24=-14C（+7）633=123（-5）9销量（bj）3656表4-30甲乙丙丁产量（ai）A11=112=2437B322=1124=-14C31=10633=1239销量（bj）3656如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方案。在表4-30中，24=-1,说明方案需要进一步改进。2.位势法对于特定的调运方案的每一行给出一个因子ui（称为行位势），每一列给出一个因子vj（称为列位势），使对于目前解的每一个基变量xij有cij=ui+vj，这里的ui和vj可正、可负也可以为零。那么任一非基变量xij的检验数就是)(jiijijvuc这一表达式完全可以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表所示），由于基变量的运价等于其所对应的行位势与列位势之和，即：kiikvuckllkvucjlljvuclkxlukv非基变量基变量ijxiuljxjv（-cik）基变量ikx（+clk）基变量（+cij）（-clj）于是所以)()()(jlklkiijljlkikijijvuvuvuccccc)(jiijijvuc对于一个具有m个产地、n个销地的运输问题，应具有m个行位势、n个列位势，即具有“m+n”个位势。运输问题基变量的个数只有“m+n-1”个，所以利用基变量所对应的“m+n-1”个方程，求出“m+n”个位势，进而计算各非基变量的检验数是不现实的。通常可以通过在这些方程中对任意一个因子假定一个任意的值（如u1=0等等），再求解其余的“m+n-1”个未知因子，这样就可求得所有空格（非基变量）的检验数。仍以表4-6中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论位势法求解非基变量检验数的过程。第一步：把方案表中基变量格填入其相应的运价并令u1=0；让每一个基变量xij都有cij=ui+vj，可求得所有的位势，如表4-32所示。iujv表4-32甲乙丙丁A310B12C45第二步：利用)(jiijijvuc计算各非基变量xij的检