1考情分析

管理運(yùn)籌學(xué)這部分的試題主要涉及線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論、排序與統(tǒng)籌、決策分析以及運(yùn)輸問(wèn)題這六大塊。這六大板塊中的重中之重是線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃與圖論。

1.1本章重點(diǎn)

2考點(diǎn)精講

2.1管理運(yùn)籌學(xué)

1．圖論—圖與最小生成樹(shù)

圖由點(diǎn)和邊構(gòu)成的，可以反映一些對(duì)象之間的關(guān)系。圖論中的點(diǎn)通常記為Vi，點(diǎn)之間的連線(xiàn)稱(chēng)之為邊，通常記為Ei。帶箭頭的連線(xiàn)，稱(chēng)之為弧，圖論中的弧記為Ai。

如果“A認(rèn)識(shí)B”，我們用一條連接A、B的箭頭指向B的弧來(lái)表示。

由點(diǎn)和邊構(gòu)成的圖叫無(wú)向圖（簡(jiǎn)稱(chēng)圖），無(wú)向圖記為G=（V，E），其中V是圖G的點(diǎn)的集合，E是圖G的邊的集合。

由點(diǎn)和弧構(gòu)成的圖叫有向圖，有向圖記為D=（V，A），其中V為圖D的點(diǎn)集合，A為圖D的弧的集合。

（1）最小生成樹(shù)問(wèn)題

一個(gè)無(wú)圈的連通圖即為樹(shù)。

最小生成樹(shù)就是在一個(gè)賦權(quán)的連通的無(wú)向圖G中找出一個(gè)生成樹(shù)，并使得這個(gè)生成樹(shù)的所有邊的權(quán)數(shù)之和最小。

求解最小生成樹(shù)的破圈算法如下：

（一）在給定的賦權(quán)的連通圖上任找一個(gè)圈；

（二）在所找的圈中去掉一條權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）；

（三）如果所余下的圖中不含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹(shù)。否則返回步聚（一）。

【例】用破圈法求下圖21-3中的最小生成樹(shù)。

解：（一）去掉圈（V1，V6，V7，V1）中權(quán)值（權(quán)值為10的邊）最大的邊[V1，V6]后，如圖21-3（b）所示：

（二）去掉圈（V5，V4，V3，V5）中權(quán)值為8的邊[V5，V4]后，如圖21-3（c）所示：

（三）同理依次去掉權(quán)值為5，4，4的邊后，最終得到的最小生成樹(shù)如圖21-3（d）所示：

在圖21-3（d）中已找不到任何一個(gè)圈了，可知其即為圖21-3的最小生成樹(shù)，這個(gè)最小生成樹(shù)的所有邊的總權(quán)數(shù)為3+3+3+1+2+7=19。

2．動(dòng)態(tài)規(guī)劃

（1）多階段決策過(guò)程最優(yōu)化問(wèn)題

動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。這種方法把困難的多階段決策問(wèn)題變換成一系列互相聯(lián)系較容易的單階段問(wèn)題，解決了這一系列較容易的單階段問(wèn)題，也就解決了這個(gè)困難的多階段決策問(wèn)題。用動(dòng)態(tài)規(guī)劃可以解決管理中的最短路問(wèn)題、資源分配等問(wèn)題。

【例】如下圖21-4所示，給定一個(gè)運(yùn)輸網(wǎng)絡(luò)，兩點(diǎn)之間連線(xiàn)的數(shù)字表示兩點(diǎn)間的距離，試求一條從A到E的運(yùn)輸線(xiàn)路，使總距離為最短。

?

解：本題可考慮分階段來(lái)求解。從而首先定義：

第一階段：以A點(diǎn)為起始點(diǎn)，而以距離A點(diǎn)正好一個(gè)弧遠(yuǎn)的點(diǎn)（B1，B2，B3，B4）為終點(diǎn)；

第二階段：以（B1，B2，B3，B4）為始點(diǎn)，以與A點(diǎn)距離兩個(gè)弧遠(yuǎn)的點(diǎn)（C1，C2，C3）為終點(diǎn)；

第三階段：以（C1，C2，C3）為始點(diǎn)，以與A點(diǎn)距離三個(gè)弧遠(yuǎn)的點(diǎn)（D1，D2）為終點(diǎn)；

第四階段：以（D1，D2）為始點(diǎn)，以與距離A點(diǎn)四個(gè)弧遠(yuǎn)的點(diǎn)（E）為終點(diǎn)。

顯然這是一個(gè)四階段決策過(guò)程的最優(yōu)化問(wèn)題，用動(dòng)態(tài)規(guī)劃來(lái)解這個(gè)問(wèn)題。即要把這個(gè)四階段的決策問(wèn)題轉(zhuǎn)化為一系列較容易解決的單階段決策的問(wèn)題。

求解時(shí)我們從最后一個(gè)階段（第四階段）開(kāi)始，從終點(diǎn)（E）向始點(diǎn)（A）方向逐階段逆推，找出各點(diǎn)到終點(diǎn)的最短距離，并把每個(gè)點(diǎn)到終點(diǎn)的最短距離標(biāo)注在該點(diǎn)上。最后，當(dāng)逆推到始點(diǎn)時(shí)，也即找到了從始點(diǎn)到終點(diǎn)的全過(guò)程最短距離。

求解過(guò)程如下：

從而可知從A到E的最短距離為14。路徑是A-B4-C3-D1-E。

3．線(xiàn)性規(guī)劃

線(xiàn)性規(guī)劃是研究在有限的資源條件下，如何有效地使用這些資源達(dá)到預(yù)定目標(biāo)的數(shù)學(xué)方法。用數(shù)學(xué)的語(yǔ)言來(lái)說(shuō)，也就是在一組約束條件下尋找目標(biāo)函數(shù)的極值問(wèn)題。

