2011年管理運(yùn)籌學(xué)自考題和答案.doc

管理運(yùn)籌學(xué)(課程代碼07296)第一大題：?jiǎn)雾?xiàng)選擇題1、在轉(zhuǎn)化標(biāo)準(zhǔn)式的過程中對(duì)于的約束條件需要加入（ A）使變成等于的約束條件 A.松弛變量 B.多余變量 C.自由變量 D.非基變量2、在利用單純性法求目標(biāo)函數(shù)最大值時(shí)判斷最優(yōu)解的方法是（D ） A.檢驗(yàn)數(shù)都小于零 B.檢驗(yàn)數(shù)都大于零 C.檢驗(yàn)數(shù)都等于零 D.檢驗(yàn)數(shù)都小于或等于零3、使目標(biāo)值達(dá)到最優(yōu)的可行解叫做（D ） A.基本解 B.可行解 C.多重解 D.最優(yōu)解4、如果線性問題有多重最優(yōu)解則表達(dá)式為 (A ) A.X=X1+(1)X2 (01) B.X= X1+(1)X2 C.X= X1+(1)X2 (01) D.X=X1+X2 (01)5、某人要從上海乘飛機(jī)到奧地利首都維也納，他希望選擇一條航線，經(jīng)過轉(zhuǎn)機(jī)，使他在空中飛行的時(shí)間盡可能短。該問題可轉(zhuǎn)化為（A） A.最短路線問題求解 B.最大流量問題求解 C.最小枝杈樹問題求解 D.樹的生成問題求解6、在解運(yùn)輸問題時(shí)，若已求得各個(gè)空格的改進(jìn)路線和改進(jìn)指數(shù)，則選擇調(diào)整格的原則是（D ） A.在所有空格中，挑選絕對(duì)值最大的正改進(jìn)指數(shù)所在的空格作為調(diào)整格 B.在所有空格中，挑選絕對(duì)值最小的正改進(jìn)指數(shù)所在的空格作為調(diào)整格 C.在所有空格中，挑選絕對(duì)值最小的負(fù)改進(jìn)指數(shù)所在的空格作為調(diào)整格 D.在所有空格中，挑選絕對(duì)值最小的負(fù)改進(jìn)指數(shù)所在的空格作為調(diào)整格7、考慮某運(yùn)輸問題，設(shè)其總需求量為Q，總供應(yīng)量為G，且QG。欲將其化為供需平衡的運(yùn)輸問題，則應(yīng)（D ） A.使諸供應(yīng)點(diǎn)的供應(yīng)總量減少G-Q B.使諸需求點(diǎn)的需求總量增加G-Q C.虛設(shè)一個(gè)需求量為G-Q的需求點(diǎn)，且任一供應(yīng)點(diǎn)到該虛設(shè)需求點(diǎn)的單位運(yùn)費(fèi)為充分大 D.虛設(shè)一個(gè)需求量為G-Q的需求點(diǎn)，且任一供應(yīng)點(diǎn)到該虛設(shè)需求點(diǎn)的單位運(yùn)費(fèi)為08、關(guān)于線性規(guī)劃模型的可行解區(qū)，敘述正確的為（C ） A.可行解區(qū)必有界 B.可行解區(qū)必然包括原點(diǎn) C.可行解區(qū)必是凸的 D.可行解區(qū)內(nèi)必有無窮多個(gè)點(diǎn)9、關(guān)于線性規(guī)劃問題，敘述正確的為（D ） A.其可行解一定存在 B.其最優(yōu)解一定存在 C.其可行解必是最優(yōu)解 D.其最優(yōu)解若存在，在可行解中必有最優(yōu)解10、在運(yùn)輸問題中如果總需求量小于總供應(yīng)量，則求解時(shí)應(yīng)（D ） A.虛設(shè)一些供應(yīng)量 B.虛設(shè)一個(gè)供應(yīng)點(diǎn) C.根據(jù)需求短缺量，虛設(shè)多個(gè)需求點(diǎn) D.虛設(shè)一個(gè)需求點(diǎn)11、關(guān)于運(yùn)輸問題的說法中錯(cuò)誤的是（C） A.最優(yōu)運(yùn)輸方案未必唯一 B.必有最優(yōu)運(yùn)輸方案 C.運(yùn)輸方案的任何調(diào)整必會(huì)引起總運(yùn)費(fèi)的下降 D.運(yùn)輸問題是線性規(guī)劃問題12、求從起點(diǎn)到終點(diǎn)的最大流量時(shí)，若已找到三條完全不同的線路，它們的流量分別為12，13，15，則表述最準(zhǔn)確的是最大流量（A） A.小于等于40 B.至少為12 C.至少為40 D.至少為1513、考慮某運(yùn)輸問題，其需求量和供應(yīng)量相等，且供應(yīng)點(diǎn)的個(gè)數(shù)為m，需求點(diǎn)的個(gè)數(shù)是n。若以西北角法求得其初始運(yùn)輸方案，則該方案中數(shù)字格的數(shù)目應(yīng)為（B ） A.（m+n）個(gè) B.（m+n-1）個(gè) C.（m-n）個(gè) D.（m-n+1）個(gè)14、某個(gè)城市的電話線網(wǎng)鋪設(shè)問題應(yīng)采用的方法是（A ） A.最短路線法 B.最大流量法 C.普賴姆法 D.西北角法15、 四個(gè)球隊(duì)進(jìn)行循環(huán)賽，其比賽結(jié)果可以表示成一個(gè)（A ） A.有向圖 B.無向圖 C.樹 D.不連通圖16、 在下面的數(shù)學(xué)模型中，屬于線性規(guī)劃模型的為（A ） A. B. C. D.17、n個(gè)點(diǎn)的不連通圖，其邊數(shù)（A ） A.必然少于n1 B.必然等于n1 C.必然多于n1 D.可能多于n118、若線性規(guī)劃問題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到，那么該線性規(guī)劃問題最優(yōu)解為（C ） A.兩個(gè) B.零個(gè) C.無窮多個(gè) D.有限多個(gè)19、求運(yùn)輸問題的解就是求滿足要求的（C ） A.各供應(yīng)點(diǎn)到各需求點(diǎn)的運(yùn)費(fèi) B.總運(yùn)費(fèi) C.各供應(yīng)點(diǎn)到各需求點(diǎn)的運(yùn)量 D.總運(yùn)量20、列敘述正確的是(A ) A.線性規(guī)劃問題，若有最優(yōu)解，則必是一個(gè)基變量組的可行基解 B.線性規(guī)劃問題一定有可行基解 C.線性規(guī)劃問題的最優(yōu)解只能在極點(diǎn)上達(dá)到 D.單純形法求解線性規(guī)劃問題時(shí)每換基迭代一次必使目標(biāo)函數(shù)值下降一次21、對(duì)于供需平衡和供需不平衡的運(yùn)輸問題，其結(jié)構(gòu)模型是（B ） A.相同的 B.不同的 C.與線性規(guī)劃模型一樣的 D.無法求解的22、線性規(guī)劃標(biāo)準(zhǔn)模型有特點(diǎn)（D） A.所有函數(shù)都是線性函數(shù) B.目標(biāo)求最小 C.有等式或不等式約束 D.變量非負(fù)第二大題：多項(xiàng)選擇題1、最小生成樹問題的算法 (CD ) A.單純刑法 B.位勢(shì)法 C.加邊法 D.破圈法2、運(yùn)輸問題的基本可行解有特點(diǎn)（BD ）。 A.產(chǎn)銷平衡 B.不含閉回路 C.有m+n個(gè)位勢(shì) D.有mn1個(gè)基變量3、關(guān)于線性規(guī)劃問題，敘述正確的為（C D ） A.其可行解一定存在 B.其最優(yōu)解一定存在 C.其基可行解必是最優(yōu)解 D.其最優(yōu)解若存在，在可行解中必有最優(yōu)解4、個(gè)線性規(guī)劃問題（P）與它的對(duì)偶問題（D）有關(guān)系（BCD ） A.（P）求最大則（D）求最小 B.（P）、（D）均有可行解則都有最優(yōu)解 C.（P）的約束均為等式，則（D）的所有變量均無非負(fù)限制 D.若（D）是（P）的對(duì)偶問題，則（P）是（D）的對(duì)偶問題5、對(duì)于總運(yùn)輸費(fèi)用最小的運(yùn)輸問題，若已得最優(yōu)運(yùn)輸方案，則其中所有空格的改進(jìn)指數(shù)必（AC）D.小于0 A.大于或等于0 B.小于或等于0 C.大于0 D.小于06、下面命題不正確的是（AC ）個(gè) A.線性規(guī)劃的最優(yōu)解是基本可行解 B.基本可行解一定是基本解 C.線性規(guī)劃一定有可行解 D.線性規(guī)劃的最優(yōu)值至多有一個(gè)7、含有兩個(gè)變量的線性規(guī)劃問題若有可行解，則可行域是 （BC ） A.全平面 B.多平面 C.凸多平面 D.凹多平面8、線性規(guī)劃的標(biāo)準(zhǔn)型有特點(diǎn)（BD ） A.右端項(xiàng)非零 B.目標(biāo)求最大 C.有等式或不等式約束 D.變量均非負(fù)第三大題：判斷改錯(cuò)題1、圖解法提供了求解線性規(guī)劃問題的通用方法。(錯(cuò) )2、用單純形法求解一般線性規(guī)劃時(shí)，當(dāng)目標(biāo)函數(shù)求最大值時(shí)，若所有的檢驗(yàn)數(shù)Cj-Zj0，則問題達(dá)到最優(yōu)。(錯(cuò) )3、滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。 (錯(cuò) )4、在線性規(guī)劃問題的求解過程中，基變量和非基變量的個(gè)數(shù)是固定的。(對(duì) )5、對(duì)偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。(錯(cuò) )6、指派問題一定有最優(yōu)解。(錯(cuò) )7、網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條權(quán)和最小的路線。（ 對(duì) ）第四大題：簡(jiǎn)答題1、（1）線性規(guī)劃問題的基本特征？1、每個(gè)模型都有若干個(gè)決策變量（x1，x2，x3，xn），其中n為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。2、目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問題可以是最大化（max）或最小化（min），二者統(tǒng)稱為最優(yōu)化（opt）。3、約束條件也是決策變量的線性函數(shù)。2、線性規(guī)劃問題模型包括那些基本假設(shè)？1) 若線性規(guī)劃中存在可行解，則其可行域是凸集；2) 若線性規(guī)劃系數(shù)方程矩陣A的秩為m時(shí)，則任一基可行解的非零分量的個(gè)數(shù)最多只有m個(gè)；3) 若線性規(guī)劃有可行解，則一定有基可行解；4) 線性規(guī)劃問題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)；5) 若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最優(yōu)解一定可以在其可行域的某個(gè)頂點(diǎn)得到。3、什么是連通圖？在圖論中，連通圖基于連通的概念。在一個(gè)無向圖 G 中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑相連(當(dāng)然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點(diǎn)都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質(zhì)。第五大題：名詞解釋題1、 基可行解基可行解是滿足非負(fù)條件的基本解，或者說既是基本解又是可行解的解。2、 影子價(jià)格用線性規(guī)劃方法求解資源最優(yōu)利用時(shí)，即在解決如何使有限資源的總產(chǎn)出最大的過程中，得出相應(yīng)的極小值，其解就是對(duì)偶解，極小值作為對(duì)資源的經(jīng)濟(jì)評(píng)價(jià)，表現(xiàn)為影子價(jià)格。3、 中國(guó)郵政問題郵遞員為了遞送郵件，每天都要到相同的地方送信，走相同的路線，其中必有一條最短的路線，如果能找到這條路，每天都按著這條路線走，必然可以減少工作量，提高效率。顯然，這個(gè)郵遞員從郵局出發(fā)，走遍每條大街小巷，而且只走過一次，最后回到郵局，這是最短的路線。歐拉定理有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)的圖形，而中間每經(jīng)過一點(diǎn)都應(yīng)和偶數(shù)條線相連。歐拉把與偶數(shù)條線相連的點(diǎn)稱為偶點(diǎn)，與奇數(shù)條線相連的點(diǎn)稱為奇點(diǎn)。如果這個(gè)圖形是封閉的，那么起點(diǎn)（也就是終點(diǎn)）一定是偶點(diǎn)。而不論什么時(shí)候，中間點(diǎn)都是偶點(diǎn)。4、 圈在無向圖中，如果一條鏈的起始與終點(diǎn)相同時(shí)，稱該鏈為圈。5、 網(wǎng)絡(luò)上的流：所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個(gè)連通的賦權(quán)有向圖 D （V、E、C） ， 其中V 是該圖的頂點(diǎn)集，E是有向邊(即弧)集，C是弧上的容量。此外頂點(diǎn)集中包括一個(gè)起點(diǎn)和一個(gè)終點(diǎn)。網(wǎng)絡(luò)上的流就是由起點(diǎn)流向終點(diǎn)的可行流，這是定義在網(wǎng)絡(luò)上的非負(fù)函數(shù)，它一方面受到容量的限制，另一方面除去起點(diǎn)和終點(diǎn)以外，在所有中途點(diǎn)要求保持流入量和流出量是平衡的。第六大題：計(jì)算題1、下圖為動(dòng)態(tài)規(guī)劃的一個(gè)圖示模型，邊上的數(shù)字為兩點(diǎn)間的距離，請(qǐng)用標(biāo)號(hào)法求出S至F點(diǎn)的最短路徑及最短路長(zhǎng)。解答如下圖所示：最短路徑為S-A1-B1-C1-F 最短路長(zhǎng)為322、 求解下例問題的最優(yōu)解。圖解法根據(jù)上述約束條件畫出問題的可行域：3X1+5X2=15 X2BA6X1+2X2=0,i=1,2,3,4由題可得，基礎(chǔ)可行解（0,0,0，100，120）建立初始單