2/4《運籌學(xué)》期末試卷2學(xué)號姓名得分得分一、(2’×6)選擇題：線性規(guī)劃可行域的頂點一定是（）A.基本可行解B.非基本解C.非可行解D.最優(yōu)解設(shè)線性規(guī)劃的約束條件，則基本解為（）A.(0,4,3,4)B.(0,0,12,7)C.(4,0,,0)D.(3,0,1,3)用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在目標(biāo)函數(shù)中的系數(shù)為（）A.0B.-1C.MD.–M對于m個產(chǎn)地，n個銷地的平衡運輸問題，其基變量的個數(shù)為（）A.B.C.D.在求解整數(shù)規(guī)劃問題時，不可能出現(xiàn)的情況是（）A.唯一最優(yōu)解B.無可行解C.有限多個最優(yōu)解D.無窮多個最優(yōu)解下列說法正確的是（）A．運輸問題不一定存在最優(yōu)解。B．整數(shù)規(guī)劃解的目標(biāo)函數(shù)值優(yōu)于其相應(yīng)的線性規(guī)劃解的目標(biāo)函數(shù)值。C．動態(tài)規(guī)劃中，定義狀態(tài)時應(yīng)保證各個階段所作決策的相互獨立性。D．動態(tài)規(guī)劃分階段順序不同，則結(jié)果不同。得分二、(2’×6)填空題：線性規(guī)劃的最優(yōu)解是，它的第1、2個約束中松弛變量等于。在資源配置優(yōu)化的線性規(guī)劃問題中，若某資源有剩余，則該資源的影子價格為。一棵有條邊的樹，其頂點數(shù)為。可用于求解混合整數(shù)規(guī)劃的方法是。在求運輸問題的初始基本可行解的方法中，通常最接近最優(yōu)解的方法是。在網(wǎng)絡(luò)計劃中，關(guān)鍵工序的單時差為。得分三、(12’)考慮線性規(guī)劃問題：這里是一個正數(shù)。假定給約束條件加上松弛變量使得問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式。考慮以為基變量的基本解，證明其為基本可行解。證明（1）中定義的基本解是最優(yōu)的。 (已知)得分四、(10’)某企業(yè)擬生產(chǎn)三種產(chǎn)品，每種產(chǎn)品的單位勞動力和原材料需求量如下：產(chǎn)品勞動力（小時/件）原材料（公斤/件）134243356三種產(chǎn)品的利潤分別為25元/件，30元/件，22元/件。現(xiàn)該企業(yè)可在如下兩處廠址選擇一處，兩地的主要區(qū)別在于勞動力和原材料的供給能力不同（見下表）。廠址可提供的勞動力（小時）可提供的原材料（公斤）1100100290120此外，由于生產(chǎn)機(jī)器的特殊性，如果產(chǎn)品3被生產(chǎn)，則其產(chǎn)量不得低于3件。請問該企業(yè)應(yīng)在何處建廠以使總利潤最大（建立適當(dāng)?shù)臄?shù)學(xué)規(guī)劃模型，不必求解）。得分五、(12’)現(xiàn)要在5個工人中確定4個人來分別完成4項工作中的一項。由于每個工人的技術(shù)特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如下表。工作工人ABCDI9437II4656III5475IV7523V10674試找出一個工作分配方案，使總工時最小。得分六、(10’)假設(shè)有9個城市之間要架設(shè)電纜，已知城市之間的可行線路和費用如下圖所示：v2v88v2v88v3256275462754v7v775v1v6v1v6331334133411v5vv5v9v44141試問：要將所有城市連通，至少需要幾條連接邊？試求一個費用最小的架設(shè)方案。得分七、(12’)如圖給出的是連結(jié)某產(chǎn)品產(chǎn)地和銷地的交通圖。弧表示從到的運輸線，弧旁的數(shù)字表示這條運輸線的最大通過能力。現(xiàn)要求制定一個運輸方案，使得從運到的產(chǎn)品數(shù)量最多，指出該網(wǎng)絡(luò)的最大流量和最小割集。513951394656449105得分八、(12’)一項小修計劃包括的工作如下表所示。工作網(wǎng)絡(luò)說明最少工時（d）正常工時（d）成本斜率（元）A(1,2)6920B(1,3)5825C(1,4)101530D(2,4)3510E(3,4)6915F(4,5)1240正常計劃工期與最小工期各是多少天？日常經(jīng)營費為50元/天，最佳工期應(yīng)是多少天？列出每項工作的相應(yīng)工時。《運籌學(xué)》期末試卷2答案得分一、(2’×6)選擇題：1.A2.C3.D4.C5.D6.C得分二、(2’×6)填空題：1.（0,2）2.03.n+14.多階段決策5.伏格爾法6.0得分三、(12’)考慮線性規(guī)劃問題：這里是一個正數(shù)。假定給約束條件加上松弛變量使得問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式。考慮以為基變量的基本解，證明其為基本可行解。證明（1）中定義的基本解是最優(yōu)的。 (已知)解：(1)以為基變量，由約束條件可以得到： ,,, 因此，該基本解是基本可行解。(2)利用最優(yōu)性條件，若則為最優(yōu)解。這里， ， ，， 所以，。得分四、(10’)某企業(yè)擬生產(chǎn)三種產(chǎn)品，每種產(chǎn)品的單位勞動力和原材料需求量如下：產(chǎn)品勞動力（小時/件）原材料（公斤/件）134243356三種產(chǎn)品的利潤分別為25元/件，30元/件，22元/件。現(xiàn)該企業(yè)可在如下兩處廠址選擇一處，兩地的主要區(qū)別在于勞動力和原材料的供給能力不同（見下表）。廠址可提供的勞動力（小時）可提供的原材料（公斤）1100100290120此外，由于生產(chǎn)機(jī)器的特殊性，如果產(chǎn)品3被生產(chǎn)，則其產(chǎn)量不得低于3件。請問該企業(yè)應(yīng)在何處建廠以使總利潤最大（建立適當(dāng)?shù)臄?shù)學(xué)規(guī)劃模型，不必求解）。解：設(shè)分別為產(chǎn)品1,2,3的生產(chǎn)量，M是一個很大的正數(shù)，并引入0-1變量,maxs.t.,得分五、(12’)現(xiàn)要在5個工人中確定4個人來分別完成4項工作中的一項。由于每個工人的技術(shù)特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如下表。工作工人ABCDI9437II4656III5475IV7523V10674試找出一個工作分配方案，使總工時最小。解：本題屬于“不平衡”指派問題，故先虛擬一項工作E，設(shè)每人完成E所用的時間都是“0”，從而轉(zhuǎn)化為5個人完成5項工作的平衡指派問題。再用匈牙利法求解，得最優(yōu)解為：I—C，II—A，III—B，IV—D，V—E，即應(yīng)安排工人I、II、III、IV分別完成工作C、A、B、D，此時總工時最小為3+4+4+3=14。得分六、(10’)假設(shè)有9個城市之間要架設(shè)電纜，已知城市之間的可行線路和費用如下圖所示：v2v88v2v88v3256275462754v7v775v1v6v1v6331334133411v5vv5v9v44141試問：要將所有城市連通，至少需要幾條連接邊？試求一個費用最小的架設(shè)方案。解：1）要將所有城市連通，至少需要8條連接邊。2）即求最小支撐樹，最小費用為17。11311342231得分七、(12’)如圖給出的是連結(jié)某產(chǎn)品產(chǎn)地和銷地的交通圖。弧表示從到的運輸線，弧旁的數(shù)字表示這條運輸線的最大通過能力。現(xiàn)要求制定一個運輸方案，使得從運到的產(chǎn)品數(shù)量最多，指出該網(wǎng)絡(luò)的最大流量和最小割集。51351394656449105解：用標(biāo)號法得到的最終結(jié)果為：13(11)9(9)13(11)9(9)4(0)5(5)6(6)5(4)6(4)4(3)4(3)9(9)10(8)5(5)因此，該網(wǎng)絡(luò)的最大流量為20，最小割集為。得分八、(12’)一項小修計劃包括的工作如下表所示。工作網(wǎng)絡(luò)說明最少工時（d）正常工時（d）成本斜率（元）A(1,2)6920B(1,3)5825C(1,4)101530D(2,4)3510E(3,4)6915F(4,5)1240正常計劃工期與最小工期各是多少天？日常經(jīng)營費為50元/天，最佳工期應(yīng)是多少天？列出每項工作的相應(yīng)工時。解：113245ABDCEF(6,9,20)(10,15,30)(5,8,25)(3,5,10)(6,9,15)(1,2,40)關(guān)鍵路徑：1345工期19天。首先選擇工作E壓縮（費用15），可壓縮2天。此時，關(guān)鍵路徑為2條：145和1345工期17天。首先選擇工作F壓縮（費用40），可壓縮1天；