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

1、《運(yùn)籌學(xué)》試卷卷第1頁共8頁運(yùn)籌學(xué)期末考試試卷運(yùn)籌學(xué)期末考試試卷一、某林業(yè)公司有一、某林業(yè)公司有6片林區(qū)，為便于樹木的維護(hù)和砍伐運(yùn)輸，需要在林區(qū)之間修建公片林區(qū)，為便于樹木的維護(hù)和砍伐運(yùn)輸，需要在林區(qū)之間修建公路，并保證任意兩個林區(qū)都可以通過這些公路彼此連通。已知鋪設(shè)公路的費(fèi)用平均為路，并保證任意兩個林區(qū)都可以通過這些公路彼此連通。已知鋪設(shè)公路的費(fèi)用平均為850元米，每兩片林區(qū)之間的距離如下表所示。現(xiàn)要最小化總鋪設(shè)成本。請回答以下問米，

2、每兩片林區(qū)之間的距離如下表所示?，F(xiàn)要最小化總鋪設(shè)成本。請回答以下問題：題：1）這是一個最小支撐樹問題，為什么？）這是一個最小支撐樹問題，為什么？(5分)2）該林業(yè)公司應(yīng)該如何鋪設(shè)公路？寫出算法步驟。）該林業(yè)公司應(yīng)該如何鋪設(shè)公路？寫出算法步驟。(10分)3）最小成本是多少？）最小成本是多少？(結(jié)果四舍五入保留兩位小數(shù)結(jié)果四舍五入保留兩位小數(shù))(5分)解答：1)因?yàn)樵搯栴}滿足最小支撐樹問題的所有假設(shè)①給定了網(wǎng)絡(luò)中可供選擇的邊及其成本(等價于

3、邊的長度即距離)；②要插入足夠多的邊使圖連通；③目標(biāo)是要使總成本最小。2)(a)用避圈法求解該問題最為簡單。避圈法的求解步驟為：開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已被選取的邊不構(gòu)成圈(如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條)。選邊的過程如下圖所示(每條邊上標(biāo)記的第一個數(shù)字為長度，小括號里的數(shù)字為第幾次被選中)；(b)破圈法的求解步驟：任取一個圈，從圈中去掉權(quán)最大的邊(如果有兩

4、條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條)。在余下的圖中，重復(fù)這個步驟，一直到圖中不含圈為止(去邊的同時必須保證圖的連通性)。(c)教材給定的啟發(fā)式算法：第一步，選擇成本最低的備選邊；第二步，在一個已經(jīng)有一條邊連接的節(jié)點(diǎn)和另一個還沒有邊連接的節(jié)點(diǎn)之間選擇成本最低的備選邊；第三步，重復(fù)第二個步驟，直到所有的節(jié)點(diǎn)都有一條邊(可能會有多于一條邊)與其相連，此時就得到了一個最小支撐樹(當(dāng)有幾條邊同時是成本最低的邊時，任意選擇一條邊)。

5、說明：只要算法步驟正確，得到了正確結(jié)果即可給分。3)最小成本為：(0.50.70.80.91.2)850=3485(千元).《運(yùn)籌學(xué)》試卷卷第3頁共8頁解答：決策變量為各種不同原材料的使用量，其中鐵合金1為噸，鐵合金2為噸，1x2x銅合金為噸，鋁合金為噸。3x4x目標(biāo)函數(shù)是最小化總成本(單位：元)：4321100240250200minxxxxC????約束條件包括：(1)鋼的產(chǎn)量要求5004321????xxxx(2)資源可用量的要求

6、???????????3002003004004321xxxx(3)品質(zhì)要求?????????????????????????????????????????????????????????????????????%65.1%2.1%4%8.0%3.1%2.1%2.1%4%8.0%3.1%6.0%4.0%96%4.0%4.0%96%3%3%5.2%2%3%5.243214321432143214321434321434321214321

7、21xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx(4)決策變量的非負(fù)要求???????????00004321xxxx三、某煉油廠根據(jù)計劃每季度需至少供應(yīng)合同單位汽油三、某煉油廠根據(jù)計劃每季度需至少供應(yīng)合同單位汽油15萬噸、煤油萬噸、煤油12萬噸、重油萬噸、重油12萬噸。該廠可從俄羅斯或中東地區(qū)購買原油進(jìn)行提煉。俄羅斯的原油采購成本萬噸。該廠可從俄羅斯或中東地區(qū)購買原油進(jìn)行提煉。俄羅斯的原油采購成本(