整數(shù)規(guī)劃簡(jiǎn)介課件

1、第4章整數(shù)規(guī)劃簡(jiǎn)介學(xué)習(xí)方法 了解整數(shù)規(guī)劃的數(shù)學(xué)模型的特點(diǎn)。 掌握整數(shù)規(guī)劃的分枝定界法。 學(xué)會(huì)指派問題及其求解方法。 整數(shù)規(guī)劃（Integer Linear Programming, ILP）可分成線性部分和整數(shù)部分，并常常把整數(shù)規(guī)劃作為線性規(guī)劃的特殊部分。 在線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問題，常要求解答必須是整數(shù)。 例如，所求解是機(jī)器的臺(tái)數(shù)、工人的人數(shù)或裝貨的車數(shù)、場(chǎng)址的選定等，都必須部分或者全部滿足整數(shù)要求，這樣的問題稱為整數(shù)線性規(guī)劃問題，簡(jiǎn)稱為整數(shù)規(guī)劃，記為ILP。 整數(shù)規(guī)劃的應(yīng)用范圍是極其廣泛的，它不僅在工業(yè)、工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)

2、計(jì)、系統(tǒng)可靠性、編碼、經(jīng)濟(jì)分析等方面也有新的應(yīng)用。整數(shù)規(guī)劃的數(shù)學(xué)模型4.1分枝定界法4.2指派問題4.3指派問題的Excel處理4.44.1 整數(shù)規(guī)劃的數(shù)學(xué)模型4.1.1 案例 例4.1 某廠生產(chǎn)A、B兩種產(chǎn)品，這兩種產(chǎn)品的單位利潤分別為25元和40元。 生產(chǎn)每種產(chǎn)品都需要3道工序，其各種產(chǎn)品的工時(shí)（單位：時(shí)）、每一工序每周可供使用的時(shí)間如表4.1所示，問工廠如何安排生產(chǎn)，使其獲利最大？ 解 設(shè)、分別是A產(chǎn)品和B產(chǎn)品的周產(chǎn)量，z為這兩種產(chǎn)品每周總的利潤。 根據(jù)題意，建立模型如下： 其中，max是英文maximize（最大化）的縮寫。 由于所有變量要求取整數(shù)，故稱它為全整數(shù)規(guī)劃問題。 例4.2

3、我們要做投資決策，就是對(duì)幾個(gè)潛在的投資方案做出選擇，若投資決策可以是在可行的幾個(gè)廠址中做出選擇；或設(shè)備購置的選擇；或?qū)σ唤M研究和發(fā)展項(xiàng)目做出決定。 在這類決策問題中，問題是在“要”或者“不要”之間進(jìn)行選擇，我們可以令決策變量是整數(shù)，且只取0或1，分別表示不投資或者投資。 假定cj代表第j項(xiàng)投資得到的收益，aij是用于第j項(xiàng)投資的第i項(xiàng)資源的數(shù)量，bi為第i種資源的限制，則上述問題可列成下式： 由于所有的變量都只能取0或1，所以，這樣的整數(shù)規(guī)劃問題稱為01規(guī)劃。4.1.2 整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式 整數(shù)規(guī)劃數(shù)學(xué)模型一般可以表示如下： 式中opt即optimize（最優(yōu)化）的縮寫，根據(jù)問題要求不

4、同，可以表示為max（最大化）或min（最小化）。 整數(shù)規(guī)劃可分為以下3種類型。（1）純整數(shù)規(guī)劃（pure integer linear programming） （2）混合整數(shù)規(guī)劃（mixed integer liner programming） （3）01型整數(shù)規(guī)劃（zeroone integer liner programming） 整數(shù)規(guī)劃特點(diǎn)如下。（1）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況。 原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 整數(shù)規(guī)劃無可行解。 有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值一定不會(huì)優(yōu)于原線性規(guī)劃的最優(yōu)值。（2）

