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

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

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

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

4、格， 則可購(gòu)進(jìn)原材 料擴(kuò)大生產(chǎn)。 （V）25、對(duì)于線性規(guī)劃問(wèn)題，已知原問(wèn)題基本解不可行，對(duì)偶問(wèn)題基本解可行，可采用對(duì)偶單純 形法求解。（V）26、 原問(wèn)題（極小值）第i個(gè)約束是“ ”約束，則對(duì)偶變量 y 0。（V）27、線性規(guī)劃問(wèn)題的原單純形解法，可以看作是保持原問(wèn)題基本解可行，通過(guò)迭代計(jì)算，逐步將對(duì)偶問(wèn)題的基本解從不可行轉(zhuǎn)化為可行的過(guò)程。（V）*28、運(yùn)輸問(wèn)題不能化為最小費(fèi)用流問(wèn)題來(lái)解決。 （X）29、運(yùn)輸問(wèn)題一定有最優(yōu)解。（V）30、 若運(yùn)輸問(wèn)題的可行解退化，則存在等于零的數(shù)字格。（V）31、 運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，表上作業(yè)法也是特殊形式的單純形法。（V）32、按最小元素法（或伏格

5、爾法）給出的初始基可行解，從每一空格出發(fā)可以找出，而且僅 能找出唯一閉合回路。 （V）33、 如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別乘上一個(gè)常數(shù)k ，調(diào)運(yùn)方案將 不會(huì)發(fā)生變化。（X）34、 如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)k ，調(diào)運(yùn)方案將 不會(huì)發(fā)生變化。 （V）35、 如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的全部元素分別乘上一個(gè)常數(shù)k k 0 ，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（V）36、 運(yùn)輸問(wèn)題獨(dú)立約束條件數(shù) m n 1個(gè)，變量數(shù)是mn個(gè)，于是基變量數(shù)為 mn m n個(gè)。（X）37、 整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問(wèn)題的解的目標(biāo)函數(shù)值。（X）38、 一個(gè)整

6、數(shù)規(guī)劃問(wèn)題如果存在兩個(gè)以上的最優(yōu)解，則該問(wèn)題一定有無(wú)窮多最優(yōu)解。（X）39、分支定界法在需要分支時(shí)必須滿足： 一是分支后的各子問(wèn)題必須容易求解； 二是各子問(wèn)題解的集合必須覆蓋原問(wèn)題的解。（V）40、 整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到。（X）41、 用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問(wèn) 題的下界。（V）42、 用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)。 通?？扇稳?其中一個(gè)作為下界值，再進(jìn)行比較剪枝。 （X）43、 求最大值的整數(shù)規(guī)劃問(wèn)題中，其松弛問(wèn)題的最優(yōu)解是整數(shù)規(guī)劃問(wèn)題最優(yōu)解的上界。 （V）44、 匈牙利

7、算法是對(duì)指派問(wèn)題求最小值的一種求解方法。（V）45、 指派問(wèn)題效率矩陣的每個(gè)元素分別乘上一個(gè)常數(shù)k ，將不影響最優(yōu)指派方案。 （X）46、 指派問(wèn)題數(shù)學(xué)模型的形式同運(yùn)輸問(wèn)題十分相似，故也可以用表上作業(yè)法求解。（V）47、 匈牙利算法是對(duì)指派問(wèn)題求最小值的一種求解方法。（V）48、 應(yīng)用匈牙利算法求解工作指派問(wèn)題時(shí)，對(duì)不打勾的行和打鉤的列畫橫線。（V）49、 求解效率最大的指派問(wèn)題，可以用指派矩陣的最小元素減去該矩陣的各元素， 得到新的 指派矩陣，再用匈牙利算法求解。 （X）二、第 4 章1、圖論中的圖不僅反映了研究對(duì)象之間的關(guān)系，而且是真實(shí)圖形的寫照，因而對(duì)圖中點(diǎn)與點(diǎn)的相對(duì)位置、點(diǎn)與點(diǎn)的連線的

