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

1、運(yùn)籌學(xué)試卷一、單項(xiàng)選擇題（1x5分）線性規(guī)劃（以下簡(jiǎn)稱LP）模型中自由變量可以用兩個(gè)非負(fù)變量之（）代換。 TOC o 1-5 h z A.和B.差C.積D.商LP原問(wèn)題的第i個(gè)約束條件是“二”型，則對(duì)偶問(wèn)題的變量*是（）。A.剩余變量B-自由變量 C.松弛變量 D.非負(fù)變量基可行解中的非零變量的個(gè)數(shù)小于約束條件數(shù)時(shí)，該LP問(wèn)題可求得（）。A.基本解 B.多重解 C-退化解 D.無(wú)解運(yùn)籌學(xué)中著名的“TSP問(wèn)題”是指（）。A.背包問(wèn)題B.中國(guó)郵遞員問(wèn)題C.哥尼斯堡七橋問(wèn)題D.貨郎擔(dān)問(wèn)題用大M法求解極大化的LP問(wèn)題時(shí)，人工變量在目標(biāo)函數(shù)中的系數(shù)是（）。A. -M B. M C. 1 D. -1二、判

2、斷正誤（對(duì)者打“”，錯(cuò)者打“X”。1x5分）線性規(guī)劃問(wèn)題的最優(yōu)解不一定只在可行域的頂點(diǎn)上取得。（）對(duì)偶單純形法是求解線性規(guī)劃對(duì)偶問(wèn)題的一種算法。（）容量網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)的最大流流量等于分離發(fā)點(diǎn)和收點(diǎn)的任一割集的容量。（）若整數(shù)規(guī)劃問(wèn)題存在可行解，則其可行解集合是凸集。（）目標(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)品原料IIIm供應(yīng)量A234100B42380單位利潤(rùn)（

3、元/件）201518要求：建立該問(wèn)題的線性規(guī)劃模型；（3分）用單純形法求該問(wèn)題的最優(yōu)解及最優(yōu)值；（15分）產(chǎn)品III的單位利潤(rùn)在什么范圍內(nèi)變動(dòng)時(shí)，最優(yōu)解不變？ （3分）直接寫出該LP的對(duì)偶問(wèn)題及其最優(yōu)解。（4分）四、（10分）某家電廠商生產(chǎn)A、B、C三種規(guī)格的某種家電產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時(shí)的工時(shí)消耗分別為2小時(shí)、2.5小時(shí)和3小時(shí)，生產(chǎn)線每月正常工作時(shí)間為480 小時(shí)；三種產(chǎn)品銷售后，每臺(tái)獲利分別為150、180和200元；每月銷售量預(yù)計(jì)分別為90、70和 50臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：P1：根據(jù)三種產(chǎn)品的需求變動(dòng)趨勢(shì)，產(chǎn)品A按預(yù)計(jì)銷量生產(chǎn)、產(chǎn)品B的產(chǎn)量不超過(guò)預(yù)計(jì)銷量、

4、產(chǎn)品C的產(chǎn)量不低于預(yù)計(jì)銷量為宜；P2：利潤(rùn)指標(biāo)為每月不低于3萬(wàn)元；P3：充分利用生產(chǎn)線的正常工作時(shí)間；P4：產(chǎn)品旺銷時(shí)可以適當(dāng)加班，但每月加班時(shí)間不宜超過(guò)40小時(shí)。試根據(jù)上述資料建立該家電廠商產(chǎn)品生產(chǎn)計(jì)劃的目標(biāo)規(guī)劃模型。（不求解）五、（15分）指派5位員工去完成5項(xiàng)不同的工作，每人做各項(xiàng)工作所需時(shí)間（單位：天）如下 表所示。試用匈牙利法求最優(yōu)指派方案及最少總時(shí)間。作 員工ABCDEI94646II56353m4149119W1211437V28584六、（10分）有總量為a和b的兩種資源，可用于n種產(chǎn)品的生產(chǎn)。如果第一種資源以數(shù)量尤、 第二種資源以數(shù)量y.分配于第i種產(chǎn)品的生產(chǎn)，其收益為g（x

