1、學習資料收集于網絡，僅供參考運籌學試題 參考答案一、填空題（每空 2 分，共 10 分）1、在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負限制的解為 可行解。2、在線性規(guī)劃問題中，圖解法適合用于處理 變量 為兩個的線性規(guī)劃問題。3、求解不平衡的運輸問題的基本思想是 的標準形式。設立虛供地或虛需求點，化為供求平衡4、在圖論中，稱無圈的連通圖為樹。最小費用法、西北角法兩5、運輸問題中求初始基本可行解的方法通常有種方法。二、（每小題 5 分，共 10 分）用圖解法求解下列線性規(guī)劃問題：1）max z = 6x1+4x2102x 1x2x 1x28x27x 1，x20、解： 此題在“ 運籌學復習參考資

2、料.doc” 中已有，不再重復。2）min z =3x1+2x2 2 x 1 4 x 2 22 x 1 4 x 2 10 2 x 1 x 2 7 x 1 3 x 2 1 x 1 , x 2 0 、解：學習資料學習資料收集于網絡，僅供參考可行解域為 abcda，最優(yōu)解為 b 點。由方程組2x14x222解出 x1=11，x2=0 x 20X*=x 1=（11，0）Tx 2min z =311+2 0=33 三、（15 分）某廠生產甲、乙兩種產品，這兩種產品均需要 A、B、C 三種資源，每種產品的資源消耗量及單位產品銷售后所能獲得的利潤值以及這三種資源的儲備如下表所示：A B C甲 9 4 3 7

3、0乙 4 6 10 120360 200 3001）建立使得該廠能獲得最大利潤的生產計劃的線性規(guī)劃模型；（5 分）學習資料學習資料收集于網絡，僅供參考 2）用單純形法求該問題的最優(yōu)解。 （10 分）解： 1）建立線性規(guī)劃數學模型：設甲、乙產品的生產數量應為 潤，則x1、x2，則 x1、x20，設 z 是產品售后的總利max z =70 x1+120 x2 s.t. 9x1x4x23604x16x22003x110 x2300 x1，202）用單純形法求最優(yōu)解：加入松弛變量 x3，x4，x5，得到等效的標準模型：max z =70 x1+120 x2+0 x3+0 x4+0 x5 s.t. 9x

4、14x22x3x53604x16x2x42003x110 x1 ,2 ,., 5300 xj,0j列表計算如下：學習資料學習資料收集于網絡，僅供參考CBXBb 70 120 0 0 0 Lx1x2x3x4x50 x3360 9 4 1 0 0 90 0 x4200 4 6 0 1 0 100/3 0 x5300 3（10）0 0 1 30 0 0 0 0 0 400/13 70 1200 0 0 0 x3240 39/5 0 1 0 - 2/5 0 x420 （11/5 ）00 1 - 3/5 100/11 120 x230 3/1010 0 1/10 100 36 120 0 0 12 34

5、0 0 0 120 x31860/11 0 0 139/1119/11 70 x1100/11 100 5/11 - 3/11 120 x2300/11 01 0 - 3/22 2/11 4300070 120 0 170/11 30/11 X*=（100 ，1111 0 0 300 ，1860，0，0） T11 11100 +120300 = 4300011 11 110 -170/11 30/11max z =70四、（10 分）用大 M 法或對偶單純形法求解如下線性規(guī)劃模型：min z =5x12x24x33x 1xx22x34x 26x 135x 310 x 1,2,x 30學習資料學

6、習資料收集于網絡，僅供參考 解：用大 M 法，先化為等效的 標準模型：max z / =5x12x24x3 s.t. 3x 1x222x 3x 4x 546x 13x5x 310yj0 ,j,12,., 5增加人工變量 x6、x7，得到：max z / =5x12x24x3M x6Mx7 s.t 3x 1x222x 3x 4x 5x 6x 746x 13x5x 310 xj0,j,12,., 7大 M 法單純形表求解過程如下：學習資料學習資料收集于網絡，僅供參考CBXBb 5 2 4 0 0 MMLx1x2x3x4x5x6x7Mx64 （3）1 2 1 0 1 0 4/3 Mx710 6 3