5、整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。 例4.5 已知整數(shù)規(guī)劃問題： 解 如果先不考慮整數(shù)條件，得到如下線性規(guī)劃問題（稱為松弛問題）：圖4.1 例4.5 在B點(diǎn)得到最優(yōu)解： 再考慮整數(shù)條件： 如將x2湊成整數(shù)，x2=2，則點(diǎn)（2, 2）落在可行域外，不是可行解；若將x2湊成整數(shù)1，但點(diǎn)（2, 1）不是最優(yōu)解。 因?yàn)楫?dāng)x1=2，x2=1，得到z=7，而當(dāng)x2=0, x2=2，得到z=10，顯然點(diǎn)（0, 2）比點(diǎn)（2,1）更好。 因此不能簡(jiǎn)單地將松弛問題的最優(yōu)解舍入化整（如四舍五入），得出整數(shù)規(guī)劃的最優(yōu)解。 通過仔細(xì)分析，從圖4.1可知，整數(shù)規(guī)劃問題的可行解集是相應(yīng)的線性規(guī)劃問題的可行域

6、內(nèi)的整數(shù)格子點(diǎn)，它是一個(gè)有限集。 因此，我們可以用另一種方法進(jìn)行討論，即將所有的可行解依次代入目標(biāo)函數(shù)，比較所得的目標(biāo)函數(shù)值的大小，從而得到最優(yōu)解。 這個(gè)方法稱為完全枚舉法。 如上例有整數(shù)可行解和目標(biāo)函數(shù)值： 經(jīng)過比較，所以得到最優(yōu)解x1=0, x2=2，目標(biāo)函數(shù)最優(yōu)值z(mì)=10。4.2 分枝定界法 整數(shù)規(guī)劃，除少數(shù)可以用完全枚舉法或用線性規(guī)劃的單純形法直接求解，一般整數(shù)規(guī)劃必需尋找新的求解方法。 常用的求解整數(shù)規(guī)劃的方法有分枝定界法、割平面法等，對(duì)于特別的01規(guī)劃問題的求解，可以采用隱枚舉法和匈牙利法。 這里我們僅介紹整數(shù)規(guī)劃的分枝定界法，它也可以用于求解混合整數(shù)規(guī)劃問題和01規(guī)劃問題。 4.

7、2.1 案例 例4.6 求解下述整數(shù)規(guī)劃。 解 （1）首先，我們注意到式（4-1）的可行解集為圖4.2中陰影部分內(nèi)的整數(shù)格子點(diǎn)組成的集合，暫時(shí)不考慮整數(shù)限制條件（5）。圖4.2 例4.6 解相應(yīng)的線性規(guī)劃（1）（4），即式（4-1）的松弛問題LP： 得最優(yōu)解x1=2.25, x2=3.75, z0=41.25（2）其次，我們注意到線性規(guī)劃式（4-2）的解x1、x2具有小數(shù)，但這兩個(gè)變量在式（4-1）中都必須是整數(shù)，那就是說必須把小數(shù)部分“劃掉”。 我們注意到，對(duì)x2=3.75而言（對(duì)x1也是如此），最終的最優(yōu)解不會(huì)在3和4之間取值，亦即必然有： 這種表達(dá)式實(shí)際上是將x2在3和4間的小數(shù)部分劃掉

8、了，把可行域RO分成了R1和R2，顯然這種分法把原來線性規(guī)劃的解（2.25,3.75）排除出去了，但沒有排除任何整數(shù)可行解，這一過程稱為分枝， 即用兩個(gè)矛盾的約束條件式（4-3）分別代入原問題式（4-1）形成兩個(gè)子問題ILP1和ILP2： 解 ILP1的松弛問題LP1，得到 x1=1.8, x2=4, z=41。 解 ILP2的松弛問題LP2，得到 x1=3, x2=3, z2=39。 （3）修改上下界：從LP1和LP2的解，我們知道有 。（4）再分枝：因?yàn)樗沙趩栴}LP1的上界 比較大，我們對(duì)ILP1進(jìn)行分枝。 求解ILP3的松弛問題LP3得：x1=1, x2=4.44, z3=40.56對(duì)于

