2013運籌學(xué)期末復(fù)習(xí)題1

1、1運籌學(xué)試題及答案運籌學(xué)試題及答案填空填空1. 線性規(guī)劃問題 maxz=cx；ax=b，x0（a 為kxl的矩陣，且lk）的基的最多個數(shù)為_，基的可行解的最多個數(shù)為_.2.指派問題的最優(yōu)解的性質(zhì)_3.線性規(guī)劃問題的所有可行解構(gòu)成的集合是 _,它們有有限個_,線性規(guī)劃問題的每個基可行解對應(yīng)可行域的 _,若線性規(guī)劃問題有最優(yōu)解，必在 _得到。4 影子價格的經(jīng)濟含義_.在完全市場經(jīng)濟的條件下，當(dāng)某種資源的市場價格低于影子價格時，企業(yè)應(yīng)_該資源，而當(dāng)某種資源的市場價格高于影子價格時，則企業(yè)應(yīng)_該資源，可見影子價格對市場有_作用。5. 運輸問題的產(chǎn)銷平衡表中有 m 個產(chǎn)地 n 個銷地，其決策變量的個數(shù)有

2、_個，其數(shù)值格有_個答案 1:clk , clk2 設(shè)指派問題的效率矩陣為 c=(cij)nn，若將該矩陣的某一行（或某一列）的各個元素都減去統(tǒng)一常數(shù)，得到新的效率矩陣b (bij)nn，則以b為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。3 凸集，頂點，頂點，頂點4 其它條件不變的情況下，單位第i種資源變化所引起目標(biāo)函數(shù)值的變化量。買進，賣出。5mn，m n 1計算計算 1 1對下列線性規(guī)劃問題 max z=2x1+x2+3x3 x1+ x2+2x35 s.t. 2x1+3x2+4x312x1, x2, x30（1） 寫出其對偶問題； （5 分）（2） 已知（3，2，0）t 是上述問題的

3、最優(yōu)解，根據(jù)互補松弛理論求出對偶問題的最優(yōu)解； （10 分）解： （1） （5 分）寫出其對偶問題； minw=5y1+12y2 s.t. y1+2y22 y1+3y21 2y1+4y23 y10， y2無約束（2） （10 分）已知（3，2，0）t是上述問題的最優(yōu)解，根據(jù)互補松弛理論求出對偶問題的最優(yōu)解；由于原問題 x1和 x2為正，根據(jù)互補松弛理論，有對偶問題取最優(yōu)解時（1） 、 （2）取嚴(yán)格等式，即為 y1+2y22 y1+3y21解得 y2-1 y14故對偶問題最優(yōu)解為 y*（4，1） ，w*=82. （15 分）運用單純形法求解下面線性規(guī)劃問題。max z 3x1 x2max z 3

4、x1 x23x15x2 x3153x15x215解：s.t6x12x2 x4 24s.t6x12x2 24x ,x 0 x ,x 01212（加入松弛變量x3,x4，上述模型可轉(zhuǎn)化為上式）2cb00cjxbx3x4zx3x1zb152403412033x13630101x252141/303x31001000 x4010-0.51/6-0.5541.2-（2 分）最優(yōu)解x* (4,0,0,0)t，最優(yōu)值z*123 3（15 分）已知運輸問題的產(chǎn)銷平衡表與單位運價表如下表所示銷地產(chǎn)地a1a2a3銷量b1101655b261042b375104b4129106產(chǎn)量494試用運用沃格爾法求出初始運輸

5、方案。解： （1） （7 分）用最小元素法求得初始可行基如下銷地b1b2b3b4產(chǎn)量產(chǎn)地a110 367 12 140 0 a216105 49 59-3-3a35 24 210 104-5-5銷量5101029 948 861212（2） （8 分）位勢方程組為 126（09）-3u1+v1=10 u1+v4=12 137（08）-1u2+v3=5 u2+v4=9 2116（103）9u3+v1=5 u3+v2=4 2210（93）4令 u10，解得 v1=10 v2=9 v3=8 3310（85）7 v4=12 u2 =-3 u3 =-5 3410（125）3各非基變量檢驗數(shù)為存在非基變量

6、檢驗數(shù)為負，沒有達到最優(yōu)解4 4 （15 分）用匈牙利法求解下列分配問題，已知效益矩陣為768691277879854610解：已知效益矩陣為7985361274879667810第一步（5 分） ，把 cij轉(zhuǎn)化為 cij,410281030210104第二步（5 分） ，求初始分配方案及尋找覆蓋所有零元素的最少直線，2410 281030210104 第三步（5 分） ，調(diào)整，求最優(yōu)解。1130370100200025所以，最優(yōu)解為x14* x23* x32* x41*1,其余xij* 0,z* 25建模建模1 1 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：班次時間所需人

7、數(shù)1606：00 10：0027010：00 14：0036014：00 18：0045018：00 22：0052022：00 2：006302：00 6：00設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員? （15 分）解：設(shè)xi 表示第 i 班次時開始上班的司機和乘務(wù)人員數(shù), （2 分）這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)： minx1 +x2 +x3 +x4 +x5 +x6 （3 分）約束條件：s.t.x1 +x6 60 x1 +x2 70 x2 +x3 60 x3 +x4 504x4 +x5

