應(yīng)用運(yùn)籌學(xué)11-12-1期末考試試卷

1、年級：_ 專業(yè)：_ 班級：_ 學(xué)號：_ 姓名：_.裝.訂.線誠信應(yīng)考 考出水平 考出風(fēng)格浙江大學(xué)城市學(xué)院2011 2012學(xué)年第一學(xué)期期末考試試卷應(yīng)用運(yùn)籌學(xué)開課單位： 計(jì)算分院 ；考試形式：閉卷；考試時間： _2012_年_1_月_13_日；所需時間： 120 分鐘題序一二三四五六七八九總 分得分評卷人（注：答案全部寫在答卷上）得分一判斷題 (本大題共10小題，每題1分，共10分。)在你認(rèn)為正確的敘述后面打“”，錯誤的后面打“”。1 線性規(guī)劃中“線性”的含義是指約束條件關(guān)于決策變量是線性等式或不等式，而對目標(biāo)函數(shù)沒有要求。 ( )2 線性規(guī)劃求解的結(jié)果可能會有無窮多個最優(yōu)解，但解相應(yīng)的最優(yōu)值都

2、相等。 ( )3 若線性規(guī)劃有最優(yōu)解則其可行域一定有界。 ( )4 若線性規(guī)劃無解，則其可行域是空集。 ( )5 影子價(jià)格為0時，表明該資源未得到充分利用。 ( )6 平衡運(yùn)輸問題的約束是資源約束。 ( )7 指派問題是運(yùn)輸問題的特例。 ( )8 匈牙利法是對運(yùn)輸問題求最小值的一種求解方法。 ( )9 點(diǎn)vi表示自來水廠及用戶，vi與vj之間的邊表示兩點(diǎn)間可以鋪設(shè)管道，權(quán)為vi與vj間鋪設(shè)管道的距離或費(fèi)用，極值問題是如何鋪設(shè)管道，將自來水送到其他5個用戶并且使總的費(fèi)用最小。這屬于最短路問題。 ( )10郵遞員從郵局vi出發(fā)要經(jīng)過每一條邊將郵件送到用戶手中，最后回到郵局vi，如何安排路線使總路程

3、最短。這屬于運(yùn)輸問題。 ( )得分二填空題 (本題每行1分，共10分。)根據(jù)靈敏度報(bào)告進(jìn)行分析，對下列情形能否得到相應(yīng)的最優(yōu)值和最優(yōu)解？或是只能重新求解？在相應(yīng)方格打“”。靈敏度報(bào)告最優(yōu)值最優(yōu)解重新求解單個目標(biāo)函數(shù)系數(shù)變動且在變動范圍內(nèi)多個目標(biāo)函數(shù)系數(shù)變動且在變動范圍內(nèi)單個約束右端值變動且在變動范圍內(nèi)多個約束右端值變動且在變動范圍內(nèi)約束條件系數(shù)變化增加一個新變量增加多個新變量增加一個約束條件增加多個約束條件同時增加變量和約束條件得分三分析解答題 (共10分。)某公司目前正在制造兩種產(chǎn)品，產(chǎn)品I和產(chǎn)品II，現(xiàn)在產(chǎn)品I和產(chǎn)品II的每天產(chǎn)量分別為30個和120個，工資負(fù)責(zé)制造的副總經(jīng)理希望了解是否可

4、以通過改變這兩種產(chǎn)品的數(shù)量來提高公司的利潤。公司制造每個產(chǎn)品所需的加工工時和每個車間的加工能力（每天加工工時數(shù)）如下表產(chǎn)品I和產(chǎn)品II一所示：生產(chǎn)兩種產(chǎn)品的有關(guān)數(shù)據(jù)車間產(chǎn)品I產(chǎn)品II車間能力12030020354032244041.21.5300每件產(chǎn)品利潤（元）500400利用EXCEL進(jìn)行線性規(guī)劃建模求解后的表格（表格一）和敏感性性分析報(bào)告（表格二）如下：問：（1） 假設(shè)生產(chǎn)的全部產(chǎn)品都能銷售出去，請確定最優(yōu)產(chǎn)品組合，即確定使得總利潤最大的產(chǎn)品I和產(chǎn)品II每天的產(chǎn)量。（2） 在問題（1）所求得的最優(yōu)產(chǎn)品組合中，在1、2、3、4四個車間中哪些車間的能力還有剩余，剩余多少？（3） 1、2、3、

5、4四個車間能力的影子價(jià)格各為多少？即1、2、3、4四個車間的能力分別增加一個加工工時數(shù)時能給公司帶來多少的額外利潤？ （4） 當(dāng)產(chǎn)品I的單位利潤不變，產(chǎn)品II的單位利潤在什么范圍內(nèi)變化時，此最優(yōu)解不變？ 分別討論各個單位產(chǎn)品利潤在什么范圍內(nèi)變化時，原生產(chǎn)計(jì)劃不變。當(dāng)產(chǎn)品II的單位利潤不變，產(chǎn)品I的單位利潤在什么范圍內(nèi)變化時，此最優(yōu)解不變？（5） 當(dāng)產(chǎn)品I的單位利潤從500元降為450元，而產(chǎn)品II的單位利潤從400元降為430元時，最優(yōu)解是否改變？表格一、EXCEl建模表格表格二、第三題的敏感性分析報(bào)告得分四計(jì)算解答題 (共20分。)某公司鋪設(shè)光導(dǎo)纖維網(wǎng)絡(luò)問題（最小支撐樹問題）。某公司的管理層

