本章開始講一些計算題了，主要是刷題，每年都會考，原來是在這裡啊，之前考高項的時候也有類似的題型，我還好奇這些題出自哪裡，原來是系分的這個章節，其實也都是一些算法題，開發出身的應該是似曾相識，估計刷力扣的時候應該會遇到過！其實就是用數學去解決現實中遇到的實際問題了，把實際問題抽象成數學模型，對應現在很火的算法，當然咱們系分要比這個簡單，隻要掌握解題思路就可以，畢竟上午時間很充足。

1.開發商需要在某小區9棟樓房之間敷設自來水管道，使各樓都能連通，又能使總成本最低。經勘察，各樓房之間敷設管道的路徑和成本（單位：千元）如下圖所示：

A.13 B.14 C.15 D.16

解析：一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。 [1] 最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普裡姆）算法求出。

舉例：我們要在n個城市中建立一個通信網絡，則連通這n個城市需要布置n-1一條通信線路，這個時候我們需要考慮如何在成本最低的情況下建立這個通信網。

上邊是百度搜的，最小生成樹概念。

思路：n個節點聯通，最少需要n-1個邊即可，不能産生環路。

看靈魂畫師，一步步畫，從成本最低的1開始畫，直到沒有環路為止

答案選A

2.己知八口海上油井（編号從1#到8#)相互之間的距離（單位：海裡）如下表所示，其中1#油井離海岸最近為5海裡。現從海岸開始鋪設輸油管道，經1#油井将這些油井都連接起來，管道的總長度至少為（）海裡（為便于計量和維修，管道隻能在油井處分叉）

A.5 B.9 C.10 D.11

解析：8個油井7條邊，給表格不給圖

最小生成樹，兩種類型的考法，1.給圖，2.不給圖，給表格

答案C，注意離海岸還有5公裡要加上！

1.下表記錄了六個結點A、B、C、D、E、F之間的路徑方向和距離。從A到F的最短距離是（）。

A、38 B、40 C、44 D、46

解析：最短路徑應該也會出圖形，不單單上邊的表格，就是窮舉了，最簡單的方式，沒那麼多複雜，就是計算比較多！

A-F最短路徑，依次求A-F最短路徑

A-B：11

A-C：分兩個路徑1.A-B-C=11 13=26，2.A-C=16

A-D：分A-B-C-D，A-B-D，A-C-D，A-D四個路徑，

A-B-C-D=11 13 14=38，A-B-D=11 16=27，A-C-D=16 14=30，A-D=24

A-E：分A-B-C-D-E，A-B-E，A-B-C-E，A-C-D-E，A-C-E，A-D-E，A-E七種路徑，

A-B-C-D-E=38 14=52，A-B-E=11 21=32，A-B-C-E=11 13 17=41，A-C-D-E=30 14=44，A-C-E=16 17=33，A-D-E=24 14=38，A-E=36。

A-F：分A-F，

A-B-F，A-B-C-F，A-B-D-F，A-B-E-F，

A-B-C-D-F，A-B-C-E-F，A-B-C-D-E-F，

A-C-F，A-C-D-F，A-C-E-F，

A-C-D-F，A-C-D-E-F，

A-D-F，A-D-E-F，

A-E-F，16中情況：

A-F=54，A-B-F=11 29=40，A-B-C-F=26 22=48，A-B-D-F=27 17=44，A-B-E-F=32 15=47，

A-B-C-D-F=38 17=55，A-B-C-E-F=41 15=56，A-B-C-D-E-F=52 15=67，

A-C-F=16 22=38，A-C-D-F=30 17=47，.............算到這裡可以不用算了，答案最低就是38了，選A

思路很清晰，簡單有效，就是有點耗時。

1.下圖标出了某地區的運輸網，各節點之間的運輸能力如下表所示。那麼，從節點①到節點⑥的最大運輸能力（流量）可以達到多少萬噸／小時？

