信息系統(tǒng)項目管理師計算題考點：運輸問題

考點分析：并不?？?，雖然第4版官方教材上介紹的是最小元素法，但考試時，我們都是用伏格爾(Vogel)法進(jìn)行計算，主要也是考察伏格爾法，所以大家需要重點理解下伏格爾法的求解方法，其他的內(nèi)容了解即可。而且這部分內(nèi)容只看文字說明是很難理解的，建議大家看視頻教程講解，然后結(jié)合試題演練加深理解。

運輸問題是一類特殊的線性規(guī)劃問題，將單純型法的思想用到運輸問題的求解里，便得到了運輸問題的表上作業(yè)法。首先確定初始方案，可選用西北角法、最小元素法或伏格爾法;其次進(jìn)行解的最優(yōu)性檢驗，有閉回路法和位勢法兩種基本方法;最后進(jìn)行解的調(diào)整優(yōu)化，直至求得最優(yōu)解。

表上作業(yè)法求解步驟：

一、在已知運輸表的基礎(chǔ)上尋找初始基可行解，通常采用下列3種方法:

1.西北角法(簡便，但求解效率低，現(xiàn)已不常使用);

2.最小元素法(整體效率適中，在某些問題中有著因追求最小運費而使得其他供銷地運費陡然增加的弊端);

3.伏格爾(Vogel)法(效率最高，但求解過程繁瑣，應(yīng)用更加廣泛)。

二、通過計算初始基可行解的檢驗數(shù)來判斷當(dāng)前解的最優(yōu)性。若已為最優(yōu)解，則直接輸出當(dāng)前解;若非最優(yōu)解，則轉(zhuǎn)入下一步。判斷最優(yōu)性的方法主要有2種:

1.閉回路法;

3.位勢法(對偶變量法)

三、最后對當(dāng)前解進(jìn)行調(diào)整，直到達(dá)到最優(yōu)解，調(diào)整時通常采用閉回路法。

各方法介紹：

●西北角法：從單位運價表未被直線覆蓋的西北角位置開始標(biāo)識基變量，依次進(jìn)行，直到找到m+n+1個變量位置。(此方法已不常用，所以大家知道有這么個東西就行了，不需要過多了解)

●最小元素法：從單位運價表未被直線覆蓋的最小運價位置開始標(biāo)識基變量，依次進(jìn)行，直到找到m+n+1個變量位置。(大家可以看下官方教材的講解，不過只看文字內(nèi)容可能還是看不懂，需要大家去看看視頻教程)

●伏格爾(Vogel)法(考試重點)：

沃格爾(Vogel)法又稱差值法，該方法考慮到，最初按某一最小單位運價優(yōu)先安排物品調(diào)運時，在后續(xù)調(diào)運過程中卻可能不得不采用運費很高的其他供銷點，從而使整個運輸費用增加。沃格爾法的基本思想是在運價表中分別計算出各行各列的最小單位運價和次小單位運價之差，并稱這兩個單位運價之差為該銷售地或供應(yīng)地的罰數(shù)，然后按照最小單位運價對罰數(shù)最大處安排運輸。因為若罰數(shù)的值很大，說明不按最小運價組織運輸就會造成很大的運費損失。

算法步驟：

1、首先計算運輸表中每一行和每一列的次小單位運價和最小單位運價之間的差值，分別稱為行罰數(shù)和列罰數(shù)。

2、選取這些罰數(shù)中最大者(若存在最大罰數(shù)相同的情況，則任選其中一個)所在的行或列的最小單位運價所在的格子，在格子中給其分配盡可能大的運量，劃去該行/該列。

3、在尚未劃去的各行或各列中，重復(fù)以上步驟，直到最后一個格子也被分配上運量，得到所求運輸問題的初始基可行解。

●位勢法(對偶變量法)：在得到運輸問題的初始基可行解后，應(yīng)對該解做最優(yōu)性判別。位勢法就是用來判斷解的最優(yōu)性的一種方法，其實質(zhì)是在求解單純形表中非基變量的檢驗數(shù)。該方法適用于產(chǎn)地和銷地較少的運輸問題。

●閉回路法：找到運輸問題的一個初始基可行解之后，判定此解是否是最優(yōu)解的一種方法。在運輸方案表中，任何一個非變量都能和若干個基變量構(gòu)成一個唯一的閉回路。

使用規(guī)則：遇到數(shù)字才能改變方向，但也可以不換;偶數(shù)次轉(zhuǎn)彎格上的運價標(biāo)負(fù)號，奇數(shù)標(biāo)正號。

結(jié)果分析：如果最終檢驗數(shù)均為非正數(shù)，則說明為最優(yōu)解，否則不是。

以下用一個例題為大家進(jìn)行講解，但還是建議大家看視頻教程!

【例題講解】

某公司有東部、中部、西部三個生產(chǎn)基地，生產(chǎn)的產(chǎn)品需要運送帶甲、乙、丙、丁四個市場，從生產(chǎn)基地到各個市場的單位運價及產(chǎn)量和需求量如表所示，完成該運輸任務(wù)所需的最小運費為()。

A.242

B.244

C.289

D.302

【答案】B

【解析】采用伏格爾法。

第一步：計算每行每列的最小元素和次小元素差額

第二步：找到差額最大的行/列的最小運價位置作為基變量，從上表可知，最大的差額為5，也就是乙那一列，乙這一列最小運價位置為5，即西部那一行，所以，我們先考慮西部到乙的情況。

西部的產(chǎn)量為22，乙需求量為14，所以可以滿足其最大需求，也就是最多可以運輸?shù)牧繛?4。運輸完成后，西部還剩余22-14=8，乙已經(jīng)滿足需求量，可以將這一列劃掉。

第三步：跟第一步一樣，重新計算除去已經(jīng)劃掉部分（即乙已經(jīng)滿足，劃掉了）每行每列的最小元素和次小元素差額，然后找到最大差額的行/列的最小運價位置作為基變量，從下表可知，最大的差額為3，也就是丁那一列，丁這一列最小運價位置為6，即西部那一行，所以，我們先考慮西部到丁的情況。

西部的產(chǎn)量已經(jīng)只剩下8，丁需求量為14，所以無法滿足其最大需求，也就是最多可以運輸?shù)牧繛?。運輸完成后，西部還剩余8-8=0，乙需求量還要14-8=6，西部已經(jīng)用完，可以將這一列劃掉。

第四步：這樣一直重復(fù)以上步驟，直到得出完整的運輸方案表，如下：

最后，對比價位表，可以算出：根據(jù)價位表，可以算出：12*4+4*11+8*2+2*9+14*5+8*6=244。所以答案選B。

【真題演練】