運籌學課件Ch3整數(shù)規(guī)劃

3.1整數(shù)規(guī)劃數(shù)學模型

MathematicalModelofIP3.2純整數(shù)規(guī)劃的求解

SolvingPureIntegerProgramming

3.3

0－1規(guī)劃的求解

SolvingBinaryIntegerProgramming

Chapter3整數(shù)規(guī)劃IntegerProgramming運籌學OperationsResearch1/12/20233.1整數(shù)規(guī)劃數(shù)學模型

MathematicalModelofIP1/12/2023

一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)，則這個規(guī)劃稱為整數(shù)規(guī)劃。當要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。如果模型是線性的，稱為整數(shù)線性規(guī)劃。本章只討論整數(shù)線性規(guī)劃。

很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題1.變量是人數(shù)、機器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)2.對某一個項目要不要投資的決策問題，可選用一個邏輯變量x，當x=1表示投資，x=0表示不投資；3.人員的合理安排問題，當變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023【例3.1】某人有一背包可以裝10公斤重、0.025m3的物品。他準備用來裝甲、乙兩種物品，每件物品的重量、體積和價值如表3-1所示。問兩種物品各裝多少件，所裝物品的總價值最大？表3-1【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學模型為：(3.1)3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

物品重量（公斤/每件）體積（m3/每件）價值(元/每件)甲乙1.20.80.0020.0025431/12/2023如果不考慮x1、x2取整數(shù)的約束（稱為（3.1）的松弛問題），線性規(guī)劃的可行域如圖3-1中的陰影部分所示。3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

圖3-11/12/2023

用圖解法求得點B為最優(yōu)解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必須取整數(shù)值，實際上整數(shù)規(guī)劃問題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點。用湊整法來解時需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）雖屬可行解，但代入目標函數(shù)得Z=33,并非最優(yōu)。實際上問題的最優(yōu)解是（5，5），Z=35。即兩種物品各裝5件，總價值35元。

由圖3－1知，點（5，5）不是可行域的頂點，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。還有些問題用線性規(guī)劃數(shù)學模型無法描述，但可以通過設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學模型。3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023【例3.2】在例3.1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學模型，使所裝物品價值最大。（1）所裝物品不變；（2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是4和3，載重量和體積的約束為【解】此問題可以建立兩個整數(shù)規(guī)劃模型，但用一個模型描述更簡單。引入0－1變量（或稱邏輯變量）yi，令i=1,2分別是采用背包及旅行箱裝載。3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023（1）

由于所裝物品不變，式(3.1)約束左邊不變，整數(shù)規(guī)劃數(shù)學模型為（2）

由于不同載體所裝物品不一樣，數(shù)學模型為3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023式中M為充分大的正數(shù)。從上式可知，當使用背包時(y1=1，y2=0)，式(b)和(d)是多余的；當使用旅行箱時(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：

同樣可以討論對于有m個條件互相排斥、有m（≤m、≥m）個條件起作用的情形。3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023（1)右端常數(shù)是k個值中的一個時，類似式(3.2)的約束條件為（2)對于m組條件中有k（≤m）組起作用時，類似式(3.3)的約束條件寫成這里yi=1表示第i組約束不起作用（如y1=1式(3.3b)、(3.3d)不起作用），yi=0表示第i個約束起作用。當約束條件是“≥”符號時右端常數(shù)項應(yīng)為（3)對于m個條件中有k（≤m）個起作用時，約束條件寫成3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

1/12/2023【例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個起作用3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

或1/12/2023（3）右端常數(shù)是5個值中的1個3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

（2）兩組約束只有一組起作用1/12/2023【例3.4】企業(yè)計劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工、外協(xié)加工任意一種形式生產(chǎn)．已知每種生產(chǎn)的固定費用、生產(chǎn)該產(chǎn)品的單件成本以及每種生產(chǎn)形式的最大加工數(shù)量（件）限制如表3－2所示，怎樣安排產(chǎn)品的加工使總成本最小．表3－2【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費用為3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

固定成本（元）變動成本（元／件）最大加工數(shù)（件）本企業(yè)加工50081500外協(xié)加工Ⅰ80052000外協(xié)加工Ⅱ6007不限1/12/2023式中kj是固定成本，cj是單位產(chǎn)品成本．設(shè)0－1變量yj，令數(shù)學模型為

3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