9、ILP4的松弛問題LP4，不難看出，無可行解。（5）再修改上下界，此時(shí)我們又有39z*40.56。（6）再分枝，繼續(xù)對(duì)ILP3進(jìn)行分枝（由于x2是小數(shù)，增限制條件 或 ）又得到：及（4-9） 求解ILP5的松弛問題LP5得到：x1=1, x2=4, z5=37 求解ILP6的松弛問題LP6得到： x1=0, x2=5, z6=40 至此，所有的子問題都已探明，求解結(jié)束。 我們得到了ILP0（即原問題）的最優(yōu)解： x1*=0, x2*=5, z*=40 為了清楚起見，可用樹形圖來表示分枝定界法的計(jì)算思路和步驟，如圖4.3所示。圖4.3 分枝定界法的計(jì)算思路和步驟4.2.2 分枝定界法的一般步驟

10、分枝定界法的一般步驟如下。 第1步，先不考慮原問題的整數(shù)限制，求解相應(yīng)的松弛問題，若求得最優(yōu)解，檢查它是否符合整數(shù)約束條件；如符合整數(shù)約束條件，即轉(zhuǎn)下一步。 第2步，定界。 第3步，分枝。 第4步，應(yīng)用對(duì)目標(biāo)函數(shù)估界的方法，或?qū)δ骋环种χ匾缘牧私?，確定出首先要解的某一分枝的后繼問題，并解此問題。 求解某子問題的松弛問題時(shí)，只要出現(xiàn)下列情況之一，該問題就已探明：（1）松弛問題沒有可行解，則原問題也沒有可行解；（2）松弛問題的最優(yōu)解恰好全取整數(shù)，則該最優(yōu)解也是其對(duì)應(yīng)的子問題的最優(yōu)解；（3）松弛問題的最大值小于現(xiàn)有的下界z，則無論其最優(yōu)解是否取整數(shù)值，都將對(duì)應(yīng)的子問題剪枝；已探明的子問題就不再用分

11、枝了，如果所有的子問題都已探明，則整數(shù)規(guī)劃（即原問題）的最優(yōu)解就一定可以求出，或可以判定它無解。4.3 指派問題 4.3.1 指派問題及其數(shù)學(xué)模型 指派問題（Assignment Problem）是運(yùn)籌學(xué)中一個(gè)具有理論意義又很有實(shí)用價(jià)值的問題。 其一般提法是：設(shè)有n個(gè)人，需要分派他們?nèi)プ鰊件工作。 例4.7 現(xiàn)有4輛裝載不同貨物的待卸車，派班員要分派給4個(gè)裝卸班組，每個(gè)班組卸一輛。 由于各個(gè)班組的技術(shù)專長不同，各個(gè)班組卸不同車輛所需時(shí)間如表4.2所示。 問派班員應(yīng)如何分配卸車任務(wù)，才能使卸車所花的總時(shí)間最少？ 解 為求解，先引入01變量xij。 并令 這樣，指派問題的數(shù)學(xué)模型就可表示為 4.3

12、.2 匈牙利法 我們知道，指派問題都要給出系數(shù)矩陣，例4.7的系數(shù)矩陣為 求出指派問題一個(gè)可行解并不難，問題是如何求出最優(yōu)解。 第1步，對(duì)系數(shù)矩陣進(jìn)行變換，使各行各列中都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素中減去該行的最小元素。（2）再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。 第2步，試求最優(yōu)解。（1）從行開始，遇到每行只有一個(gè)0元素就用括號(hào)括上，記做（0），然后劃去所在列的其他0元素，用 表示，遇到有兩個(gè)及其以上的0元素的行先放下。（2）進(jìn)行列檢驗(yàn)，給只有一個(gè)0元素的列中的0元素用括號(hào)括上，記做（0），然后劃去所在行的其他0元素，用 表示。（3）反復(fù)進(jìn)行第（1）項(xiàng)和第（2）項(xiàng)。（4）

