最小元素法寻找初始可行基的方法

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

中文名

最小元素法

英文名

The minimum element method

学科

数学

思路

运价最小的优先调运

简介

若某行(列)的产量(销量)已满足，则把运价表中该运价所在行(列)划去；找出未划去的运价中的最小数值，按此办法进行下去，直至得到一个基本可行解的方法。

所谓退化现象是指：当在平衡表中某一处填入一数字后，该数字所在的行和列同时被满足，即需方的需求得到满足，同时供方的供应数量也已经供完的现象。

基本思想

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

表上作业法是简单有效的求解运输问题的算法，而初始方案的确定对表上作业法尤为重要。对此提出了使用最小元素法的一个原则，利用该原则可以避免可能存在的多余计算过程，从而减少调整次数。[1]

第一步：列出运价表和调运物资平衡表。

运用表上作业法时，首先要列出被调运物资的运价表和运用表上作业法时，首先要列出被调运物资的运价表和供需平衡表（简称平衡表）。

第二步：编制初始调运方案。

首先，在运价表中找出最小的数值，若出现几个同为最小，则任取其中一个。可见A2B1最小，数值为1，这表示先将A2产品供应给B1是最便宜的，故应给C21所对应的变量x21以尽可能大的数值。显然x21=min{4，3}=3。

在表中的A2B1处填上“3”。B1列被满足，已不需要A1和A3再向它供货，故运价表2中的第一列数字已不起作用，因此将原运价表1中的第一列划去，并标注①（不标注可也，标注可看出是第几步划去的）。

然后，在运价表中未划去的元素中找最小运价A2B3=2，让A2尽量供应满足B3的需要，由于A2的4已经供应了3T给B1，最多只能供应1T给B3。于是在平衡表的A2B3格中填上“1”；相应地由于A2所生产的产品已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注②。

第三步：初始方案的检验与调整。

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

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

参考资料

1.运输问题最小元素法的一个原则·万方数据知识服务平台