《最小元素法.doc》由会员分享，可在线阅读，更多相关《最小元素法.doc（4页珍藏版）》请在三一文库上搜索。
1、4什么是最小元素法最小元素法 是找出运价表中最小的元素，在运量表内对应的格填入允许取得的最大数,若某行（列）的产量（销量）已满足，则把运价表中该运价所在行（列）划去；找岀未划去的运价中的最小数值，按此办法进行下去，直至得到一个基本可行解的方法。注：应用 西北角法 和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元素例 外（同时划去一行和一列）。当填上一个数后行、列同时被满足（也就是岀现退化现象）时，也 只任意划去一行（列）。需要填入“ 0”位置不能任意确定，而要根据规则来确定。所谓退化现象是指：当在平衡表中某一处填入一数字后，该数字所在的行和列同时被满足， 即需方的需求得到满足，同时
2、供方的供应数量也已经供完的现象。最小元素法的基本思想是：运价最小的优先调运，即从单位运价中最小的运价开始确定供销 关系，然后次小，一直到给岀初始基本可行解为止。编辑最小元素法的例子第一步：列出运价表和调运物资平衡表。运用表上作业法时，首先要列岀被调运 物资的运价表和供需平衡表 （简称平衡表），如表1， 2所示。强Biftft3n310a2192874105供、xBi鬲供呈（T）Al7Al4g需fid)365620第二步：编制初始调运方案。首先，在运价表中找岀最小的数值（若几个同为最小，则任取其中一个），A2B1最小，数值为1，这表示先将 A2产品供应给 B1是最便宜的，故应给 C21所对应的变
3、量 X21以尽可能大的数值。 显然X21=min4,3=3。在表4中的A2B1处填上“ 3” B1列被满足，已不需要 A1和A3再向它供货， 故运价表2中的第一列数字已不起作用，因此将原运价表1中的第一列划去，并标注（见表3 ）7地产地ftBa3 :|11 -:310*1 敦丄:丄8Ti -L7 :4 :105 z z L * 需A爲b4供呈-Ti47314為63g»S CT）365620然后，在运价表中未划去的元素中找最小运价A2B3 = 2,让A2尽量供应满足 B3的需要，由于A2的4已经供应了 3T给Bi，最多只能供应1T给B3o于是在平衡表的 A2B3格中填上“；相 应地由于
4、A2所生产的 产品已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注。仿照上面的做法，一直做下去，就可以得到表4o此时，在运价表中只有 AiB4对应的运价10没有划掉，而 B4尚有3T需求，为了满足供需平 衡，所以最后在平衡表上对应AiB4处应填入“ 3”这样就得到表5 o衷5需供、昂b4供疑订）A437314639£*（T）365620对于编制初始方案说明以下几点：应用最小元素法编制初始调运方案，这里的最小”系指局部而言，就整体考虑的 运费不见得一定是最小的。可以作为初始方案的调运方案，其填有数字的 方格数应是供应点个数加需求点个数之和再减1，即
5、（m+n-1 ）。第三步：初始方案的检验与调整。西北角法的例子从表1中可知，总的产量 =总的销量，故产销是平衡的。第一步：列出运价表和调运物资平衡表。运用表上作业法时，首先要列岀被调运物资的运价表和供需平衡表（简称平衡表），如表1，2所示。沁Biftft3n3101g2874105需二Bi5s供呈（T）7Al4g需 ft(T)365620第二步：编制初始调运方案。首先在表2的西北角方格（即左上角方格，对应变量Xu），尽可能取最大值：Xn=mi n3,7=3将数值3填入该方格（见表3）。由此可见X21 ,X31必须为0,即第一列其他各方格都不能取非零 值，戈U去第一列。在剩下的方格中，找岀其西北
6、角方格X12，X12=mi n6,7-3=4将4填入它所对应方格，第一行饱和，划去该行。再找西北角方格X22，X22=mi n6-4,4=2将2填入X22所对应方格，于是第二列饱和，划去该列。继续寻找西北方格为X23，X23=mi n5,4-2=2将2填入X23所对应方格，第二行饱和，划去该行。剩下方格的西北角方格为X33 ,Xa3=mi n5-2,9=3将3填入X33所对应方格，第三列饱和，划去该列。最后剩下X34方格，取X34 = 6。需虽供量(T)347224369出S (T)365620这样我们就找到了m + n-1 = 3 + 4-1 = 6 个基变量，它们为：x = 3,Xi2 = 4, X22 = 2,X23 = 2,X33 =3,X34 = 6。显然它们用折线连接后不形成闭回路。这就是西北角法所找初始基可行解，所对应的 目标值为：2X200 + 1 X250 + 3X150 + 1X150 + 3X250 + 3X300 + 4X200 = 4000我们找到的初始基可行解可通过各行方格中数值之和是否等于产量，各列方格中数值之和是否等于销量来简单验证。利用西北角法找初始基可行解简单可行，但也存在问题。例如在表3中可见C35 = 4，单价高于该行其他各方格，最简单想法是单价小的情况下多运些货物，这样总运费会更小些，最小元素法就改进了西北角法的缺点。