7、5 0 1 0 1 5/3 5 x19M4M7MMMMMMM4M 2 0 0 9M 57M 4 0 1/3 1/3 0 4/3 1 1/3 2/3 Mx72 01 1 （ 2）1 2 1 1 5 5- M 5/3-M 10/3-2 M +5/3M2M 5/3- M10/3 0M 1/3M 2/32M 5/3 M3M +5/30 x15/3 1 1/2 5/60 1/6 0 1/6 0 x41 0 （1/2 ）1/2 11/2 1 1/2 2 5 x15 5/2 25/6 05/6 0 5/60 1/2 1/6 0 5/6 MM+5/62/3 1 0 1/3 1 1/3 1 1/32 x22 0

8、 11 2 1 2 1225 2 11/3 1 1/3 1 1/3 30 0 1/3 1 1/3 M+1 M+1/3 2x*=（ 3，2，0，0，0）T學習資料學習資料收集于網絡，僅供參考最優(yōu)目標函數值min z =max z/=（ 22 ）= 3223五、（15 分）給定下列運輸問題： （表中數據為產地 A i 到銷地 Bj 的單位運費）B1 B2 B3 B4 siA 1 1 2 3 4 10 A 2 8 7 6 5 80 A 3 9 10 11 9 15 dj 8 22 12 18 1）用最小費用法求初始運輸方案，并寫出相應的總運費；（5 分）2）用 1）得到的基本可行解，繼續(xù)迭代求該問題

9、的最優(yōu)解。（10 分）解：用“ 表上作業(yè)法” 求解。1）先用最小費用法 （最小元素法） 求此問題的初始基本可行解：費銷地1B182B223B34B4Si用產地10A1A2887226122518182091011930A3201060 dj60 初始方案：學習資料 A18 B1A22 B3A320 B22 B218 B410 B3學習資料收集于網絡，僅供參考Z=1 8+2 2+6 2+5 18+10 20+11 10=424 2）用 閉回路法 ，求檢驗數：費銷B223B30 4B42Si產用地B1地A118210A28 4722261225181820119A39010130201060 dj

10、860 34 =10，其余j 0 選x 作為入基變量迭代調整。用 表上閉回路法 進行迭代調整：費銷地1B182B223B31 4B43Si用產地A110A28 371612 5820A390102011191030學習資料學習資料收集于網絡，僅供參考dj822121860 60 調整后，從上表可看出，所有檢驗數最優(yōu)方案為：j 0，已得最優(yōu)解。A18 B1A212 B3A320 B22 B28 B410 B4最小運費 Z=1 8+2 2+6 12+5 8+10 20+9 10=414 六、（8 分）有甲、乙、丙、丁四個人，要分別指派他們完成 人做各項工作所消耗的時間如下表所示：A、B、C、D 四

11、項不同的工作，每甲A B C D 2 10 9 7 乙15 4 14 8 丙13 14 16 11 丁4 15 13 9 問：應該如何指派，才能使總的消耗時間為最少？解：用 “ 匈牙利法” 求解。效率矩陣表示為：21097行約簡0875列約簡154148110104標號13141611235041513901195學習資料學習資料收集于網絡，僅供參考(0 )8* 02)65(0 )3(0)82511(0)5411(0 )5423(00*23(0 )0* 012450*124513(0)051443* 0(0 )(0)102300至此已得最優(yōu)解：010000011000使總消耗時間為最少的分配任務方案為：甲C，乙 B，丙 D，丁 A 此時總消耗時間 W=9+4+11+4=28 七、（6 分）計算下圖所示的網絡從A 點到 F 點的最短路線及其長度。此題在“ 運籌學參考綜合習題 （我站搜集信息自編） .doc” 中已有。A 3 5 B1 9 C1 1 D1 4 E1 1 F5 5 2 4 8 6 4 B2 3 C2 4 D2 9 E2 2 5 6 B3 1 4 4 7 5 7 C3 2 D3 學習資料學習資料收集于網絡，僅供參考解：此為動態(tài)規(guī)劃之“ 最短路問題”學習資料，可用逆向追蹤“ 圖上標