指派問題題目及答案

單項選擇題（每題2分，共10題）1.指派問題的目標是（）A.最大化總收益B.最小化總花費C.隨機分配D.平均分配2.解決指派問題常用的方法是（）A.單純形法B.匈牙利法C.動態(tài)規(guī)劃法D.分枝定界法3.一個標準指派問題，有5個人和5項任務，其系數矩陣階數是（）A.5×4B.4×5C.5×5D.6×64.指派問題中，人員與任務數量關系是（）A.人員多于任務B.人員少于任務C.人員等于任務D.無限制5.若指派問題系數矩陣某行元素全為0，該行最優(yōu)指派是（）A.任意列B.0所在列C.重新計算D.無最優(yōu)解6.指派問題中，每個人員能承擔的任務數是（）A.1項B.2項C.多項D.隨意7.經過變換后的指派問題系數矩陣，若存在m個不同行不同列的0元素，m與任務數n關系是（）A.m<nB.m>nC.m=nD.不確定8.指派問題系數矩陣中元素表示（）A.人員完成任務的時間B.人員完成任務的收益C.人員完成任務的花費等相關指標D.人員數量9.匈牙利法求解指派問題，第一步通常是（）A.找出獨立0元素B.使系數矩陣每行每列出現0元素C.計算最優(yōu)值D.檢驗最優(yōu)解10.若指派問題是求最大化問題，應（）A.直接用匈牙利法B.轉化為最小化問題C.無法求解D.用其他方法多項選擇題（每題2分，共10題）1.以下屬于指派問題特點的有（）A.人員和任務數量相等B.每個人員只承擔一項任務C.每個任務只由一個人員承擔D.目標是優(yōu)化某種指標2.解決指派問題可以采用的方法有（）A.匈牙利法B.枚舉法C.網絡算法D.分支定界法（特殊情況可用）3.關于指派問題系數矩陣說法正確的有（）A.元素非負B.方陣C.行數與列數相等D.元素可以為負數4.在匈牙利法求解過程中，可能涉及的操作有（）A.行列元素相減B.畫直線覆蓋0元素C.調整0元素位置D.計算矩陣行列式5.指派問題可以應用于（）A.工作分配B.設備分配C.資源分配D.運輸調度6.以下哪些情況表明指派問題得到最優(yōu)解（）A.存在m個不同行不同列的0元素，m等于任務數B.覆蓋0元素的直線數等于行數C.所有元素都為0D.找不到獨立0元素7.對指派問題系數矩陣進行變換時，目的是（）A.讓矩陣出現更多0元素B.讓0元素分布更合理C.降低計算復雜度D.改變問題性質8.當指派問題系數矩陣某一行或列元素全相等時（）A.不影響最優(yōu)解B.可能導致多解C.問題無解D.需重新構建矩陣9.指派問題與線性規(guī)劃的關系是（）A.指派問題是特殊的線性規(guī)劃B.線性規(guī)劃包含指派問題C.解法完全相同D.目標函數類型相同10.若指派問題模型中，人員數量大于任務數量，可（）A.增加虛擬任務B.去掉多余人員C.轉化為運輸問題D.重新定義問題判斷題（每題2分，共10題）1.指派問題一定有最優(yōu)解。（）2.匈牙利法只能用于解決最小化指派問題。（）3.指派問題系數矩陣中元素必須是整數。（）4.若系數矩陣某列元素全為1，不影響指派結果。（）5.指派問題的解中，非零元素一定是1。（）6.用匈牙利法求解指派問題，若存在多個最優(yōu)解，其目標函數值相同。（）7.當人員和任務數量很大時，枚舉法求解指派問題效率更高。（）8.指派問題可以看作是特殊的0-1規(guī)劃問題。（）9.對系數矩陣進行行變換后，最優(yōu)解會改變。（）10.指派問題中，若兩個人員對某任務花費相同，對最優(yōu)解無影響。（）簡答題（每題5分，共4題）1.簡述匈牙利法求解指派問題的基本步驟。答案：先使系數矩陣每行每列出現0元素；再找獨立0元素，若獨立0元素個數等于任務數則得最優(yōu)解，否則畫直線覆蓋0元素，調整矩陣讓0元素分布更好，重復找獨立0元素步驟直至得到最優(yōu)解。2.為什么指派問題是特殊的線性規(guī)劃問題？答案：它具有線性規(guī)劃的一般特征，如目標函數和約束條件為線性。但又有特殊之處，變量取值只能是0或1，且約束條件為人員與任務一一對應關系，所以是特殊的線性規(guī)劃。3.若指派問題求最大化，如何轉化為最小化問題求解？答案：用一個足夠大的常數減去系數矩陣中的每一個元素，得到新矩陣，將原最大化問題轉化為以新矩陣為系數矩陣的最小化指派問題來求解。4.指出指派問題模型的約束條件特點。答案：約束條件特點為：人員與任務一一對應。每個人員只能承擔一項任務，每項任務只能由一個人員承擔，表現為變量取值為0或1的等式約束。討論題（每題5分，共4題）1.在實際應用中，指派問題可能會遇到哪些復雜情況，如何應對？答案：復雜情況如人員和任務數量不相等、有特殊限制條件等。人員和任務數量不等可增加虛擬人員或任務；有特殊限制可在系數矩陣中通過設置大M等方式處理。2.對比匈牙利法和枚舉法求解指派問題的優(yōu)缺點。答案：匈牙利法優(yōu)點是計算效率高，能快速找到最優(yōu)解；缺點是對復雜變形問題處理較難。枚舉法優(yōu)點是思路簡單，能保證找到最優(yōu)解；缺點是計算量極大，當規(guī)模大時效率極低。3.如何判斷指派問題有多個最優(yōu)解，多個最優(yōu)解在實際中有何意義？答案：若在找獨立0元素過程中，有多種不同行不同列0元素組合都能達到任務數，就有多個最優(yōu)解。實際中可提供多種方案選擇，滿足不同偏好或其他附加要求。4.結合實際案例，談談指派問題在資源分配中的應用思路。答案：如項目團隊分配任務，將人員能力、任務難度等轉化為系數矩陣元素，用匈牙利法等求解，得到合理任務分配方案，使資源利用更高效，項目能更好完成。答案單項選擇題1.B2.B3.C4.C5.B6.A7.C8.C9.B10.B多項