3.3 整數規劃與指派問題#

本章導言#

第三章前兩節討論的線性規劃假設決策變數可以是連續的實數。在許多管理決策中，這個假設是合理的（如生產 40.5 單位汽車零件、分配 12.3 小時人力），四捨五入也不至於造成太大誤差。

然而，在更多實際情況中，決策變數必須是整數才有意義。例如：要派幾台車、雇用幾名工人、分配幾間教室給課程、決定要開通哪幾條航線……你不可能雇用 \(2.7\) 名全職員工、也不可能派出 \(1.5\) 輛配送卡車。

當線性規劃模型要求部分或全部決策變數必須為整數（integer） 時，便稱為整數規劃（Integer Programming, IP）。若所有決策變數都必須為整數，稱為純整數規劃（Pure Integer Programming）；若部分變數為整數、部分可為連續，稱為混合整數規劃（Mixed Integer Programming, MIP）；若變數僅限 \(0\) 或 \(1\) ，則稱為0-1 整數規劃（Binary Integer Programming）。

整數規劃最大的困難在於：四捨五入線性規劃的最優解，往往不是整數規劃的最優解，甚至可能不是可行解。更重要的是，整數限制大幅增加了可行解的搜尋空間的「組合複雜度」。單純形法在整數限制下失效，必須使用分支定界法（Branch and Bound）、割平面法（Cutting Plane） 等專門演算法。

整數規劃最具代表性的特殊情況之一是指派問題（Assignment Problem）。指派問題要解決的是：「把 \(n\) 個工作分配給 \(n\) 個人（或機器），使總成本最低或總效益最高，每個工作只能由一個人負責，每個人只能擔任一個工作」。這種「一對一」的分配結構極為常見，從人員派班、考場監考、機台指派到運動隊伍陣容安排皆可適用。

指派問題的特殊結構使得它有比一般整數規劃更有效的解法——匈牙利演算法（Hungarian Algorithm）。匈牙利演算法是由匈牙利數學家 Harold Kuhn（哈羅德·庫恩，1925–2014） 於 1955 年提出，並以此命名。事實上，匈牙利數學家 Egon Balas（埃貢·巴拉斯）、以及早期的 König（柯尼希） 等人在圖論方面已有相關貢獻，庫恩的貢獻是將其系統化並應用於指派問題。

整數規劃的模型範例#

例題 3.3.1：某物流公司要採購 \(2\) 輛新配送車。市場上有 \(A\) 型車每輛售價 \(12\) 萬元、載貨量 \(5\) 噸、油耗較低；B 型車每輛售價 \(10\) 萣元、載貨量 \(3\) 噸。公司預算 \(22\) 萬元，要求至少能載貨 \(8\) 噸。問要怎麼採購才能符合需求且花費最低？

解：設 \(x_1\) 為購買 A 型車數量、 \(x2\) 為購買 B 型車數量，且 \(x1, x2\) 均為非負整數。

目標函數（最小化成本）： $$ \min C = 12 x1 + 10 x2 $$

限制條件： $$ \begin{aligned} 12 x1 + 10 x2 &\le 22 \quad (預算)\ 5 x1 + 3 x2 &\ge 8 \quad (載貨需求)\ x1, x2 &\in {0,1,2,\ldots} \end{aligned} $$

先用線性規劃（放寬整數限制）試算：從限制式推測可能解。預算限制 \(12x1 + 10x2 <= 22\) ,由於 \(12x1 <= 22\) 數 \(x1 <= 1\) (整數)。若 \(x1 = 1\) , 則 \(12 + 10x2 <= 22 \Rightarrow 10x2 = 10 \Rightarrow x2 = 1\) 。此組合載貨量 \(5 + 3 = 8\) ,成本 \(22\) 萬元。若 \(x1 = 0\) , 則 \(10x2 <= 22 \Rightarrow x2 <= 2.2\) ,需載貨量 \(3x2 >= 8 \Rightarrow x2 >= 3 (近似) 3x2 >= 8\) 則 \(x2 >= 3\) (因 \(x2=2\) 時 \(6 < 8\) ),但預算僅允許 \(x2 <= 2.2\) ,無法達成載貨需求。因此最優整數解為 \(x1=1, x2=1, C=22\) 萬元。

這個例子較簡單,但已顯示「整數限制必須直接考慮」的必要性.

指派問題的模型#