13、若仍存在沒有括上的0元素，而且同行（列）的0元素至少有兩個(gè)，這時(shí)可以從有0元素最少的行（列）開始，比較這行（列）各0元素所在列（行）中0元素的數(shù)目；選擇給0元素少的那列（行）的0元素加括號(hào)，然后劃掉同行同列的其他元素。如此反復(fù)進(jìn)行，直到所有的0元素都已括上和劃掉為止。（5）若（0）元素的數(shù)目等于系數(shù)矩陣的階數(shù)n，那么該指派問題的最優(yōu)解已經(jīng)得到；否則，轉(zhuǎn)入第（3）項(xiàng)。 例4.8 求下面所示系數(shù)矩陣（cij）的指派問題的最優(yōu)解。 解 第1步，對(duì)原系數(shù)矩陣進(jìn)行變換，即 第2步，試求最優(yōu)解，按上述步驟運(yùn)算，得到矩陣 第3步，作最少的直線但要求覆蓋所有0元素，能覆蓋所有0元素的最少直線數(shù)等于在0處做出標(biāo)

14、號(hào)（0）的最多個(gè)數(shù)。 方法如下：（1）對(duì)沒有（0）的行打號(hào)。（2）對(duì)打號(hào)的行上的所有有0元素的列打號(hào)。（3）再對(duì)打號(hào)的列上有（0）的行打號(hào)。（4）重復(fù)第（2）項(xiàng)、第（3）項(xiàng)，直到得不出新的打號(hào)的行和列為止。（5）對(duì)沒有打號(hào)的行畫橫線，所有打號(hào)的列畫縱線，這就是能覆蓋所有0元素的最少的直線集合。 先對(duì)第4行打號(hào)，接著對(duì)第1列打號(hào)，再對(duì)第2行打號(hào)。 對(duì)第1行、第3行、第1列畫直線，得矩陣式為 第4步，對(duì)系數(shù)矩陣進(jìn)行變換，以增加0元素。 為此，在沒有被直線覆蓋的部分中找出最小元素。 然后對(duì)沒有畫直線的行，各元素都減去這個(gè)最小元素；而對(duì)畫直線的列，各元素都加上這個(gè)最小元素，以保持原來0元素的個(gè)數(shù)不變。

15、 在矩陣（4-15）中，沒有被直線覆蓋部分的最小元素為1，于是第2行、第4行都減去1；第1列加上1，得到新的矩陣 在式（4-17）中，具有n個(gè)位于不同行和不同列的0元素，這樣就得到了最優(yōu)解，其矩陣為 目標(biāo)函數(shù)值為 z=7+5+5+3=20 當(dāng)指派問題的系數(shù)矩陣經(jīng)過變換后，出現(xiàn)每行、每列都有兩個(gè)或兩個(gè)以上0元素時(shí)，可任選一行（列）中某一個(gè)0元素標(biāo)上（0），再劃去同行（列）的其他0元素。 4.3.3 對(duì)匈牙利法的兩點(diǎn)說明（1）指派問題中人數(shù)和工作任務(wù)數(shù)不相等時(shí)應(yīng)如何處理？（2）如果要求目標(biāo)函數(shù)值的最大值，應(yīng)如何處理？4.4 指派問題的Excel處理4.4.1 指派問題的模型特點(diǎn) 指派問題實(shí)際上是一個(gè)特殊的運(yùn)輸問題，可用表上作業(yè)法求解。 由于問題的要求，結(jié)果中只能有n個(gè)基變量為1，其余2n1n=n1個(gè)基變量為0（非基變量當(dāng)然為0）。 基變量為0的問題稱為退化問題。 所以，這是一個(gè)高度退化的TP（運(yùn)輸問題），表上作業(yè)法的迭代次數(shù)會(huì)很多。4.4.2 指派問題的Excel處理 例4.9 某市計(jì)劃年內(nèi)修建4座廠房，分別記為B1、B2、B3、B4，該市有4大建筑隊(duì)A1、A2、A3、A4都可能承擔(dān)這些任務(wù)。 （1）建立公式。 圖4.4 使用Exce