运筹学导论第八版5运输模型.pptVIP

运输算法运输算法的步骤与单纯形法完全一致第1步确定一个初始的基本可行解，转到第2步.第2步利用单纯形算法的最优性条件，在所有的非基变量中确定进基变量，如果最优性条件满足，停止。否则，转到第3步。第2步利用单纯形算法的可行性条件，在所有现有的基变量中确定离基变量，寻找新的基本解。返回第2步。5.3.1初始解的确定*一个具有m个起点和n个终点的一般运输模型包含(m+n)个约束方程，每一个起点和终点都对应一个约束方程。然而，因为运输模型总是平衡的（供需相等），这些约束方程中有一个是冗余的。因此，运输模型有(m+n-1)个独立的约束方程，即初始基本解由(m+n-1)个基变量组成，因此在例5.3-1中有3+4-1个基变量。运输问题可以采用西北角法（左上角法）、最小费用法、Vogel法（福格尔法）找到非人工的初始基本解。一般来说，Vogel法能够产生最好的初始基本解。最后得的初始基可行解。*西北角法34422223366总运费135.最后得的初始基可行解。*最小元素法31144363333总运费86.Vogel近似法(VAM)第1步对每一行(列)确定惩罚量：在每一行(列)中找到一个最小的以及次小的单位费用单元，惩罚量即为次小的单位费用减去最小的单位费用。第2步找出惩罚量最大的行或列。尽量分配给最小单位费用的单元最多的粮车，调整供应和需求，删去已满足的行或列。如果行和列同时满足，删去两者之一，分配给剩下的那个行(列)为零供应(需求)。第3步(a)如果仅有一个未被删去的零供应的行或零需求的列，则停止。(b)如果具有一个未被删去的大于零供应(需求)的行(列)，那么采用最小费用方法确定行(列)的基变量，停止(c)如果所有的未被删除的行和列都有零供应和零需求，那么采用最小费用方法确定零基变量。停止(d)否则，转到第1步。Vogel法求初始解求每行(列)次小和最小运价的差：7-25121123差中最大的先安排：第一行的x11x11*9573846Vogel法求初始解在最小运价的行或列中优先安排运量365145225218153315*Vogel法Vogel法的初始运输方案总运价：9573846345315110100885.3.2运输算法的迭代计算*确定初始解后，采用下面的算法确定最优解：第1步采用单纯形法的最优性条件，来确定能够改进解的作为当前非基变量的进基变量。如果最优性条件满足，停止，否则转第2步。第2步采用单纯形可行性条件确定离基变量。改变基，返回第1步。用乘子法计算z行的非基系数，来求出进基变量。在乘子法中，用ui和vi来表示运输表中第i行和第j列的乘子。对每一个现有的基变量xij，这些乘子满足ui+vj=cij，对于每一个基变量xijv1v2v3v4u1≡0u2u31234供应量1105210201115212759152052534416181010需求量5151515基变量(u,v)方程解x11u1+v1=10设置u1=0→v1=10x12u1+v2=2u1=0→v2=2x22u2+v2=7v2=2→u2=5x23u2+v3=9u2=5→v3=4x24u2+v4=20u2=5→v4=15x34u3+v4=18v4=0→u3=3u1=0，u2=5，u3=3v1=10，v3=4，v2=2，v4=15，进而使用ui和vj，计算每个非基变量的检验数ui+vj—cij的值。非基变量(u,v)方程x13u1+v3-c13=0+4-20=-16x14u1+v4-c14=0+15-11=-4x21u2+v1-c21=5+10-12=3x31u3+v1-c31=3+10-4=9x32u3+v2-c32=3+2-14=-9x33u3+v3-c33=3+4-16=-9基x11x12x13x14x21x22x23x24x31x32x33x34z00-16430009-9-90因为运输模型寻求最小化，进基变量是具有z行中最正系数的变量，因此，x31就是进基变量。*上述过程通常在运输表上进行。这不需要直接写出(u,v)方程，而是从设定u1=0开始。然后计算在第1行中有基变量的所有列的v值，即v1和v2，接下来，根据基变量x22的(u,v)方程计算u2，有