實用運籌學習題集選詳解

1、 38/38 運籌學判斷題一、第1章 線性規(guī)劃的基本理論及其應用1、線性規(guī)劃問題的可行解集不一定是凸集。（）2、若線性規(guī)劃無最優(yōu)解則其可行域無界。（）3、線性規(guī)劃具有惟一的最優(yōu)解是指最優(yōu)表中非基變量檢驗數(shù)全部非零。（）4、線性規(guī)劃問題的每一個基本可行解對應可行域的一個頂點。（）5、若線性規(guī)劃模型的可行域非空有界，則其頂點中必存在最優(yōu)解。（）6、線性規(guī)劃問題的大M法中，M是負無窮大。（）7、單純形法計算中，若不按最小比值原則選取換出變量，則在下一個解中至少有一個基變量為負。（）8、對于線性規(guī)劃問題的基本可行解，若大于零的基變量數(shù)小于約束條件數(shù)，則解是退化的。（）。9、一旦一個人工變量在迭代過程中

2、變?yōu)榉腔兞亢螅瑒t該變量及相應列的數(shù)字可以從單純性表中刪除，且這樣做不影響計算結(jié)果。（）10、線性規(guī)劃的目標函數(shù)中系數(shù)最大的變量在最優(yōu)解中總是取正值。（）11、對一個有個變量，個約束的標準型的線性規(guī)劃問題，其可行域的頂點恰好為個。（）12、線性規(guī)劃解的退化問題就是表明有多個最優(yōu)解。（）13、如果一個線性規(guī)劃問題有兩個不同的最優(yōu)解，則它有無窮多個最優(yōu)解。（）14、單純型法解線性規(guī)劃問題時值為0的變量未必是非基變量。（）15、任何線性規(guī)劃問題度存在并具有唯一的對偶問題。（）16、對偶問題的對偶問題一定是原問題。（）17、根據(jù)對偶問題的性質(zhì)，當原問題為無界解時，其對偶問題無可行解；反之，當對偶問題無

3、可行解時，其原問題為無界解。（）18、若原問題有可行解，則其對偶問題也一定有可行解。（）19、若原問題無可行解，其對偶問題也一定無可行解。（）20、若原問題有最優(yōu)解，其對偶問題也一定有最優(yōu)解。（）21、已知為線性規(guī)劃的對偶問題的最優(yōu)解，若，說明在最優(yōu)生產(chǎn)計劃中，第種資源一定有剩余。（）22、原問題具有無界解，則對偶問題不可行。（）23、互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解。（）24、某公司根據(jù)產(chǎn)品最優(yōu)生產(chǎn)計劃，若原材料的影子價格大于它的市場價格，則可購進原材料擴大生產(chǎn)。（）25、對于線性規(guī)劃問題，已知原問題基本解不可行，對偶問題基本解可行，可采用對偶單純形法求解。（）26、原問

4、題（極小值）第個約束是“”約束，則對偶變量。（）27、線性規(guī)劃問題的原單純形解法，可以看作是保持原問題基本解可行，通過迭代計算，逐步將對偶問題的基本解從不可行轉(zhuǎn)化為可行的過程。（）*28、運輸問題不能化為最小費用流問題來解決。（）29、運輸問題一定有最優(yōu)解。（）30、若運輸問題的可行解退化，則存在等于零的數(shù)字格。（）31、運輸問題是特殊的線性規(guī)劃問題，表上作業(yè)法也是特殊形式的單純形法。（）32、按最小元素法（或伏格爾法）給出的初始基可行解，從每一空格出發(fā)可以找出，而且僅能找出唯一閉合回路。（）33、如果運輸問題單位運價表的某一行（或某一列）元素分別乘上一個常數(shù)，調(diào)運方案將不會發(fā)生變化。（）34

