1、運(yùn)籌學(xué)計(jì)算題復(fù)習(xí)一、第一章線性規(guī)劃及單純形法1、 下表是某求極大化線性規(guī)劃問題時(shí)得到的單純形表，表中無任何松馳變量，為參數(shù)，（1） 試完成該表；（2） 若該表中所示的為問題的最優(yōu)基，試求的取值圍21-4b3101-12101-1000解：21-4b3101-12101-10003-42、 在下面的線性規(guī)劃問題中找出滿足約束條件的所有基解，指出哪些是基可行解，并代入目標(biāo)函數(shù)，確定哪一個(gè)是最優(yōu)解。 解：在第二個(gè)約束條件兩邊乘以-1，變?yōu)闃?biāo)準(zhǔn)形式 的系數(shù)列向量，的系數(shù)列向量，的系數(shù)列向量；的系數(shù)列向量（1） 因?yàn)榫€性獨(dú)立，令非基變量得基本可行解（2） 因?yàn)榫€性獨(dú)立，令非基變量得基本解（3） 因?yàn)榫€性

2、獨(dú)立，令非基變量得基本可行解（4） 因?yàn)榫€性獨(dú)立，令非基變量得基本可行解（5） 因?yàn)榫€性獨(dú)立，令非基變量得基本解（6） 因?yàn)榫€性獨(dú)立，令非基變量得基本解比較最大值可知為最大值，故最優(yōu)解為3、 分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形法迭代的每一步相應(yīng)于圖形上哪一個(gè)頂點(diǎn)？ S.T.解：（1）圖解法，作圖如下圖所示，由圖得唯一最優(yōu)解，對應(yīng)于圖上的點(diǎn)為，其最優(yōu)值為。X1X2A3A2A1（2） 單純形法，引入松馳變量，標(biāo)準(zhǔn)型為 S.T.用單純形法列表，求解過程見下表21000153510502462014210003041-1/23/42411/301/61201/30-1/313/4

3、011/4-1/8215/410-1/125/2400-1/12-7/24因?yàn)椋蕟栴}的最優(yōu)解，其最優(yōu)目標(biāo)函數(shù)值為4、 建模題：某公司有資金3000萬元，六年有A、B、C、D、E五種投資項(xiàng)目可供選擇。其中：項(xiàng)目A從第一年到第六年初均可投資，當(dāng)年末可獲利10%；項(xiàng)目B可在第一年到四年初投資，周期為3年，到期可25%；項(xiàng)目C只能在第二年初投資，周期為3年，到期可獲利45%，但規(guī)定最大投資額不超過1000萬元；項(xiàng)目D只能在第四年初投資，周期為3年，到期可獲利40%，但規(guī)定最大投資額不超800萬元；項(xiàng)目E只能在第五年投資，周期為2年，到期可獲利35%，但規(guī)定最大投資額不超過500萬元。又項(xiàng)目A、B、C

4、、D、E的風(fēng)險(xiǎn)指數(shù)分別為0.1，0.2，0.4，0.3，0.1，問：如何確定這些項(xiàng)目的每年投資額，使得第六年末公司獲得最大利潤？解：建模題用表示第i年投入到 j個(gè)項(xiàng)目的資金，則有 目標(biāo)函數(shù)：s.t 二、第二章線性規(guī)劃的對偶理論與靈敏度分析5、寫出線性規(guī)劃問題的對偶問題 S.T.解：要理清原問題的約束條件與對偶問題變量之間的對應(yīng)關(guān)系，以及原問題的變量與對偶問題的約束條件之間的對應(yīng)關(guān)系，具體見P53原問題中：,原問題的對偶問題為，由可知對偶問題為 S.T.三、第三章運(yùn)輸問題6、求解下列產(chǎn)銷平衡的運(yùn)輸問題單位價(jià)格表 銷地B1 銷地B2 銷地B3 銷地B4產(chǎn)量產(chǎn)地A1產(chǎn)地A2產(chǎn)地A310 5 6 7

