高考申論題
110年
[工業工程] 作業研究
第 一 題
📖 題組：
最短路徑問題（shortest path problem）為常用之數學模型。常用的求解演算法之一，為 Dijkstra 所提出之標籤設定法（label setting algorithm）。該演算法在求解過程中將網路（network）之所有節點區分為永久節點（permanent node）及暫時節點（temporary node）兩類，再逐一設定永久節點之距離標籤（distance label）。任一節點成為永久節點之後，其距離標籤即不再變動。
最短路徑問題（shortest path problem）為常用之數學模型。常用的求解演算法之一，為 Dijkstra 所提出之標籤設定法（label setting algorithm）。該演算法在求解過程中將網路（network）之所有節點區分為永久節點（permanent node）及暫時節點（temporary node）兩類，再逐一設定永久節點之距離標籤（distance label）。任一節點成為永久節點之後，其距離標籤即不再變動。
📝 此題為申論題，共 4 小題
小題 (一)
試寫出標籤設定法之步驟。（10 分）
思路引導 VIP
本題考查 Dijkstra 演算法（標籤設定法）的核心邏輯。作答時應清晰界定「永久標籤」與「暫時標籤」的轉換機制。建議按照初始化、選取節點、更新標籤、終止條件的邏輯順序撰寫，並使用標準的數學符號（如 d(v) 表示距離）增加專業感。
小題 (二)
請設計一個具有下列性質之網路：含有不多於 5 個節點及若干節線（arc）、含有長度為負值之節線、無負值長度之迴圈（negative cycle）、且以標籤設定法求解其最短路徑時將產生錯誤。請以圖形呈現所設計之網路，並使用標籤設定法求解最短路徑。請列舉詳細計算過程，並明確指出所產生之錯誤。請在圖形中明確標示各節線之長度及最短路徑起點。（15 分）
思路引導 VIP
這題是進階設計題，考驗對 Dijkstra 限制條件的理解。Dijkstra 失效的主因是「貪婪選擇」無法預見後續出現的極大負值邊。設計網路時，應構造一個「看起來較遠但包含負邊後實際較近」的路徑。節點數量限制在 5 個內，建議使用 3 或 4 個節點即可達成。
小題 (三)
利用小題(二)所得之 B⁻¹ 求出最佳解及其目標函數值。(10 分)
思路引導 VIP
本題測驗矩陣形式單純形法（Matrix Simplex Method）的核心運算概念。運用矩陣公式 $X_B = B^{-1}b$ 可求得基變數的最佳解，再代入目標函數公式 $Z = C_B X_B$ 即可求得最佳目標函數值。
小題 (四)
利用小題(二)所得之 B⁻¹ 求出各種資源之陰影價格。(5 分)
思路引導 VIP
看到求「陰影價格（Shadow Price）」，應立即連結到其數學本質即為對偶變數（Dual Variables）的最佳解。解題關鍵在於熟記公式 y = c_B * B^(-1)，先明確列出基本變數對應的目標函數係數向量 c_B，再代入前一小題求得的反矩陣 B^(-1) 進行矩陣相乘即可精準得分。