5、、如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數(shù)，調(diào)運方案將不會發(fā)生變化。（）35、如果運輸問題單位運價表的全部元素分別乘上一個常數(shù)，調(diào)運方案將不會發(fā)生變化。（）36、運輸問題獨立約束條件數(shù)個，變量數(shù)是個，于是基變量數(shù)為個。（）37、整數(shù)規(guī)劃解的目標函數(shù)值一般優(yōu)于其相應的線性規(guī)劃問題的解的目標函數(shù)值。（）38、一個整數(shù)規(guī)劃問題如果存在兩個以上的最優(yōu)解，則該問題一定有無窮多最優(yōu)解。（）39、分支定界法在需要分支時必須滿足：一是分支后的各子問題必須容易求解；二是各子問題解的集合必須覆蓋原問題的解 。（）40、整數(shù)規(guī)劃的最優(yōu)解是先求相應的線性規(guī)劃的最優(yōu)解然后取整得到。（）41、用分支

6、定界法求解一個極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標函數(shù)值是該問題的下界。（）42、用分支定界法求解一個極大化的整數(shù)規(guī)劃問題，當?shù)玫蕉嘤谝粋€可行解時。通?？扇稳∑渲幸粋€作為下界值，再進行比較剪枝。（）43、求最大值的整數(shù)規(guī)劃問題中，其松弛問題的最優(yōu)解是整數(shù)規(guī)劃問題最優(yōu)解的上界。（）44、匈牙利算法是對指派問題求最小值的一種求解方法。（）45、指派問題效率矩陣的每個元素分別乘上一個常數(shù)，將不影響最優(yōu)指派方案。（）46、指派問題數(shù)學模型的形式同運輸問題十分相似，故也可以用表上作業(yè)法求解。（）47、匈牙利算法是對指派問題求最小值的一種求解方法。（）48、應用匈牙利算法求解工作指派問題時，對不打

7、勾的行和打鉤的列畫橫線。（）49、求解效率最大的指派問題，可以用指派矩陣的最小元素減去該矩陣的各元素，得到新的指派矩陣，再用匈牙利算法求解。（）二、第4章1、圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點的連線的長短曲直等都要嚴格注意。（）2、連通圖G的部分樹是取圖G的點和G的所有邊組成的樹。（）3、在有向圖中，鏈和路是一回事。（）4、連通圖一定有支撐樹。（）5、避圈法（加邊法）是：去掉圖中所有邊，從最短邊開始添加，加邊的過程中不能形成圈，直到有條邊（為圖中的點數(shù)）。（）6、應用矩陣法計算網(wǎng)絡(luò)最小支撐樹問題，應當在所有記有T的行里沒有劃去的元素

8、中尋找最小元素。（）7、用避圈法得到的最小樹是惟一的，但破圈法得到的則不是。（）8、最小生成樹的Kruskal算法，每次迭代是將剩下邊集中的最小權(quán)邊加入樹中。（）9、Dijkstra算法和Ford算法均要求邊的權(quán)重非負。（？）。（）10、Dijkstra算法可用于正權(quán)網(wǎng)絡(luò)也可用于負權(quán)網(wǎng)絡(luò)。（）11、Dijkstra算法可用于求解有負權(quán)的網(wǎng)絡(luò)最短路問題。（）12、Dijkstra算法可用于求解最短路中的所有情形。（）13、Dijkstra算法是求最大流的一種標號算法。（）14、在最短路問題中，發(fā)點到收點的最短路長是惟一的。（）15、求圖的最小支撐樹以及求圖中一點到另一點的最短路問題，都可以歸結(jié)為

