最小元素差异法

“沃格尔法”(vogelMethod)，又称最小元素差异法。是线性规划中常用的一种方法，可以用来编制最优计划方案。本文仅就此种方法在计划工作中如何应用，我们通过具体例子来加以说明。一、问题的提出:假设本地区有甲乙丙丁四个煤炭产区，年产量分别是1300、800、600、1600万吨。有戊己庚辛四个消费地，对煤炭的需要量分别是1000、1500、800、1000万吨，该地区生产量和消费量平衡。由每个产区到各个消费区每吨煤的运费如下表所示。现要求编制合理的运输计划，使之总运输费用为最小。各个产区与各个消费区应适应以下约束条件:X11+Xl2+X13+X14=1300X21+X22+X23+X24=800X31+X32+X33+X34=600X41+X42+X43+X44=1600即=ai(i=1，2，3，…，m)1nijjXX11+X21+X31+X41=1000X12+X22+X32+X42=1500X13+X23+X33+X43=800X14+X24+X34+X44=1000即=bj(j=1，2，3，…，n)求目标函数S=→达到最小1mijiX11mnijijijCX二、运用“沃格尔法”编制最优计划的计算过程:将该地区煤炭的生产量、消费量以及运价用矩阵的形式列出:求解过程:1.先将矩阵表中的各行、各列中的运费的最小元素与次小元素之差。将其差额分别标出，找出其差额最大的一行或一列，选择其中最小的元素进行分配。(见下表)。表二中最大的差异是第四列的3，因此先分配第四列中的最小元素2，将600吨产量分配给3行4列的2，将运出量标在2的右上方，横线下方的1000万吨需要量已满足600万吨，也应标出。见表三。2．将满足了需要量或消费量的行或列消去，得出下面一个新的矩阵式，继续重复上述计算步骤，继续进行分配，到分配结束为止。上表中最大差异是2，其表中最小元素是一行三列的2，因此先分配给2，从1300万吨产量中调出800万吨给一行三列的2，并将运出量填在2的右上方，横线下方的需要量800万吨已经满足，同时减去，得出表五。上表中最大差异是3，其最小元素是一行一列的4，先分配给4，并在4的右上方标出分配的数量，竖线右边1300万吨已分配完毕，得出下表(见表六)。上表中最大差异是3，最小元素是5，将800万吨分配给表中一行二列的5(见表七)。将竖线右方的产量1600万吨，分别分配给剩下的三个消费地，至此分配完毕。(见下表)所需运费4×500+6×500+5×800+8×700+2×800+2×600+5×400=19400万元。三、对方案进行最优性检查与调整如前所述，我们编制的计划方案是否最优，还不能判定，还必须通过对此方案的检查方能判定是否最优。如不是最优同时进行调整。介绍一种矩阵式检验法:此检验方法是首先找出由两个带有分配量数字的分配点，所组成的对角线，再将这两个分配点所在的行和列组成的另外两个对应的对角点找出来。组成2×2方阵。将这个矩阵的两对对角线元素的运费之和进行比较，如果两个带有分配量的运价之和小于另外两个对角点的运费之和，则表示“最优”，检验为合格。如果两个带有分配量的运费之和大于另外两个对角点的运费之和，则运量分配为不合格，必须进行“最优化”调整，检验方法如下:因检验不合格，需要进行调整、调整方法如下:将两个分配点中较小的分配量从这两个分配点中同时减去，并将被减掉的这个数字同时加到另外两个对角点上去。请看此例，在8和2两个对角分配点上运量较小的是600，因此这两点同时减去600，将600同时加在4和5的对角点上，即:通过这样的调整与原运费就有了变化。这四点的原运费2×600+8×700+5×400=8800万元。调整后的运费4×600+8×100+5×1000=8200万元。8800万元一8200万元=600万元。(节省了600万元)将已经过调整的方案重新列出来。然后继续进行检验经过检验与调整后均已合格，因此第二个分配方案就是最优方案。此目标函数:4×500+2×800+5×800+4×600+6×500+8×100+5×1000=18800万元比原方案19400万元一18800万元=600万元，减少了600万元。经过检验此方案就是最优方案。此方法有时可以一次达到最优解，不必再进行调整，而且计算迅速简便，在制订计划中可多采用这种方法。