软考高项运筹学“伏格尔法”详解

一、伏格尔法介绍

伏格尔法(Vogel’s Approximation Method,VAM),伏格尔法又称“差值法”,通常用于解决运输问题。运输问题是一类线性规划问题,涉及在不同源点和目标点之间以最小成本或最大利润进行物品运输的问题。该方法考虑到,某产地的产品如不能按最小运费就近供应,就考虑次小运费,这就有一个差额。差额越大,说明不能按最小运费调运时,运费增加越多。因而对差额最大处,就应当采用最小运费调运。同理也适用于产销量分配。

伏格尔法是一种求解运输问题的迭代方法,它通过考虑每行和每列的最小成本差异来选择下一个基本单元。具体步骤如下:

1、对每行和每列计算差值(即找出每行和每列中最小和次小的,然后计算它们的差值)。

2、找到具有最大差值的行或列,作为下一个基本单元。如果有多个具有相同最大差值的行或列,可以任选其中之一。

3、计算选择的行或列中每个单元的运输量,确定实际运输量并更新供应和需求。

4、重复步骤1-3,直到所有供应和需求都满足。

二、例题

【2022年上半年 – 第68题】

某公司有东部、中部、西部三个生产基地,生产的产品需要运送到甲、乙、丙、丁四个市场,从生产基地到各个市场的单位运价及产量和需求量如表所示,完成该运输任务所需的最小运费为( )

A. 242

B. 244

C. 289

D. 302

答案:B

三、例题解析

题目没有说是什么单位,为方便解题,假设单位是吨。

第一步:计算每行每列的最小元素和次小元素差额

图片[1]-软考高项运筹学“伏格尔法”详解

第二步:找到最大差额为乙的列差:5

图片[2]-软考高项运筹学“伏格尔法”详解

与最大差额同行或同列的最小运价为准,用其所在行的产量,最大限度满足所在列的需求。

西部运送14吨到乙,每吨运价5,运费:14*5=70;

乙的需求被满足,删除乙这一列,西部的产量余8

第三步:找到最大差额为丁的列差3【第一次重复】

图片[3]-软考高项运筹学“伏格尔法”详解
图片[4]-软考高项运筹学“伏格尔法”详解

以最大差额同行或同列的最小运价为准,用其所在行的产量,最大限度满足所在列的需求。

西部余下的8吨全部运送到丁,每吨运价6,运费:8*6=48;

西部产量用完,删除西部这一行,丁余下的需求为6

第四步:找到最大差额为丁的列差2【第二次重复】

图片[5]-软考高项运筹学“伏格尔法”详解
图片[6]-软考高项运筹学“伏格尔法”详解

以最大差额同行或同列的最小运价为准,用其所在行的产量,最大限度满足所在列的需求。

中部运送6吨到丁,每吨运价9,运费:6*9=54;

丁的需求全部满足,删除丁这一列,中部产量余4

第五步:找到最大差额为甲的列差2【第三次重复】

图片[7]-软考高项运筹学“伏格尔法”详解
图片[8]-软考高项运筹学“伏格尔法”详解

以最大差额同行或同列的最小运价为准,用其所在行的产量,最大限度满足所在列的需求。

中部余下的4吨运送到甲,每吨运价2,运费4*2=8;

中部产量用完,删除这一行,甲的需求剩余4

第六步:最后只剩下东部有产量16吨,将其中的4吨运送到甲,12吨运输到丙,完成运输任务。

图片[9]-软考高项运筹学“伏格尔法”详解

东部运送4吨到甲,每吨运价4,运费:4*4=16;

东部运送12吨到丙,每吨运价4,运费:12*4=48;

第七步:总结所有运价,将所有运价求和

西部运送14吨到乙,每吨运价5,运费:14*5=70;

西部运送8吨到丁,每吨运价6,运费:8*6=48;

中部运送6吨到丁,每吨运价9,运费:6*9=54;

中部运送4吨到甲,每吨运价2,运费:4*2=8;

东部运送4吨到甲,每吨运价4,运费:4*4=16;

东部运送12吨到丙,每吨运价4,运费:12*4=48;

总价:70+48+54+8+16+48=244

获取更多软考资料

关注公众号

添加微信好友

© 版权声明
THE END
喜欢就支持一下吧
点赞12赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情

    暂无评论内容