运筹学表上作业法
- 格式:ppt
- 大小:532.00 KB
- 文档页数:42
4 运输问题1、运输问题表上作业法的基本步骤。
答:表上作业法的基本步骤可参照单纯形法归纳如下:(1)找出初始基可行解:即要在阶产销平衡表上给出“”个数字格(基变量);(2)求各非基变量(空格)的检验数,判断当前的基可行解是否是最优解,如已得到最优解,则停止计算,否则转到下一步;(3确定入基变量,若,那么选取为入基变量;(4确定出基变量,找出入基变量的闭合回路,在闭合回路上最大限度地增加入基变量的值,那么闭合回路上首先减少为“0”的基变量即为出基变量;(5)在表上用闭合回路法调整运输方案;(6)重复2、3、4、5步骤,直到得到最优解。
2、“最小元素法”和“伏格尔”法的基本思想及基本操作。
答:最小元素法的基本思想是就近供应,即从单位运价表中最小的运价开始确定产销关系,依此类推,一直到给出基本方案为止。
伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差(如果存在两个或两个以上的最小元素费用增量定义为零)。
最大差对应的行或列中的最小元素确定了产品的供应关系,即优先避免最大的费用增量发生。
当产地或销地中的一方在数量上供应完毕或得到满足时,划去运价表中对应的行或列,再重复上述步骤,即可得到一个初始的基可行解。
3、闭合回路的构成以及利用闭合回路法求检验数的基本操作。
答:判断基可行解的最优性,需计算空格(非基变量)的检验数。
闭合回路法即通过闭合回路求空格检验数的方法。
从给定的初始方案的任一空格出发寻找闭合回路,闭合回路顶点所在格括号内的数字是相应的单位运价,单位运价前的“+”、“-”号表示运量的调整方向。
空格处单位运量调整所引起的运费增量就是空格的检验数。
仿照此步骤可以计算初始方案中所有空格的检验数。
4、利用位势法求检验数以及利用闭合回路进行方案调整的基本操作。
答:位势法求解非基变量检验数的基本步骤:第一步:把方案表中基变量格填入其相应的运价并令;让每一个基变量都有,可求得所有的位势;第二步:利用计算各非基变量的检验数方案的优化基本步骤:在负检验数中找出最小的检验数,该检验数所对应的变量即为入基变量。
《运筹学》第三版(清华大学出版社)P79例1,表上作业法,运用西北角法确定初始基可行解。
西北角法是从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数;然后按行(列)标下一格的数;若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;如此进行下去,直至得到一个基本可行解的方法。
西北角法的例子: P79例1从表1中可知,总的产量=总的销量,故产销是平衡的。
第一步:列出运价表和调运物资平衡表。
运用表上作业法时,首先要列出被调运物资的运价表和供需平衡表(简称平衡表),如表1,2所示。
第二步:编制初始调运方案。
首先在表2的西北角方格(即左上角方格,对应变量x11),尽可能取最大值:x11=min{3,7}=3将数值3填入该方格(见表3)。
由此可见x21,x31必须为0,即第一列其他各方格都不能取非零值,划去第一列。
在剩下的方格中,找出其西北角方格x12,x12=min{6,7-3}=4将4填入它所对应方格,第一行饱和,划去该行。
再找西北角方格x22,x22=min{6-4,4}=2将2填入x22所对应方格,于是第二列饱和,划去该列。
继续寻找西北方格为x23,x23=min{5,4-2}=2将2填入x23所对应方格,第二行饱和,划去该行。
剩下方格的西北角方格为x33,x33=min{5-2,9}=3将3填入x33所对应方格,第三列饱和,划去该列。
最后剩下x34方格,取x34 = 6。
这样我们就找到了m+n-1=3+5-1=7个基变量,它们为:x11 = 3,x12 = 4,x22 = 2,x23 = 2,x33 = 3,x34 = 6。
显然它们用折线连接后不形成闭回路。
这就是西北角法所找初始基可行解,所对应的目标值为:2×200+1×250+3×150+1×150+3×250+3×300+4×200=4000我们找到的初始基可行解可通过各行方格中数值之和是否等于产量,各列方格中数值之和是否等于销量来简单验证。