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

《廣東工業(yè)大學-運籌學-試卷答案.doc》由會員分享，可在線閱讀，更多相關(guān)《廣東工業(yè)大學-運籌學-試卷答案.doc（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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