9、求解整數(shù)規(guī)劃問題。（）16、只有一個奇點的連通圖是歐拉圖。（）17、在任何網(wǎng)絡(luò)流中，零流總是一個可行流。（）18、在最大流問題中，最大流是惟一的。（）19、最大流問題是找一條從發(fā)點到收點的路，使得通過這條路的流量最大。（）20、容量是弧的實際通過量。（）21、可行流是最大流的充要條件是不存在發(fā)點到收點的增廣鏈。（）22、一個具有多個發(fā)點和多個收點地求網(wǎng)絡(luò)最大流的問題一定可以轉(zhuǎn)化為具有單個發(fā)點和單個收點地求網(wǎng)絡(luò)最大流問題。（）23、形成增廣鏈的條件是對于正向弧必須滿足。（）24、可行流的流量等于每條弧上的流量之和。（）25、最大流量等于最大流。（）26、求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個線性規(guī)劃

10、模型。（）27、若已求得網(wǎng)絡(luò)最大流，已標號節(jié)點的集合和未標號節(jié)點的集合給出了網(wǎng)絡(luò)的最小割集。（）28、網(wǎng)絡(luò)最大流等于該網(wǎng)絡(luò)最大割容量。（）29、割集中弧的流量之和稱為割量。（）30、最小割集等于最大流量。（）31、任意可行流得流量不超過任意割量。（）32、若已給網(wǎng)絡(luò)的一個最小費用可行流，它的最小費用增廣鏈對應于長度網(wǎng)絡(luò)（賦權(quán)圖）的最短路。（）33、總時差為零的各項作業(yè)所組成的路線即為關(guān)鍵路線。（）34、工程網(wǎng)絡(luò)圖中關(guān)鍵路線是最長路線。（）35、網(wǎng)絡(luò)規(guī)劃中，工作的機動時間或富余時間叫做時差，分為總時差和單時差。（）36、以同一節(jié)點為開始事件的各項作業(yè)的最早開始時間相同。（）37、以同一節(jié)點為結(jié)束

11、事件的各項作業(yè)的最遲結(jié)束時間相同。（）38、節(jié)點的最早開始時間與最遲完成時間兩兩相同所組成的路線是關(guān)鍵路線。（）39、優(yōu)化網(wǎng)絡(luò)圖計劃，保證資源的最優(yōu)配置和工期的按時完成，通常根據(jù)工作的時差，采用非關(guān)鍵路線上的工作開始時間來實現(xiàn)。（）40、采取應急措施，往往不但縮短了工期環(huán)可以減少工程總費用。（）41、工程網(wǎng)絡(luò)圖中，只能有一個開始節(jié)點，但可以有多個結(jié)束節(jié)點。（）42、工程網(wǎng)絡(luò)圖中，事項只表示某項工作結(jié)束的狀態(tài)。（）43、工程網(wǎng)絡(luò)圖可以有幾個初始事項，但不可以有幾個最終事項。（）44、虛活動的作業(yè)時間等于零。（）45、在網(wǎng)絡(luò)圖得關(guān)鍵路線上，總時差等于零。（）三、第6章1、矩陣對策中，如果最優(yōu)解要求

12、一個局中人采取純策略，則另一個局中人也必須采取純策略。（）2、任何矩陣對策一定存在混合策路意義下的解，并可以通過求解兩個互為對偶的線性規(guī)劃問題得到。（）3、對策模型的三要素：局中人、策略、贏得函數(shù)。（）4、在兩人零和對策支付矩陣的某一行（或某一列）上加上一個常數(shù)，將不影響對策雙方各自的最優(yōu)策略。（）5、二人零和對策支付矩陣的所有元素乘上一個常數(shù)，將不影響對策雙方各自的最優(yōu)策略。（）6、應對災害天氣制定預案的策略，同制訂對一場可能發(fā)生的軍事沖突的策略，具有相同的性質(zhì)和過程。（）7、如果在任一“局勢”中，全體局中人的“得失”相加總是等于零，這個對策就叫做“零和對策”。（）8、任何一個給定的矩陣對策

