[科普中國]-最小元素

簡介

最小元素法是找出運(yùn)價(jià)表中最小的元素，在運(yùn)量表內(nèi)對(duì)應(yīng)的格填入允許取得的最大數(shù)，若某行(列)的產(chǎn)量(銷量)已滿足，則把運(yùn)價(jià)表中該運(yùn)價(jià)所在行(列)劃去；找出未劃去的運(yùn)價(jià)中的最小數(shù)值，按此辦法進(jìn)行下去，直至得到一個(gè)基本可行解的方法。1

注：應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元素例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)被滿足（也就是出現(xiàn)退化現(xiàn)象）時(shí)，也只任意劃去一行（列）。需要填入“0”的位置不能任意確定，而要根據(jù)規(guī)則來確定。

所謂退化現(xiàn)象是指：當(dāng)在平衡表中某一處填入一數(shù)字后，該數(shù)字所在的行和列同時(shí)被滿足，即需方的需求得到滿足，同時(shí)供方的供應(yīng)數(shù)量也已經(jīng)供完的現(xiàn)象。

最小元素法的基本思想是：運(yùn)價(jià)最小的優(yōu)先調(diào)運(yùn)，即從單位運(yùn)價(jià)中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，一直到給出初始基本可行解為止。

基本思路運(yùn)輸問題的典型情況是研究單一品種物質(zhì)的運(yùn)輸調(diào)度問題：設(shè)某種物品有m個(gè)產(chǎn)地 ，各產(chǎn)地的產(chǎn)量分別是 ；有n個(gè)銷地，各個(gè)銷地的 銷量分別為 。假定從產(chǎn)地 向銷地 運(yùn)輸單位物品的運(yùn)價(jià)為 ，問怎么調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最?。?/p>

最小元素法是利用表上作業(yè)法解決運(yùn)輸問題的一種啟發(fā)式方法，人們?nèi)菀字庇^想到，為了減少運(yùn)費(fèi)，應(yīng)該優(yōu)先考慮單位運(yùn)價(jià)最小（或運(yùn)距最短）的供銷業(yè)務(wù)才能最大限度的滿足其供銷量，然而在統(tǒng)籌兼顧的情況下，最小元素尋找的初始可行基并不一定是就是最優(yōu)解，需要經(jīng)過解的最優(yōu)性檢驗(yàn)和解的改進(jìn)。

定律定義找出運(yùn)價(jià)表中最小的價(jià)值系數(shù)，即對(duì)所有i和j，找出 ，優(yōu)先考慮單位運(yùn)價(jià)最小的供銷業(yè)務(wù)。

為了保證供應(yīng)的數(shù)量一定出售，銷售的需求量一定能保證供應(yīng)，在運(yùn)輸表內(nèi)對(duì)應(yīng)的格填入允許取得的最大數(shù)，即由 供應(yīng)給的運(yùn)輸量應(yīng)該是

選擇在最大產(chǎn)能和最大銷售量中最小的的物品量。若

則產(chǎn)地的可供物品已用完，劃掉一行表示換掉以后不再考慮這個(gè)產(chǎn)地，且銷地的需求量由

如果

則銷地的需求已全部得到滿足，劃掉一列表示以后不再考慮這個(gè)銷地，且的可供量由減少為

然后，在余下的供、銷地的供銷關(guān)系中，繼續(xù)按上述方法安排調(diào)運(yùn)，直至安排完所有供銷任務(wù)，得到一個(gè)完整的解即一個(gè)完整的調(diào)運(yùn)方案位置。這樣就得到了運(yùn)輸問題的一個(gè)初始基可行解即調(diào)運(yùn)方案。

每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元素例外（同時(shí)劃去一行和一列）。如果填上一個(gè)數(shù)后行、列同時(shí)被滿足，也就是出現(xiàn)退化現(xiàn)象時(shí)，也只任意劃去一行（列）。需要填入“0”的位置不能任意確定，而要根據(jù)規(guī)則來確定。

