運籌學(xué)模擬試題

1、一、 填空題：（10分）1、 運輸問題中，求總利潤最大時，當(dāng)運輸圖所有空格的檢驗數(shù) ，得最優(yōu)解；求總運費最小時，當(dāng)運輸圖所有空格的檢驗數(shù) ，得最優(yōu)解。2、 若線性規(guī)劃問題的最優(yōu)基為B，則問題的最優(yōu)值為 ，線性規(guī)劃的對偶問題的最優(yōu)解是 ，其中CB是基B所對應(yīng)的基變量在目標(biāo)函數(shù)中的系數(shù)向量，線性規(guī)劃問題是： 3、 運輸問題中，當(dāng)總供應(yīng)量小于總需求量時，求解時需虛設(shè)一個 點，此點的供應(yīng)量應(yīng) （總需求量與總供應(yīng)量之差）。 4、 結(jié)點的最遲完成時間又稱 時間，若將最遲完成時間后延，將使整個網(wǎng)絡(luò)工期 。5、 樹是 的連通圖，在樹上任意除去一條邊則該樹余下的圖 。二、 單項選擇題（10分）1、為了在各住宅之

2、間安裝一條供暖管道，若要求所用材料最省，則應(yīng)采用（ ）。A求最大流量法 B.求最小支撐樹法C求最短路線法 D.樹的逐步生成法2、在網(wǎng)絡(luò)計劃中，進行時間與成本優(yōu)化時，隨工期延長，簡介費用將（ ）。A減少 B.增加 C.不變 D.不易估計3、圖論中，圖的基本要素是（ ）。A點和帶方向的連線 B.點和線C點及點與點之間的連線 D.點和一定要帶權(quán)的連線三、 判斷題。（10分）1、 線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴大。2、 根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解，反之，當(dāng)對偶問題無可行解時，其原問題具有無界解。3、 運輸問

3、題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。4、 目標(biāo)規(guī)劃中，英同時包含系統(tǒng)約束（絕對約束）與目標(biāo)約束。5、 用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值得下界。四、 建立數(shù)學(xué)模型題：（8分）某飼養(yǎng)場飼養(yǎng)動物出售，設(shè)每頭動物每天至少需700克蛋白質(zhì)、30克礦物質(zhì)、100毫克維生素?，F(xiàn)有五種飼料可供選用，各種飼料每公斤營養(yǎng)成分含量及單價如下表所示：要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料的方案。飼料 成分蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價格（元/千克）1310

4、.50.2220.51.00.7310.20.20.446220.35180.50.80.8五、 （8分）已知線性規(guī)劃問題其對偶問題最優(yōu)解為，試根據(jù)隊友理論求出原問題的最優(yōu)解。六、已知運輸問題的供需關(guān)系表與單位運價表如下所示，試用伏格爾法求出該問題的近似最優(yōu)解。（6分）產(chǎn)地 銷地甲乙丙丁產(chǎn)量132765027523603254525銷量60402015七、 用圖解法找出下列目標(biāo)規(guī)劃問題的滿意解（8分）八、 請用匈牙利法求解該指派問題：（8分）已知效率矩陣如下：九、 網(wǎng)絡(luò)最大流問題：（12分）下面為一容量網(wǎng)絡(luò)，各弧上的代表該弧的（可行流流量，容量） 請用標(biāo)號法求出該網(wǎng)絡(luò)最大流。一、 單項選擇題：

5、(10分)1、若用圖解法求解線性規(guī)劃問題，則該問題所包含決策變量的數(shù)目應(yīng)為（ ）。A 、二個 B 、五個以上C 、三個以上 D 、無限制2、原問題的檢驗數(shù)對應(yīng)于對偶規(guī)劃的一個解，符號相反，對偶規(guī)劃的檢驗數(shù)對應(yīng)于原規(guī)劃的一個解（符號性反），特別的，若原問題的最優(yōu)基為B，則對偶問題的最優(yōu)解為：（ ）A 、Y*= -CBB-1 B、Y*= CBB-1 C 、Y*= CN-CBB-1 D、Y*= B-CBB-13、甲、乙、丙、丁四個球隊進行比賽，任兩個隊都有一場比賽，且沒有和局，用來表示這四個隊比賽狀況的圖是（ ）。A 、一棵樹 B、沒有圈C 、連通圖 D、任兩點之間有一條帶有方向的線4、下列圖形中是

6、一棵樹的為：( ) A B C D5、以下哪個性質(zhì)是對偶問題所不具有的（ ） A、對稱性 B、互補松弛性C、弱對偶性 D、可行性二、 判斷題：（10分）1、如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對應(yīng)可行域邊界上的一個點。（ ）2、線性規(guī)劃問題每一個基解對應(yīng)于可行域的一個頂點。（ ）3、正偏差變量應(yīng)取正值，負偏差變量應(yīng)取負值。（ ）4、線性規(guī)劃問題是目標(biāo)規(guī)劃問題的一種特殊形式。（ ）5、表上作業(yè)法實質(zhì)就是求解運輸問題的單純形法。（ ）三、填空題：（10分）1、在圖論方法中，通常用 表示人們研究的對象，用 表示對象之間的某種聯(lián)系。2、是某線性規(guī)劃問題的一個決策變量，若它是該線性規(guī)劃問題某步單純形表

7、中的一個基變量，則的檢驗數(shù)為 ；若其檢驗數(shù)不為零，則其為 變量。3、利用單純形法求解線性規(guī)劃問題時，在最終單純形表中，若某一基變量為零，該基解稱為 解；若某一非基變量檢驗數(shù)為零，則該問題可能有 解。4、關(guān)鍵路線是從起點到終點所有路中的最 路，它的線路時差為 。5、求支撐樹有 法和 法兩種方法。四、指派問題：（10分）現(xiàn)有五個人Ai (i=1,2,3,4,5)被分配去完成完成五項工作Bj (j=1,2,3,4,5)，每人只能完成一項工作，且每項工作只能有一人來完成，每人完成每項工作所花費的費用如下表，請求使總費用最小的最優(yōu)解。人員 任務(wù)B1B2B3B4B5A1127979A289666A3717

