運(yùn)籌學(xué)ppt課件Ch3整數(shù)規(guī)劃

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

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

SolvingPureIntegerProgramming

3.3

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

SolvingBinaryIntegerProgramming

Chapter3整數(shù)規(guī)劃IntegerProgramming運(yùn)籌學(xué)OperationsResearch1/18/2023ppt課件3.1整數(shù)規(guī)劃數(shù)學(xué)模型

MathematicalModelofIP1/18/2023ppt課件

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

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

MathematicalModelofIP

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

MathematicalModelofIP

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

MathematicalModelofIP

圖3-11/18/2023ppt課件

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

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

MathematicalModelofIP

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

MathematicalModelofIP

1/18/2023ppt課件（1）由于所裝物品不變，式(3.1)約束左邊不變，整數(shù)規(guī)劃數(shù)學(xué)模型為（2）

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

MathematicalModelofIP

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

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

MathematicalModelofIP

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

MathematicalModelofIP

1/18/2023ppt課件【例3.3】試引入0－1變量將下列各題分別表達(dá)為一般線性約束條件（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個(gè)約束只有1個(gè)起作用3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

MathematicalModelofIP

或1/18/2023ppt課件（3）右端常數(shù)是5個(gè)值中的1個(gè)3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

MathematicalModelofIP

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

MathematicalModelofIP

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

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

MathematicalModelofIP

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

MathematicalModelofIP

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

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

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

1/18/2023ppt課件【例3.5】用分枝定界法求解例5.1【解】先求對(duì)應(yīng)的松弛問(wèn)題（記為L(zhǎng)P0）：

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

1/18/2023ppt課件8.3310松弛問(wèn)題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC103.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/18/2023ppt課件1010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1/18/2023ppt課件1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81/18/2023ppt課件1010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP51/18/2023ppt課件盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過(guò)程可用下圖表示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無(wú)可行解x2≥71/18/2023ppt課件設(shè)純整數(shù)規(guī)劃松弛問(wèn)題的最優(yōu)解設(shè)xi不為整數(shù)，3.2.2求解IP的割平面法3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/18/2023ppt課件將分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和：則有等式兩邊都為整數(shù)并且有3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

1/18/2023ppt課件加入松弛變量si得此式稱為以xi行為源行（來(lái)源行）的割平面，或分?jǐn)?shù)切割式，或R.E.Gomory(高莫雷)約束方程。

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

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

1/18/2023ppt課件【例3.6】用割平面法求解下列IP問(wèn)題【解】放寬變量約束，對(duì)應(yīng)的松弛問(wèn)題是

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

1/18/2023ppt課件加入松弛變量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/18/2023ppt課件分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將式(3.8)作為約束條件添加到表3－3中，用對(duì)偶單純形法計(jì)算，如表3－4所示

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

1/18/2023ppt課件Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/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ù)切割，重復(fù)上述計(jì)算過(guò)程。3.2純整數(shù)規(guī)劃的求解SolvingPureIntegerProgramming

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

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

下一節(jié)：0－1規(guī)劃的求解1/18/2023ppt課件3.30－1規(guī)劃的求解SolvingBIP

1/18/2023ppt課件3.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：

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

2.

原問(wèn)題求最大值時(shí)，則增加一個(gè)約束當(dāng)求最小值時(shí)，上式改為小于等于約束

3.列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（*），若滿足再檢驗(yàn)其它約束，若不滿足式（*），則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值

4.目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解3.30－1規(guī)劃的求解SolvingBIP

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

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

1/18/2023ppt課件jXj3.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問(wèn)題的最優(yōu)解：X＝（1，0，1，1），最優(yōu)值Z＝143.30－1規(guī)劃的求解SolvingBIP

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

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

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

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

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

1/18/2023ppt課件表3.8令x2=1同時(shí)令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1時(shí)只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝過(guò)程結(jié)束。整個(gè)計(jì)算過(guò)程可用圖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/18/2023ppt課件搜索到3個(gè)可行解，3個(gè)目標(biāo)值中Z3最大，因此X3是最優(yōu)解，轉(zhuǎn)換到原問(wèn)題的最優(yōu)解為X＝（1，0，1，1），最優(yōu)值Z＝14，計(jì)算結(jié)束。圖3－23.30－1規(guī)劃的求解SolvingBIP

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

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

“0”分枝，判斷可行性，計(jì)算過(guò)程參見表3