《運籌學(xué)》試卷及答案002

《運籌學(xué)》試卷一、單項選擇題(15分）1.線性規(guī)劃(以下簡稱LP)模型中自由變量可以用兩個非負變量之（）代換。A．和B．差C．積D．商2.LP原問題的第i個約束條件是“=”型，則對偶問題的變量yi是（）。A．剩余變量B．自由變量C．松弛變量D．非負變量3.基可行解中的非零變量的個數(shù)小于約束條件數(shù)時，該LP問題可求得(）。A．基本解B．多重解C．退化解D．無解4.運籌學(xué)中著名的“TSP問題”是指()。A.背包問題B.中國郵遞員問題 C.哥尼斯堡七橋問題D.貨郎擔(dān)問題5.用大M法求解極大化的LP問題時，人工變量在目標(biāo)函數(shù)中的系數(shù)是（）。A.-MB.MC.1D.-1二、判斷正誤（對者打“√”，錯者打“×”。15分）1.線性規(guī)劃問題的最優(yōu)解不一定只在可行域的頂點上取得。（）2.對偶單純形法是求解線性規(guī)劃對偶問題的一種算法。（）3.容量網(wǎng)絡(luò)中從發(fā)點到收點的最大流流量等于分離發(fā)點和收點的任一割集的容量。（）4.若整數(shù)規(guī)劃問題存在可行解，則其可行解集合是凸集。（）5.目標(biāo)規(guī)劃模型中可以沒有絕對約束，但不能沒有目標(biāo)約束。（）三、(25分)某企業(yè)生產(chǎn)3種產(chǎn)品，這些產(chǎn)品均需使用A、B兩種原料，每種產(chǎn)品的原料單耗(kg/件)、單位利潤以及這兩種原料在計劃期內(nèi)的可供應(yīng)量(kg)如下表。該企業(yè)應(yīng)如何安排3種產(chǎn)品生產(chǎn)，可使企業(yè)所獲利潤最大？產(chǎn)品原料ⅠⅡⅢ供應(yīng)量AB23442310080單位利潤(元/件)201518要求：1.建立該問題的線性規(guī)劃模型；（3分）2.用單純形法求該問題的最優(yōu)解及最優(yōu)值；（15分）3.產(chǎn)品Ⅲ的單位利潤在什么范圍內(nèi)變動時，最優(yōu)解不變？（3分）4.直接寫出該LP的對偶問題及其最優(yōu)解。（4分）四、(10分)某家電廠商生產(chǎn)A、B、C三種規(guī)格的某種家電產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時的工時消耗分別為2小時、2.5小時和3小時，生產(chǎn)線每月正常工作時間為480小時；三種產(chǎn)品銷售后，每臺獲利分別為150、180和200元；每月銷售量預(yù)計分別為90、70和50臺。該廠經(jīng)營目標(biāo)如下：P1：根據(jù)三種產(chǎn)品的需求變動趨勢，產(chǎn)品A按預(yù)計銷量生產(chǎn)、產(chǎn)品B的產(chǎn)量不超過預(yù)計銷量、產(chǎn)品C的產(chǎn)量不低于預(yù)計銷量為宜；P2：利潤指標(biāo)為每月不低于3萬元；P3：充分利用生產(chǎn)線的正常工作時間；P4：產(chǎn)品旺銷時可以適當(dāng)加班，但每月加班時間不宜超過40小時。試根據(jù)上述資料建立該家電廠商產(chǎn)品生產(chǎn)計劃的目標(biāo)規(guī)劃模型。（不求解）五、（15分）指派5位員工去完成5項不同的工作，每人做各項工作所需時間（單位：天）如下表所示。試用匈牙利法求最優(yōu)指派方案及最少總時間。工作員工ABCDEⅠ94646Ⅱ56353Ⅲ4149119Ⅳ1211437Ⅴ28584六、（10分）有總量為a和b的兩種資源，可用于n種產(chǎn)品的生產(chǎn)。如果第一種資源以數(shù)量xi、第二種資源以數(shù)量yi分配于第i種產(chǎn)品的生產(chǎn)，其收益為g(xi,yi),(i=1,2,…,n)。如何分配這兩種資源于n種產(chǎn)品的生產(chǎn)活動可使總收益最大？試建立該問題的動態(tài)規(guī)劃模型(不求解)。（提示建立動態(tài)規(guī)劃模型包括：確定解法(順序或逆序)；劃分階段；定義狀態(tài)變量、狀態(tài)集合、決策變量、允許決策集合、狀態(tài)轉(zhuǎn)移方程、階段指標(biāo)、最優(yōu)指標(biāo)函數(shù)；寫出動態(tài)規(guī)劃基本方程）七、（15分）用Ford-Fulkerson算法求圖1中容量網(wǎng)絡(luò)的最大流和最小割集。圖中弧旁的數(shù)字表示(cij，fij)。（提示求解過程應(yīng)寫出，并在圖上做相應(yīng)的標(biāo)記。一個可行流用一張圖表示）vvsvtv3v1v2v4(8,6)(10,8)(6,0)(6,6)(5,2)(3,3)(8,5)(3,3)(9,9)圖1圖1八、(15分)已知產(chǎn)銷平衡運輸問題表1所示。試檢驗表1中的基可行解是否是最優(yōu)解。如不是，用閉回路法對表中的解進行調(diào)整，求出最優(yōu)解及最小總運費。（提示應(yīng)簡要寫出求解過程，并將有關(guān)數(shù)據(jù)填入表中。一個基可行解用一張表表示）《運籌學(xué)》試卷一、單項選擇題(15分）1.B2.B3.C4.D5.A二、判斷正誤（對者打“√”，錯者打“×”。15分）1.√2.×3.×4.×5.√三、(25分）解:1.(3分）設(shè)產(chǎn)品Ⅰ、Ⅱ、Ⅲ在計劃期內(nèi)產(chǎn)量分別為x1、x2、x3，由題意，該問題的LP模型為：2.(15分）在約束中分別添加松弛變量x4、x5將LP化為標(biāo)準(zhǔn)形式，列單純形表求解:cj20151800bCBXBx1x2x3x4x500x4x523410[4]2301100805020j201518000∴x1換入、x5換出:500x4x10[2]5/21-1/211/23/401/460203040j0530-5-400∴x2換入、x4換出:5040x2x1015/41/2-1/4101/8-1/41/8305j00-13/4-5/2-15/4-550∵j0，∴得最優(yōu)解:X*=(5,30,0,0,0)T，最優(yōu)值z*=5503.∵x3是非基變量，故當(dāng)3’0，即c3-3=13/4，亦即c3’85/4.對偶問題為：minw=100y1+80y22y1+4y3203y1+2y2154y1+3y218y1,y20對偶問題最優(yōu)解：Y*=(5/2,15/4)T，最優(yōu)值w*=550評分標(biāo)準(zhǔn):1.正確設(shè)定決策變量:1分；正確列出LP模型:2分。2.化標(biāo)準(zhǔn)形式、答案各1分，第1張單純形表3分,第2,3張單純形表各5分；3.3分。4.正確列出對偶問題模型:3分；最優(yōu)解1分。個別數(shù)據(jù)錯誤酌情扣分。四、(10分)解:設(shè)計劃期內(nèi)A、B、C三種產(chǎn)品的產(chǎn)量分別為x1,x2,x3，由題意，該問題的GP模型為:評分標(biāo)準(zhǔn):正確設(shè)定決策變量:2分；正確列出目標(biāo)規(guī)劃模型:8分。個別條件列錯酌情扣分。五、(15分）解:化簡系數(shù)矩陣:圈出C’中的獨立0元素:552223210575981463625222321057598146362-2-2+2→70202430200835311810404140=C’’C’中只有4個獨立0元素，需要繼續(xù)變換:用最少直線數(shù)覆蓋所有0元素，未被直線覆蓋的元素中的最小元素是2，則未被直線覆蓋的行中每個元素-2,被直線覆蓋的列中每個元素+2，得到C’’。圈出C’’中的獨立0元素:7722432835311814414已得到5個獨立0元素?！嘧顑?yōu)指派方案為:I做B工作；II做C工作；III做A工作；IV做D工作；V做E工作?？偤臅r為4+3+4+3+4=18（天）。評分標(biāo)準(zhǔn):變換系數(shù)矩陣得到C’：3分；進一步變換系數(shù)矩陣得到C’’：7分；圈出5個獨立0元素、給出最優(yōu)指派方案：5分。個別數(shù)據(jù)錯誤酌情扣分。六、(10分)解:建立該問題的動態(tài)規(guī)劃模型如下:(1)采用逆序解法(順序解法亦可);(2)階段：按產(chǎn)品劃分階段,每種產(chǎn)品為一個階段，k＝1,2,…,n(3)狀態(tài)變量狀態(tài)變量sk＝(Xk,Yk)，其中：Xk：分配用于生產(chǎn)第k至第n種產(chǎn)品的第一種資源數(shù);Yk：分配用于生產(chǎn)第k至第n種產(chǎn)品的第二種資源數(shù)。(4)狀態(tài)集合:S1=(a,b)，Sn+1=(0，0),(0，0)Sk(a,b)，k=2,3,…,n(5)決策變量uk=(xk，yk)，其中xk:用于第k種產(chǎn)品生產(chǎn)的第一種資源數(shù),yk:用于第k種產(chǎn)品生產(chǎn)的第二種資源數(shù)。(6)允許決策集合:Dk(Xk,Yk)={(xk，yk)|0￡xk￡Xk，0￡yk￡Yk},k=1,2,…,n(7)狀態(tài)轉(zhuǎn)移方程：Xk+1=Xk-xk,Yk+1=Yk-yk，k＝1,2,…,n(8)階段指標(biāo):gk(xk,yk)，k＝1,2,…,n(9)最優(yōu)指標(biāo)函數(shù)f(Xk,Yk)表示表示當(dāng)分配于第k種產(chǎn)品至第n種產(chǎn)品兩種資源數(shù)量為Xk和Yk時的最大收益。(10)DP基本方程為：k=n,n-1,…,2,1k=n,n-1,…,2,1評分標(biāo)準(zhǔn):(1)～(10)項每項1分.七、(15分）解:(1)標(biāo)號過程：先給vs標(biāo)以(0，+∞)。檢查vs的相鄰未標(biāo)號點，發(fā)現(xiàn)v1、v2符合標(biāo)號條件，故給v1以標(biāo)號(vs,min｛+∞,cs1-fs1｝)=(vs,2)；給v2以標(biāo)號(vs,min｛+∞,cs2-fs2})=(vs,2)。繼續(xù)標(biāo)號過程，給v3以標(biāo)號(v2,min｛2,c23-f23｝)=(v2,2)；給vt以標(biāo)號(v3,min｛2,c3t–f3t})=(v3,2)。至此vt已得到標(biāo)號，說明存在一條可增廣鏈：vs→v2→v3→vt，如圖1。轉(zhuǎn)調(diào)整過程。vvsvtv3v1v2v3(8,6)(10,8)(6,0)(6,6)(5,2)(3,3)(8,5)(3,3)(9,9)圖1圖1(0,+∞)(vs,2)(vs,2)(v2,2)(v3,2)(2)調(diào)整過程：沿可增廣鏈調(diào)整流量，調(diào)整量δ=dvt=2，即令可增廣鏈上所有前向弧的流量增加2。調(diào)整后得到的可行流如圖2：(3)重新標(biāo)號：去掉所有標(biāo)號，對新的可行流重新標(biāo)號。給vs標(biāo)（0,+∞）,給v1以標(biāo)號(vs,min｛+∞,cs1-fs1})=(vs,2)。至此標(biāo)號進行不下去，而vt未得到標(biāo)號，說明圖中的流已是最大流。最大流量w(f*)=f4t+f3t=16。vsvtv3v1v2v4(8,6)(10,10)(6,0)(6,6)(5,4)(3,vsvtv3v1v2v4(8,6)(10,10)(6,0)(6,6)(5,4)(3,3)(8,7)(3,3)(9,9)圖1圖2(0,+∞）(vs,2)評分標(biāo)準(zhǔn):(1)、(2)、（3）、圖1、圖2各3分。若算法步驟和圖不完整,可適當(dāng)扣分。八、(15分）解:閉回路法求得表中基可行解