求極大值（或極小值）的模型表達(dá)如下：

在上述條件下，求解 ，使?jié)M足下列表達(dá)式的z取極大值（或極小值）：

（1）圖解法

解線(xiàn)性規(guī)劃問(wèn)題的方法有很多，最常用的有圖解法和單純形法。圖解法簡(jiǎn)單直觀，有助于了解線(xiàn)性規(guī)劃問(wèn)題求解的基本原理，下面，通過(guò)一個(gè)例子來(lái)說(shuō)明圖解法的應(yīng)用。

【例】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原料的消耗，如表21-3所示。

表21-3產(chǎn)品及原料表

該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)該如何安排計(jì)劃使該工廠獲利最多？

【解】該問(wèn)題可用以下數(shù)學(xué)模型來(lái)描述，設(shè)

分別表示在計(jì)劃期內(nèi)產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量，因?yàn)樵O(shè)備的有效臺(tái)時(shí)是8，這是一個(gè)限制產(chǎn)量的條件，所以在確定產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量時(shí)，要考慮不超過(guò)設(shè)備的有效臺(tái)時(shí)數(shù)，即可用不等式表示為

?

同理，因原料A、B的限量，可以得到以下不等式

?

該工廠的目標(biāo)是在不超過(guò)所有資源限制的條件下，如何確定產(chǎn)量

，以得到最大的利潤(rùn)。若用z表示利潤(rùn)，這時(shí)

。綜上所述，該計(jì)劃問(wèn)題可用數(shù)學(xué)模型表示為：

目標(biāo)函數(shù)：

?

滿(mǎn)足約束條件：

?

在以

為坐標(biāo)軸的直角坐標(biāo)系中，非負(fù)條件

是指第一象限。上述每個(gè)約束條件都代表一個(gè)半平面。例如，約束條件

?代表以直線(xiàn)

為邊界的左下方的半平面。若同時(shí)滿(mǎn)足

，

，

和

的約束條件的點(diǎn)，必然落在由這三個(gè)半平面相交組成的區(qū)域內(nèi)，如圖5-2中的陰影部分所示。陰影區(qū)域中的每一個(gè)點(diǎn)（包括邊界點(diǎn)）都是這個(gè)線(xiàn)性規(guī)劃問(wèn)題的解（稱(chēng)可行解），因而此區(qū)域是本題的線(xiàn)性規(guī)劃問(wèn)題的解的集合，稱(chēng)它為可行域。

圖5-2圖解法

再分析目標(biāo)函數(shù)

，在坐標(biāo)平面上，它可表示以z為參數(shù)，-2/3為斜率的一組平行線(xiàn)：

?

位于同一直線(xiàn)上的點(diǎn)，具有相同的目標(biāo)函數(shù)值，因此稱(chēng)它為等值線(xiàn)。當(dāng)z值由小變大時(shí)，直線(xiàn)沿其法線(xiàn)方向向右上方移動(dòng)。當(dāng)移動(dòng)到

點(diǎn)時(shí)，使z值在可行域邊界上實(shí)現(xiàn)最大化，這就得到了本題的最優(yōu)解

，

點(diǎn)的坐標(biāo)為（4，2）。經(jīng)過(guò)計(jì)算，可以得出z=14。

這說(shuō)明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)4件產(chǎn)品Ⅰ，2件產(chǎn)品Ⅱ，可得最大利潤(rùn)為14元。

3章節(jié)問(wèn)答

1．我上大學(xué)時(shí)沒(méi)有學(xué)過(guò)管理運(yùn)籌學(xué)相關(guān)知識(shí)，這方面零基礎(chǔ)，如何去學(xué)習(xí)，才能達(dá)到考試合格標(biāo)準(zhǔn)？

答：

（1）學(xué)習(xí)時(shí)間較少的考生朋友可以詳讀本章相關(guān)內(nèi)容即可；

（2）學(xué)習(xí)時(shí)間較充裕的考生朋友可以去各大書(shū)店或在線(xiàn)購(gòu)買(mǎi)《管理運(yùn)籌學(xué)》相關(guān)教材，并學(xué)習(xí)相關(guān)內(nèi)容。

2．對(duì)于產(chǎn)銷(xiāo)不平衡的管理運(yùn)籌學(xué)問(wèn)題如何來(lái)求解？

答：對(duì)于產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題，我們可以先化為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，然后再求解。

例：某公司從兩個(gè)產(chǎn)地A1，A2將物品運(yùn)往三個(gè)銷(xiāo)地B1，B2，B3，各產(chǎn)地產(chǎn)量和各銷(xiāo)地銷(xiāo)量以及各產(chǎn)地運(yùn)往各銷(xiāo)地的每件物品的運(yùn)輸表如下表所示：

應(yīng)如何組織運(yùn)輸，使得總運(yùn)輸費(fèi)用最少？

從表格中的數(shù)據(jù)可知，總產(chǎn)量是600件，而總銷(xiāo)量是500件，這是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題，為此我們可建立一個(gè)假想的銷(xiāo)地B4，B4是產(chǎn)地A1，A2的各自的倉(cāng)庫(kù)，B4的銷(xiāo)量為100件。因?yàn)锳1把物品放在自己的倉(cāng)庫(kù)，A2把物品放在自己的倉(cāng)庫(kù)都不需要運(yùn)費(fèi)。從而令C14=0，C24=0，從而得到如下表所示的產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表，這樣我們就把產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題轉(zhuǎn)化成了產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。

然后采用最小元素法來(lái)求解，得到本題的最優(yōu)解：

X11=50；X12=150；X13=0；X14=100；X21=100；X22=0；X23=200；X24=0；

總運(yùn)輸費(fèi)用最小為2500元。