表上作业法汇编.ppt

表上作业法

表上作业法例3.2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？

表上作业法解：第1步求初始方案方法1：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。B1B2B3B4产量A17A24A39销量3656311310192741058341633

表上作业法总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是z=10×8+5×2+15×1=105最小元素法：

表上作业法85102120151551510总运费z=10×5+15×2+5×1=85后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。

表上作业法方法2：Vogel法1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A177A241A391销量3656列差额2513311310192741058

表上作业法2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。B1B2B3B4产量行差额A177A241A391销量3656列差额25133113101927410585

表上作业法单位销地运价产地产量行差额311310719284741059销量3656列差×

表上作业法单位销地运价产地产量行差额311310719284741059销量3656列差额7135275×××3×

表上作业法单位销地运价产地产量行差额311310719284741059销量3656列差额113515×××3×631××2该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元

表上作业法第2步最优解的判别（检验数的求法） 求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：闭回路法位势法（▲）

表上作业法用位势法对初始方案进行最优性检验：1）由?ij=Cij-（Ui+Vj）计算位势Ui，Vj，因对基变量而言有?ij=0，即Cij-（Ui+Vj）=0，令U1=02）再由?ij=Cij-（Ui+Vj）计算非基变量的检验数?ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）当存在非基变量的检验数?kl≥0，说明现行方案为最优方案，否则目标成本还可以进一步减小。

表上作业法当存在非基变量的检验数?kl0且?kl=min{?ij}时，令Xkl进基。从表中知可选X24进基。第3步确定换入基的变量第4步确定换出基的变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示换出作为非基变量。

表上作业法B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。125

表上作业法当所有非基变量的检验数均非负时，则当前调