由于該方法基于有限滿足單位矩陣或運(yùn)距最小的供銷業(yè)務(wù)，故稱為最小元素法。

方法步驟最小元素法的是：運(yùn)價(jià)最小的優(yōu)先調(diào)運(yùn)，即從單位運(yùn)價(jià)中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，一直到給出初始基本可行解為止。

第一步：列出運(yùn)價(jià)表和調(diào)運(yùn)物資平衡表。

運(yùn)用表上作業(yè)法時(shí)，首先要列出被調(diào)運(yùn)物資的運(yùn)價(jià)表和運(yùn)用表上作業(yè)法時(shí)，首先要列出被調(diào)運(yùn)物資的運(yùn)價(jià)表和供需平衡表（簡稱平衡表），如下表所示。

第二步：編制初始調(diào)運(yùn)方案。

首先，在運(yùn)價(jià)表中找出最小的數(shù)值，若出現(xiàn)幾個(gè)同為最小，則任取其中一個(gè)?？梢夾2B1最小，數(shù)值為1，這表示先將A2產(chǎn)品供應(yīng)給B1 是最便宜的，故應(yīng)給C21所對(duì)應(yīng)的變量x21以盡可能大的數(shù)值。顯然x21=min{4,3}=3。在表4中的A2B1處填上“3”。B1列被滿足，已不需要A1和A3再向它供貨，故運(yùn)價(jià)表2中的第一列數(shù)字已不起作用，因此將原運(yùn)價(jià)表1中的第一列劃去，并標(biāo)注①（不標(biāo)注也可以，標(biāo)注可看出是第幾步劃去的）。

表三

|| ||

表四

|| ||

然后，在運(yùn)價(jià)表中未劃去的元素中找最小運(yùn)價(jià)A2B3= 2，讓A2盡量供應(yīng)滿足B3的需要，由于A2的4已經(jīng)供應(yīng)了3T給B1，最多只能供應(yīng)1T給B3。于是在平衡表的A2B3格中填上“1”；相應(yīng)地由于A2所生產(chǎn)的產(chǎn)品已全部供應(yīng)完畢，因此，在運(yùn)價(jià)表中與A2同行的運(yùn)價(jià)也不再起作用，所以也將它們劃去，并標(biāo)注②。

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

此時(shí)，在運(yùn)價(jià)表中只有A1B4對(duì)應(yīng)的運(yùn)價(jià)10沒有劃掉，而B4尚有3T需求，為了滿足供需平衡，所以最后在平衡表上對(duì)應(yīng)A1B4處應(yīng)填入“3”，這樣就得到表5。

表四

|| ||

需要注意的是，作為初始方案的調(diào)運(yùn)方案，其填有數(shù)字的方格數(shù)應(yīng)是供應(yīng)點(diǎn)個(gè)數(shù)加需求點(diǎn)個(gè)數(shù)之和再減1，即（m+n-1），即表上作業(yè)法要尋求的基變量是（m+n-1）個(gè)。當(dāng)遇到退化情形同時(shí)劃掉一行一列的時(shí)候，需要進(jìn)行補(bǔ)0，使基變量保持在（m+n-1）個(gè)，這是能讓初始方案進(jìn)行檢驗(yàn)與調(diào)整的前提。

第三步：初始方案的檢驗(yàn)與調(diào)整。

應(yīng)用最小元素法編制初始調(diào)運(yùn)方案，這里的“最小”系指局部而言，就整體考慮的運(yùn)費(fèi)不見得一定是最小的，有時(shí)按照某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)是，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷點(diǎn)對(duì)，從而使整個(gè)運(yùn)輸費(fèi)用增加。

因此得到了運(yùn)輸問題的初始基可行解之后，即對(duì)應(yīng)這個(gè)解進(jìn)行最優(yōu)性判別，看它是不是最優(yōu)解。改進(jìn)初始基本可行解有兩種最常用的方法：閉回路法和對(duì)偶變量法（位勢法）。2