5、8 2 7 69 3 4 8 252550銷量 15 20 30 35100（1）用西北角法、最小元素法求初始基本可行解；（2）由上面所得的初始方案出發(fā)，應(yīng)用表上作業(yè)法求最優(yōu)方案。解：（1）西北角法z=665 銷地B1 銷地B2 銷地B3 銷地B4產(chǎn)量產(chǎn)地A1產(chǎn)地A2產(chǎn)地A315 10 10 15 15 35252550銷量 15 20 30 35100（2）最小元素法z=540 銷地B1 銷地B2 銷地B3 銷地B4產(chǎn)量產(chǎn)地A1產(chǎn)地A2產(chǎn)地A3 2520 5 15 30 5 252550銷量 15 20 30 35100（3）最優(yōu)方案：z=535 銷地B1 銷地B2 銷地B3 銷地B4產(chǎn)量產(chǎn)

6、地A1產(chǎn)地A2產(chǎn)地A3 25 15 1015 5 30 252550銷量 15 20 30 35100四、第四章目標(biāo)規(guī)劃7、用圖解法解下面的目標(biāo)規(guī)劃五、第五章整數(shù)規(guī)劃8、已知甲、乙、丙、丁四人完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)分配方案。任務(wù) 人員ABCD甲215134乙1041415丙9141613丁78119解： 1）變換系數(shù)矩陣，增加0元素。 2）試指派（找獨(dú)立0元素） 獨(dú)立0元素的個(gè)數(shù)為4 , 指派問題的最優(yōu)指派方案即為甲負(fù)責(zé)D工作，乙負(fù)責(zé)B工作，丙負(fù)責(zé)A工作，丁負(fù)責(zé)C工作。這樣安排能使總的工作時(shí)間最少，為4491128六、第八章圖與網(wǎng)絡(luò)分析9、圖與網(wǎng)絡(luò)的基本概念10、樹的基本概念七、網(wǎng)

7、絡(luò)計(jì)劃11、某工地現(xiàn)場施工準(zhǔn)備工作關(guān)系及持續(xù)時(shí)間如表1所示，該工程要在26天完成，其全部直接費(fèi)用為30000元，間接費(fèi)用為5000元，每超過1天，間接費(fèi)用增加600元。表1工作清單序號工作名稱工作代號持續(xù)時(shí)間/天緊后工作1拆遷A5C、D、E2圍墻砌筑B10F、G3場地平整C10H4臨時(shí)水電施工D8-5工棚搭建E11G6臨時(shí)道路修筑F18-7攪拌站搭建G6H8生活設(shè)施搭建H12-要求：（1）先畫出雙代號網(wǎng)絡(luò)圖，確定關(guān)鍵線路（2）將表2中的各項(xiàng)工作的3列空格容計(jì)算出來，并填入表中。（3）進(jìn)行工期費(fèi)用優(yōu)化，求出計(jì)算工期為26天的總費(fèi)用和與原計(jì)劃相比節(jié)約的費(fèi)用 表2工作參數(shù)表工作代碼工作編號作業(yè)時(shí)間/

8、天費(fèi)用/元可縮短時(shí)間趕工費(fèi)用趕工費(fèi)率（元/天）正常趕工正常趕工A1-2538001200B1-310830003360C2-510715001740D2-68624002800E2-411840004450F3-6181456006160G4-56412001440H5-612102000218012、根據(jù)表3給出的資料，繪制雙代號網(wǎng)絡(luò)圖，找出關(guān)鍵路線，并簡要說明如要縮短工期，應(yīng)首先考慮哪些工作工作緊前工作持續(xù)時(shí)間工作緊前工作持續(xù)時(shí)間ABCDEFGHIJ-AAB,CDDDGHD2114143707014111KLMNOPQRSJDLDNOE,F,PQ,I,KM,某分部

9、工程雙代號時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃如圖1所示，根據(jù)該圖確定各項(xiàng)工作的時(shí)間參數(shù)，請將結(jié)果直接填寫在表4中相應(yīng)位置。 圖1 雙代號時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃 表4工作時(shí)間參數(shù)序號 工作名稱 工作代號 ESEFLSLFTFFF備注 1A12       2B23       3C27       4D34       5E36       6G45       7H58