8、長(zhǎng)短曲直等都要嚴(yán)格注意。（X）2、連通圖 G 的部分樹是取圖 G 的點(diǎn)和 G 的所有邊組成的樹。 （X）3、 在有向圖中，鏈和路是一回事。（X）4、 連通圖一定有支撐樹。（V）5、避圈法（加邊法）是：去掉圖中所有邊，從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到有n條邊（n為圖中的點(diǎn)數(shù)）。（X）6、 應(yīng)用矩陣法計(jì)算網(wǎng)絡(luò)最小支撐樹問(wèn)題，應(yīng)當(dāng)在所有記有T 的行里沒(méi)有劃去的元素中尋找 最小元素。（V）7、 用避圈法得到的最小樹是惟一的，但破圈法得到的則不是。（X）8、最小生成樹的 Kruskal 算法，每次迭代是將剩下邊集中的最小權(quán)邊加入樹中。（X）9、 Dijkstra算法和Ford算法均要求邊的

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

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

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

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

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

14、給定的矩陣對(duì)策 G 一定有解（在混合擴(kuò)充中的解）。（V）9、 一個(gè)矩陣對(duì)策問(wèn)題的贏得矩陣 A aij ，一定有不等式 max min aij min maxaij 。 （ X ）i j j i13210、 已知某對(duì)策問(wèn)題的贏得函數(shù)矩陣為5 2 3 ，所以它是純策略對(duì)策問(wèn)題。 （X）24311、 二人零和有限對(duì)策問(wèn)題中，對(duì)局雙方的贏得函數(shù)值互為相反數(shù)。（V）12、 最優(yōu)純策略中， max min aij min max aij , aij 為局中人贏得函數(shù)中的元素。（V）運(yùn)籌學(xué)實(shí)用教程解答題、第1章 線性規(guī)劃的基本理論及其應(yīng)用1（ 131）、用圖解法解線性規(guī)劃問(wèn)題max z3x12x22x14x

