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