（3.4）式（3.4）中是處理xj與yj一對變量之間邏輯關(guān)系的特殊約束，當xj>0時yj=1,當xj＝0時，為使Z最小化，有yj=0。例3.4是混合整數(shù)規(guī)劃問題．用WinQSB軟件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=25400.1/12/2023作業(yè)：教材P751,2，3，4，5，61.線性整數(shù)規(guī)劃模型的特征2.什么是純（混合）整數(shù)規(guī)劃3.0－1規(guī)劃模型的應(yīng)用3.1整數(shù)規(guī)劃的數(shù)學模型

MathematicalModelofIP

下一節(jié)：純整數(shù)規(guī)劃的求解1/12/20233.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming1/12/2023分枝定界法的步驟：1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；2.

若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；3.任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界；4.

檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算,若還存在非整數(shù)解并且目標值大于（max）整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。3.2.1求解純整數(shù)規(guī)劃的分枝定界法3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023【例3.5】用分枝定界法求解例5.1【解】先求對應(yīng)的松弛問題（記為LP0）：

用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示。3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/20238.3310松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC103.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/20231010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1/12/20231010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81/12/20231010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP51/12/2023盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥71/12/2023設(shè)純整數(shù)規(guī)劃松弛問題的最優(yōu)解設(shè)xi不為整數(shù)，3.2.2求解IP的割平面法3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023將分離成一個整數(shù)與一個非負真分數(shù)之和：則有等式兩邊都為整數(shù)并且有3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面，或分數(shù)切割式，或R.E.Gomory(高莫雷)約束方程。

將Gomory約束加入到松弛問題的最優(yōu)表中，用對偶單純形法計算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。則3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023例如，x1行：移項：令加入松弛變量s1得同理，對于x2行有：3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023【例3.6】用割平面法求解下列IP問題【解】放寬變量約束，對應(yīng)的松弛問題是

3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。

最優(yōu)解X(0)＝(5/2，15/4),不是IP的最優(yōu)解。選擇表3-3的第一行(也可以選第二行)為源行3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-31/12/2023分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將式(3.8)作為約束條件添加到表3－3中，用對偶單純形法計算，如表3－4所示

3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/12/2023Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4[－2]0015/215/4－2→λj00－5/8－1/4↑0430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最優(yōu)解X(1)＝(3，3)，最優(yōu)值Z＝21。所有變量為整數(shù)，X(1)就是IP的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復上述計算過程。3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

表3－4如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。1/12/2023作業(yè)：教材P76T7，8

1.理解分枝與定界的含義2.選擇合適的“枝”生“枝”3.掌握何時停止生“枝”4.領(lǐng)會割平面法的基本原理5.分離源行，求出Gomory約束6.在最優(yōu)表中增加Gomory約束，用對偶單純形法迭代3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

下一節(jié)：0－1規(guī)劃的求解1/12/20233.30－1規(guī)劃的求解SolvingBIP

1/12/20233.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：

1.找出任意一可行解，目標函數(shù)值為Z0

2.

原問題求最大值時，則增加一個約束當求最小值時，上式改為小于等于約束

3.列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值

4.目標函數(shù)值最大（最小）的解就是最優(yōu)解3.30－1規(guī)劃的求解SolvingBIP

1/12/2023【例3.7】用隱枚舉法求解下列BIP問題【解】（1）不難看出，當所有變量等于0或1的任意組合時，第一個約束滿足，說明第一個約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到X0＝(1，0，0，1)是一個可行解，目標值Z0＝11是BIP問題的下界，構(gòu)造一個約束：，原BIP問題變?yōu)?.30－1規(guī)劃的求解SolvingBIP

1/12/2023(2)列出變量取值0和1的組合，共24＝16個，分別代入約束條件判斷是否可行。首先判斷式（3.9a）是否滿足，如果滿足，接下來判斷其它約束，否則認為不可行，計算過程見表3－7所示。3.30－1規(guī)劃的求解SolvingBIP

1/12/2023jXj3.9a3.9b3.9c3.9dZjjXj3.9a3.9b3.9c3.9dZj1(0,0,0,0)×

9(1,0,0,0)×

2(0,0,0,1)×

10(1,0,0,1)√√√√113(0,0,1,0)×

11(1,0,1,0)×

4(0,0,1,1)×

12(1,0,1,1)√√√√145(0,1,0,0)×

13(1,1,0,0)×

6(0,1,0,1)×

14(1,1,0,1)√√√√137(0,1,1,0)×

