試題 二 試題代碼：453 試題名稱：運籌學(xué) 考生注意∶ １．本試題共 七 題，共 3 頁，請考生認真檢查； ２．請務(wù)必將答案寫在答卷紙上，寫在試卷上的答案無效。 題號 一 二 三 四 五 六 七 總分 得分 簽字 一、華津機器制造廠專為拖拉機廠配套生產(chǎn)柴油機，今年頭四個月收到的訂單數(shù)量分別為3000，4500，3500，5000臺柴油機。該廠正常生產(chǎn)每月可生產(chǎn)柴油機3000臺，利用加班還可生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低，建立其線性規(guī)劃模型。（20分） 二、考慮線性規(guī)劃問題：（25分） 用單純形法求解，得其終表如下： 5 12 4 0 -M B-1b 12 0 1 -1/5 2/5 -1/5 8/5 5 1 0 7/5 1/5 2/5 9/5 0 0 -3/5 -29/5 -M+2/5 X4為松弛變量，X5為人工變量， 1．上述模型的對偶模型為： ； 2．對偶模型的最優(yōu)解為： ； 3．當(dāng)兩種資源分別單獨增加一個單位時，目標函數(shù)值分別增加 和 ； 4．最優(yōu)基的逆矩陣B-1 = 5．如果原問題增加一個變量，則對偶問題的可行域?qū)⒖赡茏兇筮€是變??？ . 三、求解下列各題（解題方法自選）（20分） 四、用隱枚舉法求解下列0-1規(guī)劃問題（20分） 五、用動態(tài)規(guī)劃方法求解下列問題（25分） 六、今有三個倉庫運送某種產(chǎn)品到四個市場上去，倉庫的供應(yīng)量是20，20和100，市場需求量是20，20，60和20，倉庫與市場之間的路線上的容量如下表（容量零表示兩點間無直接的路線可通）。用圖論方法確定現(xiàn)有路線容量能否滿足市場的需求，若不能，應(yīng)修改哪條線路的容量。（20分） 市場 倉庫 1 2 3 4 供應(yīng)量 1 30 10 0 40 20 2 0 0 10 50 20 3 20 10 40 5 100 需求量 20 20 60 20 七．下列敘述中正確的是 （ ）（20分） 1. 圖解法與單純形法，雖然求解的形式不同，但從幾何上理解，兩者是一致的； 2. 若線性規(guī)劃的原問題有多重最優(yōu)解，則其對偶問題也一定具有多重最優(yōu)解； 3. 如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化； 4. 對于極大化問題max Z =…令轉(zhuǎn)化為極小化問題，則利用匈牙利法求解時，極大化問題的最優(yōu)解就是極小化問題的最優(yōu)解，但目標函數(shù)相差： n+c； 5. 如果圖中從至各點均有惟一的最短路，則連接至其他各點的最短路在去掉重復(fù)部分后，恰好構(gòu)成該圖的最小支撐樹。 試題二答案 一、 解：設(shè)代表第i月正常生產(chǎn)的柴油機數(shù)量， 代表第i月加班生產(chǎn)的柴油機數(shù)量， 代表第i月末的庫存量，則=4 二、 解： 1、 對偶模型 2、 由單純形表可看出，由于 則對偶問題的第一、二個約束是緊的，可解出 將代入第三個約束，滿足約束條件，則 3、5和2 4、 5、如果原問題增加一個變量，則對偶問題就增加一個約束條件，它的可行域要么減少，要么不變，絕對不會變大。 三、 解：此題可看作指派問題求解： 5 6 10 1 2 5 0 1 4 0 0 3 8 10 12 ~ 4 6 7 ~ 0 2 3 ~ 0 1 2 4 4 5 0 0 0 0 0 0 1 0 0 四、 解：將最大化問題化為極小化問題，并將系數(shù)轉(zhuǎn)為正，即令，整理得 綜上，該0-1規(guī)劃無可行解 五、 解：按三個變量劃分為三個階段，狀態(tài)轉(zhuǎn)移方程 第三階段： 第二階段： 其中 第一階段： 其中 六、 解：依題意，首先給出一個可行流 在初始流上增流到不能再增，得到如下結(jié)果： 此時已不能再增流，流量 ，不能滿足市場的需求量。應(yīng)修改倉庫3到市場3和4的容量，分別增流10和5即能滿足需求。 七、 解：3、5正確。