高考申論題
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$
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$）
▼ 還有更多解析內容
分枝界限法求背包問題
💡 利用線性放鬆求上限，透過分枝與剪枝搜尋整數最佳解。
🔗 分枝界限法求解流程
- 1 前處理 — 按單位價值 $c_i/a_i$ 降冪排序所有變數
- 2 根節點計算 — 放鬆整數限制，用貪婪法求 LP 放鬆解與上限值
- 3 分枝 (Branching) — 選擇分數解變數拆為 $x=0$ 與 $x=1$ 兩子節點
- 4 剪枝 (Pruning) — 若節點 UB ≤ 當前 LB 或無可行解，則停止分枝
↓
↓
↓
🔄 延伸學習：延伸學習：深度優先搜尋 vs 最佳優先搜尋對搜尋樹大小的影響
