《最小元素法》.docx

什么是最小元素法［1］最小元素法是找出运价表中最小的元素，在运量表内对应的格填入允许取得的最大数，若某行（列）的产量（销量）已满足，则把运价表中该运价所在行（列）划去；找出未划去的运价中的最小数值，按此办法进行下去，直至得到一个基本可行解的方法注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元素例外（同时划去一行和一列）O当填上一个数后行、列同时被满足（也就是出现退化现象）时，也只任意划去一行（列）需要填入“C的位置不能任意确定，而要根据规则来确定所谓退化现象是指：当在平衡表中某一处填入一数字后，该数字所在的行和列同时被满足，即需方的需求得到满足，同时供方的供应数量也已经供完的现象最小元素法的基本思想是：运价最小的优先调运，即从单位运价中最小的运价开始确定供销关系，然后次小，一直到给出初始基本可行解为止［编辑］最小元素法的例子［1］第一步：列出运价表和调运物资平衡表运用表上作业法时，首先要列出被调运物资的运价表和供需平衡表（简称平衡表），如表1,2所示Biftft虱3n310192874105\需Bi供虽（T）74出g，T）365620第二步：编制初始调运方案。

首先，在运价表中找出最小的数值（若几个同为最小，则任取其中一个），A2B1最小，数值为1,这表示先将A2产品供应给B1是最便宜的，故应给C21所对应的变量X21以尽可能大的数值显然X21=min{4,3}=3在表4中的A2B1处填上“3”B1列被满足，已不需要A1和A3再向它供货，故运价表2中的第一列数字已不起作用，因此将原运价表1中的第一列划去，并标注①（见表3）y地产ft位3:||||11-:31Q||1,9■_：£8②~L7\44::105⑤①④'③需&供虽-Ti京】47314在639若量(T)36S620然后，在运价表中未划去的元素中找最小运价A2B3=2,让A2尽量供应满足B3的需要，由于A2的4已经供应了3T给Bi，最多只能供应1T给B3o于是在平衡表的A2B3格中填上“[”相应地由于A2所生产的产品已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注②仿照上面的做法，一直做下去，就可以得到表4此时，在运价表中只有AiB4对应的运价10没有划掉，而B4尚有3T需求，为了满足供需平衡，所以最后在平衡表上对应AiB4处应填入“3”这样就得到表5。

需供BxJ?4供曝『T)A437314639需量(T)365620对于编制初始方案说明以下几点：应用最小元素法编制初始调运方案，这里的最小”系指局部而言，就整体考虑的运费不见得一定是最小的可以作为初始方案的调运方案，其填有数字的方格数应是供应点个数加需求点个数之和再减1,即（m+n-1）第三步：初始方案的检验与调整西北角法的例子[1]从表1中可知，总的产量=总的销量，故产销是平衡的第一步：列出运价表和调运物资平衡表运用表上作业法时，首先要列出被调运物资的运价表和供需平衡表（简称平衡表），如表1,2所示表1表2Biftft瓦3n310192874105供、xBi5s氏供虽（T）Al74出9需ft(T)36s620第二步：编制初始调运方案首先在表2的西北角方格（即左上角方格，对应变量X11）,尽可能取最大值:X11=min{3,7}=3将数值3填入该方格（见表3）由此可见X21,X31必须为0,即第一列其他各方格都不能取非零值，划去第一列在剩下的方格中，找出其西北角方格X12,X12=min{6,7-3}=4将4填入它所对应方格，第一行饱和，划去该行再找西北角方格X22,X22=min{6-4,4}=2X23,将2填入X22所对应方格，于是第二列饱和，划去该列。

继续寻找西北方格为X23=min{5,4-2}=2将2填入X23所对应方格，第二行饱和，划去该行剩下方格的西北角方格为X33=min{5-2,9}=3将3填入X33所对应方格，第三列饱和，划去该列最后剩下X34方格，取X34=6、需供玖%瓦供量(T)出341224瓦369ff*CT)365620这样我们就找到了m+n-1=3+4-1=6个基变量，它们为：X”=3,Xi2=4,X22=2,X23=2,X33=3,X34=60显然它们用折线连接后不形成闭回路这就是西北角法所找初始基可行解，所对应的目标值为：2X200+1X250+3X150+1X150+3X250+3X300+4X200=4000,各列方格中数值之和是我们找到的初始基可行解可通过各行方格中数值之和是否等于产量否等于销量来简单验证利用西北角法找初始基可行解简单可行，但也存在问题例如在表3中可见C35=4,单价高于该行其他各方格，最简单想法是单价小的情况下多运些货物，这样总运费会更小些，最小元素法就改进了西北角法的缺点。