假設有 \(n\) 名工人 \(W_1,\ldots,W_n\) 和 \(n\) 項工作 \(J_1,\ldots,J_n\) 。若把工人 \(i\) 指派給工作 \(j\) ,成本為 \(c_{ij}\) 。每個工人只能做一個工作,每個工作只能由一個工人承擔。求總成本最低的指派方案。

定義0-1 決策變數： $$ x_{ij} = \begin{cases} 1, & \text{若工人 } i \text{被指派給工作 } j\ 0, & \text{否則} \end{cases} $$

目標函數（最小化總成本）： $$ \min Z = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij} $$

限制條件： $$ \begin{aligned} \sum_{j=1}^{n} x_{ij} = 1, & \quad i=1,\ldots,n \quad (\text{每個工人只做一個工作})\ \sum_{i=1}^{n} x_{ij} = 1, & \quad j=1,\ldots,n \quad (\text{每個工作只能由一個工人承擔})\ x_{ij} \in {0,1} & \end{PR}(i,j)=1,\ldots,n \end{aligned} $$

這種結構稱為指派問題（assignment problem） 或最小權重匹配在完全二分圖上的問題（minimum weight bipartite matching in the case of a perfect match）。由於結構特殊,指派問題屬於運輸問題（transportation problem） 的特殊情況,也屬於線性規劚整數規劃（但其鬆弛問題的解往往自動是整數） 的特殊情況。事實上,指派問題的係數矩陣具有全么模性（totally unimodular）,因此將 \(0-1\) 限制放寬為 \(0 \le x_{ij} \le 1\) 的線性規劃也會得到整數最優解。這是整數規劃中少見的「自動整數性」案例。

例題 3.3.2：某公司要把 \(4\) 名新員工分配到 \(4\) 個部門。各員工到各部門的訓練費用（萬元）如下表:

求總訓練費用最低的指派方案。

解：這是典型指派問題,可用匈牙利演算法求解。先對每行進行行減（row reduction），找出每行的最小值並減去該值：

• 員工 A：最小值 \(2\) ，減後: \(7,0,5,6\)
• 員工 B：最小值 \(3\) ，減後: \(3,1,0,4\)
• 員工 C：最小值 \(1\) ，減後: \(4,7,0,8\)
• 員工 D：最小值 \(3\) ，減後: \(4,3,5,0\)

矩陣變為: $$ \begin{bmatrix} 7&0&5&6\ 3&1&0&4\ 4&7&0&8\ 4&3&5&0 \end{bmatrix} $$

再對每列進行列減（column reduction），各列最小值分別為 \(3,0,0,0\) ,減去後: $$ \begin{bmatrix} 4&0&5&6\ 0&1&0&4\ 1&7&0&8\ 1&3&5&0 \end{bmatrix} $$

現在我們需要找到最少畫線覆蓋所有零點的畫線數。畫線過程 (概念性):畫出覆蓋 \(0\) 點的位置。經過測試,最少畫線數為 \(3\) (小於 \(4\) ),因此需要進一步修正矩陣:找出未被畫線覆蓋的元素中的最小值 \(1\) ，將未被畫線覆蓋的元素減 \(1\) ，被畫線覆蓋兩次 (交叉處)的元素加 \(1\) ,被畫線覆蓋一次的元素不變。修正後矩陣為: $$ \begin{bmatrix} 3&0&5&5\ 0&0&0&3\ 0&6&0&7\ 0&2&5&0 \end{bmatrix} $$

再次畫線覆蓋零點,最少畫線數為 \(4\) ，此時可以找出獨立零點的指派方案:

在修正後矩陣中找到獨立零點: (1,2)=0 (員工 A 指派給部門 2), (2,1)=0? (2,1)=0,但 (1,2)=0 已佔用列 2,因此 (2,1)不能佔用員工 A 的選擑;另一種安排:(2,1)=0, (3,3)=0? (3,3)=0, (4,4)=0, (1,2)=0。結果:員工 A→部門 2, 員工 B→部門 1, 員工 C→部門 3, 員工 D→部門 4。

對應原始成本: 員工 A→部門 2: \(2\) , 員工 B→部門 1: \(6\) , 員工 C→部門 3: \(1\) , 員工 D→部門 4: \(3\) , 總成本 \(12\) 萬元。

這是一個合理的最優方案。

指派問題的其他應用#

指派問題的應用遠比人員派遣廣泛：

