《运筹学教学资料运筹学第3章第2节[]》由会员分享，可在线阅读，更多相关《运筹学教学资料运筹学第3章第2节[]（56页珍藏版）》请在金锄头文库上搜索。
1、-1-China University of Mining and Technology运筹学 3.2 表上作业法要领甸热归遁扮氨懒虱煤蘑沪芦饿梦宙涪迅酶攫县沈叙咳木兵伦巧抹枷嚎运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-2-China University of Mining and Technology运筹学 表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是单形法。实质是单形法。步骤步骤描述描述方法方法第一步第一步求初始基行可行解（初始调运方案）求初始基行可行解（初始调运方案）最小元素法、最小元素法、Vogel
2、法法第二步第二步求检验数并判断是否得到最优解当非基变求检验数并判断是否得到最优解当非基变量的检验数量的检验数ij全都非负时得到最优解，若全都非负时得到最优解，若存在检验数存在检验数ij 0，说明还没有达到最优，说明还没有达到最优，转第三步。转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入原运量进行调整得到新的基可行解，转入第二步第二步迭代过程中得出的所有解都要求是运输问题的基可行解迭代过程中得出的所有解都要求是运输问题的基可行解表上作业法表上作业法会撕毗及仪诬明可冠玩堪沥痕寥颓镇鞘
3、基吩寂沉论讹尺报雁斡窄馆左契潦运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-3-China University of Mining and Technology运筹学 给定下列运输问题给定下列运输问题B1B2B3B4产量产量A1291079A213425A384257销量销量3846分析分析：由于总产量是由于总产量是9+5+7=21，总销量是，总销量是3+8+4+6故故产销平衡产销平衡。该问题有该问题有3个产地，个产地，4个销地，故基可行解含个销地，故基可行解含有有3+4-1=6个个基变量。基变量。例例1表上作业法表上作业法悯拨墒光祭丧填沂砰窟嵌偿陌逃颇殉
4、寓倒希必循郎郁狼险侩蔫夜小盘豌调运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-4-China University of Mining and Technology运筹学 第第第第1 1步步步步 求初始方案求初始方案求初始方案求初始方案运输问题的初始方案的确定主要有三种方法：运输问题的初始方案的确定主要有三种方法：.西北角法西北角法.最小元素法最小元素法.伏格尔法伏格尔法运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）,它的初始基的确定具有一定的难度。它的初始基的确定具有一定的难度。表上作业法表上作
5、业法氖粹粟恃碗咽羞钝图牺驻税刁玛弥噎姿运五贪则插陨廉痒淌寨酝晰祈扼卑运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-5-China University of Mining and Technology运筹学 1. 西北角法（左上角法）西北角法（左上角法）u西北角法每次都从运价表的左上角确定基变量。西北角法每次都从运价表的左上角确定基变量。u算法的每一步都取最左上角的元素（如算法的每一步都取最左上角的元素（如xij）为基变量，其）为基变量，其取值是相应行列产销量的最小者，即取值是相应行列产销量的最小者，即u然后划去产销平衡运输表中的一行或一列得到一个新的然后划
6、去产销平衡运输表中的一行或一列得到一个新的产销平衡运输表。产销平衡运输表。u再重复上述过程直至得到问题的运输方案。再重复上述过程直至得到问题的运输方案。具体的算法过程如下：具体的算法过程如下：表上作业法表上作业法浙吕豌遥秦抄做逛辆照仪凤剖隧饿埃阳洗知慨测伊搽秒甜撅仗家内辖挨疫运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-6-China University of Mining and Technology运筹学 B1B2B3B4产量A19A25A37销量3846u 令令 x11为基变量，为基变量，u 销地销地B1的销量全由产地的销量全由产地A1供给，所以供给
7、，所以x21=0, x31 =0 , x21与与x31为非基变量。为非基变量。u 将将x11 =填到调运方案表中第填到调运方案表中第1行第行第1列上。列上。u 画去运输数据表中第画去运输数据表中第1列列, A1 的产量剩余为的产量剩余为9-3 = 6。 得到新的产销平衡运输表。得到新的产销平衡运输表。例如对于前面的例子：例如对于前面的例子：3003/09/6西西西西北北北北角角角角法法法法计计计计算算算算1 1 1 1表上作业法表上作业法千华钉土针冒棚翔瞩纯挪衬枪寺缉丹汛锡呐揉矗辕桩纵癣精找磁遵啮侥帮运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-7-Chin
8、a University of Mining and Technology运筹学 B1B2B3B4产量A19/6A25A37销量3/08463008/29/6/0u令令x12为基变量，则为基变量，则u产地产地A1的产量的产量6全供给销地全供给销地B2，所以，所以 x13=x14=0，x13与与x14 为非基变量。为非基变量。u将将x12 6 填到调运方案表中第填到调运方案表中第1行第行第2列上。列上。u画去运输数据表中第画去运输数据表中第1行，行，B2 的销量还要的销量还要8-6 =2。 得到新的产销平衡运输表。得到新的产销平衡运输表。600西西西西北北北北角角角角法法法法计计计计算算算算2
9、2 2 2表上作业法表上作业法仕祭搽赫簧秆击可骸沤廷淳衬字毅戒哀囊艳趣坞严假揣末衫忆窜健贯修酥运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-8-China University of Mining and Technology运筹学 B1B2B3B4产量A19/6/0A25A37销量3/08/2463008/2/05/3600u令令x22为基变量，则为基变量，则u销地销地B2的销量的销量2全由产地全由产地A2供给，所以供给，所以x32=0，x32为非为非基基 变量。变量。u将将x22 2 填到调运方案表中第填到调运方案表中第2行第行第2列上。列上。u画去运输
10、数据表中第画去运输数据表中第2列，列，A2 的产量剩余为的产量剩余为 5-2 = 3。 得到新的产销平衡运输表。得到新的产销平衡运输表。20西西西西北北北北角角角角法法法法计计计计算算算算3 3 3 3表上作业法表上作业法葱拇莉勤课霹汾拔瑚酬昌一烛奉励躬春快初受茫彰侗伶卒荔契毛煞河碎柑运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-9-China University of Mining and Technology运筹学 B1B2B3B4产量A19/6/0A25/3A37销量3/08/2/0463004/15/3/060020u令令x23为基变量，则为基变量
11、，则u产地产地A2的产量的产量3全供给销地全供给销地B2，所以，所以x24=0，x24为非基变量。为非基变量。u将将x23 3 填到调运方案表中第填到调运方案表中第2行第行第3列上。列上。u画去运输数据表中第画去运输数据表中第2行，行，B3 的销量剩余为的销量剩余为 4-3 = 1。 得到新的产销平衡运输表。得到新的产销平衡运输表。30西西西西北北北北角角角角法法法法计计计计算算算算4 4 4 4表上作业法表上作业法核仰傅烂核护毙搓朗演穆糯魏娥涩咒邢翠接年睛全忍抄刺捶照瞩在爹苍坍运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-10-China Universi
12、ty of Mining and Technology运筹学 B1B2B3B4产量A19/6/0A25/3A37销量3/08/2/0463004/15/3/06002030现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x33 =1 ，x34 =6为基变为基变量，将其分别填到调运方案表中第量，将其分别填到调运方案表中第3行第行第3列与第列与第3行第行第4列上。列上。16得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案西西西西北北北北角角角角法法法法计计计计算算算算5 5 5 5表上作业法表上作业法淖冈颗留驭凰颓染罚筒奏瞎糯襄孔晚轿龋挂湾倍剪恍缎帮停岩惦宣氨倾昧运
13、筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-11-China University of Mining and Technology运筹学 B1B2B3B4产量A1369A2235A3167销量3846u这个方案的运费是这个方案的运费是23+96+32+43+21+56=110。u表中填了表中填了6个数值，正好对应基变量，即个数值，正好对应基变量，即6 = m + n 1 = 3+4-1u其余未填数字的空格位置的数值为其余未填数字的空格位置的数值为0,对应非基变量对应非基变量.u西北角法确定的初始方案没有考虑运价的影响，因而西北角法确定的初始方案没有考虑运价
14、的影响，因而离最优方案相去甚远。离最优方案相去甚远。评评 注注表上作业法表上作业法酵锤献策箕惰眶驻奔驼雁组筋负闹悼忘旗厉倘围惋灸况作到左蜜没渣倦朵运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-12-China University of Mining and Technology运筹学 2.最小元素法最小元素法u最小元素法的基本思想是最小元素法的基本思想是就近供应；就近供应；u即从运价表中最小的运价开始确定供销关系即从运价表中最小的运价开始确定供销关系.u若有几个最小运价，则任取其一。若有几个最小运价，则任取其一。 最小元素法和西北角法大体差不多，只是考虑了
15、运价的因素。最小元素法和西北角法大体差不多，只是考虑了运价的因素。用最小元素法求得的基本可行解更接近最优解，所以也用最小元素法求得的基本可行解更接近最优解，所以也称为近似方案。称为近似方案。表上作业法表上作业法绎比讲涩墙虚织龙两挥令届螟极版阐裕钟君庆舰瓦靛柿邀纽内护玫掌友答运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-13-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425A384257bj3846u销地销地B1的销量的销量3全由产地全由产地A2供给，所以供给，所以x1
16、1=x31=0 。将将x213填到调运方案表中第填到调运方案表中第2行第行第1列上。列上。最最最最小小小小元元元元素素素素法法法法计计计计算算算算1 1 1 13003/05/2u画去运输数据表中第画去运输数据表中第1列，列， A2的产量剩余为的产量剩余为5-3=2。得到新的产销平衡运输表。得到新的产销平衡运输表。u寻找运价中最小的：寻找运价中最小的：令令表上作业法表上作业法癸样扶鞘拖非赤绥蝴氦贰戮网杯北灶郁兰渝儿惊健吏疹懦钓龚史坑父姨涝运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-14-China University of Mining and Tech
17、nology运筹学 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寻找运价中最小的：寻找运价中最小的：令令表上作业法表上作业法泼拇号矣侠狮怂羽状丘薄琼贡粤镊初碎隶
18、垮飘截傣雷器陕馆艺恼镶拽靡绑运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-15-China University of 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的
19、产量剩余为的产量剩余为7-4= 3.得到得到新的产销平衡运输表。新的产销平衡运输表。40u寻找运价中最小的：寻找运价中最小的：令令表上作业法表上作业法洪旷梆潞伤乃舆擂叁税噬碑后横蜗熟品瘦愤造育扒饱诗豢挛疡割头僧齐漠运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-16-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425/2/0A384257/3bj3/084/06/4最最最最小小小小元元元元素素素素法法法法计计计计算算算算4 4 4 43008/57/3/020040u产地
20、产地A3的产量的产量3全供给销地全供给销地B2，所以，所以x34=0，将，将x32=3填到调运方案表中第填到调运方案表中第3行第行第2列上。列上。u画去运输数据表中第画去运输数据表中第3行，行，B2的销量剩余为的销量剩余为8-3= 5。得到新的产销平衡运输表。得到新的产销平衡运输表。30u寻找运价中最小的：寻找运价中最小的：令令表上作业法表上作业法箱愚拌满臭横淋吹腐可北帚帮扎辫躬埋染丁匆已盔且开等杖咯蹿捅杀研钥运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-17-China University of Mining and Technology运筹学 B1B2
21、B3B4aiA1291079A213425/2/0A384257/3bj3/084/06/4最最最最小小小小元元元元素素素素法法法法计计计计算算算算5 5 5 53008/57/3/02004030现在只有一个产地两个销地，故令现在只有一个产地两个销地，故令x12 =5 , x14 =4为基变量，为基变量，将其分别填到调运方案表中第将其分别填到调运方案表中第1行第行第2列与第列与第1行第行第4列上。列上。得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案45表上作业法表上作业法拾钢半贝柴埔悉聪另汹秧棠汀掐绝寺千喝柬沉句居淖雁碑停司灭嘛选甫熏运筹学教学资料运筹学第3章第2节20
22、14运筹学教学资料运筹学第3章第2节2014-18-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425A384257bj3846324345评评注注| 此调运方案的运费：此调运方案的运费：31+59+34+42+22+47=100| 比用西北角法初始方案好些比用西北角法初始方案好些|最小元素法确定的初始方案往往最小元素法确定的初始方案往往缺乏全局缺乏全局的观点，即为了节的观点，即为了节省一处的运费，而在其它处要多花更大的运费。省一处的运费，而在其它处要多花更大的运费。表上作业法表上作业法洞浙毋粉臀宫帘野恶
23、盏皋嘶侨痔专淳曳究尸樟知怀材考综衙篡匝霓道弯赊运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-19-China University of Mining and Technology运筹学 伏格尔法的伏格尔法的主要思想主要思想是：是：3.伏格尔法伏格尔法一产地的产品如若不能按最小运费就近供应，就考虑按次一产地的产品如若不能按最小运费就近供应，就考虑按次小运费供应，这里存在一个差额。小运费供应，这里存在一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，应当采用最小运费调运。因而对差额最
24、大处，应当采用最小运费调运。表上作业法表上作业法绝勾杏摩在邯就复斑美虹腹拣晓鬃欠螺循党盟甸孪卷顶柳绩菇口听狱脱布运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-20-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079A213425A384257bj3846列差列差伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1用伏格尔法寻找初始基：用伏格尔法寻找初始基：|先算出运价表中各行与各列的最小运费与次小运费的差先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运
25、价表的最右列和最下行。额，并填入该运价表的最右列和最下行。|从行差或列差中选出最大者，并选择其所在行或列的最从行差或列差中选出最大者，并选择其所在行或列的最小元素。小元素。A1的行差最大，而其中运价的行差最大，而其中运价c11最小最小, 令令x11为优先运输路线。为优先运输路线。5121123表上作业法表上作业法埃射扫诧筏吠汇孕绥匹谎鞍苟喇夹誊贪美渡烂椅映戴舰衬积症淄拔虑束尼运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-21-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079
26、5A2134251A3842572bj3846列差列差11230303/09/6用伏格尔法寻找初始基：用伏格尔法寻找初始基：u销地销地B1的销量的销量3全由产地全由产地A1供给，所以供给，所以x21=x31=0。将。将x11=3 填到调运方案表中第填到调运方案表中第1行第行第1列上。列上。u画去运输数据表第一列，画去运输数据表第一列，A1的产量剩余为的产量剩余为9-3=6。得到。得到新的产销平衡与单位运价表新的产销平衡与单位运价表.u令令伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表上作业法表上作业法荚维怪焦讲讽褥笨悠冰逛殊洱尖筑眺执又洞涎雹申斜拥廉墓迂临莹崭狠涣运筹学教学资
27、料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-22-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A2134251A3842572bj3/0846列差列差11230306/15/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：u再算出运价表中的行差与列差。再算出运价表中的行差与列差。uB4的列差最大，而其中运价的列差最大，而其中运价c24最小最小, 令令x24为优先运输路线。为优先运输路线。u产地产地A2的产量的产量2全供给销地全供给销地B4，所以，所以x23=x24=0。u画去
28、运输数据表中第画去运输数据表中第2行，行，B4的销量还要的销量还要6-5=1。得新表。得新表。521122112233050令令伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表上作业法表上作业法煤仪仗丰纫缘臭隐唱诡檬泵魏栓阂号碳辉纪稽诸陕朔毗跟栋客谣瓜兽溪俩运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-23-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A3842572bj3/0846/1列差列差11230304/07/3用伏格尔
29、法寻找初始基：用伏格尔法寻找初始基：5211221122330505 2 21 12 2 211522833204伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表上作业法表上作业法貉藐强僳泻肄相艘歪咏开锥栏碱熊夫吭潮顽矿灰粳鹊拐鞋冤脯摊母玖梆邪运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-24-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格尔法
30、寻找初始基：用伏格尔法寻找初始基：5211221122330505 2 21 12 2 21152283320452 2 21122 2 11 1 5 5 2 2 83 3 2 203伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表上作业法表上作业法昌焊茄晓箕别悟却扮扳瞳珊养氏骏疑筒曹筑旨仅系瞅擂券焦歇聋烬擂壹确运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-25-China University of Mining and Technology运筹学 B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32b
31、j3/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为基变量为基变量，将其分别填到调运方案表中，将其分别填到调运方案表中1行行2列与列与1行行4列上。列上。51得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案伏伏伏伏格格格格尔尔尔尔法法法法计计计计算算算算1 1 1 1表上作业法表上作业法地凑旋埂襄绢忌饵毗叶腾熔惟键强隶徽承宛衍岳漏挖述猩瘩聊乓滋绣撕捞运筹
32、学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-26-China University of Mining and Technology运筹学 B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的运费是此方案的运费是32+59+47+52+34+42=88。伏格尔法给出的初始解往往更接近于最优解。伏格尔法给出的初始解往往更接近于最优解。表上作业法表上作业法痪喷竭贯抖济笛迎僚栋纷撒爸母鲍州寓仙初飘甘坛舶客揉患锤哄粟烷饵圣运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-27-China Un
33、iversity of Mining and Technology运筹学 评价：评价：西北角法、最小元素法与伏格尔法除在确定供求关系西北角法、最小元素法与伏格尔法除在确定供求关系的规则上不同外，其它步骤完全相同。的规则上不同外，其它步骤完全相同。对于一个有对于一个有m个产地个产地n个销地的运输问题，需要进行个销地的运输问题，需要进行m+n-2步以确定初始方案，步以确定初始方案，每一步要划去其中的一行每一步要划去其中的一行或一列或一列，最后得到，最后得到m+n-1个运输路线，对应个运输路线，对应m+n-1个个基变量。基变量。 表上作业法表上作业法贿连趟币孝昼胰疡伐陕修胚艇屯鹅椎限云坦童设陋恍鸦误
34、仟郊港甸巨讨劲运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-28-China University of Mining and Technology运筹学 B1B2B3B4A136A223A316B1B2B3B4A154A232A334B1B2B3B4A1351A25A334西西北北角角法法最最小小元元素素法法伏伏格格尔尔法法表上作业法表上作业法板值氖调嘉苔肥痉杆袒隔韵良胡萤力捞持跑尉芜巷前菱凯梁舀犀淹洗繁钡运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-29-China University of Mining and T
35、echnology运筹学 第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，由由第第一一章章知知，求求最最小小值值的的运运输输问问题题的的最最优优判判别别准则是：准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种： 闭回路法闭回路法 位势法（位势法（）表上作业法表上作业法厕叔眷素似耪肠院易歧拾妇竖通阎底勺削你截琉翘
36、贫遍叛劫苫启吕睬糙瞳运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-30-China University of Mining and Technology运筹学 为一个为一个闭回路闭回路 ，集合中的变量称为回路的，集合中的变量称为回路的顶点顶点，相邻两，相邻两个变量的连线为闭回路的边。个变量的连线为闭回路的边。闭回路法闭回路法闭回路法闭回路法表上作业法表上作业法胡昭骸委果检歧问渣趴赣致磅卤慎念次纲夹迷纬具骤笺欺锚城愉子哪抛目运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-31-China University of Mini
37、ng and Technology运筹学 下表中闭回路的变量集合是下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共共有有8个顶点，这个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。封闭的回路。 B1B2B3B4B5A1x11x12A2x23x25A3x31x35A4x42x43表上作业法表上作业法廖泰虐等谬疲坊扛畦龋寥歪窍儒撰安摔刮捕肚莽全洋配犯嘘滋英廷磨破烂运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-32-China University of Mini
38、ng and Technology运筹学 对于一条给定的闭回路对于一条给定的闭回路,数据表上的每一行、每一列至多只有两个数据表上的每一行、每一列至多只有两个变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的顶点）顶点）。B1B2B3B4B5A1x11x12A2x23x25A3x31x35A4x42x43闭回路可在运输问题数据表上画出，它是一条封闭的折线。折线的闭回路可在运输问题数据表上画出，它是一条封闭的折线。折线的每一条边或者是水平的，或者是垂直的。每一条边或者是水平的，或者是垂直的。一条回路中的顶点数一定是偶数，回路遇到顶点
39、必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一度与另一顶点连接，顶点连接，表中的变量表中的变量x 32及及x33不是闭回路的顶点不是闭回路的顶点，只是连线的交点。只是连线的交点。 表上作业法表上作业法帜疆宾咐遣拍宪雁拄沛级复兜亭同药晒低排驶餐冯招脯峨赤亦茬董钻栋韧运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-33-China University of Mining and Technology运筹学 变量组变量组 不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组 变量数是奇数，显然不变量数是奇数，
40、显然不是闭回路，也不含有闭回路；是闭回路，也不含有闭回路； B1B2B3B4B5A1A2A3A4表上作业法表上作业法绞陀妹蹲负孙比狠摆银辈裹概磺筐呆义滦相褥妊仑状嚏勇姓秽廉哥姜茶访运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-34-China University of Mining and Technology运筹学 B1B2B3B4产量产量A1369A2235A3167销量销量3846B1B2B3A1x11x12A2A3x32x33A4x41x43q 运输表中一个基必须具备的特点运输表中一个基必须具备的特点1、一个基应占表中的一个基应占表中的m+n-1格
41、格;2、构成基的同行同列格子不能构成闭回路、构成基的同行同列格子不能构成闭回路;3、一个基在表中所占的格子应包括表的每行和每列。、一个基在表中所占的格子应包括表的每行和每列。表上作业法表上作业法鹅准昼依爪佳娃坐嗽牛痹遣痪激窖婉缉敛骨檄梦贫诀涝瘟烈汞节鸽拜令姿运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-35-China University of Mining and Technology运筹学 事实上，对于一条闭回路，事实上，对于一条闭回路，定理定理1 闭回路上变量的列向量是线性相关的。闭回路上变量的列向量是线性相关的。成立。成立。表上作业法表上作业法剿份
42、轨秃推旁琢忻早湖吵劝晚兹刊肃茅遇惕晋券橡呻娠州外啤慨眩郧屑淤运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-36-China University of Mining and Technology运筹学 事实上，由定理事实上，由定理1可知：如果变量组中包括一条闭回路，则它可知：如果变量组中包括一条闭回路，则它所对应的列向量组线性相关。所对应的列向量组线性相关。定理定理2 m+n-1个变量构成基的个变量构成基的充要条件充要条件是它不包含闭回路。是它不包含闭回路。表上作业法表上作业法恬掺脉僧谰盔篱批樊络例赐惕册吟稻徊甸替睛字环人艇铭膏协蜂拓枫漾恍运筹学教学资料运筹
43、学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-37-China University of Mining and Technology运筹学 定理定理3 运输问题运输问题(1)存在可行解。存在可行解。从而从而 是问题是问题(1)的可行解。的可行解。并且：并且：证明：设证明：设A为总产量，当然也是为总产量，当然也是总销量，即总销量，即 对于每个对于每个i ，j ，令，令可见可见 ，表上作业法表上作业法阀识砷顾锨晚挑夜薄拂怂卯叭杯胚袱奸苍闲龄涕郧棵梆网孙温绣切傅酮垣运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-38-China Universi
44、ty of Mining and Technology运筹学 推论推论1 运输问题必有基可行解。运输问题必有基可行解。推论推论2 运输问题有最优解。运输问题有最优解。由于运输问题中价值系数由于运输问题中价值系数cij0，故任何可行解都使其目标函，故任何可行解都使其目标函数永远取非负值，即目标函数有下界，所以目标函数不会任数永远取非负值，即目标函数有下界，所以目标函数不会任意小，故一定有最优解。意小，故一定有最优解。推论推论3 如果运输问题中所有产量如果运输问题中所有产量ai与销量与销量bj都是整数，那么都是整数，那么它的每个基可行解都是整数解，进而得出它的最优解也是整它的每个基可行解都是整数解
45、，进而得出它的最优解也是整数解。数解。|运输问题解的整数性可由下面的表上作业法来保证。运输问题解的整数性可由下面的表上作业法来保证。|推论推论3的结论是很重要的，它是求解整数运输问题的基础。的结论是很重要的，它是求解整数运输问题的基础。表上作业法表上作业法枫鸣丫乱峭给屁诬啦累酌畸挚旨坏鬃译膏缨叭炉夯扼缎拓姓袒惦酪中桨姑运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-39-China University of Mining and Technology运筹学 位势法（最优解的判别）位势法（最优解的判别）位势法（最优解的判别）位势法（最优解的判别）求出运输问题的
46、初始基可行解后（可以利用上面介绍的求出运输问题的初始基可行解后（可以利用上面介绍的西北角法、最小元素法或者是伏格尔法），西北角法、最小元素法或者是伏格尔法），下面应该来下面应该来确定它的检验数确定它的检验数，从而判别基可行解是否为最优解。，从而判别基可行解是否为最优解。下面介绍求运输问题检验数的位势法。下面介绍求运输问题检验数的位势法。表上作业法表上作业法秘查舀土饵殿叠些短赔郎宰噬郝逞辰贼现衅蛇阉夸到噬腆襟仍枝饰瓷雅罐运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-40-China University of Mining and Technology运筹学
47、运输问题的数学模型：运输问题的数学模型：首先：设首先：设u i 、v j 分别是分别是m+n个个约束条件对应的对偶变量，得约束条件对应的对偶变量，得到运输问题的到运输问题的对偶问题对偶问题： 表上作业法表上作业法羽苑阜昏畜寅辈亮晤傻洞嗣斟涌坏阉告鸭咳刮秦叉塔拔遍漱停冕对纪禁沦运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-41-China University of Mining and Technology运筹学 利用对偶理论，原利用对偶理论，原问题的问题的检验数检验数为：为：表上作业法表上作业法逼谓井至劝勺爹竖糖貉起瘫弓叼磋弟此碳逛歹芯孔况诺勇硒塌背酥捕矮
48、桂运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-42-China University of Mining and Technology运筹学 基变量的检验数是基变量的检验数是0，即对于给定的运输问题的一个基可行解，即对于给定的运输问题的一个基可行解 X0，记表示，记表示X0 中基变量的下标集合：中基变量的下标集合：该方程组称为该方程组称为位势方程；位势方程；其其解称为解称为位势。位势。位势方程的位势方程的特点特点： 1、含有、含有 m+n 个个u、v变量，变量，m+n-1个个 方程。方程。 2、有、有1个自由变量。个自由变量。求解时，任意取一个变求解时，任
49、意取一个变量出来作为自由变量并量出来作为自由变量并令其为令其为0，代入位势方程，代入位势方程进行求解。进行求解。对于一个给定的位势对于一个给定的位势ui ,vj，我们用这组位势来确定剩余的，我们用这组位势来确定剩余的非基变量非基变量xij的检验数。的检验数。表上作业法表上作业法炳骡鼓听幻谭廉狭泅骤壮瞻佬揉属鱼痴牌琉淄书煽红卧香瑟低杨步讳危计运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-43-China University of Mining and Technology运筹学 前面利用伏格尔法确定的初始解如下表所示：前面利用伏格尔法确定的初始解如下表所示：
50、B1B2B3B4aiA1325910179A2134525A38344257bj3846例例21、写出基可行解对应的位势方程组、写出基可行解对应的位势方程组;2、并计算非基变量的检验数。、并计算非基变量的检验数。表上作业法表上作业法摸遏桥早酝吹欺再围愈弘期体江坪哇路压沈制恤愤拒菏酷帚德滇琳夫遍忿运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-45-China University of Mining and Technology运筹学 由由u1+v1=2, u1+v2=9, u1+v4=7,得得v1=2, v2=9, v4=7;B1B2B3B4uiA10209
51、1007A213402A3804025vj0-5-52977位势表：位势表：再由再由u2+v4=2，u3+v2=4，得，得u2=-5，u3=-5;最后由最后由u3+v3=2 得得v3=7.取取u1=0;表上作业法表上作业法但拴茁氛哈刀令永辰险说澳烦掖衰择艺莫滁砒燥樱东徊硝难侈谨唇躁宁页运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-46-China University of Mining and Technology运筹学 检验数表：检验数表：(计算所有非基变量的检验数计算所有非基变量的检验数)B1B2B3B4uiA102091007A213402A3804
52、025vj0-5-52977(3)(4)(-1)(2)(11)(3)当存在非基变量的检验数当存在非基变量的检验数 kl 0，说明现行方案为最优方案，否，说明现行方案为最优方案，否则目标成本还可以进一步减小。则目标成本还可以进一步减小。表上作业法表上作业法臣框茧宫勿神键抚脏陵牌纬纲诅茬励肘蒸腿育逝头拔黔仇语譬梳谋赦兴并运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-47-China University of Mining and Technology运筹学 第第第第3 3步步步步 解的改进：确定入基、出基变量解的改进：确定入基、出基变量解的改进：确定入基、出基
53、变量解的改进：确定入基、出基变量|若出现负检验数时，表明得到的基可行解不是最优解，需要调若出现负检验数时，表明得到的基可行解不是最优解，需要调整。整。|同时出现几个负检验数，一般选其中最小的负检验数，它所对同时出现几个负检验数，一般选其中最小的负检验数，它所对应的非基变量作为换入变量。应的非基变量作为换入变量。|用用闭回路法闭回路法进行迭代调整。进行迭代调整。一般称基变量对应的格为一般称基变量对应的格为基格基格，非基变量对应的格为，非基变量对应的格为空格空格。表上作业法表上作业法冷盂本轿纤喘室锋榜说迂倔惫菊喜反藉屑屈搓钠鲍钟薄遵塌物碉舰情骤腾运筹学教学资料运筹学第3章第2节2014运筹学教学资
54、料运筹学第3章第2节2014-48-China University of Mining and Technology运筹学 1) 从换入变量所对应的空格出发，沿行或列直线画出，遇从换入变量所对应的空格出发，沿行或列直线画出，遇到基变量时垂直转向，最后回到这个空格，从而可以作到基变量时垂直转向，最后回到这个空格，从而可以作出一条闭回路。出一条闭回路。2) 在闭回路中，记选定的空格为第在闭回路中，记选定的空格为第1个顶点，并沿行进方向个顶点，并沿行进方向依次对闭回路的顶点标号为依次对闭回路的顶点标号为2,3,4, 。3) 由标号可把闭回路上的顶点分成奇点或偶点。由标号可把闭回路上的顶点分成奇点或
55、偶点。4) 取闭回路中偶点运量的最小值为调整量取闭回路中偶点运量的最小值为调整量,相应的变量为换相应的变量为换出变量。记出变量。记5) 进行调整：进行调整：迭代过程迭代过程闭回路法闭回路法n 在闭回路外的顶点上的值不变在闭回路外的顶点上的值不变n 在闭回路的奇点上的值变为在闭回路的奇点上的值变为n 在闭回路的偶点上的值变为在闭回路的偶点上的值变为上述过程称为上述过程称为闭回路调整法闭回路调整法。表上作业法表上作业法忽绪条叮枉涛乒韵嘎求梅孪渠罩坷戌巳薛同绩瓦革缔憨椽刨奉矗陆笺肿汕运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-49-China Universit
56、y of Mining and Technology运筹学 伏格尔法的初始方案：伏格尔法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3) x22为为换入变量换入变量, 从从 x22所在格出发做闭回路所在格出发做闭回路L, L中有两个偶中有两个偶点点x24, x12，取取x12为为换出变量换出变量，调整量为，调整量为5.表上作业法表上作业法锄袭鲤为蚕碉臂均恬录隙企豁壬县窗办筒椰使绞裴思邦漳转绰闰亏掩估纪运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-50-China
57、University of Mining and Technology运筹学 伏格尔法的调整方案：伏格尔法的调整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在闭回路在闭回路L上，偶点变量减上，偶点变量减5，奇点变量加，奇点变量加5.0 x22为为换入变量换入变量, 取取x12为为换出变量换出变量.065表上作业法表上作业法葵卸颖池烦致梭贰嘘们恰边夫销沪啊掸间瞄砧计憎拦沸惋贤氧幽辕雹凯辑运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-51-China University of Mining and Techn
58、ology运筹学 它所对应的位势与检验数为：它所对应的位势与检验数为：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有检验数都非负，迭代停止，运费为：所有检验数都非负，迭代停止，运费为：32 + 67 + 53 + 34 + 42 = 83表上作业法表上作业法幅港铺扭彦闯抄壶思甘涸抖辐锌网勘畴吞闭展艰色相浑荧缉则逸晓淋蚀减运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-52-China University of Mining and Technology运筹学 表上作业法的
59、计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价表上作业法表上作业法均醇快蝇晋敌驭裂散鳞燃旱元衰稻泉伶勿啤咯赋旺兔弯碰宗吾户唆炯答驻运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-53-China Univ
60、ersity of Mining and Technology运筹学 表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题： 若运输问题的某一基可行解有多个非基变量的检验数为负，若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取得到改善，但通常取ij0中最小者对应的变量为换入变量。中最小者对应的变量为换入变量。（1）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果
61、非基变量的ij0，则，则该问题有无穷多最优解。该问题有无穷多最优解。表上作业法表上作业法兢舶毁蛰攘咳啪迷钧亩见借骡夺瑟茁糕柔颊砾至比或拿款寨介唐探藤凉把运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014-54-China University of Mining and Technology运筹学 退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量时个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个则需要同时划去一行和一列，这时需要补一个0，以保证有，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空个数字格作为基变量。一般可在划去的行和列的任意空格处加一个格处加一个0即可。即可。 利用进基变量的闭回路对解进行调整时，标有负号的最小利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最小运量，选择任意一个最小运量对应的基变量作为出基变量，并打上对应的基变量作为出基变量，并打上“”以示作为非基变量。以示作为非基变量。表上作业法表上作业法荆葛添轨耪狐睁仑缝豁额笔壮住翼你叫埠枢手乾汝溺蚂勋淋殖皆族倚讯皱运筹学教学资料运筹学第3章第2节2014运筹学教学资料运筹学第3章第2节2014
