理论教育 深入探讨表上作业法的优化方法

深入探讨表上作业法的优化方法

时间:2023-07-06 理论教育 版权反馈
【摘要】:在实际应用表上作业法求解运输问题时,可能会存在如下的问题。在用表上作业法求解初始解的过程中,每一次确定一个调运关系,以及根据产量与销量之间的大小关系确定调运方案后,总是划去一行或一列。这是表上作业法的第一种退化现象产生的原因。

深入探讨表上作业法的优化方法

在实际应用表上作业法求解运输问题时,可能会存在如下的问题。

1.适用条件

表上作业法适用的条件包括:一是目标函数是最小化的,即cij反映的是运输成本。二是约束条件都是等式,即运输问题是产销平衡的。

这样,min z就与max z是一致的了。

另外,当供不应求,即总产量小于总需求量时,可增加一个虚拟的产地,它的产量为供需差额,从该虚拟产地运往各个销售地的单位运价均为0,即所差的需求量并未满足;当出现了供过于求的情况时,可增加一个虚拟的销售地,其需求量为总产量与总需求量的差额,各个产地运往该销售地的运价也为0,即多余的物资并未运输,而是在各个产地存储起来了。这样两种方法总是可以将产销不平衡的运输问题转化为产销平衡的运输问题。但是需要注意的是,这里并没有考虑多余产量产生的费用和需求量未满足时产生的费用,如果要考虑这些费用,那么从虚拟产地运往各个销售地的单位运价就应该是各个销售地的单位缺货损失,而从各个产地运往虚拟销售地的运价就应该是各个产地单位物资的存储费用了。

2.退化问题(www.daowen.com)

运输问题本质上是线性规划问题,表上作业法的基础是单纯形法,所以在利用表上作业法求解时运输问题也可能出现退化现象。

在用表上作业法求解初始解的过程中,每一次确定一个调运关系,以及根据产量与销量之间的大小关系确定调运方案后,总是划去一行或一列。但是当出现产地与销地的数量相等时,会同时划去这一行和这一列,这样会造成最后得到的初始方案缺少一个方案点。这是表上作业法的第一种退化现象产生的原因。为了可以使用表上作业法进行求解,此时应该在划去这一行或这一列的某个位置添加一个0方案点,从而使方案点的个数为m+n-1个。

表上作业法在进行方案调整时,在闭回路上的奇数点位置会加上调整量,偶数点位置会减去调整量,该调整值为偶数点位置的最小运量。如果在这个闭回路上存在着多个偶数点位置的运量均是最小值,会造成一个变量入基,多个变量出基,使得方案点的个数不足。此时,也应该保留多余的0方案,只让一个方案点出基,其他点为0方案点。这样才能保证方案点的个数为m+n-1个。

总之,两种处理方法的核心都是增加0方案点,也使得方案点的个数为m+n-1个。

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

我要反馈