13、G一定有解（在混合擴充中的解）。（）9、一個矩陣對策問題的贏得矩陣，一定有不等式。（）10、已知某對策問題的贏得函數(shù)矩陣為，所以它是純策略對策問題。（）11、二人零和有限對策問題中，對局雙方的贏得函數(shù)值互為相反數(shù)。（）12、最優(yōu)純策略中，為局中人贏得函數(shù)中的元素。（）運籌學實用教程解答題一、第1章 線性規(guī)劃的基本理論及其應用1（1.3.1）、用圖解法解線性規(guī)劃問題（答案：）x=(0:0.1:12);y1=(22-2*x)/4;y2=2*x-7;y3=(x+10)/4;y4=(x-1)/3;z1=(1-3*x)/2;z2=(4-3*x)/2;z3=(8-3*x)/2;z4=(12-3*x)/2;

14、plot(x,y1,g:,x,y2,g:,x,y3,g:,x,y4,g:,x,z1,b-,x,z2,b-,x,z3,b-,x,z4,b-);title();2（1.3.2）、用圖解法解線性規(guī)劃問題（答案：）x=(0:0.1:15);y1=10;y2=(60-2*x)/5;y3=18-x;y4=44-3*x;z1=1-2*x;z2=4-2*x;z3=8-2*x;z4=12-2*x;plot(x,y1,g:,x,y2,g:,x,y3,g:,x,y4,g:,x,z1,b-,x,z2,b-,x,z3,b-,x,z4,b-);title();3（1.3.3）、用圖解法解線性規(guī)劃問題（答案：可行域無界，無

15、最優(yōu)解）(圖形是matlab結(jié)合幾何畫板繪制出來的)4（1.3.4）、用圖解法解線性規(guī)劃問題（答案：無可行域，無最優(yōu)解）(圖形是matlab結(jié)合幾何畫板繪制出來的)5（1.3.5）、用圖解法解線性規(guī)劃問題（答案：可行域無界，無最優(yōu)解）x=(0:0.1:3);y1=(6+3*x)/2;y2=(18+x)/3;z1=(12-4*x)/3;z2=(20-4*x)/3;plot(x,y1,g:,x,y2,g:,x,z1,b-,x,z2,b-);title();(圖形是matlab結(jié)合幾何畫板繪制出來的)6（1.3.6）、用圖解法解線性規(guī)劃問題（答案：）x=(0:0.1:9);y1=(8-x)/2;z1

16、=(12-2*x)/3;z2=(20-2*x)/3;plot(x,y1,g:,x,z1,b-,x,z2,b-);title();(圖形是matlab結(jié)合幾何畫板繪制出來的)7（1.4.1）、用單純形法計算（答案：，松弛變量）詳解：引進 松弛變量，標準化模型為。建立初始單純形表并作基的變換如下，xX1X2X3X4X5X6bthitac210000X3001100010X402601006060/2=30X501100101818/1=18X603100014444/3最?。j0000000Zj-cj-2-10000先找負的絕對值最大的定入X300110001010X40013/3010-2/3

17、92/392/13X5002/3001-1/310/35最??！定出X1211/30001/344/344zj22/30002/388/3下一行+cjZj-cj0-1/30002/3先找負的絕對值最大的定入X300010-3/21/25X400001-13/23/29X2101003/2-1/25X121000-1/21/213zj21001/21/231下一行+cjZj-cj0 0001/21/2最優(yōu)性判別，得知最優(yōu)解從表中得答案，松弛變量。8（1.4.2）、用單純形法計算（答案：）詳解：引進松弛變量，標準化模型為。建立初始單純形表并作基的變換如下，xX1X2X3X4X5bthitac4360

18、0X40313103030/3=10, 最小出基X50223014040/310 zj000000Zj-cj-4-3-600先找負的絕對值最大的定入X3611/311/301030X50-110-111010, 最小出基zj6262060下一行+cjZj-cj2-1020先找負的絕對值最大的定入X364/3012/3-1/320/3X23-110-1110zj5361170下一行+cjZj-cj10011最優(yōu)性判別，得知最優(yōu)解從表中得答案，9（1.4.3）、現(xiàn)有單純形法問題（1）化為標準型；（2）列出初始單純型表（答案：xX1X2X3X41X42X5X6X7X8X9X10X11bc-2-151

