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

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