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

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

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

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

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

5、說(shuō)明：只要算法步驟正確，得到了正確結(jié)果即可給分。3)最小成本為：(0.50.70.80.91.2)850=3485(千元).《運(yùn)籌學(xué)》試卷卷第3頁(yè)共8頁(yè)解答：決策變量為各種不同原材料的使用量，其中鐵合金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三、某煉油廠(chǎng)根據(jù)計(jì)劃每季度需至少供應(yīng)合同單位汽油三、某煉油廠(chǎng)根據(jù)計(jì)劃每季度需至少供應(yīng)合同單位汽油15萬(wàn)噸、煤油萬(wàn)噸、煤油12萬(wàn)噸、重油萬(wàn)噸、重油12萬(wàn)噸。該廠(chǎng)可從俄羅斯或中東地區(qū)購(gòu)買(mǎi)原油進(jìn)行提煉。俄羅斯的原油采購(gòu)成本萬(wàn)噸。該廠(chǎng)可從俄羅斯或中東地區(qū)購(gòu)買(mǎi)原油進(jìn)行提煉。俄羅斯的原油采購(gòu)成本(