高考申論題
114年
[工業工程] 作業研究
第 二 題
二、請使用分枝界限（Branch-and-Bound）法求解下列背包問題（Knapsack Problem），以將所有整數變數放鬆為實數變數的方式求取搜尋樹（Search Tree）中各節點所需之上限值（Upper Bound），請畫出搜尋樹，並標示各節點所對應的完整實數解及上限值：（25 分）
Max $z = 10x_1 + 3x_2 + x_3 + 8x_4 + 5x_5 + 3x_6$
s.t. $8x_1 + x_2 + 3x_3 + 5x_4 + 2x_5 + 2x_6 \le 15$
$x_i = 0$ or $1, i = 1, 2, ..., 6$
📝 此題為申論題
思路引導 VIP
本題為標準的 0-1 背包問題，解題第一步應先計算各變數的『單位重量價值』（即目標函數係數 / 約束條件係數），並依此由高至低決定放寬為實數時的貪婪選擇順序。接著，從根節點開始透過線性放鬆（LP Relaxation）求取 Upper Bound，針對解中的分數變數向下展開 Branch-and-Bound 搜尋樹，若達到全整數解則更新 Lower Bound，若 UB 小於目前已知最大 LB 則進行剪枝。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】計算物品的單位重量價值排定貪婪演算法選取順序，利用線性放鬆計算上限（Upper Bound），並依據分數變數進行分枝（Branching）逐步求得最佳整數解。 【解答】 Step 1：計算並排序各決策變數對應物品的單位重量價值（CP值：$c_i/a_i$）
▼ 還有更多解析內容