實(shí)用運(yùn)籌學(xué)習(xí)題選詳解

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

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

3、當(dāng)原問題為無界解時(shí)，其對(duì)偶問題無可行解；反之，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題為無界解。（×）18、若原問題有可行解，則其對(duì)偶問題也一定有可行解。（×）19、若原問題無可行解，其對(duì)偶問題也一定無可行解。（×）20、若原問題有最優(yōu)解，其對(duì)偶問題也一定有最優(yōu)解。（）21、已知為線性規(guī)劃的對(duì)偶問題的最優(yōu)解，若，說明在最優(yōu)生產(chǎn)計(jì)劃中，第種資源一定有剩余。（×）22、原問題具有無界解，則對(duì)偶問題不可行。（）23、互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無最優(yōu)解。（）24、某公司根據(jù)產(chǎn)品最優(yōu)生產(chǎn)計(jì)劃，若原材料的影子價(jià)格大于它的市場(chǎng)價(jià)格，則可購進(jìn)原材料擴(kuò)大生產(chǎn)。（）

4、25、對(duì)于線性規(guī)劃問題，已知原問題基本解不可行，對(duì)偶問題基本解可行，可采用對(duì)偶單純形法求解。（）26、原問題（極小值）第個(gè)約束是“”約束，則對(duì)偶變量。（）27、線性規(guī)劃問題的原單純形解法，可以看作是保持原問題基本解可行，通過迭代計(jì)算，逐步將對(duì)偶問題的基本解從不可行轉(zhuǎn)化為可行的過程。（）*28、運(yùn)輸問題不能化為最小費(fèi)用流問題來解決。（×）29、運(yùn)輸問題一定有最優(yōu)解。（）30、若運(yùn)輸問題的可行解退化，則存在等于零的數(shù)字格。（）31、運(yùn)輸問題是特殊的線性規(guī)劃問題，表上作業(yè)法也是特殊形式的單純形法。（）32、按最小元素法（或伏格爾法）給出的初始基可行解，從每一空格出發(fā)可以找出，而且僅能找出唯

5、一閉合回路。（）33、如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行（或某一列）元素分別乘上一個(gè)常數(shù)，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（×）34、如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（）35、如果運(yùn)輸問題單位運(yùn)價(jià)表的全部元素分別乘上一個(gè)常數(shù)，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（）36、運(yùn)輸問題獨(dú)立約束條件數(shù)個(gè)，變量數(shù)是個(gè)，于是基變量數(shù)為個(gè)。（×）37、整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解的目標(biāo)函數(shù)值。（×）38、一個(gè)整數(shù)規(guī)劃問題如果存在兩個(gè)以上的最優(yōu)解，則該問題一定有無窮多最優(yōu)解。（×）39、分支定界法在需要分支時(shí)必須

6、滿足：一是分支后的各子問題必須容易求解；二是各子問題解的集合必須覆蓋原問題的解 。（）40、整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到。（×）41、用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題的下界。（）42、用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)。通?？扇稳∑渲幸粋€(gè)作為下界值，再進(jìn)行比較剪枝。（×）43、求最大值的整數(shù)規(guī)劃問題中，其松弛問題的最優(yōu)解是整數(shù)規(guī)劃問題最優(yōu)解的上界。（）44、匈牙利算法是對(duì)指派問題求最小值的一種求解方法。（）45、指派問題效率矩陣的每個(gè)元素分別乘上一個(gè)常數(shù)，將不影響最優(yōu)指派

7、方案。（×）46、指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，故也可以用表上作業(yè)法求解。（）47、匈牙利算法是對(duì)指派問題求最小值的一種求解方法。（）48、應(yīng)用匈牙利算法求解工作指派問題時(shí)，對(duì)不打勾的行和打鉤的列畫橫線。（）49、求解效率最大的指派問題，可以用指派矩陣的最小元素減去該矩陣的各元素，得到新的指派矩陣，再用匈牙利算法求解。（×）二、第4章1、圖論中的圖不僅反映了研究對(duì)象之間的關(guān)系，而且是真實(shí)圖形的寫照，因而對(duì)圖中點(diǎn)與點(diǎn)的相對(duì)位置、點(diǎn)與點(diǎn)的連線的長(zhǎng)短曲直等都要嚴(yán)格注意。（×）2、連通圖G的部分樹是取圖G的點(diǎn)和G的所有邊組成的樹。（×）3、在有向圖中

