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

2、斷正誤（對者打“”，錯者打“X”。1x5分）線性規(guī)劃問題的最優(yōu)解不一定只在可行域的頂點上取得。（）對偶單純形法是求解線性規(guī)劃對偶問題的一種算法。（）容量網絡中從發(fā)點到收點的最大流流量等于分離發(fā)點和收點的任一割集的容量。（）若整數(shù)規(guī)劃問題存在可行解，則其可行解集合是凸集。（）目標規(guī)劃模型中可以沒有絕對約束，但不能沒有目標約束。（）三、（25分）某企業(yè)生產3種產品，這些產品均需使用A、B兩種原料，每種產品的原料單耗（kg/ 件）、單位利潤以及這兩種原料在計劃期內的可供應量（kg）如下表。該企業(yè)應如何安排3種產品生 產，可使企業(yè)所獲利潤最大？產品原料IIIm供應量A234100B42380單位利潤（

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

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

5、 y.） , （1=1,2,0）如何分配這兩種 資源于n種產品的生產活動可使總收益最大？試建立該問題的動態(tài)規(guī)劃模型（不求解）。（提示建立動態(tài)規(guī)劃模型包括：確定解法（順序或逆序）；劃分階段；定義狀態(tài)變量、狀態(tài)集合、 決策變量、允許決策集合、狀態(tài)轉移方程、階段指標、最優(yōu)指標函數(shù)；寫出動態(tài)規(guī)劃基本方程）七、（15分）用Ford-Fulkerson算法求圖1中容量網絡的最大流和最小割集。圖中弧旁的數(shù)字表示（%, f（提示 求解過程應寫出，并在圖上做相應的標記。一個可行流用一張圖表示）八、（15分）已知產銷平衡運輸問題表1所示。試檢驗表1中的基可行解是否是最優(yōu)解。如不是， 用閉回路法對表中的解進行調整，

6、求出最優(yōu)解及最小總運費。（提示 應簡要寫出求解過程，并 將有關數(shù)據(jù)填入表中。一個基可行解用一張表表示）、銷地 產地B1B2B3B4產量A1_410535060A2h.40b.35Lah.75A3_8_b.70U2090需求量40457070運籌學試卷一、單項選擇題（1x5分）B2.B3.C4.D5.A二、判斷正誤（對者打“”，錯者打“X”。1x5分）1. ”2. X 3. X 4. X 5.”三、（25分）解：（3分）設產品I、II、m在計劃期內產量分別為、x2、，由題意，該問題的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化為標準形式，列單純形表求解: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、非基變量，故當如0，即% p3=13/4，亦即c320J 3“ +S 154y1 +3y2 18-yy2 0對偶問題最優(yōu)解：Y*=（ 5/2,15/4）t，最優(yōu)值w*=550評分標準：正確設定決策變量:1分；正確列出LP模型:2分。化標準形式、答案各1分，第1張單純形表3分，第2,3張單純形表各5分；3.3 分。4.正確列出對偶問題模型:3分；最優(yōu)解1分。個別數(shù)據(jù)錯誤酌情扣分。四、（10分）解：設計劃期內A、B、C三種產品的產量分別為,%,%，由題意，該問題的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評分標準：正確設定決策變量:2分；正確列出目標規(guī)劃模型:8分。個別條件列錯酌情扣分。五、（15分）解：化簡系

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 -/結 6 3 6 2 -20 4140圈出C中的獨立0元素:=C，/+2C中只有4個獨立0元素，需要繼續(xù)變換:用最少直線數(shù)覆蓋所有0元素，未被直線覆蓋的元素中 的最小元素是2,則未被直線覆蓋的行中每個元素-2,被直線覆蓋的列中每個元素+2,得到C，。 圈出C，中的獨立0元素：

11、72024320835311814-0414.最優(yōu)指派方案為I做B工作；II做C工作；III做A工作；IV做D工已得到5個獨立0元素。作；V做E工作。總耗時為4+3+4+3+4=18 （天）。評分標準：變換系數(shù)矩陣得到C : 3分；進一步變換系數(shù)矩陣得到C，： 7分；圈出5個獨立0 元素、給出最優(yōu)指派方案：5分。個別數(shù)據(jù)錯誤酌情扣分。六、(10分)解:建立該問題的動態(tài)規(guī)劃模型如下：采用逆序解法(順序解法亦可)；階段：按產品劃分階段，每種產品為一個階段，k=1,2,.,.n狀態(tài)變量狀態(tài)變量sk=(Xk，Yk)，其中：Xk:分配用于生產第k至第n種產品的第一種資源數(shù);Yk:分配用于生產第k至第n種

12、產品的第二種資源數(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種產品生產的第一種資源數(shù),yk：用于第k種產品生 產的第二種資源數(shù)。允許決策集合:DJXYQ=3u yQ|0 x X，0 孔, k=1,2,.,nk k k kkk k k kJ狀態(tài)轉移方程：Xk+1= Xk- xk , Yk+1= Yk-yk，k=1,2,.,n階段指標:gk(xk,yk) ， k=1,2,.,n最優(yōu)指標函數(shù)f(Xk,Yk)表示表示當分配于第k種產品至第n種產品兩種資源數(shù)量為Xk和Yk時 的最大收益。(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評分標準:(1)(10)項每項1分.七、(15分)解：(1)標號過程：先給吃標以(0，+8)。檢查vs的相鄰未標號點，發(fā)現(xiàn)vr V2符合標號條件，故 給 V 以標號(vs,min +8叢去 )=(vs,2)；給 V以標號(vs,min (+,cs2-fs2)= (vs,2)。繼續(xù)標號 過程，給 v 以標號(v?,min 2,c23-f23 )=(v2,2);給 vt 以標號(v ,min 2, c 3.

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