主要內容：1、分枝定界法；
2、割平面法；
3、0－1型整數規劃；
4、指派問題。
重點與難點：分枝定界法和割平面法的原理、求解方法，0－1型規劃模型的建立及求解步驟，用匈牙利法求解指派問題的方法和技巧。
要求：理解本章內容，熟練掌握求解整數規劃的方法和步驟，能夠運用這些方法解決實際問題。
§1 問題的提出
要求變數取為整數的線性規劃問題，稱為整數規則問題（簡稱ip）。如果所有的變數都要求為（非負）整數，稱之為純整數規劃或全整數規劃；如果僅一部分變數要求為整數，稱為混合整數規劃。
例1 求解下列整數規劃問題
如果不考慮整數約束，就是乙個線性規劃問題（稱這樣的問題為原問題相應的線性規劃問題），很容易求得最優解為：。
用**法將結果表示於圖中畫「+」號的點都是可行的整數解，為滿足要求，將等值線向原點方向移動，當第一次遇到「+」號點（）時得最優解為，最優值為z=90。
由上例可看出，用列舉法是容易想到的，但常常得到最優解比較困難，尤其是遇到變數的取值更多時，就更困難了。下面介紹幾種常用解法。
§2 分枝定界法
分枝定界法可用於解純整數或混合的整數規劃問題。基本思路：設有最大化的整數規劃問題a，與之相應的線性規劃問題b，從解b開始，若其最優解不符合a的整數條件，那麼b的最優值必是a的最優值的上界，記為；而a的任意可行解的目標函式值是的乙個下界，採取將b的可行域分枝的方法，逐步減少和增大，最終求得。
現舉例說明：
例2 求解a
解：先不考慮條件⑤，即解相應的線性規劃b（①--④），得最優解4.81, 1.82, 356（見下圖）。
87 65
4321
0 1 2 3 4 5 6 7 8 9 10
顯然，它不符合整數條件⑤。
這時，為問題a的最優值的上界，記，而0, 0顯然是問題a的乙個整數可行解，這時z=0，是的乙個下界，記，即。
分枝定界法的解法，首先注意其中乙個非整數變數的解，如，在b中=4.81，於是對原問題增加兩個約束條件：，可將原問題分解為兩個子問題（即兩枝），給每枝增加乙個約束條件，如圖。
8765 問題b1
4問題b232
10 1 2 3 4 5 6 7 8 9 10
不考慮整數條件解問題得到最優解：
顯然未得到全部變數是整數解，，將改為349（=349），。
繼續對問題進行分解，，先分解為兩枝，增加條件的問題稱為；增加條件的問題稱為。在上圖中再去掉與之間的可行域，再求解問題，其結果列在下圖中，可見問題的解已都是整數，它的目標函式值，取=340，而它大於，所以再分解已無必要，而問題的，所以可能在之間有整數解，於是再對分解，得問題，為非整數解，且，問題為無可行解，於是可斷定：
，為最優整數解。
由以上解題過程可得到分枝定界法的求解步驟：
1. 給定原問題的初始上界
解與原問題a相應的線性規劃問題b，可能出現以下情況之一：
①b沒有可行解，這時a也沒有可行解，則停止；
②b有最優解，並符合a的整數條件，b的最優解即為a的最優解，則停止；
③b有最優解，但不符合a的整數條件，記它的目標函式值為。
2. 給定原問題的初始下界
用觀察法找出問題a的一整數可行解，一般取。求得其目標函式值，記作。這樣，就有。
3. 分枝
在b的最優解中任選乙個不符合整數條件的變數，其值為，以表示小於的最大整數，構造兩個約束條件:
和並將其分別加入問題b，求兩個後繼規劃問題，不考慮整數條件，解這兩個後繼問題。
4. 定界（修改上、下界）
以每個後繼問題為一分枝標明求解的結果，與其它問題的解的結果中，找出最優目標函式值最大者作為新的上界，從已符合整數條件的各分支中，找出目標函式值的最大者作為新的下界。
5. 比較與剪枝
各分枝的最優目標函式值中若有小於者，則剪掉這枝，以後不再考慮了，若大於，且不符合整數條件，則繼續分枝直到得到為止，求得最優整數解。
§3 割平面法
這個方法的基礎仍是用解線性規劃的方法去解整數規劃問題，首先不考慮變數是整數這個條件，但增加線性約束條件（用幾何術語，稱為割平面）使得由原可行域中切割掉一部分，這部分只包含非整數解，但沒有切割掉任何整數可行解。這個方法就是指出怎樣找到適當的割平面（不見得一次就找到），使切割後最終得到這樣的可行域，它的乙個有整數座標的極點恰好是問題的最優解。
例3 求解
①如不考慮條件⑤，求得相應的線性規劃的最優解：
就是圖中可行域r的極點a，不符合整數條件。
將原問題化為標準型
不考慮整數條件，用單純形法求解相應線性規劃的最優解。
由最終表中得到變數間的關係式：
將係數和常數項都分解為整數和非負真分數之和，並移項變為
現考慮整數條件，為非負整數，那麼也是非負整數。對上式，從等式左邊看是整數，等式右邊的（）是正數，所以等式右邊定一為負數，即。
整理得： ------切割方程
將新的約束方程，引入鬆馳變數，得到，將其列入最終表
最優解，最優值z=2
一、割平面法的解題步驟：
1. 若中有分數，先全部整數化，而後引入鬆馳變數，暫不考慮整數約束條件，用單純形法求出相應線性規劃的最優解。
2. 求切割方程
①令是相應線性規劃最優解中為分數值的乙個基變數，由最終單純形表得到
1）其中：（q指構成基變數下標的集合）
（k指構成非基變數下標的集合）
②將和都分解成整數部分n與真分數f之和，即
，其中2）
，其中而n表示不超過b的最大整數，如：
若 b=2.35，則n=2 f=0.35
b=–0.45,則n=–1 f=0.55
將（2）代入（1）得
③現在提出變數為整數的條件，上式由左邊看必是整數，由右邊看，因為所以不能為正，即
-------- 割線方程
3. 把切割方程作為新的約束條件，併入單純形最優表。繼續換算，取得最優解。
二．割平面法的性質
1. 割平面法割去了整數規劃原問題相應的線性規劃問題的最優解。
2. 割平面未割去整數規劃原問題的任一可行解，即未割去其相應的線性規劃問題的任一整數可行解。
§4 0–1規劃
一、0-1變數及其應用
0-1型整數規劃是整數規劃的特殊情形，它的變數僅取值0或1，這時稱為0-1變數，或稱二進位制變數。0-1變數作為邏輯變數（logical variable）,常用來表示系統是否處於某個特定狀態，或者決策時是否取某個特定方案。例如
當問題含有多項要素，而每項要素皆有兩種選擇時，可用一組0-1變數來描述。一般地，設問題有有限項要素，每項有兩種選擇和，則可令
那麼，向量就描述了問題的特定狀態或方案，即
1、選址問題----相互排斥的計畫
例4 某公司擬在市東、西、南三區建立門市部，擬議中有7個位置a可供選擇，規定
在東區，由三個點中至多選兩個；
在西區，由兩個點中至少選乙個；
在西區，由二個點中至少選乙個。
如選用點，裝置投資估計為元，每年可獲利潤估計為元，但投資總額不能超過b元，問應選擇哪幾個點可使利潤為最大？
解：先引入0–1變數
令 於是問題可列成：
2、相互排斥的約束條件
例5. 某廠決定生產兩種產品，有兩種加工方法可供選用，已知裝置**情況：
問選用哪種加工方法收益最大。
解：設a產品的日產量為，b產品的日產量為
若採用i，其約束條件：
若採用ii，其約束條件：
由於最終只能選用一種方法，我們引入0–1變數和乙個任意大的正數m。
令 於是，上述約束條件可變為：
若選用第一種方法生產，則y=1，約束條件就變成，其餘的約束條件就失去了作用；若選用第二種方法生產，則y=0，第乙個約束條件由於右側多了乙個m成了多餘的限制。
注意：引入的變數y不必出現在目標函式內，即認為在目標函式中y的係數為0。
3、關於固定費用問題(fixed cost problem)
例6 某廠生產某種產品，有幾種生產方式可供選擇，如選定的生產方式投資高（自動化程度高的裝置），由於產量大，因而分配到每件產品的變動成本就降低，反之，分配到每件產品的變動成本就可能增加，所以應全面考慮。
設有三種方式可供選擇，令
表示採用第j種方式時的產量
表示採用第j種方式時每件產品的變動成本
表示採用第j種方式時的固定成本
則採用各種方式的總成本分別為
引入0–1變數和任意大的正數m，令
於是目標函式
約束條件
當時，；當時，，才有意義。
二、0–1規劃的解法
解0-1規劃最容易想到的方法，就是窮舉法，即檢查變數取值為0或1的每一種組合，比較目標函式值以求得最優解，這就需要檢查變數取值的2n個組合。對於變數個數n較大（如n>10）時，是不可能的。因此，人們設計一種方法，只檢查變數取值的組合的一部分，就能求到問題的最優解，這種方法稱為隱舉法（implicit enumeration），下面舉例說明這種方法。
第五章整數規劃
主要內容 1 分枝定界法 2 割平面法 3 0 1型整數規劃 4 指派問題。重點與難點 分枝定界法和割平面法的原理 求解方法，0 1型規劃模型的建立及求解步驟，用匈牙利法求解指派問題的方法和技巧。要求 理解本章內容，熟練掌握求解整數規劃的方法和步驟，能夠運用這些方法解決實際問題。1 問題的提出 要求...
第五章線性規劃
2 步驟 a，整理為正則方程組，求初始基本可行解，帶入目標函式，判斷是否最優 b，從原來的非基變數中選出乙個進基變數稱為新的基變數 目標函式的係數中最小的數 絕對值最大的負係數 從原來的基變數中選出乙個離基變數使其成為新的非基變數 minl b l a lk xk且滿足非負要求 c，求出另一組基本可...
第五章人事
第五章人事 人力資源管理 第一節人事概述 人力資源的含義 是指綜合運用現代科學技術方法豐富人的知識 提公升人的能力 激發人的活力 發揮人的潛能。廣義 包括 現實的人力資源 潛在的人力資源 未來的人力資源 人力資源的特點 1 人力資源的能動性 2 人力資源的時效性 3 人力資源的時代性 4 人力資源具...