8、，鏈和路是一回事。（×）4、連通圖一定有支撐樹。（）5、避圈法（加邊法）是：去掉圖中所有邊，從最短邊開始添加，加邊的過程中不能形成圈，直到有條邊（為圖中的點(diǎn)數(shù)）。（×）6、應(yīng)用矩陣法計(jì)算網(wǎng)絡(luò)最小支撐樹問題，應(yīng)當(dāng)在所有記有T的行里沒有劃去的元素中尋找最小元素。（）7、用避圈法得到的最小樹是惟一的，但破圈法得到的則不是。（×）8、最小生成樹的Kruskal算法，每次迭代是將剩下邊集中的最小權(quán)邊加入樹中。（×）9、Dijkstra算法和Ford算法均要求邊的權(quán)重非負(fù)。（？）。（×）10、Dijkstra算法可用于正權(quán)網(wǎng)絡(luò)也可用于負(fù)權(quán)網(wǎng)絡(luò)。（×

9、;）11、Dijkstra算法可用于求解有負(fù)權(quán)的網(wǎng)絡(luò)最短路問題。（×）12、Dijkstra算法可用于求解最短路中的所有情形。（×）13、Dijkstra算法是求最大流的一種標(biāo)號(hào)算法。（×）14、在最短路問題中，發(fā)點(diǎn)到收點(diǎn)的最短路長(zhǎng)是惟一的。（）15、求圖的最小支撐樹以及求圖中一點(diǎn)到另一點(diǎn)的最短路問題，都可以歸結(jié)為求解整數(shù)規(guī)劃問題。（）16、只有一個(gè)奇點(diǎn)的連通圖是歐拉圖。（×）17、在任何網(wǎng)絡(luò)流中，零流總是一個(gè)可行流。（）18、在最大流問題中，最大流是惟一的。（×）19、最大流問題是找一條從發(fā)點(diǎn)到收點(diǎn)的路，使得通過這條路的流量最大。（×

10、;）20、容量是弧的實(shí)際通過量。（×）21、可行流是最大流的充要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈。（）22、一個(gè)具有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)地求網(wǎng)絡(luò)最大流的問題一定可以轉(zhuǎn)化為具有單個(gè)發(fā)點(diǎn)和單個(gè)收點(diǎn)地求網(wǎng)絡(luò)最大流問題。（）23、形成增廣鏈的條件是對(duì)于正向弧必須滿足。（×）24、可行流的流量等于每條弧上的流量之和。（×）25、最大流量等于最大流。（×）26、求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個(gè)線性規(guī)劃模型。（）27、若已求得網(wǎng)絡(luò)最大流，已標(biāo)號(hào)節(jié)點(diǎn)的集合和未標(biāo)號(hào)節(jié)點(diǎn)的集合給出了網(wǎng)絡(luò)的最小割集。（）28、網(wǎng)絡(luò)最大流等于該網(wǎng)絡(luò)最大割容量。（×）29、割集中弧的流量

11、之和稱為割量。（×）30、最小割集等于最大流量。（×）31、任意可行流得流量不超過任意割量。（）32、若已給網(wǎng)絡(luò)的一個(gè)最小費(fèi)用可行流，它的最小費(fèi)用增廣鏈對(duì)應(yīng)于長(zhǎng)度網(wǎng)絡(luò)（賦權(quán)圖）的最短路。（）33、總時(shí)差為零的各項(xiàng)作業(yè)所組成的路線即為關(guān)鍵路線。（）34、工程網(wǎng)絡(luò)圖中關(guān)鍵路線是最長(zhǎng)路線。（）35、網(wǎng)絡(luò)規(guī)劃中，工作的機(jī)動(dòng)時(shí)間或富余時(shí)間叫做時(shí)差，分為總時(shí)差和單時(shí)差。（）36、以同一節(jié)點(diǎn)為開始事件的各項(xiàng)作業(yè)的最早開始時(shí)間相同。（）37、以同一節(jié)點(diǎn)為結(jié)束事件的各項(xiàng)作業(yè)的最遲結(jié)束時(shí)間相同。（）38、節(jié)點(diǎn)的最早開始時(shí)間與最遲完成時(shí)間兩兩相同所組成的路線是關(guān)鍵路線。（×）39、優(yōu)化

