2/4《運籌學》期末試卷2學號姓名得分得分一、(2’×6)選擇題：線性規劃可行域的頂點一定是（）A.基本可行解B.非基本解C.非可行解D.最優解設線性規劃的約束條件，則基本解為（）A.(0,4,3,4)B.(0,0,12,7)C.(4,0,,0)D.(3,0,1,3)用大M法求目標函數為極大值的線性規劃問題時，引入的人工變量在目標函數中的系數為（）A.0B.-1C.MD.–M對于m個產地，n個銷地的平衡運輸問題，其基變量的個數為（）A.B.C.D.在求解整數規劃問題時，不可能出現的情況是（）A.唯一最優解B.無可行解C.有限多個最優解D.無窮多個最優解下列說法正確的是（）A．運輸問題不一定存在最優解。B．整數規劃解的目標函數值優于其相應的線性規劃解的目標函數值。C．動態規劃中，定義狀態時應保證各個階段所作決策的相互獨立性。D．動態規劃分階段順序不同，則結果不同。得分二、(2’×6)填空題：線性規劃的最優解是，它的第1、2個約束中松弛變量等于。在資源配置優化的線性規劃問題中，若某資源有剩余，則該資源的影子價格為。一棵有條邊的樹，其頂點數為。可用于求解混合整數規劃的方法是。在求運輸問題的初始基本可行解的方法中，通常最接近最優解的方法是。在網絡計劃中，關鍵工序的單時差為。得分三、(12’)考慮線性規劃問題：這里是一個正數。假定給約束條件加上松弛變量使得問題轉化為標準形式。考慮以為基變量的基本解，證明其為基本可行解。證明（1）中定義的基本解是最優的。 (已知)得分四、(10’)某企業擬生產三種產品，每種產品的單位勞動力和原材料需求量如下：產品勞動力（小時/件）原材料（公斤/件）134243356三種產品的利潤分別為25元/件，30元/件，22元/件。現該企業可在如下兩處廠址選擇一處，兩地的主要區別在于勞動力和原材料的供給能力不同（見下表）。廠址可提供的勞動力（小時）可提供的原材料（公斤）1100100290120此外，由于生產機器的特殊性，如果產品3被生產，則其產量不得低于3件。請問該企業應在何處建廠以使總利潤最大（建立適當的數學規劃模型，不必求解）。得分五、(12’)現要在5個工人中確定4個人來分別完成4項工作中的一項。由于每個工人的技術特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如下表。工作工人ABCDI9437II4656III5475IV7523V10674試找出一個工作分配方案，使總工時最小。得分六、(10’)假設有9個城市之間要架設電纜，已知城市之間的可行線路和費用如下圖所示：v2v88v2v88v3256275462754v7v775v1v6v1v6331334133411v5vv5v9v44141試問：要將所有城市連通，至少需要幾條連接邊？試求一個費用最小的架設方案。得分七、(12’)如圖給出的是連結某產品產地和銷地的交通圖。弧表示從到的運輸線，弧旁的數字表示這條運輸線的最大通過能力。現要求制定一個運輸方案，使得從運到的產品數量最多，指出該網絡的最大流量和最小割集。51394651394656449105得分八、(12’)一項小修計劃包括的工作如下表所示。工作網絡說明最少工時（d）正常工時（d）成本斜率（元）A(1,2)6920B(1,3)5825C(1,4)101