19、-10-M0-M00-MX503001-1100000025X6-M1111-1010000020X8-M4060000-110005X900232-2000010030X11-M0232-200000-112zj-5M-3M-10M-3M3M0-MM-M0M-M-27MZj-cj-5M+2-3M+1-10M-5-3M-1-3M+100M00M0）10（1.6.1.1）、求線性規(guī)劃的對偶問題（答案：）11（1.6.1.2）、求線性規(guī)劃的對偶問題（答案：）12（1.6.1.3）、求線性規(guī)劃的對偶問題（答案：繼而得）13（1.6.1.4）、求線性規(guī)劃的對偶問題（答案：）14（1.6.1.5）、求線

20、性規(guī)劃的對偶問題（答案：）15（1.6.2）、用對偶單純型法解（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標準化模型為。建立初始對偶單純形表并作基的變換如下，XX1X2X3X4bc-20-1000X30-5-110-6先取負的最大的b值所在，確定換出X40-2-201-8zj00000Zj-cj201000thita|20/-2|10/-2|再找比值的絕對值最小的定入X30-401-1/2-2先取負的最大的b值所在，確定換出X2-10110-1/24zj-10-1005下行加cjZj-cj10005-40thita|-10/4|-5/0.5|再找比值的絕對值最小的定入X1-2010-1/41/

21、81/2已經(jīng)全為正了，說明基解已可行X2-10011/4-5/83.5zj-20-105/23.75下行加cjZj-cj005/23.75-45依判據(jù)，得最優(yōu)解從表中看出，16（1.6.3）、現(xiàn)有線性規(guī)劃問題：，用單純形法求最優(yōu)解和資源1、資源2、資源3的影子價格。（答案：最優(yōu)解，資源1、資源2、資源3的影子價格1,1,0）詳解：轉(zhuǎn)化為，引入松弛變量，得到標準化模型為。建立初始單純形表并作基的變換如下，xX1X2X3X4X5X6bthitac2-11000X403-221001515/3=5X50-1110103X601-1100144/1=4最??！定出基變量zj000000Zj-cj-21-

22、1000先找負的絕對值最大的定入基變量X4001-110-333/1=3最?。《ǔ龌兞縓500020117X121-110014zj2-22002下行加cj定入基變量Zj-cj0-110028先找負的絕對值最大X2-101-110-33X5000201177/1=7最??！定出基變量X121 0010-27zj2-1110-1下行加cj定入基變量Zj-cj00010-111先找負的絕對值最大X2-101513024X600020117X121 0412021zj2-13110下行加cjZj-cj00211018判定最優(yōu)解從表中看出，由表的最后一行，可得資源1、資源2、資源3的影子價格分別為1,

23、1,0。17（1.6.4）、現(xiàn)有線性規(guī)劃問題：，（1）用單純形法求解該問題；（2）用對偶單純形法求解該問題（答案：（1）用單純性法迭代；（2）用對偶單純性法迭代）18（1.6.5）、求解線性規(guī)劃（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標準化模型為。建立初始對偶單純形表并作基的變換如下，XX1X2X3X4X5bc-20-15000X30-2-1100-5先取負的最大的b值所在，確定換出X40-320103X50-1-1001-3zj00000下行加cjZj-cj20150000thita再找比值的絕對值|20/（-2）|=10，|15/（-1）|=15最小的定入XX1X2X3X4X5bc-2

24、0-15000X1011/2-1/2005/2先取負的最大的b值所在，確定換出X4007/2-3/21021/2X500-1/2-1/201-1/2zj-20-101000下行加cjZj-cj051000-50thita再找比值的絕對值|5/（-1/2）|=10，|10/（-1）|=20最小的定入XX1X2X3X4X5bc-20-15000X1010-1 012全正，基解可行X4000-5177X200110-21zj-20-155010下行加cjZj-cj005010-55判定最優(yōu)從表中看出最優(yōu)解為 19（1.6.6）、用對偶單純型法解（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標準化模型為