12、網(wǎng)絡(luò)圖計(jì)劃，保證資源的最優(yōu)配置和工期的按時(shí)完成，通常根據(jù)工作的時(shí)差，采用非關(guān)鍵路線上的工作開始時(shí)間來實(shí)現(xiàn)。（）40、采取應(yīng)急措施，往往不但縮短了工期環(huán)可以減少工程總費(fèi)用。（×）41、工程網(wǎng)絡(luò)圖中，只能有一個(gè)開始節(jié)點(diǎn)，但可以有多個(gè)結(jié)束節(jié)點(diǎn)。（×）42、工程網(wǎng)絡(luò)圖中，事項(xiàng)只表示某項(xiàng)工作結(jié)束的狀態(tài)。（×）43、工程網(wǎng)絡(luò)圖可以有幾個(gè)初始事項(xiàng)，但不可以有幾個(gè)最終事項(xiàng)。（×）44、虛活動(dòng)的作業(yè)時(shí)間等于零。（）45、在網(wǎng)絡(luò)圖得關(guān)鍵路線上，總時(shí)差等于零。（）三、第6章1、矩陣對(duì)策中，如果最優(yōu)解要求一個(gè)局中人采取純策略，則另一個(gè)局中人也必須采取純策略。（×）2、

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

14、、一個(gè)矩陣對(duì)策問題的贏得矩陣，一定有不等式。（×）10、已知某對(duì)策問題的贏得函數(shù)矩陣為，所以它是純策略對(duì)策問題。（×）11、二人零和有限對(duì)策問題中，對(duì)局雙方的贏得函數(shù)值互為相反數(shù)。（）12、最優(yōu)純策略中，為局中人贏得函數(shù)中的元素。（）運(yùn)籌學(xué)實(shí)用教程解答題一、第1章 線性規(guī)劃的基本理論及其應(yīng)用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;plo

