《《运筹学教学资料》运筹学第3章第2节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第3章第2节.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-1-China University of Mining and Technology运筹学 3.2 表上作业法-2-China University of Mining and Technology运筹学 表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是单形法。实质是单形法。步骤步骤描述描述方法方法第一步第一步求初始基行可行解（初始调运方案）求初始基行可行解（初始调运方案）最小元素法、最小元素法、Vogel法法第二步第二步求检验数并判断是否得到最优解当非基变求检验数并判断是否得到最优解当非基变量的检验数量的检验数ij全都非负时得到最优解，若全都非负
2、时得到最优解，若存在检验数存在检验数ij 0，说明还没有达到最优，说明还没有达到最优，转第三步。转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入原运量进行调整得到新的基可行解，转入第二步第二步迭代过程中得出的所有解都要求是运输问题的基可行解迭代过程中得出的所有解都要求是运输问题的基可行解表表 上上 作作 业业 法法-3-China University of Mining and Technology运筹学 给定下列运输问题给定下列运输问题B1B2B3B4产量产量A1291079A
3、213425A384257销量销量3846分析分析：由于总产量是由于总产量是9+5+7=21，总销量是，总销量是3+8+4+6故故产销平衡产销平衡。该问题有该问题有3个产地，个产地，4个销地，故基可行解含个销地，故基可行解含有有3+4-1=6个个基变量。基变量。例例1表表 上上 作作 业业 法法-4-China University of Mining and Technology运筹学 第第第第1 1步步步步 求初始方案求初始方案求初始方案求初始方案运输问题的初始方案的确定主要有三种方法：运输问题的初始方案的确定主要有三种方法：.西北角法西北角法.最小元素法最小元素法.伏格尔法伏格尔法运输问
4、题是一种特殊的线性规划问题（大型稀疏矩阵的处理）运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）,它的初始基的确定具有一定的难度。它的初始基的确定具有一定的难度。表表 上上 作作 业业 法法-5-China University of Mining and Technology运筹学 1.西北角法（左上角法）西北角法（左上角法）u西北角法每次都从运价表的左上角确定基变量。西北角法每次都从运价表的左上角确定基变量。u算法的每一步都取最左上角的元素（如算法的每一步都取最左上角的元素（如xij）为基变量，其）为基变量，其取值是相应行列产销量的最小者，即取值是相应行列产销量的最小者，即u然后划去
5、产销平衡运输表中的一行或一列得到一个新的然后划去产销平衡运输表中的一行或一列得到一个新的产销平衡运输表。产销平衡运输表。u再重复上述过程直至得到问题的运输方案。再重复上述过程直至得到问题的运输方案。具体的算法过程如下：具体的算法过程如下：表表 上上 作作 业业 法法-6-China University of Mining and Technology运筹学 B1B2B3B4产量A19A25A37销量3846u 令令 x11为基变量，为基变量，u 销地销地B1的销量全由产地的销量全由产地A1供给，所以供给，所以x21=0,x31=0,x21与与x31为非基变量。为非基变量。u 将将x11=填到
6、调运方案表中第填到调运方案表中第1行第行第1列上。列上。u 画去运输数据表中第画去运输数据表中第1列列,A1 的产量剩余为的产量剩余为9-3=6。得到新的产销平衡运输表。得到新的产销平衡运输表。例如对于前面的例子：例如对于前面的例子：3003/09/6西西西西北北北北角角角角法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-7-China University of Mining and Technology运筹学 B1B2B3B4产量A19/6A25A37销量3/08463008/29/6/0u令令x12为基变量，则为基变量，则u产地产地A1的产量的产量6全供给销地全供给销
7、地B2，所以，所以 x13=x14=0，x13与与x14 为非基变量。为非基变量。u将将x12 6 填到调运方案表中第填到调运方案表中第1行第行第2列上。列上。u画去运输数据表中第画去运输数据表中第1行，行，B2 的销量还要的销量还要8-6=2。得到新的产销平衡运输表。得到新的产销平衡运输表。600西西西西北北北北角角角角法法法法计计计计算算算算2 2 2 2表表 上上 作作 业业 法法-8-China University of Mining and Technology运筹学 B1B2B3B4产量A19/6/0A25A37销量3/08/2463008/2/05/3600u令令x22为基变量
8、，则为基变量，则u销地销地B2的销量的销量2全由产地全由产地A2供给，所以供给，所以x32=0，x32为非为非基基 变量。变量。u将将x22 2 填到调运方案表中第填到调运方案表中第2行第行第2列上。列上。u画去运输数据表中第画去运输数据表中第2列，列，A2 的产量剩余为的产量剩余为 5-2=3。得到新的产销平衡运输表。得到新的产销平衡运输表。20西西西西北北北北角角角角法法法法计计计计算算算算3 3 3 3表表 上上 作作 业业 法法-9-China University of Mining and Technology运筹学 B1B2B3B4产量A19/6/0A25/3A37销量3/08/
9、2/0463004/15/3/060020u令令x23为基变量，则为基变量，则u产地产地A2的产量的产量3全供给销地全供给销地B2，所以，所以x24=0，x24为非基变量。为非基变量。u将将x23 3 填到调运方案表中第填到调运方案表中第2行第行第3列上。列上。u画去运输数据表中第画去运输数据表中第2行，行，B3 的销量剩余为的销量剩余为 4-3=1。得到新的产销平衡运输表。得到新的产销平衡运输表。30西西西西北北北北角角角角法法法法计计计计算算算算4 4 4 4表表 上上 作作 业业 法法-10-China University of Mining and Technology运筹学 B1B
10、2B3B4产量A19/6/0A25/3A37销量3/08/2/0463004/15/3/06002030现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x33=1，x34=6为基变为基变量，将其分别填到调运方案表中第量，将其分别填到调运方案表中第3行第行第3列与第列与第3行第行第4列上。列上。16得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案西西西西北北北北角角角角法法法法计计计计算算算算5 5 5 5表表 上上 作作 业业 法法-11-China University of Mining and Technology运筹学 B1B2B3B4产量A1369A2
11、235A3167销量3846u这个方案的运费是这个方案的运费是23+96+32+43+21+56=110。u表中填了表中填了6个数值，正好对应基变量，即个数值，正好对应基变量，即6=m+n 1=3+4-1u其余未填数字的空格位置的数值为其余未填数字的空格位置的数值为0,对应非基变量对应非基变量.u西北角法确定的初始方案没有考虑运价的影响，因而西北角法确定的初始方案没有考虑运价的影响，因而离最优方案相去甚远。离最优方案相去甚远。评评 注注表表 上上 作作 业业 法法-12-China University of Mining and Technology运筹学 2.2.最小元素法最小元素法最小元
12、素法最小元素法u最小元素法的基本思想是最小元素法的基本思想是就近供应；就近供应；u即从运价表中最小的运价开始确定供销关系即从运价表中最小的运价开始确定供销关系.u若有几个最小运价，则任取其一。若有几个最小运价，则任取其一。最小元素法和西北角法大体差不多，只是考虑了运价的因素。最小元素法和西北角法大体差不多，只是考虑了运价的因素。用用最小最小元素法求得的基本可行解更接近最优解，所以也元素法求得的基本可行解更接近最优解，所以也称为近似方案。称为近似方案。表表 上上 作作 业业 法法-13-China University of Mining and Technology运筹学 B1B2B3B4ai
13、A1291079A213425A384257bj3846u销地销地B1的销量的销量3全由产地全由产地A2供给，所以供给，所以x11=x31=0。将将x213填到调运方案表中第填到调运方案表中第2行第行第1列上。列上。最最最最小小小小元元元元素素素素法法法法计计计计算算算算1 1 1 13003/05/2u画去运输数据表中第画去运输数据表中第1列，列，A2的产量剩余为的产量剩余为5-3=2。得到新的产销平衡运输表。得到新的产销平衡运输表。u寻找运价中最小的：寻找运价中最小的：令令表表 上上 作作 业业 法法-14-China University of Mining and Technology
14、运筹学 B1B2B3B4aiA1291079A213425/2A384257bj3/0846最最最最小小小小元元元元素素素素法法法法计计计计算算算算2 2 2 23006/45/2/0u产地产地A2的产量的产量2全供给销地全供给销地B4，所以，所以x22=x23=0。将。将x24 2填到调运方案表中第填到调运方案表中第2行第行第4列上。列上。u画去运输数据表中第画去运输数据表中第2行，行，B4 的销量还要的销量还要 6-2=4。得到新的产销平衡运输表。得到新的产销平衡运输表。200u寻找运价中最小的：寻找运价中最小的：令令表表 上上 作作 业业 法法-15-China University o
15、f Mining and Technology运筹学 B1B2B3B4aiA1291079A213425/2/0A384257bj3/0846/4最最最最小小小小元元元元素素素素法法法法计计计计算算算算3 3 3 33004/07/3200u销地销地B3的销量的销量4全由产地全由产地A3供给，所以供给，所以x13=0。将。将x334填填到调运方案表中第到调运方案表中第3行第行第3列上。列上。u画去运输数据表中第画去运输数据表中第3列，列，A3的产量剩余为的产量剩余为7-4=3.得到得到新的产销平衡运输表。新的产销平衡运输表。40u寻找运价中最小的：寻找运价中最小的：令令表表 上上 作作 业业
16、法法-16-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425/2/0A384257/3bj3/084/06/4最最最最小小小小元元元元素素素素法法法法计计计计算算算算4 4 4 43008/57/3/020040u产地产地A3的产量的产量3全供给销地全供给销地B2，所以，所以x34=0，将，将x32=3填到调运方案表中第填到调运方案表中第3行第行第2列上。列上。u画去运输数据表中第画去运输数据表中第3行，行，B2的销量剩余为的销量剩余为8-3=5。得到新的产销平衡运输表。得到新的产销平衡运输表。30u寻
17、找运价中最小的：寻找运价中最小的：令令表表 上上 作作 业业 法法-17-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425/2/0A384257/3bj3/084/06/4最最最最小小小小元元元元素素素素法法法法计计计计算算算算5 5 5 53008/57/3/02004030现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x12=5,x14=4为基变量，将为基变量，将其分别填到调运方案表中第其分别填到调运方案表中第1行第行第2列与第列与第1行第行第4列上。列上。得到产销平衡运输问题的一个初
18、始方案得到产销平衡运输问题的一个初始方案45表表 上上 作作 业业 法法-18-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425A384257bj3846324345评评注注|此调运方案的运费：此调运方案的运费：31+59+34+42+22+47=100|比用西北角法初始方案好些比用西北角法初始方案好些|最小元素法确定的初始方案往往最小元素法确定的初始方案往往缺乏全局缺乏全局的观点的观点，即为了节即为了节省一处的运费，而在其它处要多花更大的运费。省一处的运费，而在其它处要多花更大的运费。表表 上上 作作
19、 业业 法法-19-China University of Mining and Technology运筹学 伏格尔法的伏格尔法的主要思想主要思想是：是：3.伏格尔法伏格尔法一产地的产品如若不能按最小运费就近供应，就考虑按次一产地的产品如若不能按最小运费就近供应，就考虑按次小运费供应，这里存在一个差额。小运费供应，这里存在一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，应当采用最小运费调运。因而对差额最大处，应当采用最小运费调运。表表 上上 作作 业业 法法-20-China University of Minin
20、g and Technology运筹学 B1B2B3B4ai行差行差A1291079A213425A384257bj3846列差列差伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1用伏格尔法寻找初始基：用伏格尔法寻找初始基：|先算出运价表中各行与各列的最小运费与次小运费的差先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。额，并填入该运价表的最右列和最下行。|从行差或列差中选出最大者，并选择其所在行或列的最从行差或列差中选出最大者，并选择其所在行或列的最小元素。小元素。A1的行差最大，而其中运价的行差最大，而其中运价c11最小最小,令令x11为优
21、先运输路线。为优先运输路线。5121123表表 上上 作作 业业 法法-21-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A12910795A2134251A3842572bj3846列差列差11230303/09/6用伏格尔法寻找初始基：用伏格尔法寻找初始基：u销地销地B1的销量的销量3全由产地全由产地A1供给，所以供给，所以x21=x31=0。将。将x11=3 填到调运方案表中第填到调运方案表中第1行第行第1列上。列上。u画去运输数据表第一列，画去运输数据表第一列，A1的产量剩余为的产量剩余为9-3=6。得到得到新的
22、产销平衡与单位运价表新的产销平衡与单位运价表.u令令伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-22-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A2134251A3842572bj3/0846列差列差11230306/15/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：u再算出运价表中的行差与列差。再算出运价表中的行差与列差。uB4的列差最大，而其中运价的列差最大，而其中运价c24最小最小,令令x24为优先运输路线。为优先运输路线。u产地产地A2的产
23、量的产量2全供给销地全供给销地B4，所以，所以x23=x24=0。u画去运输数据表中第画去运输数据表中第2行，行，B4的销量还要的销量还要6-5=1。得新表。得新表。521122112233050令令伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-23-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A3842572bj3/0846/1列差列差11230304/07/3用伏格尔法寻找初始基：用伏格尔法寻找初始基：52112211223305
24、05 2 21 12 2 211522833204伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-24-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：5211221122330505 2 21 12 2 21152283320452 2 21122 2 11 1 5 5 2 2 83 3 2 203伏伏伏伏格格格格
25、尔尔尔尔法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-25-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：0500452 2 21122 2 11 1 5 5 2 2 83 3 2 203现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x12=5,x14=1为基变量，为基变量，将其分别填到调运方案表中将其分别填到调运方案表中
26、1行行2列与列与1行行4列上。列上。51得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表表 上上 作作 业业 法法-26-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的运费是此方案的运费是32+59+47+52+34+42=88。伏格尔法给出的初始解往往更接近于最优解。伏格尔法给出的初始解往往更接近于最优解。表表 上上 作作 业业 法法-27-China Universit
27、y of Mining and Technology运筹学 评价：评价：西北角法、最小元素法与伏格尔法除在确定供求关系西北角法、最小元素法与伏格尔法除在确定供求关系的规则上不同外，其它步骤完全相同。的规则上不同外，其它步骤完全相同。对对于于一一个个有有m个个产产地地n个个销销地地的的运运输输问问题题，需需要要进进行行m+n-2步步以以确确定定初初始始方方案案，每每一一步步要要划划去去其其中中的的一一行行或或一一列列，最最后后得得到到m+n-1个个运运输输路路线线，对对应应m+n-1个个基变量。基变量。表表 上上 作作 业业 法法-28-China University of Mining an
28、d Technology运筹学 B1B2B3B4A136A223A316B1B2B3B4A154A232A334B1B2B3B4A1351A25A334西西北北角角法法最最小小元元素素法法伏伏格格尔尔法法表表 上上 作作 业业 法法-29-China University of Mining and Technology运筹学 第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，由由第第一一章章知知
29、，求求最最小小值值的的运运输输问问题题的的最最优优判判别别准则是：准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种：闭回路法闭回路法 位势法（位势法（）表表 上上 作作 业业 法法-30-China University of Mining and Technology运筹学 为一个为一个闭回路闭回路，集合中的变量称为回路的，集合中的变量称为回路的顶点顶点，相邻两，相邻两个变量的连线为闭回路的边。个变量的连线为闭回路的边。闭回路法闭回路法闭回路法闭回路法表表 上上 作作 业业 法法-31-China Univ
30、ersity of Mining and Technology运筹学 下表中闭回路的变量集合是下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有共有8个顶点，这个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。封闭的回路。B1B2B3B4B5A1x11x12A2x23x25A3x31x35A4x42x43表表 上上 作作 业业 法法-32-China University of Mining and Technology运筹学 对于一条给定的闭回路对于一条给定的闭回路,数据表上的每一行、每一列至多
31、只有两个数据表上的每一行、每一列至多只有两个变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的顶点）顶点）。B1B2B3B4B5A1x11x12A2x23x25A3x31x35A4x42x43闭回路可在运输问题数据表上画出，它是一条封闭的折线。折线的闭回路可在运输问题数据表上画出，它是一条封闭的折线。折线的每一条边或者是水平的，或者是垂直的。每一条边或者是水平的，或者是垂直的。一条回路中的顶点数一定是偶数，回路遇到顶点必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一度与另一顶点连接，顶点连接，表中的变量表中的变
32、量x 32及及x33不是闭回路的顶点不是闭回路的顶点，只是连线的交点。只是连线的交点。表表 上上 作作 业业 法法-33-China University of Mining and Technology运筹学 变量组变量组 不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组 变量数是奇数，显然不是变量数是奇数，显然不是闭回路，也不含有闭回路；闭回路，也不含有闭回路；B1B2B3B4B5A1A2A3A4表表 上上 作作 业业 法法-34-China University of Mining and Technology运筹学 B1B2B3B4产量产量A13
33、69A2235A3167销量销量3846B1B2B3A1x11x12A2A3x32x33A4x41x43q 运输表中一个基必须具备的特点运输表中一个基必须具备的特点1、一个基应占表中的一个基应占表中的m+n-1格格;2、构成基的同行同列格子不能构成闭回路、构成基的同行同列格子不能构成闭回路;3、一个基在表中所占的格子应包括表的每行和每列。、一个基在表中所占的格子应包括表的每行和每列。表表 上上 作作 业业 法法-35-China University of Mining and Technology运筹学 事实上，对于一条闭回路，事实上，对于一条闭回路，定理定理1 闭回路上变量的列向量是线性相
34、关的。闭回路上变量的列向量是线性相关的。成立。成立。表表 上上 作作 业业 法法-36-China University of Mining and Technology运筹学 事实上，由定理事实上，由定理1可知：如果变量组中包括一条闭回路，则它可知：如果变量组中包括一条闭回路，则它所对应的列向量组线性相关。所对应的列向量组线性相关。定理定理2 m+n-1个变量构成基的个变量构成基的充要条件充要条件是它不包含闭回路。是它不包含闭回路。表表 上上 作作 业业 法法-37-China University of Mining and Technology运筹学 定理定理3 运输问题运输问题(1)存
35、在可行解。存在可行解。从而从而 是问题是问题(1)的可行解。的可行解。并且：并且：证明：设证明：设A为总产量，当然也是为总产量，当然也是总销量，即总销量，即 对于每个对于每个i，j，令，令可见可见 ，表表 上上 作作 业业 法法-38-China University of Mining and Technology运筹学 推论推论1 运输问题必有基可行解。运输问题必有基可行解。推论推论2 运输问题有最优解。运输问题有最优解。由于运输问题中价值系数由于运输问题中价值系数cij0，故任何可行解都使其目标函，故任何可行解都使其目标函数永远取非负值，即目标函数有下界，所以目标函数不会任数永远取非负值
36、，即目标函数有下界，所以目标函数不会任意小，故一定有最优解。意小，故一定有最优解。推论推论3 如果运输问题中所有产量如果运输问题中所有产量ai与销量与销量bj都是整数，那么都是整数，那么它的每个基可行解都是整数解，进而得出它的最优解也是整它的每个基可行解都是整数解，进而得出它的最优解也是整数解。数解。|运输问题解的整数性可由下面的表上作业法来保证。运输问题解的整数性可由下面的表上作业法来保证。|推论推论3的结论是很重要的，它是求解整数运输问题的基础。的结论是很重要的，它是求解整数运输问题的基础。表表 上上 作作 业业 法法-39-China University of Mining and T
37、echnology运筹学 位势法（最优解的判别）位势法（最优解的判别）位势法（最优解的判别）位势法（最优解的判别）求出运输问题的初始基可行解后（可以利用上面介绍的求出运输问题的初始基可行解后（可以利用上面介绍的西北角法、最小元素法或者是伏格尔法），西北角法、最小元素法或者是伏格尔法），下面应该来下面应该来确定它的检验数确定它的检验数，从而判别基可行解是否为最优解。，从而判别基可行解是否为最优解。下面介绍求运输问题检验数的位势法。下面介绍求运输问题检验数的位势法。表表 上上 作作 业业 法法-40-China University of Mining and Technology运筹学 运输问题
38、的数学模型：运输问题的数学模型：首先：设首先：设u i、v j 分别是分别是m+n个个约束条件对应的对偶变量，得约束条件对应的对偶变量，得到运输问题的到运输问题的对偶问题对偶问题：表表 上上 作作 业业 法法-41-China University of Mining and Technology运筹学 利用对偶理论，原利用对偶理论，原问题的问题的检验数检验数为：为：表表 上上 作作 业业 法法-42-China University of Mining and Technology运筹学 基变量的检验数是基变量的检验数是0，即对于给定的运输问题的一个基可行解，即对于给定的运输问题的一个基可行
39、解 X0，记表示，记表示X0 中基变量的下标集合：中基变量的下标集合：该方程组称为该方程组称为位势方程；位势方程；其其解称为解称为位势。位势。位势方程的位势方程的特点特点：1、含有、含有 m+n 个个u、v变量，变量，m+n-1个个 方程。方程。2、有、有1个自由变量。个自由变量。求解时，任意取一个变求解时，任意取一个变量出来作为自由变量并量出来作为自由变量并令其为令其为0，代入位势方程，代入位势方程进行求解进行求解。对于一个给定的位势对于一个给定的位势ui,vj，我们用这组位势来确定剩余的，我们用这组位势来确定剩余的非非基变量基变量xij的检验数。的检验数。表表 上上 作作 业业 法法-43
40、-China University of Mining and Technology运筹学 前面利用伏格尔法确定的初始解如下表所示：前面利用伏格尔法确定的初始解如下表所示：B1B2B3B4aiA1325910179A2134525A38344257bj3846例例21、写出、写出基可行解对应的位势方程组基可行解对应的位势方程组;2、并计算非基变量的检验数。、并计算非基变量的检验数。表表 上上 作作 业业 法法-45-China University of Mining and Technology运筹学 由由u1+v1=2,u1+v2=9,u1+v4=7,得得v1=2,v2=9,v4=7;B1
41、B2B3B4uiA102091007A213402A3804025vj0-5-52977位势表：位势表：再由再由u2+v4=2，u3+v2=4，得，得u2=-5，u3=-5;最后由最后由u3+v3=2 得得v3=7.取取u1=0;表表 上上 作作 业业 法法-46-China University of Mining and Technology运筹学 检验数表：检验数表：(计算所有非基变量的检验数计算所有非基变量的检验数)B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)当存在非基变量的检验数当存在非基变量的检
42、验数 kl 0，说明现行方案为最优方案，否，说明现行方案为最优方案，否则目标成本还可以进一步减小。则目标成本还可以进一步减小。表表 上上 作作 业业 法法-47-China University of Mining and Technology运筹学 第第第第3 3步步步步 解的改进：解的改进：解的改进：解的改进：确定入基、出基变量确定入基、出基变量确定入基、出基变量确定入基、出基变量|若出现负检验数时，表明得到的基可行解不是最优解，需要调若出现负检验数时，表明得到的基可行解不是最优解，需要调整。整。|同时出现几个负检验数，一般选其中最小的负检验数，它所对同时出现几个负检验数，一般选其中最小的
43、负检验数，它所对应的非基变量作为换入变量。应的非基变量作为换入变量。|用用闭回路法闭回路法进行迭代调整。进行迭代调整。一般称基变量对应的格为一般称基变量对应的格为基格基格，非基变量对应的格为，非基变量对应的格为空格空格。表表 上上 作作 业业 法法-48-China University of Mining and Technology运筹学 1)从换入变量所对应的空格出发，沿行或列直线画出，遇从换入变量所对应的空格出发，沿行或列直线画出，遇到基变量时垂直转向，最后回到这个空格，从而可以作到基变量时垂直转向，最后回到这个空格，从而可以作出一条闭回路。出一条闭回路。2)在闭回路中，记选定的空格为
44、第在闭回路中，记选定的空格为第1个顶点，并沿行进方向个顶点，并沿行进方向依次对闭回路的顶点标号为依次对闭回路的顶点标号为2,3,4,。3)由标号可把闭回路上的顶点分成奇点或偶点。由标号可把闭回路上的顶点分成奇点或偶点。4)取闭回路中偶点运量的最小值为调整量取闭回路中偶点运量的最小值为调整量,相应的变量为换相应的变量为换出变量。记出变量。记5)进行调整：进行调整：迭代过程迭代过程闭回路法闭回路法n 在闭回路外的顶点上的值不变在闭回路外的顶点上的值不变n 在闭回路的奇点上的值变为在闭回路的奇点上的值变为n 在闭回路的偶点上的值变为在闭回路的偶点上的值变为上述过程称为上述过程称为闭回路调整法闭回路调
45、整法。表表 上上 作作 业业 法法-49-China University of Mining and Technology运筹学 伏格尔法的初始方案：伏格尔法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)x22为为换入变量换入变量,从从 x22所在格出发做闭回路所在格出发做闭回路L,L中有两个偶中有两个偶点点x24,x12，取取x12为为换出变量换出变量，调整量为，调整量为5.表表 上上 作作 业业 法法-50-China University of Mining and Technology运
46、筹学 伏格尔法的调整方案：伏格尔法的调整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在闭回路在闭回路L上，偶点变量减上，偶点变量减5，奇点变量加，奇点变量加5.0 x22为为换入变量换入变量,取取x12为为换出变量换出变量.065表表 上上 作作 业业 法法-51-China University of Mining and Technology运筹学 它所对应的位势与检验数为：它所对应的位势与检验数为：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有检验数
47、都非负，迭代停止，运费为：所有检验数都非负，迭代停止，运费为：32+67+53+34+42=83表表 上上 作作 业业 法法-52-China University of Mining and Technology运筹学 表上作业法的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最
48、优方案，得到最优方案，算出总运价算出总运价表表 上上 作作 业业 法法-53-China University of Mining and Technology运筹学 表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：若运输问题的某一基可行解有多个非基变量的检验数为负，若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取得到改善，但通常取ij0中最小者对应的变量为换入变量。中最小者对应的变量为换入变量。（1）无穷多最优解
49、）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则，则该问题有无穷多最优解。该问题有无穷多最优解。表表 上上 作作 业业 法法-54-China University of Mining and Technology运筹学 退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量时个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个则需要同时划去一行和一列，这时需要补一个0，以保证有，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空个数字格作为基变量。一般可在划去的行和列的任意空格处加一个格处加一个0即可。即可。利用进基变量的闭回路对解进行调整时，标有负号的最小利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最小运量，选择任意一个最小运量对应的基变量作为出基变量，并打上对应的基变量作为出基变量，并打上“”以示作为非基变量。以示作为非基变量。表表 上上 作作 业业 法法