15、222片4x210(答案：max z 21; x!s.t 2x14x27x13x21x-i, x20x=(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;plot(x,y1, g：,x,y2,g:,x,y3,b-,x,z4,b-)；title(?D?1? i ?a );g：,x,y4,g:,x,z1,b-,x,z2b-,x,z32( 132)、用圖解法解線性規(guī)劃問(wèn)題max z 2x1 x2x2102x1 5x26012(答案:

16、s.t x1 x2183x-i x244max z 31“13, x25)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(?D?1? i ?a );maxz3x1 2x2%33 (133)、用圖解法解線性規(guī)劃問(wèn)題(答案:可行域無(wú)界，無(wú)最優(yōu)解)St %x20x1,x20（圖形是matlab結(jié)合幾何畫板繪制出來(lái)的）

17、max z 3x1 2x24 （134）、用圖解法解線性規(guī)劃問(wèn)題Xix21St2為 2x24（答案：無(wú)可行域，無(wú)最優(yōu)解）Xi,X20（圖形是matlab結(jié)合幾何畫板繪制出來(lái)的）max z 4x1 3x23人 2x265 (135)、用圖解法解線性規(guī)劃問(wèn)題12(答案：可行域無(wú)界，無(wú)最優(yōu)解)s.t% 3x2 18%, x2 0線性規(guī)劃圖解法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(?D?1? i ?a );(圖形是m

18、atlab結(jié)合幾何畫板繪制出來(lái)的)maxz2為3x24x1166 (136)、用圖解法解線性規(guī)劃問(wèn)題(答案：maxz 14;x14, x22 )S.t為2x28x1,x20x=(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(?D?1? i ?a );(圖形是matlab結(jié)合幾何畫板繪制出來(lái)的)max z 2x1 x2x2107 (141)、用單純形法計(jì)算2x1 5x260s.t x1 x2183x! x244x1, x20(答案：max z 31; x1 13, x2 5

19、，松弛變量 x35,X49,X5X60)maxz2x,X2X2X310詳解：引進(jìn) 松弛變量x3,x4,%5,x6，標(biāo)準(zhǔn)化模型為2x-i5x2x460s.tx.X2X5183X|X2X644oX(,X2,X3, X4,X5,X6建立初始單純形表并作基的變換如下,xX1X2X3X4X5X6bthitac210000X3001100010X402601006060/2=30X501100101818/1=18X603100014444/3最?。j0000000Zj-cj-2-10000先找負(fù)的絕對(duì)值最大的定入X300110001010X40013/3010-2/392/392/13X5002/30

20、01-1/310/35最小！定出X1211/30001/344/344zj22/30002/388/3下一行+cjZj-cj0-1/30002/3先找負(fù)的絕對(duì)值最大的定入X300010-3/21/25X400001-13/23/29X2101003/2-1/25X121000-1/21/213zj21001/21/231下一行+cjZj-cj00001/21/2最優(yōu)性判別，得知最優(yōu)解從表中得答案， maxz 31;x 13,x2 5，松弛變量x3 5,x4 9,x5 x6 0 。max z 4x13x26x38（ 142）、用單純形法計(jì)算s.t3x1 x22x1 3x2Xi,X2,X33X33

21、x303040(答案：maxz 70; x10,x210, X320/3)maxz4x1詳解：引進(jìn)松弛變量 x4,x5，標(biāo)準(zhǔn)化模型為3X|s.t 2xX23x23x23x33x36x3X4Xi,X2,X3,X4,X530X5400建立初始單純形表并作基的變換如下,XX1X2X3X4X5bthitac43600X40313103030/3=10,最小出基X50223014040/310zj000000Zj-cj-4-3-600先找負(fù)的絕對(duì)值最大的定入X3611/311/301030X50-110-111010,最小出基zj6262060下一行+cjZj-cj2-1020先找負(fù)的絕對(duì)值最大的定入X

22、364/3012/3-1/320/3X23-110-1110zj5361170下一行+cjZj-cj10011最優(yōu)性判別，得知最優(yōu)解從表中得答案， maxz 70“0,x210, x320/3minz2x1x2 5x3 x4X1X425X1X2x3 x420s.t4x16X3522x23x3 2x430X1,X2, X30,x4無(wú)非負(fù)要求9 (143)、現(xiàn)有單純形法問(wèn)題(1)化為標(biāo)準(zhǔn)型；(2)列出初始單純型表 (答案:max( z)X40 x5 MX6 0 x7 MX8 0 x9 0 為0 MX11X1x4x4X525X1X2X3X4X4X620st你6X3X7X 52X23X32x42x4X

23、302X23X32x42x4XI0X11 22xi5x3 X4X2X4Xi,X2,X3,X4,X4,X5,X6,X7,X3,X9,Xio,XiiXX1X2X3X41X42X5X6X7X8X9X10X11bc-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)max z 60x1 50x2X

24、 2x24010 ( 1.6.1.1 )、求線性規(guī)劃2 x26 的對(duì)偶問(wèn)題(答案s.t為 X225MX 0min w 40y1 6 y2 25y3y1 2 y2 y3 60s.t. 2 y1 y2y3 50y1,y2, y3 0max z 24x1 28x211 ( 1.6.1.2 )、4x1 6 x2求 線 性 規(guī) 劃x1 9s.t. 1x2 7x1, x2 048的對(duì)偶問(wèn)題（答案min w 48y1 9 y2 7y34y1y224）s.t.6 y1y328min z 2 x1x2 6 x3x43x1 x4 25x1 x2x3x412 ( 1.6.1.3)、 求 線 性 規(guī) 劃 1234s.

25、t. 4 x16 x3520的對(duì)偶問(wèn)題（答案：2 2x2 3x3 2 x430x1, x2, x30,x4無(wú)非負(fù)要求min z2x1 x26x3x43x1x4 25x1x2x3x420s.t.4x16x352x23x32x422 x2 3x32x4303 y1y24y32y2 2 y42y51繼而得 2 4）s.ty26 y33y43y56y1y22y42 y511/-/- 冷 1 1 :、maxw25y1 20y2 5y3 2y4 30y5yi, 丫3”4,丫50, y2無(wú)非負(fù)要求x,x2, x3 0,x4無(wú)非負(fù)要求maxw 4 y12 y2x12x24y12y213（ 1.6.1.4）、求

26、線性規(guī)劃1的對(duì)偶問(wèn)題（答案：s.t.2x1x22s.t.2y1y2x1, x20y1, y20min f6x1 4x26)4min f5x1 3x214（ 1.6.1.5）、求線性規(guī)劃2x1 3x2 6的對(duì)偶問(wèn)題（答案：s.t. 3x1 6x24x1, x20maxw 6y1 4y22 y1 y2 5 )s.t. 3y1 6 y2 3y1, y20目2、科30,%無(wú)非負(fù)要求minz 20x110x2偶單純法解5x1x26+15 (1.6.2 )、用對(duì)型（答案：S.t2x12x28X,x：,0maxz45;%1,X231)22min z 20x110X2max：(z)20x11C)X2詳解：5x

27、26轉(zhuǎn)化為5X26引入松弛變量 x3, x4，得到st2x1 2x28s.t2x12x28x1, x?0X1,X20max(z)20x1 10x20 x30 X45x. x2 x36標(biāo)準(zhǔn)化模型為123s.t 2x1 2x2 x48X,X2,X3,X4建立初始對(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-10

28、05下行加cjZj-cj10005-40thita|-10/4|-5/0.5|再找比值的絕對(duì)值最小的定入X1-2010-1/41/81/2已經(jīng)全為正了，說(shuō)明基解已可行X2-10011/4-5/83.5zj-20-105/23.75下行加cjZj-cj005/23.75-45依判據(jù)，得最優(yōu)解從表中看出max z 45;為,x2 3 ， mi nz 452 2maxz 2x1 x2%3 2x2 2%151、16（ 1.6.3）、現(xiàn)有線性規(guī)劃問(wèn)題：x1 x2 x33，用單純形法求最優(yōu)解和資源stx1 x2 x34花必公30資源2、資源3的影子價(jià)格。（答案：最優(yōu)解x 21,24,0,0,7 T，資源1

29、、資源2、資源3的影子價(jià)格1,1,0)maxz2x1X2X3maxz2x1X2X33為2x?2x3153%2x22x3 15詳解：x1X2x33 轉(zhuǎn)化為丄XX2x33，引入松弛變量x4, x5, x(5，s.ts.tX1X2X3 4X1X2X34X1,X2,X30X1,X2,X30maxz 2x x2 x33% 2x2 2x3 x415得到標(biāo)準(zhǔn)化模型為x, x2 x3疋 3stx, X2 X3 x64X,X2,X3,x4,X5,x建立初始單純形表并作基的變換如下,XX1X2X3X4X5X6bthitac2-11000X403-221001515/3=5X50-1110103X601-11001

30、4P4/仁4最小！定出基變量zj000000Zj-cj-21-1000先找負(fù)的絕對(duì)值最大的定入基變量X4001-110-333/仁3最?。《ǔ龌兞縓500020117X121-110014zj2-22002下行加cj定入基變量Zj-cj0-110028先找負(fù)的絕對(duì)值最大X2-101-110-33X500020117P 7/仁7最??！定出基變量X1210010-27zj2-1110-1下行加cj定入基變量Zj-cj00010-111先找負(fù)的絕對(duì)值最大X2-101513024X600020117X1210412021zj2-13110下行加cjZj-cj00211018判定最優(yōu)解從表中看出x 2

31、1,24,0,0,7 T,max z 18，由表的最后一行，可得資源1、資源2、資源3的影子價(jià)格分別為1,1,0。min z 2x-i 4x2 6x32x1 X2 X31017（ 1.6.4）、現(xiàn)有線性規(guī)劃問(wèn)題：x1 2x2 2x3 12，（ 1）用單純形法求解該問(wèn)題;st2x2 x34X1,X2,X30（2）用對(duì)偶單純形法求解該問(wèn)題（答案:x 6,2,0 T , z 20min( z)2X| 4x2 6x3 Mx5Mx80 x4 x6 x72x1 x2 x3 x5 x410(1)x1 2x2 2x3 xs 12s.t_2x2 X3 x X74X1,X2,X3,x5,x8,X4,X6,X70用

32、單純性法迭代;min( z)2x1 4x2 6x3 0 x4 x5 x62x1 x2 x3 x410(2)x1 2x2 2x3 x 12s.t2x2 X3 X64用對(duì)偶單純性法迭代）Xi,X2, X3,X4, X5, X60min z 20x115x22x1 x2518( 1.6.5)、求解線性規(guī)劃3x1 2X2 3 (答案：x 2,1,7,0,0T,z 55)s.t為 x23NX 0minz 20x1 15x2max( z)2x1 x2 52x13x120為 15x253x, 2x23轉(zhuǎn)化為3詳解：stx1 x2x1,x20max( z)s.tX22x233，引入松弛變量x3, x4, x5

33、，得X1 x2x1,x2020x1 15x2 0x3 0& 0x52xi3x1到標(biāo)準(zhǔn)化模型為s.tX2 X3 5 2x2 x43X1 X? X53X1,X2,X3,X4,X50建立初始對(duì)偶單純形表并作基的變換如下，XX1X2X3X4X5bc-20-15000X30-2-1100-5先取負(fù)的最大的bX40-320103值所在，確定換出X50-1-1001-3zj00000下行加cjZj-cj20150000thita再找比值的絕對(duì)值|20/ （-2） |=10，|15/ （-1）|=15最小、的定入XX1X2X3X4X5bc-20-15000X1011/2-1/2005/2先取負(fù)的最大 的b值所

34、在，確 定換出X4007/2-3/21021/2X500-1/2-1/201-1/2zj-20-101000下行加cjZj-cj051000-50thita再找比值的絕對(duì)值|5/ （-1/2）|=10，|10/ （-1）|=20最小的定入XX1X2X3X4X5bc-20-15000X1010-1012全正，基解可行X4000-5177X200110-21zj-20-155010下行加cjZj-cj005010-55判定最優(yōu)從表中看出最優(yōu)解為x2,1,7,0qT,z 55mi nz 10捲 8冷 7x319（ 166）、用對(duì)偶單純型法解2為s.t x1X2X24（答案：X1,2,0 T,z26)

35、X33XX2，X30mi nz 10為 8x27X3maxz10X-!8x2 7x32% x242為x24詳解：12轉(zhuǎn)化為引入松弛變量X4, X5 ,s.t x1 x2 x33stX1X2X33為必兀 0X1，X2，X30max( z)10為8x27X30X40x5t2x1X2X44得到標(biāo)準(zhǔn)化模型為10st為X2X3X53XpX2，X3，X4，X5建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3X4X5bc-10-8-700X30-2-1010-4先取負(fù)的最大的b值所在，確定換出X40-1-1-101-3cj -Zj-10-8-7000thita再找比值的-10/ （-2） =5，-8/（

36、-1） =8最小的定入X1-1011/20-1/202先取負(fù)的最大的bX400-1/2-1-1/21-1值所在，確定換出cj -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ù)非正，確認(rèn)最優(yōu)從而得最優(yōu)解x 1,2,0 T,z 26min w 3為 3x220 （ 167）、用對(duì)偶單純型法解4,2,4 T ,w 16)2為 3x218x1 x2 2(答案：xst 12% 3x210x1, x20max( z)3xi

37、 3x2 0x3 0x4 OX5min w3x13x2max( w)3x1 3x223x182x13x2 18詳解：x1X22轉(zhuǎn)化為為x22，引入松弛變量x3, x4, x5，得到s.ts.tx13x210x13x210x1, x，002x13x2X318標(biāo)準(zhǔn)化模型為x1X2X42s.tX13x2X510N,X2, X3 , X4, X50建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3X4X5bc-3-3000X302310018先取負(fù)的最大的b值所在，確定換出X40-11010-2X50-1-3001-10cj -Zj-3-30000thita再找比值的-3/（-1）=3，-3/（ -

38、3）=1最小的定入X30101018先取負(fù)的最大的b值所在，確定換出X40r-4/30011/3-16/3X2-31/3100-1/310/3cj -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)解為 x 4,2,4 T ,w 16二、第4章1 （421）、某市舉行1990年世界杯6強(qiáng)（A、B、C、D、E、F）聯(lián)賽。競(jìng)賽采取循環(huán)制， 每天