• 機器指派：將不同工作分配給不同機台,使加工成本最低或生產時間最小
• 教師排課：將課程分配給教師,考慮教師專長與時段限制 (一般排課是更複雜的時段指派)
• 物流配送：配送車與配送路線的「車輛路徑與指派」問題中的基礎結構
• 競賽編排：體育比賽的對陣編排或裁判指派
• 社會工作：將個案分配給社工,使資源利用最有效
• 最小重量完美匹配:在二分圖結構下的圖論應用

整數規劃與線性規劃的比較#

與第4章的鋪路#

整數規劃的 0-1 變數概念在後續章節也會用到。例如：項目選擇（project selection） 問題中決定「要不要投資某個專案」就要用 0-1 變數；設施選址（facility location） 決定「要在哪些地點設廠」也需要整數決策。雖然第4章主要討論排隊論,但作業研究整體是互相貫通的,整數規劃提供了「非連續決策”的最佳化工具。

前因後果與驅動關係#

• 管理問題驅動理論：戰後企業發現線性規劃的「連續解」在實際執行時常與整數現實衝突。人事、設備、運輸等決策亟需整數最佳化,促使整數規劃理論發展。
• 理論如何改變實務:指派問題與整數規劃廣泛應用於人員排班、機台安排、航班編組、運輸路線規劃等,大幅提升資源利用效率。尤其在航空、物流、電信等「高成本資源」產業,整數規劃的效益極為顯著.
• 對後續章節的影響:第5章存貨中的「訂單批次」（批量訂購)雖未必直接用整數規劃,但「整數決策」觀念貫穿管理數學。第6章專案管理中的資源限制排程（Resource-Constrained Project Scheduling)常以整數規劃建模。第9章網路流與組合最佳化會更深入整數規劃的應用.
• 與兄弟書的連結:《會計的數學》第6章本量利分析雖是單一變數模型,整數規劃可以擴展到「多項目投資組合」的選擇問題。《經濟的數學》第7章不完全競爭與市場結構雖不同,但企業在有限資源下選擇「產出組合」的思路與線性規劃相似。

練習#

1. 說明線性規劃、純整數規劃、混合整數規劃、0-1 整數規劃之間的差異.
2. 某公司要從 4 名員工中選派 2 名參加培訓,選派方式有多少種?試用指派問題的思路說明這是一個 0-1 整數規劃問題 (提示:可將「剩下 4 人中 2人參加」轉換成指派問題的形式)。
3. 指派問題為何能用匈牙利演算法求解而一般整數規劃不行?試從「結構特殊性」與「全么模性」角度說明.
4. 思考題:將線性規劃的連續最優解 \(x1=1.7, x2=2.3\) 四捨五入為 \(x1=2, x2=2\) 復建議用這種方法解決整數規劃問題嗎?請舉例說明理由.
5. 思考題:整數規劃的計算難度遠超線性規劃。試從「可行解數量”角度說明,並問為何現代電腦仍然廣泛應用整數規劃於大規模管理決策?

年表速查#

• 1784：Gaspard Monge 提出「最小運輸成本」問題（對運輸問題理論的早期貢獻）。
• 1916：Dénes König 證明二分圖匹配定理（匈牙利演算法的理論源頭）。
• 1939：Kantorovich 提出運輸問題的線性規劃形式。
• 1955：Harold W. Kuhn 提出匈牙利演算法,系統化指派問題解法。
• 1950 年代：Land & Doig、Gomory 等人分別提出分支定界法與割平面法,奠定整數規劃演算法基礎。
• 1960 年代以來:整數規劃廣泛應用於作業研究與管理科學。

名詞速查表#

• 整數規劃（Integer Programming, IP）：要求部分或全部決策變數為整數的線性規劃。
• 純整數規劃（Pure Integer Programming）：所有決策變數均為整數.
• 混合整數規劃（Mixed Integer Programming, MIP）：部分變數為整數,部分為連續.
• 0-1 整數規劵 (Binary Integer Programming）：決策變數僅限 0 或 1.
• 指派問題（Assignment Problem）：把 n 個工作分配給 n 個人,使總成本或效益最出極值的問題.
• 匈牙利演算法（Hungarian Algorithm）：解決指派問題的專用演算法.
• 分支定界法（Branch and Bound）：整數規劃最常用的求解演算法,透過「分支」與「定界」搜尋整數可行解。
• 割平面法（Cutting Plane）：通過添加不等式「切割」掉線性規劃可行區域中非整數部分的方法.
• 全么模性（Totally Unimodular）：某些矩陣具有的特殊性質,使得線性規劃鬆弛後的解自動為整數.