15(1,1,1,0)√×

8(0,1,1,1)×

16(1,1,1,1)√√√×

表3－5(3)由表3-5知，BIP問題的最優(yōu)解：X＝（1，0，1，1），最優(yōu)值Z＝143.30－1規(guī)劃的求解SolvingBIP

1/12/2023選擇不同的初始可行解，計算量會不一樣。一般地，當目標函數(shù)求最大值時，首先考慮目標函數(shù)系數(shù)最大的變量等于1，如例3.8。當目標函數(shù)求最小值時，先考慮目標函數(shù)系數(shù)最大的變量等于0。在表3－7的計算過程中，當目標值等于14時，將其下界11改為14，可以減少計算量。3.3.2分枝－隱枚舉法求解BIP問題將分枝定界法與隱枚舉法結(jié)合起來用，得到分枝－隱枚舉法。計算步驟如下：（1）將BIP問題的目標函數(shù)的系數(shù)化為非負，如3.30－1規(guī)劃的求解SolvingBIP

1/12/2023當變量作了代換后，約束條件中的變量也相應(yīng)作代換。（3）求主枝：目標函數(shù)是max形式時令所有變量等于1，得到目標值的上界；目標函數(shù)是min形式時令所有變量等于0，得到目標值的下界；如果主枝的解滿足所有約束條件則得到最優(yōu)解，否則轉(zhuǎn)下一步；（4）分枝與定界：從第一個變量開始依次取“1”或“0”，求極大值時其后面的變量等于“1”，求極小值時其后面的變量等于“0”，用分枝定界法搜索可行解和最優(yōu)解。分枝－隱枚舉法是從非可行解中進行分枝搜索可行解，第（1）步到第（3）步用了隱枚舉法的思路，第（4）步用了分枝定界法的思路。3.30－1規(guī)劃的求解SolvingBIP

(2)變量重新排序：變量依據(jù)目標函數(shù)系數(shù)值按升排序；1/12/2023停止分枝和需要繼續(xù)分枝的原則：（1）當某一子問題是可行解時則停止分枝并保留；（2）不是可行解但目標值劣于現(xiàn)有保留分枝的目標值時停止分枝并剪枝；（3）后續(xù)分枝變量無論取“1”或“0”都不能得到可行解時停止分枝并剪枝；（4）當某一子問題不可行但目標值優(yōu)于現(xiàn)有保留分枝的所有目標值，則要繼續(xù)分枝。

【例3.8】用分枝－隱枚舉法求解下列BIP問題3.30－1規(guī)劃的求解SolvingBIP

1/12/2023解（1）目標函數(shù)系數(shù)全部非負，直接對變量重新排序（2）求主枝：令X＝(1，1，1，1)得到主枝1，檢查約束條件知(3.10c)不滿足，則進行分枝。（3）令x2=0同時令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝停止并保留，如表3-8及圖3-8所示。3.30－1規(guī)劃的求解SolvingBIP

1/12/2023表3.8令x2=1同時令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1時只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝過程結(jié)束。整個計算過程可用圖3－2和表3.8表示。分枝(x2,x3,x4,x1)3.10a3.10b3.10cZj可行性1(1,1,1,1)√√×16不可行2(0,0,1,1)√√√11可行3(0,1,1,1)√√√14可行4(1,0,1,1)√√√13可行5(1,1,0,1)×

11不可行6(1,1,1,0)×

10不可行3.30－1規(guī)劃的求解SolvingBIP

1/12/2023搜索到3個可行解，3個目標值中Z3最大，因此X3是最優(yōu)解，轉(zhuǎn)換到原問題的最優(yōu)解為X＝（1，0，1，1），最優(yōu)值Z＝14，計算結(jié)束。圖3－23.30－1規(guī)劃的求解SolvingBIP

1/12/2023【例3.9】用分枝－隱枚舉法求解下列BIP問題解（1）令x2=1－x'2及x5=1－x'5，代入模型后整理得3.30－1規(guī)劃的求解SolvingBIP

1/12/2023（2）目標函數(shù)系數(shù)按升序?qū)?yīng)的變量重新排列得到模型（3）求主枝。由于目標函數(shù)求最小值，令所有變量等于零，得到主枝的解X1＝（0，0，0，0，0），Z1＝－7，檢驗約束條件知X1不可行，進行分枝。（4）取x1=1和x1=0，分別其它變量等于“1”和

“0”分枝，判斷可行性，計算過程