最小元素

运筹学术语

最小元素法是找出运价表中最小的元素，在运量表内对应的格填入允许取得的最大数，若某行(列)的产量(销量)已满足，则把运价表中该运价所在行(列)划去；找出未划去的运价中的最小数值，按此办法进行下去，直至得到一个基本可行解的方法。

简介

注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元素例外（同时划去一行和一列）。当填上一个数后行、列同时被满足（也就是出现退化现象）时，也只任意划去一行（列）。需要填入“0”的位置不能任意确定，而要根据规则来确定。

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

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

基本思路

运输问题的典型情况是研究单一品种物质的运输调度问题：设某种物品有m个产地，各产地的产量分别是；有n个销地，各个销地的销量分别为。假定从产地向销地运输单位物品的运价为，问怎么调运这些物品才能使总运费最小？

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

定律定义

找出运价表中最小的价值系数，即对所有i和j，找出，优先考虑单位运价最小的供销业务。

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

选择在最大产能和最大销售量中最小的的物品量。若

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

如果

则销地的需求已全部得到满足，划掉一列表示以后不再考虑这个销地，且的可供量由减少为

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

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

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

方法步骤

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

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

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

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

首先，在运价表中找出最小的数值，若出现几个同为最小，则任取其中一个。可见A2B1最小，数值为1，这表示先将A2产品供应给B1 是最便宜的，故应给C21所对应的变量x21以尽可能大的数值。显然x21=min{4,3}=3。在表4中的A2B1处填上“3”。B1列被满足，已不需要A1和A3再向它供货，故运价表2中的第一列数字已不起作用，因此将原运价表1中的第一列划去，并标注①（不标注也可以，标注可看出是第几步划去的）。

表三

表四

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

仿照上面的做法，一直做下去，就可以得到表4。

此时，在运价表中只有A1B4对应的运价10没有划掉，而B4尚有3T需求，为了满足供需平衡，所以最后在平衡表上对应A1B4处应填入“3”，这样就得到表5。

表四

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

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

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

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

全国各地天气预报查询

上海市