廣東工業(yè)大學-運籌學-試卷答案.doc

廣東工業(yè)大學考試試卷 ( A )課程名稱: 運籌學B 試卷滿分 100 分考試時間: 2008 年 7月 11 日 (第 20 周 星期 五 )題 號一二三四五六七八九十總分評卷得分評卷簽名復核得分復核簽名一、判斷題（每小題2分，共20分，無須改錯）1標準形式的線性規(guī)劃模型中決策變量的取值可以無任何限制。（ ）2線性規(guī)劃問題的可行域一定非空。（ ）3若線性規(guī)劃問題無可行解，則其對偶問題一定無可行解。（ ）4任何一個無向圖中偶點的個數(shù)不能是奇數(shù)。（ ）5對產大于銷的運輸問題，可通過添加假想的銷地化為產銷平衡運輸問題。（ ） 6目標規(guī)劃中任意一個目標約束的正負偏差變量不可能同時為正數(shù)。（ ）7若指派問題的系數(shù)矩陣中某行元素都減去同一個常數(shù)，則得到的新矩陣為系數(shù)矩陣的指派問題與原問題有同樣的最優(yōu)解（ ）8增廣鏈上的每條后向邊都為零流邊。（ ）9動態(tài)規(guī)劃的最優(yōu)策略應該具有性質，無論先前的狀態(tài)與決策如何，當前的決策應該是最優(yōu)。（ ）10矩陣對策就是二人有限零和對策。（ ）學 院： 專 業(yè)： 學 號： 姓 名： 裝 訂 線二、單項選擇題（每小題2分，共20分）1下列哪個模型是線性規(guī)劃模型 A B C D 2若用單純形法求解線性規(guī)劃問題得到的最終單純形表中，基變量不含人工變量，且非基變量的檢驗數(shù)均非零，則線性規(guī)劃問題為下面的情形 A有唯一最優(yōu)解， B有無窮多個最優(yōu)解， C無界解， D無可行解。3若線性規(guī)劃的原問題不存在最優(yōu)解，則對偶問題 A可能存在最優(yōu)解，B不存在最優(yōu)解， C一定是無可行解， D一定是無界解。4若線性規(guī)劃問題的某個資源常數(shù)發(fā)生變化，則在最終單純形表中這一變化 A對檢驗數(shù)存在影響， B對b列數(shù)存在影響， C對該資源常數(shù)所在行的數(shù)存在影響， D對所有數(shù)都無影響。5對于有m個產地n個銷地的產銷平衡運輸問題的表上作業(yè)法求解，下面不正確的說法是 A每個空格有唯一的閉回路， B數(shù)字格的個數(shù)為m+n-1， C沃格爾法得到的調運方案是最優(yōu)方案， D若存在負檢驗數(shù)，則調運方案仍可改進。6對于目標規(guī)劃問題的求解，在滿足一個目標時 A必須同時考慮優(yōu)先級別較低的目標， B不得違背已經得到滿足的優(yōu)先級別更高的目標，C不必顧慮優(yōu)先級別較高的目標， D無須考慮上述情況。7若一個無向圖可以一筆畫出，則該圖中 A最多有一個奇點，B恰好有兩個奇點，C最多有兩個奇點，D沒有奇點。8下圖v1v2v3v4v5的鄰接矩陣是 A，B，C，D9在一個容量網絡中，一個可行流滿足的條件中不包括下面的哪一點 A各邊上的流量不全為零； B對每個中間點，流入的物質的和等于流出的物質的和； C每邊上的流量不超過其容量； D發(fā)點發(fā)出的物資的和等于收點接受的物資的和。10在矩陣對策中，若局中人1的贏得矩陣不存在鞍點，則 A矩陣對策問題雖然存在純策略意義下的解，但不能通過求矩陣鞍點的方法求解；B矩陣對策不存在解；C矩陣對策不存在純策略意義下的解；D矩陣對策不存在混合策略意義下的解。三、 設有如下的線性規(guī)劃問題（1） 求該線性規(guī)劃問題的標準形式；（6分）（2） 寫出其對偶問題模型。（6分）四、 設用單純形法求解某極大化線性規(guī)劃問題得到如下的單純形表203/2000CBXBbx1x2x3x4x5x6ax12d-1001-1bx33/20210-12cx40e001-10sj0-100-1/2f(1) 試求上述表中的各參數(shù)af的值（6分）(2) 上表是否給出了最優(yōu)解，若是則求出最優(yōu)解及對偶問題最優(yōu)解（6分）五、某公司擬建立3個超市，可選的地址有A、B、C三處。在不同地址建立超市，每個月的營業(yè)利潤估算如下表所示（單位：萬元）：超市地址123A162030B121520C101316問這三個超市應如何分布，可使公司總的營業(yè)利潤最高？（12分）六、下面的圖給出了某工廠7個車間科室之間的內部網線可行的架設路線及架設成本（單位：百元）。（1）如何架設才能將所有7個單位連接起來，并使總成本最低？（8分）（2）若圖中A、B兩個單位之間必須直接連通，則最低總成本是多少？（4分）57468612374529A4B七、設矩陣對策問題（1） 當實數(shù)滿足什么條件時，該問題以純局勢為平衡局勢，此時矩陣對策的值是多少？（8分）（2） 純局勢可不可能為平衡局勢？（4分） 廣東工業(yè)大學試卷參考答案及評分標準 ( )課程名稱: 運籌學 ?？荚嚂r間: 2008年7月11日 (第 20周 星期五 )一、判斷題（每小題2分，共20分，無須改錯）1標準形式的線性規(guī)劃模型中決策變量的取值可以無任何限制。（ ）2線性規(guī)劃問題的可行域一定非空。（ ）3若線性規(guī)劃問題無可行解，則其對偶問題一定無可行解。（ ）4任何一個無向圖中偶點的個數(shù)不能是奇數(shù)。（ ）5對產大于銷的運輸問題，可通過添加假想的銷地化為產銷平衡運輸問題。（ ） 6目標規(guī)劃中任意一個目標約束的正負偏差變量不可能同時為正數(shù)。（ ）7若指派問題的系數(shù)矩陣中某行元素都減去同一個常數(shù)，則得到的新矩陣為系數(shù)矩陣的指派問題與原問題有同樣的最優(yōu)解（ ）8增廣鏈上的每條后向邊都為零流邊。（ ）9動態(tài)規(guī)劃的最優(yōu)策略應該具有性質，無論先前的狀態(tài)與決策如何，當前的決策應該是最優(yōu)。（ ）10矩陣對策就是二人有限零和對策。（ ）二、單項選擇題（每小題2分，共20分）1下列哪個模型是線性規(guī)劃模型 C A B C D 2若用單純形法求解線性規(guī)劃問題得到的最終單純形表中，基變量不含人工變量，且非基變量的檢驗數(shù)均非零，則線性規(guī)劃問題為下面的情形 A A有唯一最優(yōu)解， B有無窮多個最優(yōu)解， C無界解， D無可行解。3若線性規(guī)劃的原問題不存在最優(yōu)解，則對偶問題 B A可能存在最優(yōu)解，B不存在最優(yōu)解， C一定是無可行解， D一定是無界解。4若線性規(guī)劃問題的某個資源常數(shù)發(fā)生變化，則在最終單純形表中這一變化 B A對檢驗數(shù)存在影響， B對b列數(shù)存在影響， C對該資源常數(shù)所在行的數(shù)存在影響， D對所有數(shù)都無影響。5對于有m個產地n個銷地的產銷平衡運輸問題的表上作業(yè)法求解，下面不正確的說法是 C A每個空格有唯一的閉回路， B數(shù)字格的個數(shù)為m+n-1， C沃格爾法得到的調運方案是最優(yōu)方案， D若存在負檢驗數(shù)，則調運方案仍可改進。6對于目標規(guī)劃問題的求解，在滿足一個目標時 B A必須同時考慮優(yōu)先級別較低的目標， B不得違背已經得到滿足的優(yōu)先級別更高的目標，C不必顧慮優(yōu)先級別較高的目標， D無須考慮上述情況。7若一個無向圖可以一筆畫出，則該圖中 C A最多有一個奇點，B恰好有兩個奇點，C最多有兩個奇點，D沒有奇點。8下圖v1v2v3v4v5的鄰接矩陣是 D A，B，C，D9在一個容量網絡中，一個可行流滿足的條件中不包括下面的哪一點 A A各邊上的流量不全為零， B對每個中間點，流入的物質的和等于流出的物質的和， C每邊上的流量不超過其容量， D發(fā)點發(fā)出的物資的和等于收點接受的物資的和。10在矩陣對策中，若局中人1的贏得矩陣不存在鞍點，則 C A矩陣對策問題雖然存在純策略意義下的解，但不能通過求矩陣鞍點的方法求解；B矩陣對策不存在解；C矩陣對策不存在純策略意義下的解；D矩陣對策不存在混合策略意義下的解。五、 設有如下的線性規(guī)劃問題（3） 求該線性規(guī)劃問題的標準形式；（6分）（4） 寫出其對偶問題模型。（6分）解：（1）標準形式是目標函數(shù)2分，每個約束方程各1分，變量2分（2）對偶問題為目標函數(shù)1分，每個約束（包括變量約束）各1分六、 設用單純形法求解某極大化線性規(guī)劃問題得到如下的單純形表203/2000CBXBbx1x2x3x4x5x6ax12d-1001-1bx33/20210-12cx40e001-10sj0-100-1/2f(3) 試求上述表中的各參數(shù)af的值（6分）(4) 上表是否給出了最優(yōu)解，若是則求出最優(yōu)解及對偶問題最優(yōu)解（6分）解（1）a=2, b=3/2, c=0, d=1, e=0, f=-1每個參數(shù)值1分（2）由于所有檢驗數(shù)都非正，因此該表給出最優(yōu)解2分，最優(yōu)解為2分利用對偶關系可得對偶問題最優(yōu)解為2分五、某公司擬建立3個超市，可選的地址有A、B、C三處。在不同地址建立超市，每個月的營業(yè)利潤估算如下表所示（單位：萬元）：超市地址123A162030B121520C101316問這三個超市應如何分布，可使公司總的營業(yè)利潤最高？（12分）解：這是最大化指派問題，化為標準化指派問題，系數(shù)矩陣為故最優(yōu)解為超市1在位置B，超市2在位置C，超市3在位置A；總利潤為55萬元?；癁闃藴市问?分，求解過程正確5分，最優(yōu)解2分，最優(yōu)值2分六、下面的圖給出了某工廠7個車間科室之間的內部網線可行的架設路線及架設成本（單位：百元）。（1）如何架設才能將所有7個單位連接起來，并使總成本最低？（8分）（2）若圖中A、B兩個單位之間必須直接連通，則最低總成本是多少？（4分）57468612374529A4B解（1）由避圈法或破圈法得到如下的最小樹，即最優(yōu)架設線路6分57468612374529A4B總費用為25（百元）2分（2）在上述求解中總是保留AB之間的線路，得相應的線路為3分57468612374529A4B總費用28（百元）1分七、設矩陣對策問題（3） 當實數(shù)滿足什么條件時，該問題以純局勢為平衡局勢，此時矩陣對策的值是多少？（8分）（4） 純局勢可不可能為平衡局勢？（4分）解：（1）由條件位于第二行的第二個元素2是鞍點2分，故它是所在行的最小元素且是所在列的最大元素，因此必有4分故2分（2）若純局勢為平衡局勢1分，則q為鞍點，因此有且，矛盾2分；故純局勢不可能為平衡局勢1分。廣東工業(yè)大學試卷用紙，共11頁，第10頁