15、t(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=

16、(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('ÏßÐԹ滮ͼ½â&

17、#183;¨');3（1.3.3）、用圖解法解線性規(guī)劃問題（答案：可行域無界，無最優(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,&

18、#39;b-');title('ÏßÐԹ滮ͼ½â·¨'); (圖形是matlab結(jié)合幾何畫板繪制出來的)6（1.3.6）、用圖解法解線性規(guī)劃問題（答案：）x=(0:0.1:9)'y1=(8-x)/2;z1=(12-2*x)/3;z2=(20-2*x)/3;plot(x,y1,'g:',x,z1,'b-',x,z2,'b-');title('Ïß

19、;ÐԹ滮ͼ½â·¨');(圖形是matlab結(jié)合幾何畫板繪制出來的)7（1.4.1）、用單純形法計(jì)算（答案：，松弛變量）詳解：引進(jìn) 松弛變量，標(biāo)準(zhǔn)化模型為。建立初始單純形表并作基的變換如下，xX1X2X3X4X5X6bthitac210000X3001100010 X402601006060/2=30X501100101818/1=18X603100014444/3最??！zj0000000Zj-cj-2-10000先找負(fù)的絕對(duì)值最大的定入X3001100010

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

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

22、X41X42X5X6X7X8X9X10X11bc-2-151-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ī)劃的對(duì)偶問題（答案：）11（1.6.1.2）、求線性規(guī)劃的對(duì)偶問題（答案：）12（1.6.1.3）、求線性規(guī)劃的對(duì)偶問題（答案：繼而得）13（1.6.1.4）

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

24、5/0.5|再找比值的絕對(duì)值最小的定入X1-2010-1/41/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的影子價(jià)格。（答案：最優(yōu)解，資源1、資源2、資源3的影子價(jià)格1,1,0）詳解：轉(zhuǎn)化為，引入松弛變量，得到標(biāo)準(zhǔn)化模型為。建立初始單純形表并作基的變換如下，xX1X2X3X4X5X6bthitac2-11000X403-221001515/3=5X50-1110103X601-1100

25、144/1=4最?。《ǔ龌兞縵j000000 Zj-cj-21-1000先找負(fù)的絕對(duì)值最大的定入基變量X4001-110-333/1=3最??！定出基變量X500020117X121 -110014zj2-22002下行加cj定入基變量Zj-cj0-110028先找負(fù)的絕對(duì)值最大X2-101-110-33X5000201177/1=7最小！定出基變量X121 0010-27zj2-1110-1下行加cj定入基變量Zj-cj00010-111先找負(fù)的絕對(duì)值最大X2-101513024X600020117 X121 0412021zj2-13110下行加cj Zj-cj00211018判定最優(yōu)解從

26、表中看出，由表的最后一行，可得資源1、資源2、資源3的影子價(jià)格分別為1,1,0。17（1.6.4）、現(xiàn)有線性規(guī)劃問題：，（1）用單純形法求解該問題；（2）用對(duì)偶單純形法求解該問題（答案：（1）用單純性法迭代；（2）用對(duì)偶單純性法迭代）18（1.6.5）、求解線性規(guī)劃（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標(biāo)準(zhǔn)化模型為。建立初始對(duì)偶單純形表并作基的變換如下，XX1X2X3X4 X5bc-20-15000X30-2-1100-5先取負(fù)的最大的b值所在，確定換出X40-320103X50-1-1001-3zj00000下行加cjZj-cj20150000thita再找比值的絕對(duì)值|20/（-2）

27、|=10，|15/（-1）|=15最小的定入XX1X2X3X4 X5bc-20-15000X1011/2-1/2005/2先取負(fù)的最大的b值所在，確定換出X4007/2-3/21021/2X500-1/2-1/201-1/2zj-20-101000下行加cjZj-cj051000-50thita再找比值的絕對(duì)值|5/（-1/2）|=10，|10/（-1）|=20最小的定入XX1X2X3X4 X5bc-20-15000X1010-1 012全正，基解可行X4000-5177X200110-21zj-20-155010下行加cjZj-cj005010-55判定最優(yōu)從表中看出最優(yōu)解為 19（1.6.

28、6）、用對(duì)偶單純型法解（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標(biāo)準(zhǔn)化模型為。建立初始對(duì)偶單純形表并作基的變換如下，XX1X2X3X4 X5bc-10-8-700X30-2-1010-4先取負(fù)的最大的b值所在，確定換出X40-1-1-101-3cj -Zj-10-8-7000thita再找比值的-10/（-2）=5，-8/（-1）=8最小的定入X1-1011/20-1/202先取負(fù)的最大的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

29、/202全正，基解可行X2-80121-22cj -Zj00-1-2-626判別數(shù)非正，確認(rèn)最優(yōu)從而得最優(yōu)解20（1.6.7）、用對(duì)偶單純型法解（答案：）詳解：轉(zhuǎn)化為 ，引入松弛變量，得到標(biāo)準(zhǔn)化模型為。建立初始對(duì)偶單純形表并作基的變換如下，XX1X2X3X4 X5bc-3-3000X302310018先取負(fù)的最大的b值所在，確定換出X40-11010-2X50-1-3001-10cj -Zj-3-30000thita再找比值的-3/（-1）=3，-3/（-3）=1最小的定入X30101018先取負(fù)的最大的b值所在，確定換出X40-4/30011/3-16/3X2-31/3100-1/310/3

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

31、。（答案： ，G是完全圖，為非連通圖，且都是G的子圖）2（4.2.2）、寫出右圖的關(guān)聯(lián)矩陣和相關(guān)矩陣。（答案：列都對(duì)應(yīng)頂點(diǎn)，關(guān)聯(lián)矩陣為，相關(guān)矩陣為）3（4.2.3）、有甲乙丙丁戊己6名運(yùn)動(dòng)員報(bào)名參加ABCDEF6個(gè)項(xiàng)目的比賽。下表中打“”的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目（表4-1）。問：6個(gè)項(xiàng)目比賽順序如何安排，做到每名運(yùn)動(dòng)員不連續(xù)參加兩項(xiàng)比賽？ABCDEF甲乙丙丁戊己（答案：， 有人同時(shí)參加則連線，方案一ACBFED，方案二AFBCDE，一條任意兩點(diǎn)不相關(guān)序列）4（4.2.4）、出席某處國(guó)際學(xué)術(shù)報(bào)告會(huì)的6個(gè)成員ABCDEF被分在一組。他們的情況是：A會(huì)講漢語、法語和日語；B會(huì)講德語、俄語和日語

32、；C會(huì)講英語、法語；D會(huì)講漢語和西班牙語；E會(huì)講英語和德語；F會(huì)講俄語和西班牙語。怎么把他們安排在一張圓桌旁坐下，使得每個(gè)人能和他兩旁的人交談？（答案： 找一條漢密頓回路ACEBFDA ）5（4.2.5）、圖G=（V，E）是連通圖，且。證明：屬于每一棵生成樹的充要條件是為G的割集。（答案：都用反證法。充分性：屬于每一棵生成樹，若不為G的割集（反設(shè)）。則G-e必連通，則G-e中必存在生成樹T，因?yàn)門也是G的生成樹，但T不包含e，導(dǎo)致矛盾。必要性：設(shè)不為G的割集（反設(shè)）。若G有生成樹T，則T+e包含回路。刪去e后連通，即與e屬于每棵生成樹矛盾，反設(shè)不成立。）6（4.2.6）、已知圖得結(jié)點(diǎn)集V=a,

33、b,c,d，以及圖G和圖D的邊集合分別為E(G)=(a,a),(a,b),(b,c),(a,c); E(D)= <a,b>,<a,c>,<c,d>,<c,a>,<c,b>。試作圖G和圖D，寫出個(gè)結(jié)點(diǎn)的度數(shù)，回答圖G、圖D是簡(jiǎn)單圖還是多重圖。（答案：在圖G中，；在圖D中；D是簡(jiǎn)單圖，其中，圖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

34、+4+2+5+5=24）9（4.3.3）、某銀行打算與其分行之間建立計(jì)算機(jī)網(wǎng)絡(luò)，用電話線作為通訊聯(lián)網(wǎng)手段，已知主行與各分行之間的距離如下表。試用矩陣法求其聯(lián)網(wǎng)的最短線路。項(xiàng)目主行B1B2B3B4B5主行-16027011570190B1-3108022050B2-175120215B3-140240B4-100B5-（答案：最短路線為B5，B1，主行，B4，B1，B3，B4，B2， B4，B5，總長(zhǎng)420=50+70+80+120+100）10（4.3.4）、某工廠內(nèi)聯(lián)結(jié)6個(gè)車間的道路網(wǎng)如下圖，已知每條道路的距離，求怎樣沿部分道路假設(shè)電話網(wǎng)，使電話線總距離最短。（答案：A1B2C3D5E4F5

35、T1A0 13T2B1 028T3C32073T5D87056T4E3506T5F660最小樹權(quán)為1+2+3+5+6=17）11（4.3.5）、用生長(zhǎng)法求下圖的最小生成樹。（答案：最小權(quán)值為2+4+4+4+5+7=26）12（4.3.6）、有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與15個(gè)控制點(diǎn)連通，下圖標(biāo)出了允許挖電纜溝的地點(diǎn)和距離（單位：百米）。若電纜線100元/米，挖電纜溝（深1米，寬0.6米）土方30元/立方米，其他建材和施工費(fèi)用50元/米，請(qǐng)作出該項(xiàng)工程預(yù)算的最小費(fèi)用。（答案：3+4+2+5+5+4+4+5+4+3+5+2+7+4+5=62百米，6200×150+6200×

36、;0.6×30=1041600，）13（4.4.1.1）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，有兩條，總長(zhǎng)16）詳解 令P(S)=0，其余T（i）=。第一次迭代 ；因最小，故。第2次迭代 ；因在所有臨時(shí)標(biāo)號(hào)中最小，故。第3次迭代 ；因在所有臨時(shí)標(biāo)號(hào)中最小，故。第4次迭代 ；因在所有臨時(shí)標(biāo)號(hào)中最小，故。第4次迭代 ；因在所有臨時(shí)標(biāo)號(hào)中最小，故。從而最短路有兩條，總長(zhǎng)16。見圖所示。14（4.4.1.2）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，總長(zhǎng)17）15（4.4.2）、某工廠準(zhǔn)備購置一臺(tái)新機(jī)器來擴(kuò)大生產(chǎn)，新機(jī)器安裝使用期限為3年，在此之后

37、不再使用。然而其工作的3年內(nèi)，負(fù)荷較大，所以隨著時(shí)間的增長(zhǎng)，運(yùn)行和保養(yǎng)費(fèi)用將有較大幅度的增加。因此在機(jī)器使用1年或2年后再購置1臺(tái)新機(jī)器來代替它可能更經(jīng)濟(jì)。下表給出了第年年底購進(jìn)一臺(tái)新機(jī)器并在第年年底將其賣掉所花費(fèi)的總費(fèi)用（購置費(fèi)加運(yùn)行和保養(yǎng)費(fèi)減去殘值）。試用凸輪的方法，將其描述為最短路問題，并給出設(shè)備更新的最佳方案。(單位：千元)ij12304815151126（答案：，1.4萬）16（4.4.3）、某公司每年年初都要決定是否更換某件設(shè)備。購置新設(shè)備要支付一定的購置費(fèi)用；繼續(xù)使用舊設(shè)備，需要支付一定的維修費(fèi)用。兩類費(fèi)用隨年份變化見下表。如何運(yùn)用最短路問題計(jì)劃一個(gè)5年內(nèi)的設(shè)備更新方案，使總費(fèi)用

38、最小？(單位：萬元)年份第1年第2年第3年第4年第5年年購置費(fèi)1111121213使用年數(shù)0112233445維修費(fèi)5681118（答案：，22+31=30+23=53）17（4.4.4）、試求下面網(wǎng)絡(luò)從到的最短路（圖上數(shù)字表示距離）。（答案：，）詳解 令，其余各點(diǎn)賦T標(biāo)號(hào)。第一次迭代 ；因最小，故。第2次迭代 ；因在所有新舊臨時(shí)標(biāo)號(hào)里最小，故。第3次迭代 ；因在所有新舊臨時(shí)標(biāo)號(hào)里最小，故。第4次迭代 因；所以。；，故；令。第5次迭代 ；令。因；所以仍為 -1。故。第6次迭代 ；令。故。18（4.4.5）、試求下面網(wǎng)絡(luò)從S到T的最短路（圖上數(shù)字表示距離）。（答案：，5+1+5=11）19（4.

39、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）、試求下面網(wǎng)絡(luò)從A到H的最短路（圖上數(shù)字表示距離）。（答案：，13）三、第6章1（6.2.1）、甲乙兩名兒童玩猜拳游戲。游戲中雙方可分別出拳頭、手掌、兩個(gè)指頭（分別代表石頭、布和剪刀）。規(guī)則是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分。若雙方所出相同，算和局，均不得分。試列出游戲中兒童甲的贏得矩陣。（答案：）2（6.2.2）、兩個(gè)游戲

40、者分別在紙上寫0、1、2三個(gè)數(shù)字中的一個(gè)，且不讓對(duì)方知道。先讓第一個(gè)人猜兩人寫的數(shù)字之和，再讓第二個(gè)人猜兩人寫的數(shù)字總和，但規(guī)定第二個(gè)人猜的總和數(shù)不能和第一個(gè)人相同。猜中者從對(duì)方處贏得1元，如果誰都沒有猜中，算和局。試回答每個(gè)游戲者各有多少個(gè)純策略。（答案：設(shè)兩個(gè)游戲者分別為甲乙：表示甲寫的數(shù)，表示甲猜的數(shù)（兩個(gè)寫的數(shù)字之和。則有0、1、2三種選擇，有0，1、2、3、4五種選擇。第一個(gè)人有15種策略。C表示乙寫的數(shù)；表示乙等甲猜數(shù)后所猜得數(shù)，有四種選擇。第二個(gè)人乙的純策略數(shù)為個(gè) ）3（6.2.3）、已知A、B兩人進(jìn)行對(duì)策時(shí)，A的贏得矩陣如下，求雙方的最優(yōu)策略與對(duì)策值。（1）、；（2）、；（3）、；（4）、；（5）、；（6）、；（7）、；（8）、；（答）詳解（1） A:B:所以，最優(yōu)解為A選 ，B選。對(duì)策值。4（6.2.4）、已知甲乙兩人進(jìn)行對(duì)策時(shí)甲的贏得矩陣如下，求雙方的最優(yōu)策略與對(duì)策值。（1）、；（2）、；（答案：）5（6.2.5）、甲乙兩人玩游戲，甲可出策略A、B、C，乙可出策略D、E、F、G?，F(xiàn)有甲乙二人的贏得矩陣如下，應(yīng)用優(yōu)勢(shì)原則簡(jiǎn)化后求出雙方的最優(yōu)策略與對(duì)策值。（答案：第二列優(yōu)于第三列，應(yīng)用優(yōu)勢(shì)原則簡(jiǎn)化劃去第三列后。甲的最優(yōu)策略為B，乙的最優(yōu)策略為E）6（6.2.6）、某單位采購員在秋天要決定冬季取暖用煤的儲(chǔ)量問題。已知在正常的冬季氣溫條件下要消耗30噸煤，在較暖