25、。建立初始對偶單純形表并作基的變換如下，XX1X2X3X4X5bc-10-8-700X30-2-1010-4先取負的最大的b值所在，確定換出X40-1-1-101-3cj-Zj-10-8-7000thita再找比值的-10/（-2）=5，-8/（-1）=8最小的定入X1-1011/20-1/202先取負的最大的b值所在，確定換出X400-1/2-1-1/21-1cj-Zj0-3-7-5020thita再找比值的-3/（-1/2）=6，-7/（-1）=7，-5/（-1/2）=10最小的定入X1-1011/20-1/202全正，基解可行X2-80121-22cj-Zj00-1-2-626判別數(shù)非正

26、，確認最優(yōu)從而得最優(yōu)解20（1.6.7）、用對偶單純型法解（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標準化模型為。建立初始對偶單純形表并作基的變換如下，XX1X2X3X4X5bc-3-3000X302310018先取負的最大的b值所在，確定換出X40-11010-2X50-1-3001-10cj-Zj-3-30000thita再找比值的-3/（-1）=3，-3/（-3）=1最小的定入X30101018先取負的最大的b值所在，確定換出X40-4/30011/3-16/3X2-31/3100-1/310/3cj-Zj-2000-110thita再找比值的-2/（-4/3）=3/2 最小的定入X3

27、00013/45/44全正，基解可行X1-3100-3/4-1/44X2-30101/4-1/42cj-Zj-2000-110判別數(shù)非正，確認最優(yōu)thita再找比值的-2/（-4/3）=3/2 最小的定入從表中看出，最優(yōu)解為二、第4章1（4.2.1）、某市舉行1990年世界杯6強（A、B、C、D、E、F）聯(lián)賽。競賽采取循環(huán)制，每天安排三場比賽。同一個隊一天之內(nèi)只安排一場，要求競賽在5天之內(nèi)賽完，請用圖的方法表示6個隊之間的聯(lián)賽，和競賽日程安排，并指出每個圖是什么類型的圖，各日程安排圖與聯(lián)賽圖是什么關(guān)系。（答案：，G是完全圖，為非連通圖，且都是G的子圖）2（4.2.2）、寫出右圖的關(guān)聯(lián)矩陣和相關(guān)

28、矩陣。（答案：列都對應頂點，關(guān)聯(lián)矩陣為，相關(guān)矩陣為）3（4.2.3）、有甲乙丙丁戊己6名運動員報名參加ABCDEF6個項目的比賽。下表中打“”的是各運動員報名參加的比賽項目（表4-1）。問：6個項目比賽順序如何安排，做到每名運動員不連續(xù)參加兩項比賽？ABCDEF甲乙丙丁戊己（答案：，有人同時參加則連線，方案一ACBFED，方案二AFBCDE，一條任意兩點不相關(guān)序列）4（4.2.4）、出席某處國際學術(shù)報告會的6個成員ABCDEF被分在一組。他們的情況是：A會講漢語、法語和日語；B會講德語、俄語和日語；C會講英語、法語；D會講漢語和西班牙語；E會講英語和德語；F會講俄語和西班牙語。怎么把他們安排在