解析：短闆優先（比如上圖1-2-5-6這個路徑為例，最大的運輸量取決于最短闆1-2的運輸量6萬噸，多了也運不過去了），實時更新（還是以1-2-5-6路徑舉例，1-2的6萬噸運過去之後，2-5運力7-6=1，隻剩下1萬噸了，1-2路徑就變成0了，理解理解每小時最多的流量），每一次運輸的過程都要加起來！

思路就三點：1.短闆優先，2.實時更新，3.每次運輸都相加，最終得到最大運輸量！

路徑有很多條，上圖隻是一種情況，但是所有路徑的最終運力結果都是一樣的！

2.X、Y、Z是某企業的三個分廠，每個分廠每天需要同一種原料20噸，下圖給出了鄰近供應廠A、B、C的供應運輸路線圖，每一段路線上标明了每天最多能運輸這種原料的噸數。根據該圖可以算出，從A、B、C三廠每天最多能給該企業運來這種原料共（）噸。

A.45 B.50 C.55 D.60

解析：也是網絡與最大流量的題，區别與第一題，起點終點不唯一，多個起點多個終點！

大家看圖領會做題思路吧！我隻是讓大家明白思路，完全不用畫這麼麻煩的圖，主要是幫助大家理解。

答案選C

不止考計算，還考理論，如下：

在一組約束條件下來尋找目标函數的極值（極大值和極小值）問題。

線性規劃問題的數學模型通常由線性目标函數、線性約束條件、變量非負條件組成（實際問題中的變量一般都是非負的）。

線性規劃問題就是面向實際應用，求解一組非負變量，使其滿足給定的一組線性約束條件，并使某個線性目标函數達到極值。滿足這些約束條件的非負變量組的集合稱為可行解域。

可行解域中使目标函數達到極值的解稱為最優解。

線性規劃問題的最優解要麼是0個（沒有），要麼是唯一的（1個），要麼有無窮個（隻要有2個，就會有無窮個）。

在實際應用中，可以直接求約束條件方程組的解，即是交叉點，将這些解代入到目标函數中判斷是否極值即可。

1.某企業需要采用甲、乙、丙三種原材料生産I、II兩種産品。生産兩種産品所需原材料數量、單位産品可獲得利潤以及企業現有原材料數如下表所示，則公司可以獲得的最大利潤是（ )萬元。取得最大利潤時，原材料（ )尚有剩餘。

A.21 B.34 C.39 D.48

A.甲 B.乙 C.丙 D.乙和丙

解析：先讀懂圖的意思吧！然後就是假設未知數，生産I為X，II為Y，就是求9X 12Y的最大值，也就是利潤。

我簡單解釋下：x y<=4，4x 3y<=12，x 3y<=6這三個式子怎麼的出來的，我明明假設的生産I産品x噸，生産II産品Y噸。

每生産1噸I産品，需要1噸甲，按照這個比例，假設x噸I，A噸甲，則A=X

每生産1噸II産品，需要1噸甲，按照這個比例，假設y噸II，B噸甲，則B=Y

A B<=4（甲的現有原料不能超過4噸），所以x y<=4！

同理：

每生産1噸I産品，需要4噸乙，按照這個比例，假設x噸I，C噸乙，則1/4=x/C，C=4X,

每生産1噸II産品，需要3噸乙，按照這個比例，假設y噸II，D噸乙，則1/3=y/D，D=3y

C D<=12（乙的現有原料不能超過12噸），所以4x 3y<=12!

每生産1噸I産品，需要1噸丙，按照這個比例，假設x噸I，E噸丙，則E=X，E=x,

每生産1噸II産品，需要3噸丙，按照這個比例，假設y噸II，F噸丙，則，1/3=y/F，F=3y，

E F<=6（丙的現有原料不能超過6噸），x 3y<=6!

感謝大夥點贊 關注的支持，是我持續學習更新的動力，關注公衆号：Coding-9527，跟大夥一起學習，成長，進步！