【正文】 法求解整數(shù)規(guī)劃時，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。D．用割平面法求解整數(shù)規(guī)劃問題時，必須首先將原問題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。2．在求解整數(shù)規(guī)劃問題時，可能出現(xiàn)的是ABC。A．唯一最優(yōu)解B．無可行解 C．多重最佳解D．無窮多個最優(yōu)解3．關(guān)于分配問題的下列說法正確的是_ ABD。A．分配問題是一個高度退化的運輸問題B．可以用表上作業(yè)法求解分配問題 C．從分配問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案D．匈牙利法所能求解的分配問題，要求規(guī)定一個人只能完成一件工作，同時一件工作也只給一個人做。（ CDE ）A 線性規(guī)劃 B 非線性規(guī)劃 C 純整數(shù)規(guī)劃 D 混合整數(shù)規(guī)劃 E 0—1規(guī)劃（ ABCDE ）A 求其松弛問題 B 在其松弛問題中增加一個約束方程 C 應(yīng)用單形或圖解法D 割去部分非整數(shù)解 E多次切割三、名詞純整數(shù)規(guī)劃：如果要求所有的決策變量都取整數(shù)，這樣的問題成為純整數(shù)規(guī)劃問題。0—1規(guī)劃問題：在線性規(guī)劃問題中，如果要求所有的決策變量只能取0或1，這樣的問題稱為0—1規(guī)劃?；旌险麛?shù)規(guī)劃：在線性規(guī)劃問題中，如果要求部分決策變量取整數(shù)，則稱該問題為混合整數(shù)規(guī)劃。四、用分枝定界法求解下列整數(shù)規(guī)劃問題：(提示:可采用圖解法) maxZ=40x1+90x2 五、用割平面法求解 六、下列整數(shù)規(guī)劃問題 說明能否用先求解相應(yīng)的線性規(guī)劃問題然后四舍五入的辦法來求得該整數(shù)規(guī)劃的一個可行解。答：不考慮整數(shù)約束，求解相應(yīng)線性規(guī)劃得最優(yōu)解為 x1=10/3，x2=x3=0，用四舍五人法時，令x1=3，x2=x3=0，其中第2個約束無法滿足，故不可行。七、若某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油。使總的鉆探費用為最小。若10個井位的代號為S1,S2．…，S10相應(yīng)的鉆探費用為C1 ,C2 ,… C10，并且井位選擇要滿足下列限制條件： (1)在s1，s2，S4中至多只能選擇兩個； (2)在S5，s6中至少選擇一個；(3)在s3，s6，S7，S8中至少選擇兩個； 試建立這個問題的整數(shù)規(guī)劃模型八、有四項工作要甲、乙、丙、丁四個人去完成．每項工作只允許一人去完成。每個人只完成其中一項工作，已知每個人完成各項工作的時間如下表。問應(yīng)指派每個人完成哪項工作，使總的消耗時間最少?工作 人 I Ⅱ Ⅲ Ⅳ甲乙丙丁151961918237212l22162324181917第八章 圖與網(wǎng)絡(luò)分析一、填空題1．圖的最基本要素是點、點與點之間構(gòu)成的邊 2．在圖論中，通常用點表示，用邊或有向邊表示研究對象，以及研究對象之間具有特定關(guān)系。3．在圖論中，通常用點表示研究對象，用邊或有向邊表示研究對象之間具有某種特定的關(guān)系。4．在圖論中，圖是反映研究對象_之間_特定關(guān)系的一種工具。5．任一樹中的邊數(shù)必定是它的點數(shù)減1。6．最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點，而且連接的總長度最小。7．最小樹的算法關(guān)鍵是把最近的未接_結(jié)點連接到那些已接結(jié)點上去。8．求最短路問題的計算方法是從0≤fij≤cij開始逐步推算的，在推算過程中需要不斷標(biāo)記平衡和最短路線。二、單選題關(guān)于圖論中圖的概念，以下敘述(B)正確。A圖中的有向邊表示研究對象，結(jié)點表示銜接關(guān)系。 B圖中的點表示研究對象，邊表示點與點之間的關(guān)系。C圖中任意兩點之間必有邊。 D圖的邊數(shù)必定等于點數(shù)減1。2．關(guān)于樹的概念，以下敘述(B)正確。A樹中的點數(shù)等于邊數(shù)減1 B連通無圈的圖必定是樹 C含n個點的樹是唯一的 D任一樹中，去掉一條邊仍為樹。3．一個連通圖中的最小樹(B)，其權(quán)(A)。A是唯一確定的 B可能不唯一 C可能不存在 D一定有多個。4．關(guān)于最大流量問題，以下敘述(D)正確。A一個容量網(wǎng)絡(luò)的最大流是唯一確定的B達(dá)到最大流的方案是唯一的C當(dāng)用標(biāo)號法求最大流時，可能得到不同的最大流方案D當(dāng)最大流方案不唯一時，得到的最大流量亦可能不相同。5．圖論中的圖，以下敘述(C)不正確。A．圖論中點表示研究對象，邊或有向邊表示研究對象之間的特定關(guān)系。B．圖論中的圖，用點與點的相互位置，邊的長短曲直來表示研究對象的相互關(guān)系。C．圖論中的邊表示研究對象，點表示研究對象之間的特定關(guān)系。 D．圖論中的圖，可以改變點與點的相互位置。只要不改變點與點的連接關(guān)系。6．關(guān)于最小樹，以下敘述(B)正確。A．最小樹是一個網(wǎng)絡(luò)中連通所有點而邊數(shù)最少的圖B．最小樹是一個網(wǎng)絡(luò)中連通所有的點，而權(quán)數(shù)最少的圖C．一個網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹內(nèi)D．一個網(wǎng)絡(luò)的最小樹一般是不唯一的。7．關(guān)于可行流，以下敘述(A)不正確。A．可行流的流量大于零而小于容量限制條件B．在網(wǎng)絡(luò)的任一中間點，可行流滿足流人量=流出量。C．各條有向邊上的流量均為零的流是一個可行流D．可行流的流量小于容量限制條件而大于或等于零。三、多選題1．關(guān)于圖論中圖的概念，以下敘述(123)正確。(1)圖中的邊可以是有向邊，也可以是無向邊 (2)圖中的各條邊上可以標(biāo)注權(quán)。(3)結(jié)點數(shù)等于邊數(shù)的連通圖必含圈(4)結(jié)點數(shù)等于邊數(shù)的圖必連通。2．關(guān)于樹的概念，以下敘述(123)正確。1)樹中的邊數(shù)等于點數(shù)減1(2)樹中再添一條邊后必含圈。(3)樹中刪去一條邊后必不連通(4)樹中兩點之間的通路可能不唯一。3．從連通圖中生成樹，以下敘述(134)正確。(1)任一連通圖必有支撐樹 (2)任一連通圖生成的支撐樹必唯一(3)在支撐樹中再增加一條邊后必含圈(4)任一連通圖生成的各個支撐樹其邊數(shù)必相同4．在下圖中，(abcd)不是根據(jù)(a)生成的支撐樹。5．從賦權(quán)連通圖中生成最小樹，以下敘述(124)不正確。(1)任一連通圖生成的各個最小樹，其總長度必相等(2)任一連通圖生成的各個最小樹，其邊數(shù)必相等。(3)任一連通圖中具有最小權(quán)的邊必包含在生成的最小樹上。(4)最小樹中可能包括連通圖中的最大權(quán)邊。6．從起點到終點的最短路線，以下敘述(123)不正確。1)從起點出發(fā)的最小權(quán)有向邊必含在最短路線中。 (2)整個圖中權(quán)最小的有向邊必包含在最短路線中。(3)整個圖中權(quán)最大的有向邊可能含在最短路線中 (4)從起點到終點的最短路線是唯一的。7．關(guān)于帶收發(fā)點的容量網(wǎng)絡(luò)中從發(fā)點到收點的一條增廣路，以下敘述( 123)不正確。 (1)增廣路上的有向邊的方向必須是從發(fā)點指向收點的(2)增廣路上的有向邊，必須都是不飽和邊 (3)增廣路上不能有零流邊(4)增廣路上與發(fā)點到收點方向一致的有向邊不能是飽和邊，相反方向的有向邊不能是零流邊8．關(guān)于樹，以下敘述(ABCE)正確。A．樹是連通、無圈的圖B．任一樹，添加一條邊便含圈C．任一樹的邊數(shù)等于點數(shù)減1。D．任一樹的點數(shù)等于邊數(shù)減1E．任一樹，去掉_條邊便不連通。9．關(guān)于最短路，以下敘述(ACDE)不正確。A從起點出發(fā)到終點的最短路是唯一的。B．從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的。C．從起點出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點到終點的最短路上D．從起點出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點到終點的最短路上。 E．整個網(wǎng)絡(luò)的最大權(quán)邊的一定不包含在從起點到終點的最短路線上。10．關(guān)于增廣路，以下敘述(BC )正確。A．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向必一致。B．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向可不一致。C．增廣路上與發(fā)點到收點方向一致的邊必須是非飽和邊，方向相反的邊必須是流量大于零的邊。D．增廣路上與發(fā)點到收點方向一致的邊必須是流量小于容量的邊，方向相反的邊必須是流量等于零的邊。E．增廣路上與發(fā)點到收點方向一致的邊必須是流量為零的邊，方向相反的邊必須是流量大于零的邊。四、名詞解釋樹:在圖論中，具有連通和不含圈特點的圖稱為樹。2．權(quán)：在圖中，邊旁標(biāo)注的數(shù)字稱為權(quán)。3．網(wǎng)絡(luò)：在圖論中，給邊或有向邊賦了權(quán)的圖稱為網(wǎng)絡(luò)4．最大流問題：最大流問題是指在網(wǎng)絡(luò)圖中，在單位時間內(nèi)，從發(fā)點到收點的最大流量5．最大流問題中流量：最大流問題中流量是指單位時間的發(fā)點的流出量或收點的流入量。6．容量：最大流問題中，每條有向邊單位時間的最大通過能力稱為容量7．飽合邊：容量與流量相等的有向邊稱為飽合邊。8零流邊：流量為零的有向邊稱為零流邊：若樹T是無向圖G的生成樹，則稱T是G 的生成樹。.。10根：有向圖G中可以到達(dá)圖中任一頂點的頂點u稱為G的根。11枝：樹中的邊稱為枝。：具有相同端點的邊叫平行邊。13根樹：若有向圖G有根u，且它的基本圖是一棵樹，則稱G為以u為根的根樹。四、計算題 1．下圖是6個城市的交通圖，為將部分道路改造成高速公路，使各個城市均能通達(dá)，又要使高速公路的總長度最小，應(yīng)如何做?最小的總長度是多少? 2．對下面的兩個連通圖，試分別求出最小樹。 第1題中的交通圖，求城市A到D沿公路走的最短路的路長及路徑。 4．對下面兩圖，試分別求出從起點到終點的最短路線。 5．分別求出下面兩圖中從發(fā)點到收點的最大流。每條有向邊上的數(shù)字為該邊的容量限制。 6．下面網(wǎng)絡(luò)中，點①，②是油井，點⑥是原油脫水處理廠，點③、④、⑤是泵站，各管道的每小時最大通過能力(噸／小時)如有向邊上的標(biāo)注。求從油井①、②每小時能輸送到脫水處理廠的最大流量。 (提示：虛設(shè)一個發(fā)點S，令有向邊(S，1)，(S，2)的容量為∞)。 名詞十一章 需求：需求就是庫存的輸出。 存貯費：一般是指每存貯單位物資單位時間所需花費的費用。 缺貨損失費：一般指由于中斷供應(yīng)影響生產(chǎn)造成的損失賠償費。 訂貨批量Q：存貯系統(tǒng)根據(jù)需求，為補充某種物資的庫存而向供貨廠商一次訂貨或采購的數(shù)量。 訂貨間隔期T：兩次訂貨的時間間隔可訂貨合同中規(guī)定的兩次進(jìn)貨之間的時間間隔。 記賬間隔期R：指庫存記賬制度中的間隔記賬制所規(guī)定的時間。十二章 預(yù)測：是決策的基礎(chǔ)，它借助于經(jīng)濟(jì)學(xué)、概率論與數(shù)理統(tǒng)計、現(xiàn)代管理科學(xué)、系統(tǒng)論和計算機科學(xué)等所提供的理論及方法，通過適當(dāng)?shù)哪Ｐ图夹g(shù)，分析和預(yù)測研究對象的發(fā)展趨勢。十三章 決策：凡是根據(jù)預(yù)定目標(biāo)而采取某種行動方案所作出的選擇或決定就稱為決策。 單純選優(yōu)決策：是指根據(jù)已掌握的數(shù)據(jù)，不需再加工計算，或僅進(jìn)行方案指標(biāo)值的簡單計算，通過比較便可以直接選出最優(yōu)方案的決策方法。 模型選 優(yōu)決策：是在決策對象的客觀狀態(tài)完全確定的條件下，建立一定的符合實際經(jīng)濟(jì)狀況的數(shù)學(xué)模型，進(jìn)而通過對模型的求解來選擇最優(yōu)方案的方法。 非確定型決策：是一種在決策分析過程中，對決策方案付諸實施后可能遇到的客觀狀態(tài)，雖然能夠進(jìn)行估計，但卻無法確定每一種客觀狀態(tài)出現(xiàn)的概率的決策。 風(fēng)險型決策：是一種在分析過程中，對方案付諸實施后可能遇到的客觀狀態(tài)，不僅在決策分析時能夠加以估計，而且對每一種狀態(tài)出現(xiàn)的概率大小也有所掌握。 決策樹：就是對一個決策問題畫一張圖，用更容易了解的形式來表示有關(guān)信息。十四章 排隊論：排隊論所討論的是一個系統(tǒng)對一群體提供某種服務(wù)時該群體占用此服務(wù)系統(tǒng)時所呈現(xiàn)的狀態(tài)。 排隊規(guī)則：是描述顧客來到服務(wù)系統(tǒng)時，服務(wù)機構(gòu)是否充許，顧客是否愿意排隊，在排隊等待情形下服務(wù)的順序。 M/G/1排隊系統(tǒng)：是單服務(wù)臺系統(tǒng)，其顧客到達(dá)服從參數(shù)為λ的泊松分布，服務(wù)時間屬一般分布。隨機排隊模型：稱服務(wù)員個數(shù)為隨機變量的排隊系統(tǒng)為隨機排隊服務(wù)系統(tǒng)，相應(yīng)的模型為隨機排隊模