5、 y.） , （1=1,2,0）如何分配這兩種 資源于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ù)；寫出動(dòng)態(tài)規(guī)劃基本方程）七、（15分）用Ford-Fulkerson算法求圖1中容量網(wǎng)絡(luò)的最大流和最小割集。圖中弧旁的數(shù)字表示（%, f（提示 求解過(guò)程應(yīng)寫出，并在圖上做相應(yīng)的標(biāo)記。一個(gè)可行流用一張圖表示）八、（15分）已知產(chǎn)銷平衡運(yùn)輸問(wèn)題表1所示。試檢驗(yàn)表1中的基可行解是否是最優(yōu)解。如不是， 用閉回路法對(duì)表中的解進(jìn)行調(diào)整，

6、求出最優(yōu)解及最小總運(yùn)費(fèi)。（提示 應(yīng)簡(jiǎn)要寫出求解過(guò)程，并 將有關(guān)數(shù)據(jù)填入表中。一個(gè)基可行解用一張表表示）、銷地 產(chǎn)地B1B2B3B4產(chǎn)量A1_410535060A2h.40b.35Lah.75A3_8_b.70U2090需求量40457070運(yùn)籌學(xué)試卷一、單項(xiàng)選擇題（1x5分）B2.B3.C4.D5.A二、判斷正誤（對(duì)者打“”，錯(cuò)者打“X”。1x5分）1. ”2. X 3. X 4. X 5.”三、（25分）解：（3分）設(shè)產(chǎn)品I、II、m在計(jì)劃期內(nèi)產(chǎn)量分別為、x2、，由題意，該問(wèn)題的LP模型為:max z = 20 x +15 x +18 x2x + 3x + 4x 100s.t. 4x + 2

7、x + 3x 0, j= 1,2,3i j（15分）在約束中分別添加松弛變量x4、x5將LP化為標(biāo)準(zhǔn)形式，列單純形表求解:c.j20151800b0CBXBx1x2x3x4x50 x423410100500 x 5_423018020b-i201518000.換入、x5換出:50 x4025/21-1/260300 x11/23/401/42040b-i0530-5-400.x2換入、x4換出:50 x2015/41/2-1/43040*101/8-1/41/85b -d00-13/4-5/2-15/4-550.7、0，.得最優(yōu)解：X*=（5,30,0,0,0）T，最優(yōu)值 z*=5507x3是

8、非基變量，故當(dāng)如0，即% p3=13/4，亦即c320J 3“ +S 154y1 +3y2 18-yy2 0對(duì)偶問(wèn)題最優(yōu)解：Y*=（ 5/2,15/4）t，最優(yōu)值w*=550評(píng)分標(biāo)準(zhǔn)：正確設(shè)定決策變量:1分；正確列出LP模型: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)量分別為,%,%，由題意，該問(wèn)題的GP模型 為：min P (d + + d - + d -1112氣+X +3+ d +), P d -, Pd -, P d +32

9、43 54 6d- d+ = 90d- d+ = 70d - d + = 5033st A150 氣 +180 x 2 + 200 x 3 + d - d + = 300002 x + 2.5 x + 3 x + d - d + = 480 TOC o 1-5 h z 12355d + + d - d + = 40566 HYPERLINK l bookmark71 o Current Document x 0, j = 1,2,3, d -, d + 0, i = 1, 6l ji i評(píng)分標(biāo)準(zhǔn)：正確設(shè)定決策變量:2分；正確列出目標(biāo)規(guī)劃模型:8分。個(gè)別條件列錯(cuò)酌情扣分。五、（15分）解：化簡(jiǎn)系

10、數(shù)矩陣:C =94646-5020256353230204149119010575121143798104_28584 _06362 _5 2025 2027 020223 _0 223 _0 2 4 3020I 10 575/ 10 575-2 一0 83534 8 -4-98十一一 4-11 8 104/ 6362 -/結(jié) 6 3 6 2 -20 4140圈出C中的獨(dú)立0元素:=C，/+2C中只有4個(gè)獨(dú)立0元素，需要繼續(xù)變換:用最少直線數(shù)覆蓋所有0元素，未被直線覆蓋的元素中 的最小元素是2,則未被直線覆蓋的行中每個(gè)元素-2,被直線覆蓋的列中每個(gè)元素+2,得到C，。 圈出C，中的獨(dú)立0元素：

