ch2第二节-表上作业法

§3.2运输问题求解—表上作业法表上作业法:建立在运输表上的求解运输问题的方法。由于运输问题系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。一、表上作业法求解思路（单纯形法完全类似）基本可行解是否最优解结束换基是否2为了表上求解方便，我们往往把单位运价表、产销平衡表合在一起列一个表：销产B1B2…Bn产量A1c11c12…c1na1x11x12x1nA2c21c22…c2na2x21x22x2n┇┇┇┇┇┇Amcm1cm2…cmnamxm1xm2xmn销量b1b1…bn表3-3运输问题求解作业数据表（运输表）运输问题解的每一个分量都惟一对应其运输表中一个格。表示作业时得出运输问题的一个基可行解后，就将基变量的值xij填入表中相应的格（Ai,Bj)内，这种格叫做填有数字的格含0数字）或数字格；非基变量对应的格不填数字称为空格。3产销平衡运输问题基变量（数字格）(1)个数:运输问题的基变量共有m+n-1个（因为此时问题系数矩阵A的秩为m+n-1)。(2)条件：运输问题的m+n-1个变量构成基变量的充分必要条件是不构成闭回路。二、几点说明闭回路及其顶点在表3-3的决策变量格中，凡是能够排列成下列形式的xab,xac,xdc,xde,…,xst,xsb(3.3)或xab,xcb,xcd,xed,…,xst,xat(3.4)其中，a,d,…,s各不相同；b,c,…,t各不相同，我们称之为变量集合的一个闭回路，并将式（3.3）、式（3.4）中的变量称为这个闭回路的顶点。4例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：根据定义可以看出闭回路的一些明显特点：(1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；(2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。5关于闭回路有如下的一些重要结论：(1)设xab,xac,xdc,xde,…,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量pab,pac,pdc,pde,…,pst,psb线性相关；(2)若变量组xab,xcd,xef,…,xst中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量pab,pcd,pef,…,pst线性相关。根据上述结论以及线性规划基变量的特点，可以得到下面重要定理及其推论。定理3.1变量组xab,xcd,xef,…,xst所对应的系数列向量pab,pcd,pef,…,pst线性无关的充分必要条件是这个变量组中不包含闭回路。推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。7三、表上作业法的计算步骤(1)找出初始基可行解（初始调运方案）。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法、西北角法或伏格尔法）(2)求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)对方案进行改善，找出新的调运方案。（表上闭回路法调整）确定m+n-1个基变量(4)重复（2）、（3），直到求得最优调运方案。空格（一）初始调运方案的确定根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到m+n–1个不构成闭回路的基变量。一般步骤如下：(1)在运输问题求解作业数据表中任选一个单元格xij(Ai行Bj列交叉位置上的格),令xij=min{ai,bj}即从Ai向Bj运最大量(使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足),填入xij的相应位置；8(2)从ai和bj中分别减去xij的值，修正为新的ai和bj即调整Ai的拥有量及Bj的需求量；(3)若ai=0，则划去对应的行（已经把拥有的量全部运走），若bj=0则划去对应的列（已经把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；否则在剩下的运输平衡表中选下一个变量，返回(1)。按照上述方法所产生的一组变量的取值将满足下面条件：(1)所得的变量均为非负，且变量总数恰好为m+n–1个；(2)所有的约束条件均得到满足；(3)所得的变量不构成闭回路。因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有给予限制，若采取不同的规则来选取xij，则得到不同的方法，较常用的方法有最小元素法和Vogel法。910例3.2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？1、求初始方案：最小元素法、西北角法、伏格尔法4321BBBB321AAA基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。B1B2B3B4产量A17A24A39销量3656410总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元1.最小元素法311310192758341633方法：按运价由小到大顺序从运价最小的格开始，在格内的右下角标上允许取得的最大数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。然后次小运价填数。从如此进行下去，直至得到一个基本可行解。12练习销地产地B1B2B3B4产量A1675314A2842727A35910619销量2213121312131319122.西北角法（或左上角法）此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036在满足约束条件下尽可能的给最左上角的变量最大值.销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214488864814所以，初始基可行解为：(8,8,4,8,14)目标函数值Z＝372例3.3某运输资料如下表所示：练习销地产地B1B2B3B4产量A1675314A2842727A35910619销量221312138131314663．Vogel法（元素差额法）最小元素法的缺点：按某一最小单位运价优先调运，为了节省一处的费用，有时造成在其他处要多花几倍的运费，从而使整个运费增加。Vogel法的思想：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就会有一个差额。最小和次小单位运价之间的差额（称为罚数）。若罚数的值不大，当不能按最小单位运价调运时造成的损失就不大；反之，如果罚数的值很大，不按最小单位运价组织调运就会运费增加很多。故应对罚数最大处，采用最小运费调运。17Vogel法的步骤：（1）计算每行和每列的最小单位运价和次小单位运价（相同的元素重复算）之间的差值，并称之为行罚数和列罚数。将算出的行罚数填入运输表右侧行罚数栏左边第一列相应格子中，列罚数填入运输表下边列罚数栏的第一行的相应格子中。18用Vogel法重解上例，见下表。(2)从所有罚数中选出最大者，选择他所在行或列中的最小元素格填数，满足最大的需要量。如出现几个相同的最大差额，可任取一行或一列。若某行（或某列）的产量（销量）已用尽，则把这一行（列）划去。19销地产地A1A2A3B1B2B3B4产量销量行罚数331110192874105749665320011253162354112345列罚数（3）对表中尚未划去的元素重复以上步骤，直到给出初始调运方案为止。20销地产地A1A2A3B1B2B3B4产量销量行罚数3311101928741057496653200112531623411234列罚数01221330121231276512总运费=85元21练习销地产地B1B2B3B4产量A1675314A2842727A35910619销量221312131213121319注:应用最小元素法和Vogel法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0，以示数字格（与空格区别）。2223二、最优解的判别（检验数的求法）求检验数的方法有两种：闭回路法对偶变量法（位势法）（1）闭合回路法：σij≥0（因为目标函数要求最小化）表格中有调运量的地方即数字格为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij0表示运费减少，σij0表示运费增加。24闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。注：1.每一空格有且仅有一条闭回路；2.如果某数字格有闭回路，则此解不是可行解。1、闭回路法为了方便，我们以（表3-4）最小元素法给出的初始调运方案为例，考察初始方案的任意一个非基变量即空格，比如x24。根据初始方案，产地A2的产品是不运往销地B4的。如果现在改变初始方案，把A2的产品运送1个单位给B4，那么为了保持产销平衡，就必须使x14或x34减少1个单位；而如果x14减少1个单位，第1行的运输量就必须增加1个单位，例如x13增加1个单位，那么为了保持产销平衡，就必须使x23减少1个单位。25[x24]+1C13=3C23=2C24=8C14=10-1+1-1这个过程就是寻找一个以非基变量x24为起始顶点的闭回路——{x24，x14，x13，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为c24-c14+c13-c23=8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。26表3-5中用虚线画出以非基变量x22为起始顶点的闭回路.表3-5以非基变量x22为起始顶点的闭回路27销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A3可以计算出以空格（非基变量）x22为起始顶点的闭回路调整使总的运输费用发生的变化为c22-c23+c13-c14+c34-c32=9–2+3–10+5–4＝1即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个空格（非基变量）增加一个单位时，有若干个数字格（基变量）的取值受其影响。28这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。如果规定作为起始顶点的非基变量为第1个顶点，闭回路的其他顶点依次为第2个顶点、第3个顶点……，那么就有ij=(闭回路上的奇数次顶点单位运费之和)-(闭回路上的偶数次顶点单位运费之和)其中ij为非基变量的下角指标。29按上述做法计算出表3-4所有空格的检验数22=1，24=-111=c11-c13+c23-c21=112=c12-c14+c34-c32=231=c31-c34+c14-c13+c23-c21=1033=c33-c34+c14-c13=1230显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。24=-10,此方案不最优。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。31练习销地产地B1B2