《运筹学教学资料》运筹学第3章第2节ppt课件.ppt

《《运筹学教学资料》运筹学第3章第2节ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单形法。步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、Vogel法第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存在检验数σij<0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步迭代过程中得出的所有解都要求是运输问题的基可行解表上作业法给定下列运输问题B1B2B3B4产量A1291079A213425A384257销量3846分析：由于总产量是9

2、+5+7=21，总销量是3+8+4+6故产销平衡。该问题有3个产地，4个销地，故基可行解含有3+4-1=6个基变量。例1表上作业法第1步求初始方案运输问题的初始方案的确定主要有三种方法：１.西北角法２.最小元素法３.伏格尔法运输问题是一种特殊的线性规划问题（大型稀疏矩阵的处理）,它的初始基的确定具有一定的难度。表上作业法1.西北角法（左上角法）西北角法每次都从运价表的左上角确定基变量。算法的每一步都取最左上角的元素（如xij）为基变量，其取值是相应行列产销量的最小者，即然后划去产销平衡运输表中的一行或一列得到一个新的产销平衡运输表。再重复上述过

3、程直至得到问题的运输方案。具体的算法过程如下：表上作业法B1B2B3B4产量A19A25A37销量3846令x11为基变量，销地B1的销量３全由产地A1供给，所以x21=0,x31=0,x21与x31为非基变量。将x11=３填到调运方案表中第1行第1列上。画去运输数据表中第1列,A1的产量剩余为9-3=6。得到新的产销平衡运输表。例如对于前面的例子：3003/09/6西北角法计算1表上作业法B1B2B3B4产量A19/6A25A37销量3/08463008/29/6/0令x12为基变量，则产地A1的产量6全供给销地B2，所以x13=x14=0，

4、x13与x14为非基变量。将x12＝6填到调运方案表中第1行第2列上。画去运输数据表中第1行，B2的销量还要8-6=2。得到新的产销平衡运输表。600西北角法计算2表上作业法B1B2B3B4产量A19/6/0A25A37销量3/08/2463008/2/05/3600令x22为基变量，则销地B2的销量2全由产地A2供给，所以x32=0，x32为非基变量。将x22＝2填到调运方案表中第2行第2列上。画去运输数据表中第2列，A2的产量剩余为5-2=3。得到新的产销平衡运输表。20西北角法计算3表上作业法B1B2B3B4产量A19/6/0A25/3A

5、37销量3/08/2/0463004/15/3/060020令x23为基变量，则产地A2的产量3全供给销地B2，所以x24=0，x24为非基变量。将x23＝3填到调运方案表中第2行第3列上。画去运输数据表中第2行，B3的销量剩余为4-3=1。得到新的产销平衡运输表。30西北角法计算4表上作业法B1B2B3B4产量A19/6/0A25/3A37销量3/08/2/0463004/15/3/06002030现在只有一个产地两个销地，故令x33=1，x34=6为基变量，将其分别填到调运方案表中第3行第3列与第3行第4列上。16得到产销平衡运输问题的一个

6、初始方案西北角法计算5表上作业法B1B2B3B4产量A1369A2235A3167销量3846这个方案的运费是2×3+9×6+3×2+4×3+2×1+5×6=110。表中填了6个数值，正好对应基变量，即6=m+n–1=3+4-1其余未填数字的空格位置的数值为0,对应非基变量.西北角法确定的初始方案没有考虑运价的影响，因而离最优方案相去甚远。评注表上作业法2.最小元素法最小元素法的基本思想是——就近供应；即从运价表中最小的运价开始确定供销关系.若有几个最小运价，则任取其一。最小元素法和西北角法大体差不多，只是考虑了运价的因素。用最小元素法求得的基

7、本可行解更接近最优解，所以也称为近似方案。表上作业法B1B2B3B4aiA1291079A213425A384257bj3846销地B1的销量3全由产地A2供给，所以x11=x31=0。将x21＝3填到调运方案表中第2行第1列上。最小元素法计算13003/05/2画去运输数据表中第1列，A2的产量剩余为5-3=2。得到新的产销平衡运输表。寻找运价中最小的：令表上作业法B1B2B3B4aiA1291079A213425/2A384257bj3/0846最小元素法计算23006/45/2/0产地A2的产量2全供给销地B4，所以x22=x23=0。将

8、x24＝2填到调运方案表中第2行第4列上。画去运输数据表中第2行，B4的销量还要6-2=4。得到新的产销平衡运输表。200寻找运价中最小的：令表上作业