《《运筹学教学资料》运筹学第3章第2节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第3章第2节.ppt（56页珍藏版）》请在三一办公上搜索。
1、3.2 表上作业法,表上作业法是一种求解运输问题的特殊方法，其实质是单形法。,迭代过程中得出的所有解都要求是运输问题的基可行解,表上作业法,给定下列运输问题,分析：由于总产量是9+5+7=21，总销量是3+8+4+6故产销平衡。该问题有3个产地，4个销地，故基可行解含有3+4-1=6个基变量。,例1,表上作业法,第1步 求初始方案,运输问题的初始方案的确定主要有三种方法：,.西北角法,.最小元素法,.伏格尔法,运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）,它的初始基的确定具有一定的难度。,表上作业法,1.西北角法（左上角法）,西北角法每次都从运价表的左上角确定基变量。算法的每一步都取
2、最左上角的元素（如xij）为基变量，其取值是相应行列产销量的最小者，即,然后划去产销平衡运输表中的一行或一列得到一个新的产销平衡运输表。再重复上述过程直至得到问题的运输方案。具体的算法过程如下：,表上作业法,令 x11为基变量，销地B1的销量全由产地A1供给，所以x21=0,x31=0,x21与x31为非基变量。将x11=填到调运方案表中第1行第1列上。画去运输数据表中第1列,A1 的产量剩余为9-3=6。得到新的产销平衡运输表。,例如对于前面的例子：,西北角法计算1,表上作业法,令x12为基变量，则,产地A1的产量6全供给销地B2，所以 x13=x14=0，x13与x14 为非基变量。将x1
3、2 6 填到调运方案表中第1行第2列上。,画去运输数据表中第1行，B2 的销量还要8-6=2。得到新的产销平衡运输表。,西北角法计算2,表上作业法,令x22为基变量，则,销地B2的销量2全由产地A2供给，所以x32=0，x32为非基 变量。将x22 2 填到调运方案表中第2行第2列上。,画去运输数据表中第2列，A2 的产量剩余为 5-2=3。得到新的产销平衡运输表。,西北角法计算3,表上作业法,令x23为基变量，则,产地A2的产量3全供给销地B2，所以x24=0，x24为非基变量。将x23 3 填到调运方案表中第2行第3列上。,画去运输数据表中第2行，B3 的销量剩余为 4-3=1。得到新的产
4、销平衡运输表。,西北角法计算4,表上作业法,现在只有一个产地两个销地，故令x33=1，x34=6为基变量，将其分别填到调运方案表中第3行第3列与第3行第4列上。,得到产销平衡运输问题的一个初始方案,西北角法计算5,表上作业法,这个方案的运费是23+96+32+43+21+56=110。表中填了6个数值，正好对应基变量，即6=m+n 1=3+4-1,其余未填数字的空格位置的数值为0,对应非基变量.西北角法确定的初始方案没有考虑运价的影响，因而离最优方案相去甚远。,评 注,表上作业法,2.最小元素法,最小元素法的基本思想是就近供应；即从运价表中最小的运价开始确定供销关系.若有几个最小运价，则任取其
5、一。,最小元素法和西北角法大体差不多，只是考虑了运价的因素。,用最小元素法求得的基本可行解更接近最优解，所以也称为近似方案。,表上作业法,销地B1的销量3全由产地A2供给，所以x11=x31=0。将x213填到调运方案表中第2行第1列上。,最小元素法计算1,画去运输数据表中第1列，A2的产量剩余为5-3=2。得到新的产销平衡运输表。,表上作业法,最小元素法计算2,产地A2的产量2全供给销地B4，所以x22=x23=0。将x24 2填到调运方案表中第2行第4列上。,画去运输数据表中第2行，B4 的销量还要 6-2=4。得到新的产销平衡运输表。,表上作业法,最小元素法计算3,销地B3的销量4全由产
6、地A3供给，所以x13=0。将x334填到调运方案表中第3行第3列上。,画去运输数据表中第3列，A3的产量剩余为7-4=3.得到新的产销平衡运输表。,表上作业法,最小元素法计算4,产地A3的产量3全供给销地B2，所以x34=0，将x32=3填到调运方案表中第3行第2列上。,画去运输数据表中第3行，B2的销量剩余为8-3=5。得到新的产销平衡运输表。,表上作业法,最小元素法计算5,现在只有一个产地两个销地，故令x12=5,x14=4为基变量，将其分别填到调运方案表中第1行第2列与第1行第4列上。,得到产销平衡运输问题的一个初始方案,表上作业法,评注,此调运方案的运费：31+59+34+42+22
7、+47=100 比用西北角法初始方案好些最小元素法确定的初始方案往往缺乏全局的观点，即为了节省一处的运费，而在其它处要多花更大的运费。,表上作业法,伏格尔法的主要思想是：,3.伏格尔法,一产地的产品如若不能按最小运费就近供应，就考虑按次小运费供应，这里存在一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，应当采用最小运费调运。,表上作业法,伏格尔法计算1,用伏格尔法寻找初始基：,先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。从行差或列差中选出最大者，并选择其所在行或列的最小元素。,A1的行差最大，而其中运价c11最小,令x11为
8、优先运输路线。,表上作业法,用伏格尔法寻找初始基：,销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3 填到调运方案表中第1行第1列上。,画去运输数据表第一列，A1的产量剩余为9-3=6。得到新的产销平衡与单位运价表.,令,伏格尔法计算1,表上作业法,用伏格尔法寻找初始基：,再算出运价表中的行差与列差。,B4的列差最大，而其中运价c24最小,令x24为优先运输路线。,产地A2的产量2全供给销地B4，所以x23=x24=0。,画去运输数据表中第2行，B4的销量还要6-5=1。得新表。,令,伏格尔法计算1,表上作业法,用伏格尔法寻找初始基：,伏格尔法计算1,表上作业法,用伏格尔
9、法寻找初始基：,伏格尔法计算1,表上作业法,用伏格尔法寻找初始基：,现在只有一个产地两个销地，故令x12=5,x14=1为基变量，将其分别填到调运方案表中1行2列与1行4列上。,得到产销平衡运输问题的一个初始方案,伏格尔法计算1,表上作业法,此方案的运费是32+59+47+52+34+42=88。伏格尔法给出的初始解往往更接近于最优解。,表上作业法,评价：,西北角法、最小元素法与伏格尔法除在确定供求关系的规则上不同外，其它步骤完全相同。,对于一个有m个产地n个销地的运输问题，需要进行m+n-2步以确定初始方案，每一步要划去其中的一行或一列，最后得到m+n-1个运输路线，对应m+n-1个基变量。
10、,表上作业法,西北角法,最小元素法,伏格尔法,表上作业法,第2步 最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优,求检验数的方法有两种：闭回路法 位势法（）,表上作业法,为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。,闭回路法,表上作业法,下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,表上作业法,对于一条给定的闭回路,数
11、据表上的每一行、每一列至多只有两个变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的顶点）。,闭回路可在运输问题数据表上画出，它是一条封闭的折线。折线的每一条边或者是水平的，或者是垂直的。一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表中的变量x 32及x33不是闭回路的顶点，只是连线的交点。,表上作业法,变量组 不能构成一条闭回路，但A中包含有闭回路,变量组 变量数是奇数，显然不是闭回路，也不含有闭回路；,表上作业法,运输表中一个基必须具备的特点1、一个基应占表中的m+n-1格;2、构成基的同行同列格子不能构成闭回路;3、一个基在表中所占的格子应包括表的每行和
12、每列。,表上作业法,事实上，对于一条闭回路，,定理1 闭回路上变量的列向量是线性相关的。,成立。,表上作业法,事实上，由定理1可知：如果变量组中包括一条闭回路，则它所对应的列向量组线性相关。,定理2 m+n-1个变量构成基的充要条件是它不包含闭回路。,表上作业法,定理3 运输问题(1)存在可行解。,从而 是问题(1)的可行解。,并且：,证明：设A为总产量，当然也是总销量，即 对于每个i，j，令可见，,表上作业法,推论1 运输问题必有基可行解。,推论2 运输问题有最优解。由于运输问题中价值系数cij0，故任何可行解都使其目标函数永远取非负值，即目标函数有下界，所以目标函数不会任意小，故一定有最优
13、解。,推论3 如果运输问题中所有产量ai与销量bj都是整数，那么它的每个基可行解都是整数解，进而得出它的最优解也是整数解。,运输问题解的整数性可由下面的表上作业法来保证。推论3的结论是很重要的，它是求解整数运输问题的基础。,表上作业法,位势法（最优解的判别）,求出运输问题的初始基可行解后（可以利用上面介绍的西北角法、最小元素法或者是伏格尔法），下面应该来确定它的检验数，从而判别基可行解是否为最优解。下面介绍求运输问题检验数的位势法。,表上作业法,运输问题的数学模型：,首先：设u i、v j 分别是m+n个约束条件对应的对偶变量，得到运输问题的对偶问题：,表上作业法,利用对偶理论，原问题的检验数
14、为：,表上作业法,基变量的检验数是0，即对于给定的运输问题的一个基可行解 X0，记表示X0 中基变量的下标集合：,位势方程的特点：1、含有 m+n 个u、v变量，m+n-1个 方程。2、有1个自由变量。,求解时，任意取一个变量出来作为自由变量并令其为0，代入位势方程进行求解。,对于一个给定的位势ui,vj，我们用这组位势来确定剩余的非基变量xij的检验数。,表上作业法,前面利用伏格尔法确定的初始解如下表所示：,例2,1、写出基可行解对应的位势方程组;2、并计算非基变量的检验数。,表上作业法,求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下：在原单位运价表增加一行与一列，在列中
15、填入ui，在行中填入vj；把运价cij记在每一格的右上角，用框标定，在基变量对应的格中标出0，构成表。,表上作业法,由u1+v1=2,u1+v2=9,u1+v4=7,得v1=2,v2=9,v4=7;,0,-5,-5,2,9,7,7,位势表：,再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;,最后由u3+v3=2 得v3=7.,取u1=0;,表上作业法,检验数表：,(计算所有非基变量的检验数),0,-5,-5,2,9,7,7,(3),(4),(-1),(2),(11),(3),当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,表上作业法,第3步
16、 解的改进：确定入基、出基变量,若出现负检验数时，表明得到的基可行解不是最优解，需要调整。同时出现几个负检验数，一般选其中最小的负检验数，它所对应的非基变量作为换入变量。用闭回路法进行迭代调整。,一般称基变量对应的格为基格，非基变量对应的格为空格。,表上作业法,1)从换入变量所对应的空格出发，沿行或列直线画出，遇到基变量时垂直转向，最后回到这个空格，从而可以作出一条闭回路。2)在闭回路中，记选定的空格为第1个顶点，并沿行进方向依次对闭回路的顶点标号为2,3,4,。3)由标号可把闭回路上的顶点分成奇点或偶点。4)取闭回路中偶点运量的最小值为调整量,相应的变量为换出变量。记5)进行调整：,迭代过程
17、闭回路法,在闭回路外的顶点上的值不变,在闭回路的奇点上的值变为,在闭回路的偶点上的值变为,上述过程称为闭回路调整法。,表上作业法,伏格尔法的初始方案：,(3),(4),(-1),(2),(11),(3),x22为换入变量,从 x22所在格出发做闭回路L,L中有两个偶点x24,x12，,取x12为换出变量，调整量为5.,表上作业法,伏格尔法的调整方案：,在闭回路L上，偶点变量减5，奇点变量加5.,0,x22为换入变量,取x12为换出变量.,0,6,5,表上作业法,它所对应的位势与检验数为：,2,8,6,7,0,-5,-4,(1),(4),(4),(3),(10),(2),所有检验数都非负，迭代停
18、止，运费为：32+67+53+34+42=83,表上作业法,表上作业法的计算步骤：,表上作业法,表上作业法计算中的问题：,若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。（1）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。,表上作业法,退化解：表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。利用进基变
19、量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量，选择任意一个最小运量对应的基变量作为出基变量，并打上“”以示作为非基变量。,表上作业法,2退化,存在基变量为0的解称为退化解。有两种情况：,(1)在确定初始基可行解的过程中，如果某一步中出现情况：当产地Ai处的余量与销地Bj处的需求量相等时，在格(i,j)填入运量后，产地Ai处的余量与销地Bj处的销量同时为0，相应地要划去一行和一列。这时就出现了退化。,为了使基变量个数恰好有m+n-1个，应在同时划去的一行或一列中的某个格中填入数字0，表示这格中的变量是取值为0的基变量；,表上作业法,(2)在用闭回路法调整时，当闭回路的偶点中有两个或两个以上的值与调整量相等时，经过调整，就会出现多个原基变量为0的情况，这时只能选择其中一个作为换出变量，其它的仍需作为基变量，取值为0.,表上作业法,
