理论教育 运筹学:高效表上作业法解决运输问题

运筹学:高效表上作业法解决运输问题

时间:2023-11-26 理论教育 版权反馈
【摘要】:因为求解过程都是在平衡表上进行,所以把这种方法称为表上作业法。单纯形法通过行运算进行迭代,而表上作业法是在闭回路上对基本可行解进行调整。通过以上分析,现在给出表上作业法的主要步骤:第一步:把运输问题给出的产量、销量和单位产品运价整合成平衡表。为了系统、深入地掌握表上作业法的步骤,下面对表上作业法的过程做具体介绍。

运筹学:高效表上作业法解决运输问题

表上作业法是应用比较广泛的运输问题的求解方法,它也是一种迭代计算,求解思路和单纯形法一样,也是先求出初始基本可行解,然后用检验数判定这个解是否为最优解,如果是最优解,计算停止,否则就对解进行调整,然后再判断,如此循环迭代下去,直到求出最优解为止。因为求解过程都是在平衡表上进行,所以把这种方法称为表上作业法。

尽管表上作业法和单纯形法的求解思路一样,但求解过程和计算方法会有一些差别。为了更好地掌握表上作业法的求解步骤和具体的计算过程,下面把两者主要的相同之处和不同之处列出来:

(1)单纯形法是通过寻找或构造单位矩阵来确定初始基本可行解,而表上作业法是通过另外的西北角法、最小元素法或差值法来确定初始基本可行解。

(2)单纯形法是计算出机会费用zj以后,直接计算检验数的代数式cj-zj或zj-cj,而表上作业法是通过另外的闭回路法或位势法来计算检验数,其实也是间接的计算代数式cj-zj

(3)表上作业法判断基本可行解是否为最优解的原则和方法与单纯形法一样。

(4)若基本可行解不是最优解,需要迭代调整,二者在确定换入变量和换出变量的原则是一样的,但是方法不同,表上作业法是通过闭回路的方法来确定换入变量和换出变量。

(5)单纯形法通过行运算进行迭代,而表上作业法是在闭回路上对基本可行解进行调整。

通过以上分析,现在给出表上作业法的主要步骤:(www.daowen.com)

第一步:把运输问题给出的产量、销量和单位产品运价整合成平衡表。

第二步:通过西北角法、最小元素法或差值法来确定初始基本可行解。

第三步:通过闭回路法或位势法求出检验数。

第四步:利用第2.2节单纯形法中最优解判断的思路来判断是否达到最优解,如果达到最优解,停止计算,否则转到下一步。

第五步:确定换入变量和换出变量,再利用表上的闭回路进行解的调整,从而找出新的基本可行解。

第六步:返回第三步。

为了系统、深入地掌握表上作业法的步骤,下面对表上作业法的过程做具体介绍。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