11、72024320835311814-0414.最優(yōu)指派方案為I做B工作；II做C工作；III做A工作；IV做D工已得到5個(gè)獨(dú)立0元素。作；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ī)劃模型如下：采用逆序解法(順序解法亦可)；階段：按產(chǎn)品劃分階段，每種產(chǎn)品為一個(gè)階段，k=1,2,.,.n狀態(tài)變量狀態(tài)變量sk=(Xk，Yk)，其中：Xk:分配用于生產(chǎn)第k至第n種產(chǎn)品的第一種資源數(shù);Yk:分配用于生產(chǎn)第k至第n種

12、產(chǎn)品的第二種資源數(shù)。k狀態(tài)集合：S1=(a,b), S 1=(0, 0), (0, 0)Sk(a,b), k=2,3,.,n決策變量uk=3k，yk)，n其中:用于第k種產(chǎn)品生產(chǎn)的第一種資源數(shù),yk：用于第k種產(chǎn)品生 產(chǎn)的第二種資源數(shù)。允許決策集合:DJXYQ=3u yQ|0 x X，0 孔, k=1,2,.,nk k k kkk k k kJ狀態(tài)轉(zhuǎn)移方程：Xk+1= Xk- xk , Yk+1= Yk-yk，k=1,2,.,n階段指標(biāo):gk(xk,yk) ， k=1,2,.,n最優(yōu)指標(biāo)函數(shù)f(Xk,Yk)表示表示當(dāng)分配于第k種產(chǎn)品至第n種產(chǎn)品兩種資源數(shù)量為Xk和Yk時(shí) 的最大收益。(10)D

13、P基本方程為:fk ( X k ,七)=maxg (x , y ) + f (X - x , Y - y ) k=n,n-1,.,2,1k k k k+1 k k k kf (sn +1n +1評(píng)分標(biāo)準(zhǔn):(1)(10)項(xiàng)每項(xiàng)1分.七、(15分)解：(1)標(biāo)號(hào)過(guò)程：先給吃標(biāo)以(0，+8)。檢查vs的相鄰未標(biāo)號(hào)點(diǎn)，發(fā)現(xiàn)vr V2符合標(biāo)號(hào)條件，故 給 V 以標(biāo)號(hào)(vs,min +8叢去 )=(vs,2)；給 V以標(biāo)號(hào)(vs,min (+,cs2-fs2)= (vs,2)。繼續(xù)標(biāo)號(hào) 過(guò)程，給 v 以標(biāo)號(hào)(v?,min 2,c23-f23 )=(v2,2);給 vt 以標(biāo)號(hào)(v ,min 2, c 3.

14、)= (v ,2)。至此 3tv已得到標(biāo)號(hào)，說(shuō)明存在一條可增廣鏈：V -V2V 一V，如圖1。轉(zhuǎn)調(diào)整過(guò)程。ts 2 3 I(vs,2)(2)調(diào)整過(guò)程：沿可增廣鏈調(diào)整流量，調(diào)整量6=叫=2,即令可增廣鏈上所有前向弧的流量增加2。 調(diào)整后得到的可行流如圖2：重新標(biāo)號(hào)：去掉所有標(biāo)號(hào)，對(duì)新的可行流重新標(biāo)號(hào)。給Vs標(biāo)(0,+8),給V以標(biāo)號(hào)(vs,min +8叢1去)= (vs,2)。至此標(biāo)號(hào)進(jìn)行不下去，而vt未得到 標(biāo)號(hào)，說(shuō)明圖中的流已是最大流。最大流量w(f * ) =f4t+f3 t=16。最小割集,=（v，v ），（v，v ） ,（v ,v ）,如圖2中的虛線所示。最小割集的容量為：c（S,S）=c +S 21314S1c13+c14=10+3+3=16,與最大流的流量相等。評(píng)分標(biāo)準(zhǔn):（1）、（2）、（3圖1、圖2各3分。若算法步驟和圖不完整,可適當(dāng)扣分。八、（15分）解：閉回路法求得表中基可行解的非基變量的檢驗(yàn)數(shù)，填入表1中空格的左下角。 */q11*， - 7 I/ .、“，1 /“，122221、*，11 /，I * X “，12,x21=1