39、安排三場(chǎng)比賽。同一個(gè)隊(duì)一天之內(nèi)只安排一場(chǎng)，要求競(jìng)賽在5天之內(nèi)賽完，請(qǐng)用圖的方法表示6個(gè)隊(duì)之間的聯(lián)賽，和競(jìng)賽日程安排，并指出每個(gè)圖是什么類型的圖，各日程安排圖G與聯(lián)賽圖是什么關(guān)系。（答案:A*（ BFE、4DE*D，G疋完王圖，G-i, G2, G3, G4, G5為非連通G4G5圖，且都是G的子圖）V101011V2101012（ 4.2.2 ）、寫 V301011出右圖的關(guān)聯(lián)矩陣和相關(guān)矩陣。V410100V511100V4e3V3（答案：列都對(duì)應(yīng)頂點(diǎn),11000e01100V101011e300110V210101關(guān)聯(lián)矩陣為e410010，相關(guān)矩陣為v301011 )e501001V4101

40、00e600101V511100e7100013 （423）、有甲乙丙丁戊己 6名運(yùn)動(dòng)員報(bào)名參加 ABCDEF6個(gè)項(xiàng)目的比賽。下表中打“V” 的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目（表 4-1）。問(wèn)：6個(gè)項(xiàng)目比賽順序如何安排，做到每名運(yùn) 動(dòng)員不連續(xù)參加兩項(xiàng)比賽？（答案：，ABCDEF甲VV乙VVV丙VV丁VV戊VV己VV有人同時(shí)參加則連線，方案一 ACBFED，方案二AFBCDE，一條任意兩點(diǎn)不相關(guān)序列）4 （424）、出席某處國(guó)際學(xué)術(shù)報(bào)告會(huì)的6個(gè)成員ABCDEF被分在一組。他們的情況是：A會(huì)講漢語(yǔ)、法語(yǔ)和日語(yǔ)；B會(huì)講德語(yǔ)、俄語(yǔ)和日語(yǔ)； C會(huì)講英語(yǔ)、法語(yǔ)；D會(huì)講漢語(yǔ)和西班牙語(yǔ)；E會(huì)講英語(yǔ)和德語(yǔ)；F會(huì)講

