運籌學第三版試卷及答案一、單項選擇題（每題2分，共20分）1.線性規(guī)劃問題的標準形式是（）。A.所有變量都非負B.所有約束條件都是等式C.所有變量都非負，所有約束條件都是等式D.所有變量都非負，所有約束條件都是不等式答案：C2.單純形法中，若引入人工變量后，最優(yōu)解中人工變量的值為（）。A.0B.正數(shù)C.負數(shù)D.任意實數(shù)答案：A3.動態(tài)規(guī)劃中，狀態(tài)轉移方程的作用是（）。A.確定最優(yōu)策略B.確定狀態(tài)的最優(yōu)值C.確定狀態(tài)的次優(yōu)值D.確定狀態(tài)的可行值答案：B4.整數(shù)規(guī)劃問題中，變量取值限制為（）。A.任意實數(shù)B.任意整數(shù)C.非負整數(shù)D.非負實數(shù)答案：B5.運輸問題中，若某條線路的運量為0，則稱該線路為（）。A.基線路B.非基線路C.退化線路D.非退化線路答案：B6.目標規(guī)劃問題中，目標函數(shù)是（）。A.最小化目標與實際值之間的偏差B.最大化目標與實際值之間的偏差C.最小化目標與實際值之間的絕對偏差D.最大化目標與實際值之間的絕對偏差答案：A7.網絡流問題中，最大流問題的目標是（）。A.最小化成本B.最大化流量C.最小化時間D.最大化利潤答案：B8.決策樹問題中，期望值的計算方法是（）。A.概率乘以結果值的和B.結果值乘以概率的和C.概率乘以結果值的差D.結果值乘以概率的差答案：A9.敏感性分析中，目標函數(shù)系數(shù)的變化范圍稱為（）。A.允許值B.影子價格C.靈敏度D.臨界值答案：D10.排隊論中，M/M/1隊列的特點是（）。A.到達服從泊松分布，服務服從指數(shù)分布，單服務臺B.到達服從指數(shù)分布，服務服從泊松分布，單服務臺C.到達服從泊松分布，服務服從指數(shù)分布，多服務臺D.到達服從指數(shù)分布，服務服從泊松分布，多服務臺答案：A二、填空題（每題2分，共20分）1.線性規(guī)劃問題中，目標函數(shù)的最優(yōu)解一定在可行域的______上。答案：頂點2.單純形法中，如果目標函數(shù)的最優(yōu)值為負無窮，則說明該線性規(guī)劃問題是______。答案：無界3.動態(tài)規(guī)劃問題中，狀態(tài)的最優(yōu)值可以通過______方程來確定。答案：貝爾曼4.整數(shù)規(guī)劃問題中，變量的取值限制為______。答案：整數(shù)5.運輸問題中，若某條線路的運量為0，則稱該線路為______。答案：非基線路6.目標規(guī)劃問題中，目標函數(shù)是最小化目標與實際值之間的______。答案：偏差7.網絡流問題中，最大流問題的目標是______流量。答案：最大化8.決策樹問題中，期望值的計算方法是概率乘以結果值的______。答案：和9.敏感性分析中，目標函數(shù)系數(shù)的變化范圍稱為______。答案：臨界值10.排隊論中，M/M/1隊列的特點是到達服從______分布，服務服從指數(shù)分布，單服務臺。答案：泊松三、計算題（每題10分，共30分）1.已知線性規(guī)劃問題的標準形式為：MaxZ=3x1+2x2s.t.x1+x2≤102x1+x2≤15x1,x2≥0請使用單純形法求解該問題，并給出最優(yōu)解。答案：首先，將線性規(guī)劃問題轉化為標準形式，添加松弛變量x3和x4，得到：MaxZ=3x1+2x2s.t.x1+x2+x3=102x1+x2+x4=15x1,x2,x3,x4≥0然后，使用單純形法求解，得到最優(yōu)解為x1=5，x2=5，x3=0，x4=0，Z=25。2.已知動態(tài)規(guī)劃問題的狀態(tài)轉移方程為：V(k)=max{V(k-1)+3,V(k-2)+2}初始狀態(tài)V(0)=0，V(1)=1，求V(3)的值。答案：根據(jù)狀態(tài)轉移方程，可以計算得到：V(2)=max{V(1)+3,V(0)+2}=max{1+3,0+2}=4V(3)=max{V(2)+3,V(1)+2}=max{4+3,1+2}=7所以，V(3)=7。3.已知整數(shù)規(guī)劃問題：MinZ=x1+2x2s.t.x1+x2≥10x1,x2≥0請使用分支定界法求解該問題，并給出最優(yōu)解。答案：首先，將整數(shù)規(guī)劃問題轉化為線性規(guī)劃問題，忽略整數(shù)約束，得到：MinZ=x1+2x2s.t.x1+x2≥10x1,x2≥0求解線性規(guī)劃問題，得到最優(yōu)解x1=10，x2=0，Z=10。然后，使用分支定界法，對x1和x2進行分支，得到兩個子問題：子問題1：MinZ=x1+2x2s.t.x1+x2≥10x1≥1x1,x2≥0子問題2：MinZ=x1+2x2s.t.x1+x2≥10x1=0x1,x2≥0求解子問題1，得到最優(yōu)解x1=1，x2=9，Z=11。求解子問題2，得到最優(yōu)解x1=0，x2=10，Z=20。比較兩個子問題的最優(yōu)值，選擇較小的值，即Z=11，對應的解為x1=1，x2=9。所以，整數(shù)規(guī)劃問題的最優(yōu)解為x1=1，x2=9，Z=11。四、簡答題（每題5分，共30分）1.請簡述線性規(guī)劃問題的基本性質。答案：線性規(guī)劃問題的基本性質包括：1.線性：目標函數(shù)和約束條件都是線性的。2.非負性：所有變量都非負。3.凸性：可行域是一個凸多面體。4.有界性：可行域是有界的。5.極點性：最優(yōu)解一定在可行域的頂點上。2.請簡述單純形法的基本步驟。答案：單純形法的基本步驟包括：1.將線性規(guī)劃問題轉化為標準形式。2.引入松弛變量，將不等式約束轉化為等式約束。3.選擇一個初始基本可行解。4.計算目標函數(shù)的系數(shù)，確定進入基的變量和離開基的變量。5.進行主元變換，更新基本可行解。6.檢查是否達到最優(yōu)解，如果達到，則停止；否則，返回步驟4。3.請簡述動態(tài)規(guī)劃問題的基本思想。答案：動態(tài)規(guī)劃問題的基本思想是將復雜問題分解為一系列簡單問題，通過求解簡單問題來求解復雜問題。具體步驟包括：1.確定問題的狀態(tài)和決策。2.確定狀態(tài)轉移方程。3.確定初始狀態(tài)和邊界條件。4.根據(jù)狀態(tài)轉移方程，從初始狀態(tài)開始，逐步求解各個狀態(tài)的最優(yōu)值。5.根據(jù)最優(yōu)值，確定最優(yōu)策略。4.請簡述整數(shù)規(guī)劃問題的特點。答案：整數(shù)規(guī)劃問題的特點包括：1.變量的取值限制為整數(shù)。2.問題求解難度較大，需要使用特殊的算法，如分支定界法、割平面法等。3.整數(shù)規(guī)劃問題可以轉化為線性規(guī)劃問題，但需要添加額外的約束條件。4.整數(shù)規(guī)劃問題在實際應用中具有重要意義，如資源分配、調度等問題。5.請簡述運輸問題的基本模型。答案：運輸問題的基本模型包括：1.供應點：表示貨物的供應地，具有供應量限制。2.需求點：表示貨物的需求量，具有需求量限制。3.運輸成本：表示從供應點到需求點的運輸成本。4.運輸量：表示從供應點到需求點的運輸量。5.目標函數(shù)：最小化總運輸成本。6.請簡述目標規(guī)劃問題的基本