《运筹学教学资料》运筹学第3章第2节.ppt
《《运筹学教学资料》运筹学第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个基变量。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学教学资料 运筹学 教学 资料

链接地址:https://www.31ppt.com/p-5904497.html