29、一X圓桌旁坐下，使得每個人能和他兩旁的人交談？（答案：找一條漢密頓回路ACEBFDA）5（4.2.5）、圖G=（V，E）是連通圖，且。證明：屬于每一棵生成樹的充要條件是為G的割集。（答案：都用反證法。充分性：屬于每一棵生成樹，若不為G的割集（反設(shè)）。則G-e必連通，則G-e中必存在生成樹T，因為T也是G的生成樹，但T不包含e，導致矛盾。必要性：設(shè)不為G的割集（反設(shè)）。若G有生成樹T，則T+e包含回路。刪去e后連通，即與e屬于每棵生成樹矛盾，反設(shè)不成立。）6（4.2.6）、已知圖得結(jié)點集V=a,b,c,d，以及圖G和圖D的邊集合分別為E(G)=(a,a),(a,b),(b,c),(a,c);E(

30、D)= ,。試作圖G和圖D，寫出個結(jié)點的度數(shù)，回答圖G、圖D是簡單圖還是多重圖。（答案：在圖G中，；在圖D中；D是簡單圖，其中，圖G是多重圖。）7（4.3.1）、用破圈法或避圈法求右圖的最小生成樹。（答案：權(quán)值9+7+8+9.5+10=43.5）8（4.3.2）、求下圖的最小生成樹，畫出該最小生成樹，并給出該最小生成樹的權(quán)值。旁邊的數(shù)字為該邊的權(quán)值。（答案：，權(quán)值3+1+1+3+4+2+5+5=24）9（4.3.3）、某銀行打算與其分行之間建立計算機網(wǎng)絡(luò)，用線作為通訊聯(lián)網(wǎng)手段，已知主行與各分行之間的距離如下表。試用矩陣法求其聯(lián)網(wǎng)的最短線路。項目主行B1B2B3B4B5主行-1602701157

31、0190B1-3108022050B2-175120215B3-140240B4-100B5-（答案：最短路線為B5，B1，主行，B4，B1，B3，B4，B2， B4，B5，總長420=50+70+80+120+100）10（4.3.4）、某工廠內(nèi)聯(lián)結(jié)6個車間的道路網(wǎng)如下圖，已知每條道路的距離，求怎樣沿部分道路假設(shè)網(wǎng)，使線總距離最短。（答案：A1B2C3D5E4F5T1A0 13T2B1 028T3C32073T5D87056T4E3506T5F660最小樹權(quán)為1+2+3+5+6=17）11（4.3.5）、用生長法求下圖的最小生成樹。（答案：最小權(quán)值為2+4+4+4+5+7=26）12（4.3

32、.6）、有一項工程，要埋設(shè)電纜將中央控制室與15個控制點連通，下圖標出了允許挖電纜溝的地點和距離（單位：百米）。若電纜線100元/米，挖電纜溝（深1米，寬0.6米）土方30元/立方米，其他建材和施工費用50元/米，請作出該項工程預算的最小費用。（答案：3+4+2+5+5+4+4+5+4+3+5+2+7+4+5=62百米，6200150+62000.630=1041600，）13（4.4.1.1）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，有兩條，總長16）詳解 令P(S)=0，其余T（i）=。第一次迭代 ；因最小，故。第2次迭代；因在所有臨時標號中最小，故。第3次迭代 ；因在

33、所有臨時標號中最小，故。第4次迭代 ；因在所有臨時標號中最小，故。第4次迭代 ；因在所有臨時標號中最小，故。從而最短路有兩條，總長16。見圖所示。14（4.4.1.2）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，總長17）15（4.4.2）、某工廠準備購置一臺新機器來擴大生產(chǎn)，新機器安裝使用期限為3年，在此之后不再使用。然而其工作的3年內(nèi)，負荷較大，所以隨著時間的增長，運行和保養(yǎng)費用將有較大幅度的增加。因此在機器使用1年或2年后再購置1臺新機器來代替它可能更經(jīng)濟。下表給出了第年年底購進一臺新機器并在第年年底將其賣掉所花費的總費用（購置費加運行和保養(yǎng)費減去殘值）。試用凸輪的方法

