加載中. ..
PDF
110年公務人員高等考試三級考試試題
類 科
：
工業工程
科 目
：
作業研究
考試時間
：
2
小時
座號
：
※注意：可以使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
37440
頁次：
2
－
1
一、最短路徑問題（shortest path problem）為常用之數學模型。常用的求解演
算法之一，為 Dijkstra 所提出之標籤設定法（label setting algorithm）。該
演算法在求解過程中將網路（network）之所有節點區分為永久節點
（permanent node）及暫時節點（temporary node）兩類，再逐一設定永久
節點之距離標籤（distance label）。任一節點成為永久節點之後，其距離
標籤即不再變動。
試寫出標籤設定法之步驟。（10 分）
請設計一個具有下列性質之網路：含有不多於 5個節點及若干節線
（arc）、含有長度為負值之節線、無負值長度之迴圈（negative cycle）、
且以標籤設定法求解其最短路徑時將產生錯誤。請以圖形呈現所設計
之網路，並使用標籤設定法求解最短路徑。請列舉詳細計算過程，並
明確指出所產生之錯誤。請在圖形中明確標示各節線之長度及最短路
徑起點。（15 分）
二、假設某港口營運公司欲分配 n艘船（編號 1至n）靠泊 m個席位（編號
1至m）。每個席位最多僅可分配予一艘船舶。對每艘船，公司可將之安
排於任何一個席位，也可以不予分配任何席位。若船舶 i安排在席位 j，
則將產生 Fij 之效益。在這 n艘船當中，有 a、b、c三艘特殊船。不論安
排在何席位，a與b不可二者均獲得席位分配，但若 c有獲得席位分配
則無此限制。港口營運公司欲得到總效益最大化之席位分配計畫，試寫
出線性整數規劃模式以協助達成之。請注意所有的數學式均必須為線性。
寫出決策變數並明確說明其定義。（8分）
寫出目標函數並說明其意義。（5分）
寫出限制式並說明其意義。（12 分）
代號：
37440
頁次：
2
－
2
三、考慮下列線性規劃問題：
Maximize 2x1–x2+x3
subject to
3x1+x2+x3 ≤ 60
2x1– 2x2+ 4x3 ≤ 20
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
試以單形法（simplex algorithm）求解其最佳解，或明確指出其最佳解
不存在。必須使用表列式（tableau）求解，並完整列出每一回合求解
之列表。請明確寫出最佳解之基底變數（basic variables）以及最佳之
目標函數值。（15 分）
試寫出其對偶問題（dual problem）。（不必求解）（10 分）
四、某公司欲以單一機臺處理 N批貨件。所有貨件各不相同，編號 1至N。
該機臺在同一時間僅能處理一批貨件。第 i批貨件在機臺上所需要之處
理時間長度已知為 Ti。機臺可依任何順序處理，但在完成貨件 i之後，
若下一批貨為第 j貨件時，其間的機臺清理時間已知為 Rij，在進行清理
時，機臺無法處理任何貨件。在開始工作之前，以及完成所有工作之後，
均無額外機臺清理時間。今欲將此問題模化成為旅行推銷員問題
（travelling salesman problem），以求取能夠極小化完成處理所有貨件總時
間之工作順序。
試寫出旅行推銷員問題之定義。（文字敘述即可，不必寫出數學式）
（5分）
說明將這個機臺處理貨件問題模化成為旅行推銷員問題之方法。至少
需要說明如何定義旅行推銷員問題中之⑴節點、⑵節線長度，並說明
求解完成後，如何將旅行推銷員問題之最佳解轉化成為原機臺處理貨
件問題之最佳解。（20 分）