加入收藏设为首页

新闻详情

最小元素法

作者:兴发国际-兴发游戏平台-兴发官网    发布时间:2020-04-26 21:58:33    来源:兴发国际-兴发游戏平台-兴发官网    浏览:245
  

  声明:百科词条人人可编辑,词条创建和修改均免费,绝不存在官方及代理商付费代编,请勿上当受骗。详情

  最小元素法是表上作业法是求解运输问题时寻找初始可行基的一种简便而有效的方法,具体方法就是找出运价表中最小的元素,在运量表内对应的格填入允许取得的最大数。

  运输问题的典型情况是研究单一品种物质的运输调度问题:设某种物品有m个产地A

  (j=1,2,···,n)运输单位物品的运价为cij,问怎么调运这些物品才能使总运费最小?

  最小元素法是利用表上作业法解决运输问题的一种启发式方法,人们容易直观想到,为了减少运费,应该优先考虑单位运价最小(或运距最短)的供销业务才能最大限度的满足其供销量,然而在统筹兼顾的情况下,最小元素寻找的初始可行基并不一定是就是最优解,需要经过解的最优性检验和解的改进。

  为了保证供应的数量一定出售,销售的需求量一定能保证供应,在运输表内对应的格填入允许取得的最大数,即由

  的可供物品已用完,划掉一行表示换掉以后不再考虑这个产地,且销地的需求量由

  然后,在余下的供、销地的供销关系中,继续按上述方法安排调运,直至安排完所有供销任务,得到一个完整的解即一个完整的调运方案位置。这样就得到了运输问题的一个初始基可行解即调运方案。

  每次填完数,都只划去一行或一列,只有最后一个元素例外(同时划去一行和一列)。如果填上一个数后行、列同时被满足,也就是出现退化现象时,也只任意划去一行(列)。需要填入“0”的位置不能任意确定,而要根据规则来确定。

  由于该方法基于有限满足单位矩阵或运距最小的供销业务,故称为最小元素法。

  最小元素法的是:运价最小的优先调运,即从单位运价中最小的运价开始确定供销关系,然后次小,一直到给出初始基本可行解为止。

  运用表上作业法时,首先要列出被调运物资的运价表和运用表上作业法时,首先要列出被调运物资的运价表和供需平衡表(简称平衡表),如下表1、2所示。

  首先,在运价表中找出最小的数值,若出现几个同为最小,则任取其中一个。可见

  再向它供货,故运价表2中的第一列数字已不起作用,因此将原运价表1中的第一列划去,并标注①(不标注可也,标注可看出是第几步划去的)。

  需要注意的是,作为初始方案的调运方案,其填有数字的方格数应是供应点个数加需求点个数之和再减1,即(m+n-1),即表上作业法要寻求的基变量是(m+n-1)个。当遇到退化情形同时划掉一行一列的时候,需要进行补0,使基变量保持在(m+n-1)个,这是能让初始方案进行检验与调整的前提。

  应用最小元素法编制初始调运方案,这里的“最小”系指局部而言,就整体考虑的运费不见得一定是最小的,有时按照某一最小单位运价优先安排物品调运是,却可能导致不得不采用运费很高的其他供销点对,从而使整个运输费用增加。

  因此得到了运输问题的初始基可行解之后,即对应这个解进行最优性判别,看它是不是最优解。,改进初始基本可行解有两种最常用的方法:闭回路法和对偶变量法(位势法)。