-
1 视频
-
2 重点、难点提要
计算步骤:
(1) 找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法)
(2) 求检验数。(闭回路法或位势法) 判别是否达到最优解。如已是最优解,则停止计算,否则转到下一步。
(3) 对方案进行改善,找出新的调运方案。(表上闭回路法调整)
(4) 重复(2)、(3),直到求得最优调运方案。
确定初始方案
①初始基可行解——最小元素法
基本思想:为了减少运费,应优先考虑单位运价最小(或运距员短)的供销业务,最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地,以后将不再考虑。然后,在余下的供、销点的供销关系中,继续按上述方法安排调运,直至安排完所有供销任务,得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务,故称为最小元素法。
②初始基可行解--沃格尔法
对每一个供应地或销售地,均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。
沃格尔法基本思想: 在罚数最大处采用最小运费调运。
如果罚数的值不大,当不能按最小单位运价安排运输时造成的运费损失不大;反之,如果罚数的值很大,不按最小运价组织运输就会造成很大损失,故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。
沃格尔法计算步骤:
分别计算各行、各列次小、最小运价的差额(罚数),优先在最大差额处进行供需搭配。
步骤:
1、计算未划去行、列的差额;
2、找出最大差额对应的最小元素cij进行供需分配;
3、在未被划去的行、列重新计算差额。
表上作业法须注意的问题:
(1)无穷多最优解
在前面提到,产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解?依线性规划单纯性最优解判别标准,即某个非基变量(空格)的检验数为0时,该问题有无穷多最优解。
(2)退化
用表上作业法求解运输问题当出现退化时,在相应的格中一定要填一个0,以表示此格为数字格。有以下两种情况:
(1)当确定初始解的各供求关系时,若在(i,j)格填入某数字后,出现Ai处的余量等于Bj处的需量,这时在产销平衡表上填一个数,而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格。这时需要添一个“0”。它的位置可在对应同时划去的那行或那列的任一空格处。
(2)在用闭回路法调整时,在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后,得到退化解。这时有一个数字格调必需填入一个0,表明它是基变量,当出现退化解后,并作改进调整时,可能在某闭回路上有标记为(-1)的取值为0的数字格,设应取调整量θ=0。