3.1 整數規劃的數學模型
乙個規劃問題中要求部分或全部決策變數是整數，則這個規劃稱為整數規劃。當要求全部變數取整數值的，稱為純整數規劃(pure integer programming，ip)，要求一部分變數取整數值的，稱為混合整數規劃(mixed integer programming，mip)，決策變數全部取0或1的規劃稱為0－1整數規劃(binary integer programming，bip)，如果模型是線性的，稱為整數線性規劃（integer linear programming, ilp）。本章只討論整數線性規劃。
求解整數規劃問題時，如果先不能考慮對變數的整數約束，作為一般線性規劃問題來求解，當解為非整數時再用捨入湊整方法尋求最優解，這樣得到的解有可能不是整數規劃的可行解或是可行解而不是最優解。
【例3.1】某人有一揹包可以裝10公斤重、0.025m3的物品。
他準備用來裝甲、乙兩種物品，每件物品的重量、體積和價值如表3－1所示。問兩種物品各裝多少件，所裝物品的總價值最大。
表3－1
【解】設甲、乙兩種物品各裝x1、x2件，則數學模型為
3.1)
如果不考慮x1、x2取整數的約束（稱為式（3.1）的鬆弛問題），線性規劃的可行域如圖3-1中的陰影部分所示。
圖3-1
用**法求得點b為最優解：x＝(3.57，7.
14)，z＝35.7。由於x1，x2必須取整數值，整數規劃問題的可行解集只是圖中可行域內的那些整數點。
用湊整法求解時需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）雖屬可行解，代入目標函式得z=33,並非最優。實際上問題的最優解是（5，5），z=35。即兩種物品各裝5件，總價值35元。
由圖3-1知，點（5，5）不是可行域的頂點，直接用**法或單純形法都無法求出整數規劃問題的最優解，因此求解整數規劃問題的最優解需要採用其它特殊方法。
有些問題用線性規劃數學模型無法描述，可以通過設定邏輯變數建立整數規劃的數學模型。
【例3.2】在例3.1中，假設此人還有乙隻旅行箱，最大載重量為12公斤，其體積是0.02m3。揹包和旅行箱只能選擇其一，建立下列2種情形的數學模型，使所裝物品價值最大。
（1）所裝物品不變；
（2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是4和3，載重量和體積的約束為
【解】此問題可以建立兩個整數規劃模型，但用乙個模型描述更簡單。
引入0－1變數（或稱邏輯變數）yi，令
i=1,2分別是採用揹包及旅行箱裝載。
（1）由於所裝物品不變，式(3.1)約束左邊不變，整數規劃數學模型為
（3.2）
（2）由於不同載體所裝物品不一樣，但物品價值相同，目標函式不變，數學模型為
式中m為充分大的正數。從上式可知，當使用揹包時(y1=1，y2=0)，式(3.3b)和(3.
3d)是多餘的，即約束條件不起作用；當使用旅行箱時(y1=0，y2=1)，式(3.3a)和(3.3c)是多餘的。
上式也可以令.
一般地，右端常數是k個值中的乙個時，類似式(3.2)的約束條件為
對於m組條件中有k（≤m）組起作用時，類似式(3.3)的約束條件寫成
這裡yi=1表示第i組約束不起作用（如y1=1式(3.3b)、(3.3d)不起作用），yi=0表示第i個約束起作用。當約束條件是「≥」符號時右端常數項應為,下同。
對於m個條件中有k（≤m）個起作用時，約束條件寫成
【例3.3】試引入0－1變數將下列各題分別表達為一般線性約束條件
（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20
（2）若x1≤5，則x2≥0，否則x2≤8
（3）x2取值0，1，3，5，7
【解】（1）3個約束只有1個起作用
或如果要求至少乙個條件滿足，第1個式子改為，第2個式子改為。
（2）兩組約束只有一組起作用
（3）右端常數是5個值中的1個
【例3.4】企業計畫生產4000件某種產品，該產品可自己加工、外協加工任意一種形式生產。已知每種生產的固定費用、生產該產品的單件成本以及每種生產形式的最大加工數量（件）限制如表3－2所示，怎樣安排產品的加工使總成本最小。
表3－2
【解】設xj為採用第j（j=1,2,3）種方式生產的產品數量，生產費用為
式中kj是固定成本，cj是單位產品成本。設0－1變數yj，令
目標函式為
（3.4）
式（3.4）中是處理xj與yj一對變數之間邏輯關係的特殊約束，當xj>0時yj=1, 當xj＝0時，為使z最小化，有yj=0。
例3.4是混合整數規劃問題。求解得到：x＝（0，2000，2000）t，y＝（0，1，1）t，z=25400.
3.2 純整數規劃的求解
整數規劃的求解要比一般線性規劃的求解複雜。常用的方法有完全列舉法(***plete enumeration)、分枝定界法（branch and bound method）、割平面法(cutting-plane method)、隱列舉法（(implicit enumeration method）和lagrange鬆弛法。對於乙個複雜的模型，完全列舉不是有效的演算法，用的較多的是後面幾種。
3.2.1求解純整數規劃的分枝定界法
分枝定界法的步驟：
（1）求整數規劃的鬆弛問題最優解；
（2）若鬆弛問題的最優解滿足整數要求，得到整數規劃的最優解，否則轉下一步；
（3）任意選乙個非整數解的變數xi，在鬆弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的鬆弛問題，稱為分枝。新的鬆弛問題具有特徵：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界；
（4）檢查所有分枝的解及目標函式值，若某分枝的解是整數並且目標函式值大於（max）等於其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數解並且目標值大於（max）整數解的目標值，需要繼續分枝，再檢查，直到得到最優解。
【例3.5】用分枝定界法求解例3.1
【解】先求對應的鬆弛問題（記為lp0）：用**法得到最優解x＝（3.57,7.14）,z0=35.7,如圖3-2所示 。
圖3-2
**法見圖3-3所示。選擇目標值最大的分枝lp2進行分枝，增加約束x2≤6及x2≥7，由圖3-3知x2≥7不可行，因此得到線性規劃lp3，**法見圖3-4所示。
由圖3-4可知，對x1進行分枝，取x1≤4及x1≥5，得到兩個線性規劃lp4和lp5。顯然lp4的可行解在x1=4的線段上，**法見圖3-5所示。
從圖3－5知，lp4和lp5已是整數解，儘管lp1還可以對x2分枝，但z1小於z5，比較目標值lp5的解是整數規劃的最優解，最優解為x1=5，x2=5，最優值z＝35。
圖３-3
圖3圖3-5
上述分枝過程可用圖3-6表示。
圖3-6
由例3.5的求解過程看出，分枝定界法求解整數規劃要比單純形法求解線性規劃複雜得多，尤其變數較多的大型整數規劃問題，即使是計算機計算，所耗時間令人難以容忍。
圖3-7
3.2.2 求解ip的割平面法
割平面法(cutting-planemethod)由高莫雷(r.e.gomory)於2023年提出。
其基本思想是放寬變數的整數約束，首先求對應的鬆弛問題最優解，當某個變數xi不滿足整數要求時，尋找乙個約束方程並新增到鬆弛問題中，其作用是切割掉非整數部分，縮小原鬆弛問題的可行域，最後逼近整數問題的最優解。
設整數規劃
對應的鬆弛問題
的最優解為：。
設xi不為整數，， xk為非基變數。將分離成乙個整數與乙個非負真分數之和
則有3.5)
式(3.5)兩邊都為整數,則有
3.6)
加入鬆弛變數si(非負整數)得
3.7)
式(3.7)稱為以xi行為源行（**行）的割平面，或分數切割式，或高莫雷約束方程。將高莫雷約束加入到鬆弛問題的最優表中，用對偶單純形法計算，若最優解中還有非整數解，再繼續切割，直到全部為整數解。
例如：分解成：，將整數部分列於等式左邊，分數部分列於等式右邊得
加入鬆弛變數得到以x1行為源行的割平面
又如：分解成，高莫雷方程是
【例3.6】用割平面法求解下列ip問題
【解】 放寬變數約束，對應的鬆弛問題是
加入鬆弛變數x3及x4後，用單純形法求解，得到最優表3－3。
表3－3
最優解x(0)＝(5/2，15/4),不是ip的最優解。選擇表3－3的第一行(也可以選第二行)為源行
分離係數後改寫成
加入鬆弛變數x5得到高莫雷約束方程
3.8)
將式(3.8)作為約束條件新增到表3－3中，用對偶單純形法計算，如表3－4所示。
表3－4
最優解x(1)＝(3，3)，最優值z＝21。所有變數為整數，x(1)就是ip的最優解。如果不是整數解，需要繼續切割，重複上述計算過程。
運籌學 第4章 整數規劃習題
第四章整數規劃 4.1 某工廠生產甲 乙兩種裝置，已知生產這兩種裝置需要消耗材料a 材料b，有關資料如下，問這兩種裝置各生產多少使工廠利潤最大？只建模不求解 表4 1 解 設生產甲 乙這兩種裝置的數量分別為x1 x2，由於是裝置台數，則其變數都要求為整數，建立模型如下 4.2割平面法求解。下表為最優...
第3章動態規劃
動態規劃是本書介紹的五種演算法設計方法中難度最大的一種，它建立在最優原則的基礎上。採用動態規劃方法，可以優雅而高效地解決許多用貪婪演算法或分而治之演算法無法解決的問題。在介紹動態規劃的原理之後，本章將分別考察動態規劃方法在解決揹包問題 圖象壓縮 矩陣乘法鏈 最短路徑 無交叉子集和元件摺疊等方面的應用...
第3章人力資源規劃
1 年度人力資源規劃表 範本一 填表人審核人填表時間 年月日 填表說明 本 由人力資源部經理填寫，由總經理審批。2 年度人力資源規劃表 範本二 填表人審核人 填表說明 本 用於各部門人員規劃，由人力資源部經理填寫，由總經理審核。1 職位類人員需求 表 填表日期 年月日 填表人審核人 填表說明 本 用...