优化运输方案的调整方法

视频-3．2．3表上作业法-3-调整运输方案-闭回路法

根据判定定理,当非基变量的检验数中有负数时,说明当前方案不是最优方案,因此需要调整,闭回路法是常用的调整方法,步骤如下:

①对于某一非基变量xij,若σij＜0,则以该空格为起始顶点做闭回路。

②确定调整量θ,θ＝min{该闭回路中奇数次顶点调运量}。

③在闭回路内,将奇数次顶点对应的调运量减去θ,偶数次顶点对应的调运量加上θ。调整后,某一奇数次顶点对应的调运量将变为0,另有一偶数次顶点对应的调运量变为xij＋θ,前者出基,后者入基。

注意:如果存在两个或两个以上的σij＜0,应选择最小的σij做闭回路进行调整。

【例3-8】用闭回路法对【例3-3】的初始方案进行调整。

解:

由检验结果可知,【例3-3】的初始方案不是最优,因此需要对其进行调整,过程如下:

因σ12＝－20＜0,因此以x12空格为顶点做出闭回路,如表3-22所示。调整量为θ＝min{100,150}＝100,调整后的结果如表3-23所示。

表3-22

从表3-23中可以看出,原非基变量x12入基(0→100),原基变量x13出基(100→0)。(www.xing528.com)

新的运输方案为:

S(1)＝100×90＋100×70＋50×65＋200×75＝34 250

即A1→B1(100),A1→B2(100),A2→B2(50),A2→B3(200),其他路线调运量为零,总费用为34 250。

表3-23

接下来的计算步骤请读者自己完成,参考答案为:

第二次检验,σ13＝20,σ21＝－5。

第二次调整后方案为:

第三次检验,σ13＝15,σ22＝5。

因所有非基变量检验数均大于零,该运输问题得到的最优方案为: