1 圖論應(yīng)用

①最小生成樹

• 連接所有頂點(diǎn)；
• 無(wú)環(huán)路；
• 權(quán)值之和最小。

②最短路徑

• 起點(diǎn)；
• 終點(diǎn)；
• 只要有1條通路就可以了
• 權(quán)值之和最小。

③網(wǎng)路與最大流量

• 起點(diǎn)；
• 終點(diǎn)；
• 多條路徑合并。

1.1 最小生成樹

例題：
某小區(qū)有七棟樓房①~⑦(見(jiàn)下圖),各樓房之間可修燃?xì)夤艿缆肪€的長(zhǎng)度（單位:百米)已標(biāo)記在連線旁。為修建連通各個(gè)樓房的燃?xì)夤艿?#xff0c;該小區(qū)內(nèi)部煤氣管道的總長(zhǎng)度至少為多少百米?

分析

• 克魯斯卡爾算法：最短邊
  

• 普利姆算法：最近頂點(diǎn)
  

• 故煤氣管道的總長(zhǎng)度至少為：2+3+3+4+5+6=23百米

注意：最小生成樹可以有多種，但是最小權(quán)值只有一個(gè)。

1.2 最短路徑

例題：
有一批貨物要從城市s發(fā)送到城市t，線條上的數(shù)字代表通過(guò)這條路的費(fèi)用(單位為萬(wàn)元)。那么，運(yùn)送這批貨物，至少需要花費(fèi)多少萬(wàn)元?

分析

最短路徑：S->2->3->5->6->t，需要花費(fèi)21+20+20+8+12=81萬(wàn)元

1.3 網(wǎng)絡(luò)與最大流量

例題
下圖標(biāo)出了某地區(qū)的運(yùn)輸網(wǎng)，各節(jié)點(diǎn)之間的運(yùn)輸能力如下表所示。那么，從節(jié)點(diǎn)①到節(jié)點(diǎn)⑥的最大運(yùn)輸能力(流量)可以達(dá)到多少萬(wàn)噸/小時(shí)?

分析

1. 多段流量分析時(shí)，流量由瓶頸決定；
2. 以抽取的方式分析剩余流量；

• 先根據(jù)表在圖中標(biāo)上數(shù)據(jù)：
  
• 步驟1：（1）最大流量路徑：1->3->5->6，最大運(yùn)輸能力10
• 步驟2：抽取對(duì)應(yīng)路徑
• 重復(fù)步驟1、步驟2，直到?jīng)]有路徑為止。
• （2）1->2->5->6，最大運(yùn)輸能力6
• （3）1->4->6，最大運(yùn)輸能力5
• （4）1->4->2->5->6或1->4->3->5->6，最大運(yùn)輸能力1，1
• 故從節(jié)點(diǎn)①到節(jié)點(diǎn)⑥的最大運(yùn)輸能力(流量)可以達(dá)到10+6+5+1+1=23萬(wàn)噸/小時(shí)

例2
在軍事演習(xí)中，張司令希望將部隊(duì)盡快從A地通過(guò)公路網(wǎng)(見(jiàn)下圖)運(yùn)送到F地:

圖中標(biāo)出了各路段上的最大運(yùn)量（單位:千人/小時(shí))。根據(jù)該圖可以算出，從A地到F地的最大運(yùn)量是（）千人/小時(shí)。
A 20
B 21
C 22
D 23

分析
（1）A->B->F，最大運(yùn)輸能力8；
（2）A->B->E->F或A->D->E->F，最大運(yùn)輸能力4，4；
（3）A->D->C->E->F，最大運(yùn)輸能力3；
（4）A->C->E->F，最大運(yùn)輸能力2；
（5）A->B->C->E->F，最大運(yùn)輸能力1；
故最大運(yùn)量是8+4+4+3+2+1=22千人/小時(shí)

2 運(yùn)籌方法

2.1 線性規(guī)劃

線性規(guī)劃的一些特點(diǎn):

• 線性規(guī)劃的可行解域是由一組線性約束條件形成的，從幾何意義來(lái)說(shuō)，就是由一些線性解面圍割形成的區(qū)域，不一定是封閉的多邊形或多面體。
• 如果存在兩個(gè)最優(yōu)解，則連接這兩點(diǎn)的線段內(nèi)所有的點(diǎn)都是最優(yōu)解，而線段兩端延長(zhǎng)線上可能會(huì)超出可行解區(qū)。
• 增加一個(gè)約束條件時(shí)，要么縮小可行解域(新的約束條件分割了原來(lái)的可行解域)，要么可行解域不變(新的約束條件與原來(lái)的可行解域不相交)
• 如果最優(yōu)解在可行解域邊界某個(gè)非頂點(diǎn)處達(dá)到，則隨著等值域向某個(gè)方向移動(dòng)，目標(biāo)函數(shù)的值會(huì)增加或減少(與最優(yōu)解矛盾)或沒(méi)有變化(在此段邊界上都達(dá)到最優(yōu)解)，從而仍會(huì)在可行解域的某個(gè)頂點(diǎn)處達(dá)到最優(yōu)解。若最優(yōu)解存在且唯一，則可以從可行解區(qū)頂點(diǎn)處比較目標(biāo)函數(shù)值來(lái)求解。

線性規(guī)劃的標(biāo)準(zhǔn)型(standard form of linear programrmng)是線性規(guī)劃模型的標(biāo)準(zhǔn)形式。其主要特征為:
(1）目標(biāo)函數(shù)為極大化類型;
(2）所有的約束條件都是等式;
(3）所有約束方程右端的常數(shù)都是非負(fù)的;
(4）所有決策變量都是非負(fù)的。

例題
線性規(guī)劃問(wèn)題由線性的目標(biāo)函數(shù)和線性的約束條件（包括變量非負(fù)條件)組成。滿足約束條件的所有解的集合稱為可行解區(qū)。既滿足約束條件，又使目標(biāo)函數(shù)達(dá)到極值的解稱為最優(yōu)解。以下關(guān)于可行解區(qū)和最優(yōu)解的敘述中，正確的是（ )。
A 可行解區(qū)一定是封閉的多邊形或多面體
B 若增加一個(gè)線性約束條件，則可行解區(qū)可能會(huì)擴(kuò)大
C 若存在兩個(gè)最優(yōu)解，則它們的所有線性組合都是最優(yōu)解
D 若最優(yōu)解存在且唯一，則可以從可行解區(qū)頂點(diǎn)處比較目標(biāo)函數(shù)值來(lái)求解

分析

• 由一些線性解面圍割形成的區(qū)域，不一定是封閉的多邊形或多面體
• 增加一個(gè)約束條件時(shí)，要么縮小可行解域，要么可行解域不變
• 如果存在兩個(gè)最優(yōu)解，則連接這兩點(diǎn)的線段內(nèi)所有的點(diǎn)都是最優(yōu)解，而線段兩端延長(zhǎng)線上可能會(huì)超出可行解區(qū)
• 若最優(yōu)解存在且唯一，則可以從可行解區(qū)頂點(diǎn)處比較目標(biāo)函數(shù)值來(lái)求解
• 故答案D

例2
某企業(yè)需要采用甲、乙、丙三種原材料生產(chǎn)l、I兩種產(chǎn)品。生產(chǎn)兩種產(chǎn)品所需原材料數(shù)量、單位產(chǎn)品可獲得利潤(rùn)以及企業(yè)現(xiàn)有原材料數(shù)如下表所示，則公司可以獲得的最大利潤(rùn)是(1）萬(wàn)元。取得最大利潤(rùn)時(shí)，原材料（2）尚有剩余。

(1)
A.21
B.34
C.39
D.48

(2)
A.甲
B.乙
C.丙
D.乙和丙

分析
設(shè)生產(chǎn)Ⅰ與Ⅱ產(chǎn)品的數(shù)量分別為︰X和Y。
則有:
(1)X+Y<= 4
(2)4X+3Y<=12
(3) X+3Y<=6
(4)X>= 0，Y>=0
目標(biāo)函數(shù)：
9X+12Y

圖解法：
找頂點(diǎn)，代入
聯(lián)立方程求解：

例2
某公司現(xiàn)有400萬(wàn)元用于投資甲、乙、丙三個(gè)項(xiàng)目，投資額以百萬(wàn)元為單位，已知甲、乙、丙三項(xiàng)投資的可能方案及相應(yīng)獲得的收益如下表所示，則該公司能夠獲得的最大收益值是（)百萬(wàn)元。
A 17
B 18
C 20
D 21

分析
窮舉法：

• 甲：1，乙：2，丙：1，收益值18
• 故答案：B。

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

2.2.1 供需平衡問(wèn)題

例題
設(shè)三個(gè)煤場(chǎng)A、B、C分別能供應(yīng)煤12、14、10萬(wàn)噸，三個(gè)工廠x、Y、Z分別需要煤11、12、13萬(wàn)噸，從各煤場(chǎng)到各工廠運(yùn)煤的單價(jià)（百元/噸)見(jiàn)下表方框內(nèi)的數(shù)字。只要選擇最優(yōu)的運(yùn)輸方案，總的運(yùn)輸成本就能降到（）百萬(wàn)元。

A 83
B 91
C113
D 153

貪心策略分析

1. 找單價(jià)最低的：
   煤場(chǎng)A到工廠Y的單價(jià)最低；
   煤場(chǎng)B到工廠X的單價(jià)最多；
   煤場(chǎng)C到工廠X的單價(jià)最低。
   由于工廠Z沒(méi)有單價(jià)最低的，就需要考慮分配一些產(chǎn)量給工廠C；
   

2. 分配一些產(chǎn)量給工廠C：
   對(duì)于煤場(chǎng)A：工廠Y分配產(chǎn)量給工廠X，單價(jià)成本增加4，分配產(chǎn)量給工廠Z，單價(jià)成本增加5；
   對(duì)于煤場(chǎng)B：工廠X分配產(chǎn)量給工廠Y，單價(jià)成本增加2，分配產(chǎn)量給工廠Z，單價(jià)成本增加1；
   對(duì)于煤場(chǎng)C：工廠X分配產(chǎn)量給工廠Y，單價(jià)成本增加3，分配產(chǎn)量給工廠Z，單價(jià)成本增加4；
   

現(xiàn)在想要成本越少越好，所以成本增長(zhǎng)越少越好，所以把煤場(chǎng)B的產(chǎn)量分配給工廠Z，又工廠Z的需求量為13，煤場(chǎng)B最大供煤量14，所以工廠X分配產(chǎn)量為1，工廠Z分配產(chǎn)量為13。煤場(chǎng)C的最大供煤量10全部都分配給工廠X。煤場(chǎng)A的最大供煤量12全部都分配給工廠Y。最終得到最優(yōu)方案。

3. 運(yùn)輸成本最低為：21+310+112+313=83百萬(wàn)元
4. 答案：A

伏格爾法求解供需平衡問(wèn)題
伏格爾法的步驟是:
1、算出各行各列中最小元素和次小元素的差額,并標(biāo)出差額最大的(若幾個(gè)差額同為最大，則可任取其一)。
2、在差額最大的行或列中的最小元素處填上盡可能大的數(shù)。
3、對(duì)未劃去的行列重復(fù)以上步驟,直到得到一個(gè)初始解。

2.2.2 任務(wù)指派問(wèn)題

例題
某企業(yè)準(zhǔn)備將四個(gè)工人甲、乙、丙、丁分配在A、B、C、D四個(gè)崗位。每個(gè)工人由于技術(shù)水平不同，在不同崗位上每天完成任務(wù)所需的工時(shí)見(jiàn)下表。適當(dāng)安排崗位，可使四個(gè)工人以最短的總工時(shí)( ）全部完成每天的任務(wù)。

A 13
B 14
C 15
D 16

貪心策略分析

匈牙利算法分析

例2
某工廠分配四個(gè)工人甲、乙、丙、丁同時(shí)去操作四臺(tái)機(jī)床A、B、C、D,每人分配其中的一臺(tái)。已知每個(gè)工人操作每臺(tái)機(jī)床每小時(shí)的效益值如下表所示，則總效益最高的最優(yōu)分配方案共有（）個(gè)。
A 1
B 2
C 3
D 4

匈牙利算法分析
按行減：
按列減：

故正確答案C

3 預(yù)測(cè)與決策

3.1 不確定型決策分析

例題

分析
樂(lè)觀主義者：（500，300，300）=>積極型
悲觀主義者：（50，100，200）=>保守型
平均值決策法：（700/3，600/3，750/3）=>保守型
后悔值：（250，200，300）=>穩(wěn)健型

例2
某公司為經(jīng)營(yíng)業(yè)務(wù)的需要，決定要在現(xiàn)有生產(chǎn)條件歹變的情況下，生產(chǎn)一種新產(chǎn)品，現(xiàn)可供生產(chǎn)的產(chǎn)品有甲、乙、丙、丁四種類型。由于缺少相關(guān)資料背景，對(duì)新產(chǎn)品的市場(chǎng)需求只能估計(jì)為大、中、小三種狀態(tài)，在不同的市場(chǎng)需求條件下，新產(chǎn)品的收益值如表所示。如果決策者采用后悔值方法進(jìn)行決策，該公司應(yīng)生產(chǎn)（ ) 。

A 甲
B 乙
C 丙
D 丁

分析

答案：B

3.2 風(fēng)險(xiǎn)型決策

3.2.1 決策樹

例1
某電子商務(wù)公司要從A地向B地的用戶發(fā)送一批價(jià)值為90000元的貨物。從A地到B地有水、陸兩條路線。走陸路時(shí)比較安全，其運(yùn)輸成本為10000元;走水路時(shí)一般情況下的運(yùn)輸成本只要7000元，不過(guò)一旦遇到暴風(fēng)雨天氣，則會(huì)造成相當(dāng)于這批貨物總價(jià)值的10%的損失。根據(jù)歷年情況，這期間出現(xiàn)暴風(fēng)雨天氣的概率為1/4，那么該電子商務(wù)公司該如何選擇呢?

分析
水路：
好天氣：70000.75=5250
壞天氣：（7000+9000010%）0.25=4000
總計(jì)：70000.75+（7000+90000*10%）*0.25=9250

陸路：10000

水路的成本低些，故選擇水路

例2
某企業(yè)擬進(jìn)行電子商務(wù)系統(tǒng)的建設(shè)，有四種方式可以選擇:①企業(yè)自行從頭開發(fā);②復(fù)用已有的構(gòu)件來(lái)構(gòu)造;③購(gòu)買現(xiàn)成的軟件產(chǎn)品;④承包給專業(yè)公司開發(fā)。針對(duì)這幾種方式，項(xiàng)目經(jīng)理提供了如圖所示的決策樹，根據(jù)此圖，管理者選擇建設(shè)方式的最佳決策是（ ） 。
A．企業(yè)自行從頭開發(fā)
B．復(fù)用已有的構(gòu)件來(lái)構(gòu)造
C．購(gòu)買現(xiàn)成的軟件產(chǎn)品
D．承包給專業(yè)公司開發(fā)

分析
自行從頭開發(fā)：0.338+0.745=42.9
復(fù)用：0.427.5+0.60.231+0.60.849=38.24
購(gòu)買：0.721+0.330=23.7
承包：0.635+0.4*50=41
故最佳決策為購(gòu)買現(xiàn)成的軟件產(chǎn)品
答案C。

例3
生產(chǎn)某種產(chǎn)品有兩個(gè)建廠方案:(1)建大廠，需要初期投資500萬(wàn)元。如果產(chǎn)品銷路好，每年可以獲利200萬(wàn)元;如果銷路不好，每年會(huì)虧損20萬(wàn)元。(2)建小廠，需要初期投資200萬(wàn)元。如果產(chǎn)品銷路好，每年可以獲利100萬(wàn)元;如果銷路不好，每年只能獲利20萬(wàn)元。
市場(chǎng)調(diào)研表明，未來(lái)2年這種產(chǎn)品銷路好的概率為70%。如果這2年銷路好，則后續(xù)5年銷路好的概率上升為80%;如果這2年銷路不好，則后續(xù)5年銷路好的概率僅為10%.為取得7年最大總收益，決策者應(yīng)（) 。

A 建大廠，總收益超500萬(wàn)元
B 建大廠，總收益略多于300萬(wàn)元
C 建小廠，總收益超500萬(wàn)元
D 建小廠，總收益略多于300萬(wàn)元

分析
首先畫決策樹：
求平均收益值：
建大廠的平均收益高，總收益略高于300萬(wàn)。
故答案選A。

3.2.2 決策表

案例
評(píng)估和選擇最佳系統(tǒng)設(shè)計(jì)方案時(shí)，甲認(rèn)為可以采用點(diǎn)值評(píng)估方法，即根據(jù)每一個(gè)價(jià)值因素的重要性，綜合打分來(lái)選擇最佳的方案。乙根據(jù)甲的提議，對(duì)如表所示的系統(tǒng)A和B進(jìn)行評(píng)估，那么乙認(rèn)為( ) 。

A．最佳方案是A
B．最佳方案是B
c．條件不足，不能得出結(jié)論
D．只能用成本/效益分析方法做出判斷

分析
系統(tǒng)A：9535%+7040%+8525%=82.5
系統(tǒng)B：7535%+9540%+9025%=86.75
故最佳方案是B
答案：B

4 隨機(jī)函數(shù)

例1
根據(jù)歷史數(shù)據(jù)和理論推導(dǎo)可知，某應(yīng)用中，隨機(jī)變量s的分布密度函數(shù)為f (x)=2x，(0<x<1)。這意味著，當(dāng)Δx充分小時(shí)，隨機(jī)變量s落在區(qū)間（x，x+Δx）內(nèi)的概率約等于f (x) Δx。為此，開發(fā)該應(yīng)用的仿真系統(tǒng)時(shí)，可用（）來(lái)模擬該隨機(jī)變量，其中，r1和r2為計(jì)算機(jī)逐個(gè)產(chǎn)生的、均勻分布在(0，1)區(qū)間內(nèi)的互相獨(dú)立的偽隨機(jī)數(shù)。

A max (r1，r2)
B min (r1，r2)
C r1*r2
D (r1+r2)/2

分析
假設(shè)隨機(jī)變量s的分布密度函數(shù)為f (x)=2x
這意味著，當(dāng)△x充分小時(shí)，隨機(jī)變量s落在區(qū)間(x，x+Ax)內(nèi)的概率約等于f (x)Ax。r1和r2為計(jì)算機(jī)逐個(gè)產(chǎn)生的、均勻分布在(0，1）區(qū)間內(nèi)的互相獨(dú)立的偽隨機(jī)數(shù)。

–隨機(jī)數(shù)即約等于密度函數(shù)的結(jié)果
密度函數(shù)為上升趨勢(shì)，則隨機(jī)數(shù)應(yīng)該滿足上升趨勢(shì)。此處采用模擬函數(shù)max (r1, r2)隨機(jī)產(chǎn)生隨機(jī)數(shù)r1和r2。

法二：
f(x)近似等于命中率，則：
假設(shè)r1 = 0.1，r2= 0.2，
A：max(r1，r2）=0.2，f(x)=0.4；
B：min(r1，r2）=0.1，f(x)=0.2；
C：r1*r2=0.02，f(x)=0.04；
D：(r1+r2)/2=0.15，f(x)=0.3
f(x)越大，命中率越高，故max(r1,r2)命中率最高

答案：A

例2
根據(jù)歷史數(shù)據(jù)和理論推導(dǎo)可知，某應(yīng)用中，隨機(jī)變量s的分布密度函數(shù)為f (x)=3x^2，(0<x<1)。這意味著，當(dāng)Ax充分小時(shí)，隨機(jī)變量s落在區(qū)間(x，x+△x)內(nèi)的概率約等于f (x)Ax。為此，開發(fā)該應(yīng)用的仿真系統(tǒng)時(shí)，可用（）來(lái)模擬該隨機(jī)變量，其中，r1、r2、r3…為計(jì)算機(jī)逐個(gè)產(chǎn)生的、均勻分布在(0，1）區(qū)間內(nèi)的互相獨(dú)立的偽隨機(jī)數(shù)。

A max (r1，r2，r3)
B min (r1，r2，r3)
C r1r2r3
D (r1+r2+r3)/3

分析
假設(shè)r1=0.1，r2=0.2，r3=0.3
A：max(r1，r2，r3）=0.3，f(x)=0.18；
B：min(r1，r2，r3）=0.1，f(x)=0.02；
C：r1r2r3=0.006，f(x)=0.000072；
D：(r1+r2+r3)/3=0.2，f(x)=0.08
f(x)越大，命中率越高，故max(r1,r2,r3)命中率最高
答案：A。

5 數(shù)學(xué)建模

數(shù)學(xué)建模是一種數(shù)學(xué)的思考方法，是運(yùn)用數(shù)學(xué)的語(yǔ)言和方法，通過(guò)抽象和簡(jiǎn)化，建立能近似刻畫并解決實(shí)際問(wèn)題的模型的一種強(qiáng)有力的數(shù)學(xué)手段。

數(shù)學(xué)建模過(guò)程

• 模型準(zhǔn)備：了解問(wèn)題的實(shí)際背景,用數(shù)學(xué)語(yǔ)言來(lái)描述問(wèn)題。
• 模型假設(shè)：根據(jù)實(shí)際對(duì)象的特征和建模的目的，對(duì)問(wèn)題進(jìn)行必要的簡(jiǎn)化，并用精確的語(yǔ)言提出一些恰當(dāng)?shù)募僭O(shè)。
• 模型建立：在假設(shè)的基礎(chǔ)上，建立相應(yīng)的數(shù)學(xué)結(jié)構(gòu)。
• 模型求解：利用獲取的數(shù)據(jù)資料，對(duì)模型的所有參數(shù)做出計(jì)算(估計(jì))。模型分析:對(duì)所得的結(jié)果進(jìn)行數(shù)學(xué)上的分析。
• 模型檢驗(yàn)：將模型分析結(jié)果與實(shí)際情形進(jìn)行比較，以此來(lái)驗(yàn)證模型的準(zhǔn)
  確性、合理性和適用性。
• 模型應(yīng)用：應(yīng)用方式因問(wèn)題的性質(zhì)和建模的目的而異。

模型分析

• 模型的合理性分析:最佳、適中、滿意等。
  • 利用實(shí)際案例數(shù)據(jù)對(duì)模型進(jìn)行檢驗(yàn)
  • 可以請(qǐng)專家來(lái)分析模型是否合理
  • 利用計(jì)算機(jī)來(lái)模擬實(shí)際問(wèn)題，再在計(jì)算機(jī)上檢驗(yàn)該數(shù)學(xué)模型。
• 模型的誤差分析:模型誤差、觀測(cè)誤差、截?cái)嗾`差、舍入誤差、過(guò)失誤差、絕對(duì)誤差、相對(duì)誤差等。
• 參數(shù)的靈敏性分析∶變量數(shù)據(jù)是否敏感，在最優(yōu)方案不變的條件下這些變量允許變化的范圍。

例1
面對(duì)復(fù)雜的實(shí)際問(wèn)題，常需要建立數(shù)學(xué)模型來(lái)求解，但根據(jù)數(shù)學(xué)模型求出的解答可能不符合實(shí)際情況，故還需分析模型參數(shù)和輸入數(shù)據(jù)的微小變化是否會(huì)引起輸出結(jié)果的很大變化。這種分析常稱為（ ) 。

A 準(zhǔn)確度分析
B 敏感度分析
C 可靠性分析
D 風(fēng)險(xiǎn)分析

分析
答案：敏感度分析