41、俄語(yǔ)和西班牙語(yǔ)。怎么把他們安排在一張圓桌旁坐下，使 得每個(gè)人能和他兩旁的人交談？（答案：Ac 日（B找一條漢密頓回路 ACEBFDA ）5（ 425）、圖G=（ V，E）是連通圖，且 為G的割集。（答案：都用反證法。充分性： 設(shè)）。則G-e必連通，則 G-e中必存在生成樹 導(dǎo)致矛盾。必要性：設(shè) e不為G的割集（反設(shè)）。若G有生成樹T，則T+e包含回路。刪去 e后連通，即與e屬于每棵生成樹矛盾，反設(shè)不成立。）6（ 426）、已知圖得結(jié)點(diǎn)集 V=a,b,c,d，以及圖G和圖D的邊集合分別為 E（G）=（a,a）,（a,b）,（b,c）,（a,c）; E（D）= ,。試作圖 G 和圖 D，D是簡(jiǎn)單圖

42、還是多重圖。E。證明：e屬于每一棵生成樹的充要條件是ee屬于每一棵生成樹，若 e不為G的割集（反T，因?yàn)門也是G的生成樹，但T不包含e，寫出G、圖dG（答案：在圖 G 中 deg(a) 4,deg(b)deg(c)2,deg(d) 0 ;在圖 D 中 deg(a)3,deg(b) 2,deg(c) 4,deg(d) 1 ; D是簡(jiǎn)deg (c)其 中 deg (a) 2,deg (a)1,deg (b)0,deg (b)2,deg (c)3，1,deg (d) 0,deg (d)1,圖 G 是多重圖。)V612 V4101210171619.57（ 4.3.1）、用破圈法或避圈法求右圖的最小生成樹。數(shù)字為該邊的權(quán)值。（答案：權(quán)值 9+7+8+9.5+10=43.5 ）8 （432）、求下圖的最小生成樹，畫出該最小生成樹，并給出該最小生成樹的權(quán)值。旁邊的V3（答案：，權(quán)值 3+1 + 1+3+4+2+5+5=24 ）9（433）、某銀行打算與其分行之間建立計(jì)算機(jī)網(wǎng)絡(luò)，用電話線作為通訊聯(lián)網(wǎng)手段，已知主 行與各分行之間的距離如下表。試用矩陣法求其聯(lián)網(wǎng)的最短線路。項(xiàng)目主行