8、121412A415146610A54107106五、規(guī)劃問題：（7分）用單純形法求解某線性規(guī)劃問題得如下單純形表：cj1008000S基變量x1x2x3x4ac013/10-1/512bd10-1/102/516cj-zjef-14-24g（1） 上述問題是求maxS=100x1+80x2 ,x3,x4為松弛變量，則a,b,c,d,e,f,g各為多少，上述表所給出的解是最優(yōu)解嗎？（2） 上述問題的對偶問題的解是什么？最優(yōu)值是什么？六、運輸問題：（10分）對如下表的運輸方案：（1） 若要使總利潤最大，該方案是否為最優(yōu)方案？（2） 若問題中B1的需要量改為700，該方案是否為最優(yōu)方案？（3） 填

9、空題：（10分）1、在圖論中，圖的基本要素有兩個，它們是 和 。2、結(jié)點的最早開始時間和 時間是同一時間，最早開始是對結(jié)點的后接工序而言， 是對結(jié)點的緊前工序而言。3、對需要量 供應(yīng)量的運輸問題，求最優(yōu)解時要先 一個供應(yīng)點。4、關(guān)鍵路線是從起點到終點所有路中的最 路，它的線路時差為 。5、在圖論中，為了表示兩個隊比賽的勝負關(guān)系可以用一條帶 的 來表示。（4） 選擇題（10分）1、若T是圖G的最小支撐樹，則（ ）AT必唯一 B. G不一定是連通圖CT中必不含圈 D.G中不含圈4、若線性規(guī)劃問題的最優(yōu)解在可行域的兩個頂點達到，則最優(yōu)解（ ）。A有兩個 B.有無窮多個 C.過這兩點的直線 D.不可能

10、發(fā)生5、在n個產(chǎn)地，m個銷地的產(chǎn)銷平衡運輸問題中，（ ）是錯誤的。A 運輸問題是線性規(guī)劃問題B 基變量的個數(shù)是數(shù)字格的個數(shù)C 空格有mn-n-m+1個D 每一格在運輸圖中均有一閉合回路一、 判斷題（10分）1、用單純形法求解標(biāo)準型式的線性規(guī)劃問題時，與0對應(yīng)的變量都可以被選作換入變量。（ ）2、對偶問題的對偶一定是原問題。（ ）3、如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化。（ ）4、指派問題效率矩陣地每個元素都乘以同意常數(shù)k，將不影響最優(yōu)指派方案。（ ）5、求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個線性規(guī)劃模型。（ ）二、 規(guī)劃問題（16分）已知線性

11、規(guī)劃問題（1） 寫出其對偶問題；（2） 用圖解法求對偶問題的解；（3） 利用（2）的結(jié)果及對偶性質(zhì)求原問題解。三、 運輸問題（10分）某土石方從三個產(chǎn)地運往四個工地，產(chǎn)地的產(chǎn)量、工地的需求量及單位運費如下表，求最優(yōu)運輸方案。產(chǎn)地 銷地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656四、 支撐樹問題（6分）求下面網(wǎng)絡(luò)圖的最小支撐樹：五、 運輸問題（10分）求總運費最小的運輸問題，某步運輸圖如下：(1) 寫出a, b ,c ,d ,e的值，并求出最優(yōu)運輸方案；(2) A3到B1的單位運費滿足什么條件時，表中運輸方案為最優(yōu)方案。六、 指派問題（10分）分配甲、乙、丙、

12、丁、戊五人去完成五項工作，每人完成一項工作，每人完成各項任務(wù)時間如下表，試確定總花費時間為最少的指派問題。人 任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊4107109七、求下圖所示容量網(wǎng)絡(luò)中從的最大流。其中每邊上的數(shù)為。一、多項選擇題（18分）1、 下面命題正確的是（ ）。A、 線性規(guī)劃的最優(yōu)解是基本可行解；B、 基本可行解一定是基本解；C、 線性規(guī)劃一定有可行解；D、 線性規(guī)劃的最優(yōu)值至多有一個。2、 一個線性規(guī)劃問題（P）與它的對偶問題（D）有關(guān)系（ ）。A、（P）有可行解則（D）有最優(yōu)解；B、（P）、（D）均有可行解則都有最優(yōu)解；C、（P）可行（D）無

13、解，則（P）無有限最優(yōu)解；D、（P）（D）互為對偶。3、 運輸問題的基本可行解有特點（ ）。A、 有mn1個基變量；B、 有m+n個位勢；C、 產(chǎn)銷平衡；D、 不含閉回路。4、 關(guān)于動態(tài)規(guī)劃問題的下列命題中（ ）是錯誤的。A、 動態(tài)規(guī)劃分階段順序不同，則結(jié)果不同；B、 狀態(tài)對決策有影響；C、 在求解最短路徑問題時，標(biāo)號法與逆序法求解的思路是相同的；D、 動態(tài)規(guī)劃的求解過程都可以用列表形式實現(xiàn)。二、計算題1、某公司下屬的3個分廠A1、A2、A3生產(chǎn)質(zhì)量相同的工藝品，要運輸?shù)紹1、B2、B3、B4 ，4個銷售點，分廠產(chǎn)量、銷售點銷量、單位物品的運費數(shù)據(jù)如下：求最優(yōu)運輸方案。2、考慮下列線性規(guī)劃：最

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