8、 20 x5 +x6 30 x1,x2,x3,x4,x5,x6 0（5 分）2.2. 某工廠要做 100 套鋼架，每套用長為 2.9 m,2.1 m,1.5 m 的圓鋼各一根。已知原料每根長 7.4 m，問：應(yīng)如何下料，可使所用原料最省？（15 分）解： 共可設(shè)計下列 5 種下料方案，見下表（5 分設(shè)x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)： minx1 +x2 +x3 +x4 +x5約束條件： s.t.x1 + 2x2 +x4 100 2x3 + 2x4 +x5 100 3x1 +x2 + 2x3 + 3x5 100 x1,x

9、2,x3,x4,x5 02.9 m2.1 m1.5 m合計剩余料頭方案 11037.40方案 22017.30.1方案 30227.20.2方案 41207.10.3方案 50136.60.8選題選題 1 1 線性規(guī)劃原問題中的變量個數(shù)與其對偶問題中的 約束條件個數(shù)相等。因此，當(dāng)原問題增加一個變量時，對偶問題就增加一個 約束條件，從而對偶可行域?qū)⒖赡茏?小 (小還是大)。2 2 用表上作業(yè)法求解m 個產(chǎn)地 n 個銷地的平衡運輸問題，其方案表上數(shù)字格的個數(shù)為 m+n-1個；若已計算出某空格的檢驗數(shù)為-3，若從該空格出發(fā)進行調(diào)整，設(shè)調(diào)整量為 2，則調(diào)整后可使總運費下降 6。3 3 下表中給出某線性

10、規(guī)劃問題計算過程中的一個單純形表，約束條件為，目標(biāo)函數(shù)為 maxz=284+5+26，表中1，2，3為松弛變量，表中解的目標(biāo)函數(shù)值 z=14。cbxbbx1x2x3x4x5x6x6a30-14/3011x256d205/20x400ef100-zbc00-1g5其中，a= 7，b= -6，c= 0 ，d= 1，e= 0，f= 1/3，g= 0；表中所給出的解 是 (是否）為最優(yōu)解，如為最優(yōu)解，解的情況是 無窮多最優(yōu)解 (唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解)。4 4 運輸問題解的情況有四種：無可行解；無界解；唯一最優(yōu)解；無窮多最優(yōu)解。錯5 5 運輸問題的所有結(jié)構(gòu)約束條件都是等式約束。對6

11、 6 某建材廠生產(chǎn)四種型號的特用構(gòu)件：型-、型、型、型。各型號每件所需組裝時間、檢驗時間、銷售收入及該廠組裝調(diào)試能力如表1所示型型型型工廠生產(chǎn)能力（h）組裝時間81012152000(h)檢驗時間2245500（h）售價 （百元） 46810但現(xiàn)在因為某種特型材料比較緊張，每月最多只能進貨180只（每件構(gòu)件用一只） ，其中型、型用到的不超過100只。令1、2、3、4依次表示各型號每月計劃產(chǎn)量?，F(xiàn)工廠擬定使目標(biāo)總銷售收入 z為最大的生產(chǎn)計劃。（1） 寫出該問題的數(shù)學(xué)模型，對于約束條件依下列順序：組裝時間、檢驗時間、特種材料數(shù)、型、型用到的特種材料數(shù)，并引入松弛變量使之成為等式。（2） 用單純型法

12、求解的終表入下表。468100000cbxbb-1bx1x2x3x4x5x6x7x80x850-0.200.200.1-0.501-0.76x21250.51000.25005-0.10x750.300.200.2510510x4500.200.81-0.10.500-1000-0.5-0.500分別回答：最優(yōu)生產(chǎn)計劃是什么？x1=0,x2=125,x3=0,x4=50是否還有其他的最優(yōu)生產(chǎn)計劃？是為什么？因為非基變量的檢驗數(shù)為零組裝時間的影子價格是多少？0.5若外廠可調(diào)劑增加80h 的檢驗時間，但每小時需付0.4百元，這樣的調(diào)劑值得嗎？值得能增加多少收入？ 8設(shè)型構(gòu)件售價由4百元增加到4.5百元，最優(yōu)計劃要改變嗎？不要如果增加到5.5百元呢？ 要說明理由。寫出本問題的對偶模型，并指出其最優(yōu)解。y1=0.5,y2=0.5，y3=0,y4=067 7 運輸問題運輸問題表中5-1給出一個運輸問題及它的一個解(見表4-2)， 試問： 1.表中給出的解是否為最優(yōu)解？請進行檢驗。2.若不是，請求出最優(yōu)解；若是，請判斷解的情況，如果有無窮多最優(yōu)解，除了題中給出的方案外，至少寫出另外一個。 （14分）表4-1產(chǎn)地銷地b1b2b3b4產(chǎn)量a141241116a22103910a38511622銷量814121448表4-2產(chǎn)地銷地b1b2b3b4產(chǎn)量a112416 0 2a28210