信息系統(tǒng)項(xiàng)目管理師計(jì)算題考點(diǎn)：運(yùn)輸問題

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

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

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

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

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

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

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

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

1.閉回路法;

3.位勢(shì)法(對(duì)偶變量法)

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

各方法介紹：

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

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

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

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

算法步驟：

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

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

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

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

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

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

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

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

【例題講解】

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

A.242

B.244

C.289

D.302

【答案】B

【解析】采用伏格爾法。

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

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

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

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

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

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

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

【真題演練】