34、，將其描述為最短路問題，并給出設(shè)備更新的最佳方案。(單位：千元)ij12304815151126（答案：，1.4萬）16（4.4.3）、某公司每年年初都要決定是否更換某件設(shè)備。購置新設(shè)備要支付一定的購置費用；繼續(xù)使用舊設(shè)備，需要支付一定的維修費用。兩類費用隨年份變化見下表。如何運用最短路問題計劃一個5年內(nèi)的設(shè)備更新方案，使總費用最??？(單位：萬元)年份第1年第2年第3年第4年第5年年購置費1111121213使用年數(shù)0112233445維修費5681118（答案：，22+31=30+23=53）17（4.4.4）、試求下面網(wǎng)絡(luò)從到的最短路（圖上數(shù)字表示距離）。（答案：，）詳解 令，其余各點賦T

35、標號。第一次迭代 ；因最小，故。第2次迭代 ；因在所有新舊臨時標號里最小，故。第3次迭代 ；因在所有新舊臨時標號里最小，故。第4次迭代 因；所以。；，故；令。第5次迭代 ；令。因；所以仍為 -1。故。第6次迭代 ；令。故。18（4.4.5）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，5+1+5=11）19（4.4.6）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，10）20（4.4.7）、試求下面網(wǎng)絡(luò)從A到F的最短路（圖上數(shù)字表示距離）。（答案：，8）21（4.4.8）、試求下面網(wǎng)絡(luò)從A到G的最短路（圖上數(shù)字表示距離）。（答案：，13）22（4.4.9）、試求

36、下面網(wǎng)絡(luò)從A到H的最短路（圖上數(shù)字表示距離）。（答案：，13）三、第6章1（6.2.1）、甲乙兩名兒童玩猜拳游戲。游戲中雙方可分別出拳頭、手掌、兩個指頭（分別代表石頭、布和剪刀）。規(guī)則是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分。若雙方所出相同，算和局，均不得分。試列出游戲中兒童甲的贏得矩陣。（答案：）2（6.2.2）、兩個游戲者分別在紙上寫0、1、2三個數(shù)字中的一個，且不讓對方知道。先讓第一個人猜兩人寫的數(shù)字之和，再讓第二個人猜兩人寫的數(shù)字總和，但規(guī)定第二個人猜的總和數(shù)不能和第一個人相同。猜中者從對方處贏得1元，如果誰都沒有猜中，算和局。試回答每個游戲者各有多少個純策略。（答案：設(shè)兩個游戲者

37、分別為甲乙：表示甲寫的數(shù)，表示甲猜的數(shù)（兩個寫的數(shù)字之和。則有0、1、2三種選擇，有0，1、2、3、4五種選擇。第一個人有15種策略。C表示乙寫的數(shù)；表示乙等甲猜數(shù)后所猜得數(shù)，有四種選擇。第二個人乙的純策略數(shù)為個 ）3（6.2.3）、已知A、B兩人進行對策時，A的贏得矩陣如下，求雙方的最優(yōu)策略與對策值。（1）、；（2）、；（3）、；（4）、；（5）、；（6）、；（7）、；（8）、；（答）詳解（1） A:B:所以，最優(yōu)解為A選 ，B選。對策值。4（6.2.4）、已知甲乙兩人進行對策時甲的贏得矩陣如下，求雙方的最優(yōu)策略與對策值。（1）、；（2）、；（答案：）5（6.2.5）、甲乙兩人玩游戲，甲可出策略A、B、C，乙可出策略D、E、F、G。現(xiàn)有甲乙二人的贏得矩陣如下，應用優(yōu)勢原則簡化后求出雙方的最優(yōu)策略與對策值。（答案：第二列優(yōu)于第三列，應用優(yōu)勢原則簡化劃去第三列后。甲的最優(yōu)策略為B，乙的最優(yōu)策略為E）6（6.2.6）、某單位采購員在秋天要決定冬季取暖用煤的儲量問題。已知在正常的冬季氣溫條件下要消耗30噸煤，在較暖和較冷氣溫條件下要消耗20噸和40噸煤。假定冬季時的煤價隨天氣寒冷程度而有所變化，在較暖、正常、較冷的氣候條件下每噸煤價分別為10元、15元和20元，又設(shè)秋季時每噸煤價為10元。在