6、已經(jīng)決定鋪設(shè)最先進(jìn)的光導(dǎo)纖維網(wǎng)絡(luò)，為它的主要中心之間提供高速通信（數(shù)據(jù)、聲音和圖像）。圖一中的節(jié)點(diǎn)顯示了該公司主要中心（包括公司的總部、巨型計(jì)算機(jī)、研究區(qū)、生產(chǎn)和配送中心等八個位置）的分布圖。虛線是鋪設(shè)纖維光纜可能的位置。每條虛線旁邊的數(shù)字表示了如果選擇在這個位置鋪設(shè)光纜需要花費(fèi)的成本。（分別用破圈法和避圈法、Prim算法和Sollion算法求解，給出算法步驟，不用建立模型。）圖一、第三題的節(jié)點(diǎn)分布圖22526752334CEHABFDGF6得分五計(jì)算解答題 (共10分。)指派問題。根據(jù)下面的費(fèi)用矩陣，采用匈牙利算法給出最優(yōu)的指派方案。（給出算法步驟，不用建立模型。） 得分六線性規(guī)劃建模題(共

7、10分。)解題要求：給出三要素，建立相應(yīng)的規(guī)劃模型。（生產(chǎn)與存儲問題問題）。某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表三所示。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用1500元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護(hù)）費(fèi)用最小的決策。表格三、各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本季度生產(chǎn)能力（臺）單位成本（萬元）12510.823511.133011.041011.3（1） 以各季度的產(chǎn)量及庫存為決策變量，建立線性規(guī)劃模型；（2） 以第i季度生產(chǎn)的第j季度

8、交貨的柴油機(jī)數(shù)為決策變量，建立產(chǎn)大于銷的運(yùn)輸問題模型。 得分七優(yōu)化建模題 (共10分。)解題要求：給出三要素，建立相應(yīng)的規(guī)劃模型。圖二、第五題的城市網(wǎng)絡(luò)圖333333313232467910512244118224311441) 在進(jìn)行貨郎擔(dān)問題試求解時，有回路“2>3>6>5>2”，“4>7>8>4”，“9<>12”，給出貨郎擔(dān)問題的數(shù)學(xué)模型；2) 給出上圖求解中國郵路問題的數(shù)學(xué)模型； 得分八最大流建模題(共10分。) 解題要求：給出三要素，建立相應(yīng)的規(guī)劃模型。計(jì)劃編制問題。某市政工程公司在未來58月份內(nèi)需完成4項(xiàng)工程：修建一條地下通道、

9、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表3。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應(yīng)如何分配勞動力完成所有工程，是否能按期完成？(1) 畫出將該問題轉(zhuǎn)化為最大流問題的網(wǎng)絡(luò)圖；(2) 給出求解最大流問題的數(shù)學(xué)模型；工程工期需要勞動力（人）A.地下通道57月100B.人行天橋67月80C.新建道路58月200D.道路維修 8月80 得分九整數(shù)規(guī)劃建模題(共10分。)解題要求：給出三要素，建立相應(yīng)的規(guī)劃模型。某速遞公司提供快遞服務(wù)，所有快件兩天內(nèi)都能送到?？旒谕砩系竭_(dá)各收集中心，并于第二天早上裝上送往該地區(qū)的幾輛卡車。因?yàn)榭爝f行業(yè)的競爭

10、加劇，為了減少平均的送貨時間，必須將各包裹根據(jù)目的地的地理位置加以分類，并分裝到不同的卡車上。假設(shè)每天有三輛卡車提供快遞服務(wù)，卡車可行的路線有10條，如表格五所示（其中各列的數(shù)字表示送貨的先后次序）。公司有特制軟件，該軟件第一步就是根據(jù)當(dāng)天要送快遞的地點(diǎn)，找出各卡車可能的路線。假設(shè)當(dāng)天有9個快件需要送到9個地點(diǎn)，請根據(jù)各種可能的路線以及所需時間的估計(jì)值，建立相應(yīng)的0-1整數(shù)規(guī)劃模型，為每輛卡車選出一條路線，以最短的總時間完成各地的送貨工作。表格五 某速遞公司的路線選擇的相關(guān)數(shù)據(jù)快遞地點(diǎn)可行的路線12345678910A111B21222C3333D211E223F12G3123H131I342

11、時間(小時)6475465376年級：_ 專業(yè)：_ 班級：_ 學(xué)號：_ 姓名：_.裝.訂.線誠信應(yīng)考 考出水平 考出風(fēng)格浙江大學(xué)城市學(xué)院2011 2012學(xué)年第一學(xué)期期中末考試試卷應(yīng)用運(yùn)籌學(xué)題序一二三四總 分得分評卷人得分一判斷題(本大題共10小題，每題1分，共10分。) 題號12345678910得分二填空題(本大題共30空，每空1分，其中第一小題每行1分，共30分。) 靈敏度報(bào)告最優(yōu)值最優(yōu)解重新求解單個目標(biāo)函數(shù)系數(shù)變動且在變動范圍內(nèi)多個目標(biāo)函數(shù)系數(shù)變動且在變動范圍內(nèi)單個約束右端值變動且在變動范圍內(nèi)多個約束右端值變動且在變動范圍內(nèi)約束條件系數(shù)變化增加一個新變量增加多個新變量增加一個約束條件增加多個約束條件同時增加變量和約束條件得分三分析解答題 (共10分。)得分四計(jì)算解答題 (共20分。)得分五計(jì)算解答題 (共10分。)解題要求：給出三要素，