運(yùn)籌學(xué)模擬試題

運(yùn)籌學(xué)模擬試題填空題：（10分）運(yùn)輸問題中，求總利潤最大時(shí)，當(dāng)運(yùn)輸圖所有空格的檢驗(yàn)數(shù)，得最優(yōu)解；求總運(yùn)費(fèi)最小時(shí)，當(dāng)運(yùn)輸圖所有空格的檢驗(yàn)數(shù)，得最優(yōu)解。若線性規(guī)劃問題的最優(yōu)基為B，則問題的最優(yōu)值為，線性規(guī)劃的對(duì)偶問題的最優(yōu)解是，其中CB是基B所對(duì)應(yīng)的基變量在目標(biāo)函數(shù)中的系數(shù)向量，線性規(guī)劃問題是：運(yùn)輸問題中，當(dāng)總供應(yīng)量小于總需求量時(shí)，求解時(shí)需虛設(shè)一個(gè)點(diǎn)，此點(diǎn)的供應(yīng)量應(yīng)（總需求量與總供應(yīng)量之差）。結(jié)點(diǎn)的最遲完成時(shí)間又稱時(shí)間，若將最遲完成時(shí)間后延，將使整個(gè)網(wǎng)絡(luò)工期。樹是的連通圖，在樹上任意除去一條邊則該樹余下的圖。單項(xiàng)選擇題（10分）1、為了在各住宅之間安裝一條供暖管道，若要求所用材料最省，則應(yīng)采用（）。A．求最大流量法B.求最小支撐樹法C．求最短路線法D.樹的逐步生成法2、在網(wǎng)絡(luò)計(jì)劃中，進(jìn)行時(shí)間與成本優(yōu)化時(shí)，隨工期延長，簡介費(fèi)用將（）。A．減少B.增加C.不變D.不易估計(jì)3、圖論中，圖的基本要素是（）。A．點(diǎn)和帶方向的連線B.點(diǎn)和線C．點(diǎn)及點(diǎn)與點(diǎn)之間的連線D.點(diǎn)和一定要帶權(quán)的連線判斷題。（10分）線性規(guī)劃模型中增加一個(gè)約束條件，可行域的范圍一般將縮小，減少一個(gè)約束條件，可行域的范圍一般將擴(kuò)大。根據(jù)對(duì)偶問題的性質(zhì)，當(dāng)原問題為無界解時(shí)，其對(duì)偶問題無可行解，反之，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題具有無界解。運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。目標(biāo)規(guī)劃中，英同時(shí)包含系統(tǒng)約束（絕對(duì)約束）與目標(biāo)約束。用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值得下界。建立數(shù)學(xué)模型題：（8分）某飼養(yǎng)場飼養(yǎng)動(dòng)物出售，設(shè)每頭動(dòng)物每天至少需700克蛋白質(zhì)、30克礦物質(zhì)、100毫克維生素?，F(xiàn)有五種飼料可供選用，各種飼料每公斤營養(yǎng)成分含量及單價(jià)如下表所示：要求確定既滿足動(dòng)物生長的營養(yǎng)需要，又使費(fèi)用最省的選用飼料的方案。飼料成分蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價(jià)格（元/千克）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8（8分）已知線性規(guī)劃問題其對(duì)偶問題最優(yōu)解為，，試根據(jù)隊(duì)友理論求出原問題的最優(yōu)解。六、已知運(yùn)輸問題的供需關(guān)系表與單位運(yùn)價(jià)表如下所示，試用伏格爾法求出該問題的近似最優(yōu)解。（6分）產(chǎn)地銷地甲乙丙丁產(chǎn)量132765027523603254525銷量60402015用圖解法找出下列目標(biāo)規(guī)劃問題的滿意解（8分）請(qǐng)用匈牙利法求解該指派問題：（8分）已知效率矩陣如下：網(wǎng)絡(luò)最大流問題：（12分）下面為一容量網(wǎng)絡(luò)，各弧上的代表該弧的（可行流流量，容量）請(qǐng)用標(biāo)號(hào)法求出該網(wǎng)絡(luò)最大流。單項(xiàng)選擇題：(10分)1、若用圖解法求解線性規(guī)劃問題，則該問題所包含決策變量的數(shù)目應(yīng)為（）。A、二個(gè)B、五個(gè)以上C、三個(gè)以上D、無限制2、原問題的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶規(guī)劃的一個(gè)解，符號(hào)相反，對(duì)偶規(guī)劃的檢驗(yàn)數(shù)對(duì)應(yīng)于原規(guī)劃的一個(gè)解（符號(hào)性反），特別的，若原問題的最優(yōu)基為B，則對(duì)偶問題的最優(yōu)解為：（）A、Y*=-CBB-1B、Y*=CBB-1C、Y*=CN-CBB-1D、Y*=B-CBB-13、甲、乙、丙、丁四個(gè)球隊(duì)進(jìn)行比賽，任兩個(gè)隊(duì)都有一場比賽，且沒有和局，用來表示這四個(gè)隊(duì)比賽狀況的圖是（）。A、一棵樹B、沒有圈C、連通圖D、任兩點(diǎn)之間有一條帶有方向的線4、下列圖形中是一棵樹的為：()ABCD5、以下哪個(gè)性質(zhì)是對(duì)偶問題所不具有的（）A、對(duì)稱性B、互補(bǔ)松弛性C、弱對(duì)偶性D、可行性判斷題：（10分）1、如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)可行域邊界上的一個(gè)點(diǎn)。（）2、線性規(guī)劃問題每一個(gè)基解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)。（）3、正偏差變量應(yīng)取正值，負(fù)偏差變量應(yīng)取負(fù)值。（）4、線性規(guī)劃問題是目標(biāo)規(guī)劃問題的一種特殊形式。（）5、表上作業(yè)法實(shí)質(zhì)就是求解運(yùn)輸問題的單純形法。（）三、填空題：（10分）1、在圖論方法中，通常用表示人們研究的對(duì)象，用表示對(duì)象之間的某種聯(lián)系。2、是某線性規(guī)劃問題的一個(gè)決策變量，若它是該線性規(guī)劃問題某步單純形表中的一個(gè)基變量，則的檢驗(yàn)數(shù)為；若其檢驗(yàn)數(shù)不為零，則其為變量。3、利用單純形法求解線性規(guī)劃問題時(shí)，在最終單純形表中，若某一基變量為零，該基解稱為解；若某一非基變量檢驗(yàn)數(shù)為零，則該問題可能有解。4、關(guān)鍵路線是從起點(diǎn)到終點(diǎn)所有路中的最路，它的線路時(shí)差為。5、求支撐樹有法和法兩種方法。四、指派問題：（10分）現(xiàn)有五個(gè)人Ai(i=1,2,3,4,5)被分配去完成完成五項(xiàng)工作Bj(j=1,2,3,4,5)，每人只能完成一項(xiàng)工作，且每項(xiàng)工作只能有一人來完成，每人完成每項(xiàng)工作所花費(fèi)的費(fèi)用如下表，請(qǐng)求使總費(fèi)用最小的最優(yōu)解。人員任務(wù)B1B2B3B4B5A1127979A289666A3717121412A415146610A54107106五、規(guī)劃問題：（7分）用單純形法求解某線性規(guī)劃問題得如下單純形表：cj1008000S基變量x1x2x3x4ac013/10-1/512bd10-1/102/516cj-zjef-14-24g上述問題是求maxS=100x1+80x2,x3,x4為松弛變量，則a,b,c,d,e,f,g各為多少，上述表所給出的解是最優(yōu)解嗎？上述問題的對(duì)偶問題的解是什么？最優(yōu)值是什么？六、運(yùn)輸問題：（10分）對(duì)如下表的運(yùn)輸方案：若要使總利潤最大，該方案是否為最優(yōu)方案？若問題中B1的需要量改為700，該方案是否為最優(yōu)方案？填空題：（10分）1、在圖論中，圖的基本要素有兩個(gè)，它們是和。2、結(jié)點(diǎn)的最早開始時(shí)間和時(shí)間是同一時(shí)間，最早開始是對(duì)結(jié)點(diǎn)的后接工序而言，是對(duì)結(jié)點(diǎn)的緊前工序而言。3、對(duì)需要量供應(yīng)量的運(yùn)輸問題，求最優(yōu)解時(shí)要先一個(gè)供應(yīng)點(diǎn)。4、關(guān)鍵路線是從起點(diǎn)到終點(diǎn)所有路中的最路，它的線路時(shí)差為。5、在圖論中，為了表示兩個(gè)隊(duì)比賽的勝負(fù)關(guān)系可以用一條帶的來表示。選擇題（10分）1、若T是圖G的最小支撐樹，則（）A．T必唯一B.G不一定是連通圖C．T中必不含圈D.G中不含圈4、若線性規(guī)劃問題的最優(yōu)解在可行域的兩個(gè)頂點(diǎn)達(dá)到，則最優(yōu)解（）。A．有兩個(gè)B.有無窮多個(gè)C.過這兩點(diǎn)的直線D.不可能發(fā)生5、在n個(gè)產(chǎn)地，m個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問題中，（）是錯(cuò)誤的。運(yùn)輸問題是線性規(guī)劃問題基變量的個(gè)數(shù)是數(shù)字格的個(gè)數(shù)空格有mn-n-m+1個(gè)每一格在運(yùn)輸圖中均有一閉合回路判斷題（10分）1、用單純形法求解標(biāo)準(zhǔn)型式的線性規(guī)劃問題時(shí)，與>0對(duì)應(yīng)的變量都可以被選作換入變量。（）2、對(duì)偶問題的對(duì)偶一定是原問題。（）3、如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（）4、指派問題效率矩陣地每個(gè)元素都乘以同意常數(shù)k，將不影響最優(yōu)指派方案。（）5、求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個(gè)線性規(guī)劃模型。（）規(guī)劃問題（16分）已知線性規(guī)劃問題寫出其對(duì)偶問題；用圖解法求對(duì)偶問題的解；利用（2）的結(jié)果及對(duì)偶性質(zhì)求原問題解。運(yùn)輸問題（10分）某土石方從三個(gè)產(chǎn)地運(yùn)往四個(gè)工地，產(chǎn)地的產(chǎn)量、工地的需求量及單位運(yùn)費(fèi)如下表，求最優(yōu)運(yùn)輸方案。產(chǎn)地銷地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656支撐樹問題（6分）求下面網(wǎng)絡(luò)圖的最小支撐樹：運(yùn)輸問題（10分）求總運(yùn)費(fèi)最小的運(yùn)輸問題，某步運(yùn)輸圖如下：寫出a,b,c,d,e的值，并求出最優(yōu)運(yùn)輸方案；A3到B1的單位運(yùn)費(fèi)滿足什么條件時(shí)，表中運(yùn)輸方案為最優(yōu)方案。指派問題（10分）分配甲、乙、丙、丁、戊五人去完成五項(xiàng)工作，每人完成一項(xiàng)工作，每人完成各項(xiàng)任務(wù)時(shí)間如下表，試確定總花費(fèi)時(shí)間為最少的指派問題。人任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊4107109七、求下圖所示容量網(wǎng)絡(luò)中從～的最大流。其中每邊上的數(shù)為。一、多項(xiàng)選擇題（18分）線性規(guī)劃模型有特點(diǎn)（）所有函數(shù)都是線性函數(shù)；目標(biāo)求最大；有等式或不等式約束；變量非負(fù)。下面命題正確的是（）。線性規(guī)劃的最優(yōu)解是基本可行解；基本可行解一定是基本解；線性規(guī)劃一定有可行解；線性規(guī)劃的最優(yōu)值至多有一個(gè)。一個(gè)線性規(guī)劃問題（P）與它的對(duì)偶問題（D）有關(guān)系（）。A、（P）有可行解則（D）有最優(yōu)解；B、（P）、（D）均有可行解則都有最優(yōu)解；C、（P）可行（D）無解，則（P）無有限最優(yōu)解；D、（P）（D）互為對(duì)偶。運(yùn)輸問題的基本可行解有特點(diǎn)（）。有m＋n－1個(gè)基變量；有m+n個(gè)位勢(shì)；產(chǎn)銷平衡；不含閉回路。關(guān)于動(dòng)態(tài)規(guī)劃問題的下列命題中（）是錯(cuò)誤的。動(dòng)態(tài)規(guī)劃分階段順序不同，則結(jié)果不同；狀態(tài)對(duì)決策有影響；在求解最短路徑問題時(shí)，標(biāo)號(hào)法與逆序法求解的思路是相同的；動(dòng)態(tài)規(guī)劃的求解過程都可以用列表形式實(shí)現(xiàn)。二、計(jì)算題1、某公司下屬的3個(gè)分廠A1、A2、A3生產(chǎn)質(zhì)量相同的工藝品，要運(yùn)輸?shù)紹1、B2、B3、B4，4個(gè)銷售點(diǎn)，分廠產(chǎn)量、銷售點(diǎn)銷量、單位物品的運(yùn)費(fèi)數(shù)據(jù)如下：求最優(yōu)運(yùn)輸方案。2、考慮下列線性規(guī)劃：最優(yōu)單純形表為：

（1）、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)基B和它的逆B-1；

（2）、求此線性規(guī)劃的對(duì)偶問題的最優(yōu)解；

（3）、試求c2在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；

（4）、若b1=20變?yōu)?5，最優(yōu)解及最優(yōu)值是什么？3、某公司決定投資60萬元（以10萬元為單位），以提高三種主要產(chǎn)品A、B、C的產(chǎn)量?，F(xiàn)決定每種產(chǎn)品至少要投資10萬元。各種產(chǎn)品投資不同資金后可獲得的期望利潤如下：試確定如何安排對(duì)各種產(chǎn)品的投資數(shù)，可獲得最大總期望利潤？有下面線性規(guī)劃：要求：1、用單純性發(fā)就解該線性規(guī)劃問題；2、寫出該問題的對(duì)偶規(guī)劃；3、利用原問題的最優(yōu)解和互補(bǔ)松弛性，直接秋池對(duì)偶問題的最優(yōu)解；4、利用原問題的最后一張單純形表，直接秋池對(duì)偶問題最優(yōu)解。二、某公司有3個(gè)生產(chǎn)同類產(chǎn)品的工廠，生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)銷售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量以及各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如下表所示。問該