5運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃

第六章整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃模型及其與線性規(guī)劃的區(qū)別整數(shù)規(guī)劃的求解——分支定界法、割平面法0-1整數(shù)線性規(guī)劃模型與求解指派問題模型與求解整數(shù)規(guī)劃的應(yīng)用——建模1第六章整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃模型及其與線性規(guī)劃的區(qū)別1一、整數(shù)線性規(guī)劃的一般形式例1（P133）某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如下表：貨物體積(米3/箱)重量(百斤/箱)利潤(百元/箱)甲乙54252010托運(yùn)限制2413問兩種貨物各托運(yùn)多少箱，可使獲得的利潤為最大？第一節(jié)整數(shù)規(guī)劃問題的提出2一、整數(shù)線性規(guī)劃的一般形式例1（P133）某廠擬用集裝箱托運(yùn)1.整數(shù)線性規(guī)劃模型的一般形式解：設(shè)托運(yùn)甲、乙兩種貨物x1，x2箱，用數(shù)學(xué)式可表示為：xj部分或全部為整數(shù)31.整數(shù)線性規(guī)劃模型的一般形式解：設(shè)托運(yùn)甲、乙兩種貨物x1，（1）求解方法方面

2.ILP問題與一般LP問題的區(qū)別在例1中，ILP問題實(shí)際上，此ILP問題的最優(yōu)解為：不考慮整數(shù)約束的最優(yōu)解為：(1)X(1)=(5,0)T不是(1)的可行解X(2)=(4,0)T雖是可行解，但不是最優(yōu)解4（1）求解方法方面2.ILP問題與一般LP問題的區(qū)做圖分析例1的最優(yōu)解(直觀)ILP問題的可行域不是凸集（2）理論方面x1x24840

1235673

125x1+4x2=242x1+5x2=13(4.8,0)TZ=96(4,1)TZ=905做圖分析例1的最優(yōu)解(直觀)ILP問題的可行域不是凸集（2二、整數(shù)線性規(guī)劃的分類1.純整數(shù)線性規(guī)劃2.全整數(shù)線性規(guī)劃在ILP問題（1）中，還要求aij,bi

全為整數(shù)。xj

全部為整數(shù)（1）4.0-1規(guī)劃在ILP問題（1）中，要求xj＝0或1.3.混合整數(shù)線性規(guī)劃在ILP問題（1）中，只要求部分xj為整數(shù).6二、整數(shù)線性規(guī)劃的分類1.純整數(shù)線性規(guī)劃2.全整數(shù)線性規(guī)劃在一、幾何解釋適用范圍：全整數(shù)線性規(guī)劃、純整數(shù)線性規(guī)劃、混合整數(shù)線性規(guī)劃例2（P135）求解整數(shù)線性規(guī)劃問題第二節(jié)分支定界法

(BranchandBoundMethod)7一、幾何解釋適用范圍：全整數(shù)線性規(guī)劃、純整數(shù)線性規(guī)劃、例2（解：圖解法。x1x2012345678910123456789x1+7x2=567x1+20x2=70BC問題B1Z1=349x1=4.00x2=2.10問題B2Z2=341x1=5.00x2=1.57x1<=[x(0)]x1>=[x(0)]+1X(0)=(4.81,1.82)Z0=3568解：圖解法。x1x201234567891012345678二、分支規(guī)則情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分支定界法情況6

問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分支所得到的解進(jìn)行比較。9二、分支規(guī)則情況2,4,5找到最優(yōu)解9滿足要求?結(jié)束分支YN三、運(yùn)算步驟解松弛問題10滿足要求?結(jié)束分支YN三、運(yùn)算步驟解松弛問題10例3

求解下列ILP問題

松弛問題的最優(yōu)解為：X*=(5/2,2),Z*=23分支B1:

x1

2分支B2:x1

311例3求解下列ILP問題松弛問題的最優(yōu)解為：X*=(5/2問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分支都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分支，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程。當(dāng)存在很多變量有整數(shù)約束時(shí)，分支即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解。分支問題的松弛解貨物問題I問題IIx1x229/431Z212212問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分支都是非方法1：圖解法x1x2012345678910123456782x1+x2=72x1+4x2=13X*=(5/2,2)Z*=23X*=(2,9/4)Z*=21X*=(3,1)Z*=2213方法1：圖解法x1x20123456789101234567方法2：單純形表cj

6400

CBXB

b

x1x2x3x44x2

6x125/2

011/3-1/310-1/62/3σj

-23

00-1/3-8/3松弛問題最優(yōu)單純形表如下：14方法2：單純形表cj640將約束條件直接寫入單純形表：cj

6400

CBXBb

x1x2x3x44x2

6x1

25/2

011/3-1/310-1/62/3σj

-23

00-1/3-8/3cj

64000

CBXBb

x1x2x3x4

x54x2

6x1

0x525/2-1/2

011/3-1/3010-1/62/30001/6[-2/3]1σj

-23

00-1/3-8/300

x5210001x50000[1]15將約束條件直接寫入單純形表：cj64cj

64000

CBXBb

x1x2x3x4x54x2

6x1

0x49/423/4

011/40-1/21000100-1/41-3/2σj

-21

00-10-4將另一約束條件直接寫入單純形表：cj

6400

CBXBb

x1x2x3x44x2

6x1

25/2

011/3-1/310-1/62/3

σj

-23

00-1/3-8/30x6-3-10001x6000016cj6400cj

64000

CBXBb

x1

x2x3x4x64x2

6x1

0x625/2-1/2

011/3-1/3010-1/62/3000-1/62/31σj-23

00-1/3-8/30cj

64000

CBXBb

x1x2

x3x4x64x2

6x1

0x3133

010121000-1001-4-6σj-22

000-4-217cj640一、一個(gè)符號(hào)的說明適用范圍：全整數(shù)線性規(guī)劃第三節(jié)割平面法18一、一個(gè)符號(hào)的說明適用范圍：全整數(shù)線性規(guī)劃第三節(jié)割平面法二、Gomory約束的推導(dǎo)cj6400CBXBbx1x2x3x44x22011/3-1/36x15/210-1/62/3σj-2300-1/3-8/3例如1.令xi是松弛問題最優(yōu)解中取值為分?jǐn)?shù)的一個(gè)基變量，由最優(yōu)單純形表可得：19二、Gomory約束的推導(dǎo)cj6400CBXBbx1x2x把(2)(3)代入(1)并移項(xiàng)得：20把(2)(3)代入(1)并移項(xiàng)得：20例4

寫出下列問題的Gomory約束cj6400CBXBbx1x2x3x44x22011/3-1/36x15/210-1/62/3σj-2300-1/3-8/3解：21例4寫出下列問題的Gomory約束cj6400CBXBbAllxi

為整數(shù)?結(jié)束寫出Gomory約束，并進(jìn)行靈敏度分析YN例5三、計(jì)算步驟解松弛問題22Allxi為整數(shù)?結(jié)束寫出Gomory約束，并進(jìn)行解：cj

7900

CBXBb

x1

x2x3x49x2

7x1

7/29/2

017/221/2210-1/223/22

-63

00-28/11-15/110x5-1/200-7/22-1/221x50000解：由單純形法計(jì)算得松弛問題的最優(yōu)表23解：cj790cj

79000

CBXBb

x1x2x3x4x59x2

7x1

0x3332/711/7

010011001/7-1/70011/7-22/7-59

000-1-80x6-4/7000-1/7000x6001-6/7用對(duì)偶單純形法進(jìn)行計(jì)算，可得如下最優(yōu)表24cj790cj

790000

CBXBb

x1x2

x3

x4x5

x6

9x2

7x1

0x30x43414

0100101000-110010-4100016-7

-55

0000-2-7同樣用對(duì)偶單純形法進(jìn)行計(jì)算，可得如下最優(yōu)表，此時(shí)xi的值都已經(jīng)是整數(shù)，解題完成。25cj7900四、幾何解釋26四、幾何解釋26x1x201234567891012345678-x1+3x2=67x1+x2=35X(1)=(9/2,7/2)Z(1)=63x2=3X(2)=(32/7,3)Z(2)=59x1+x2=7X*=(4,3)Z*=5527x1x201234567891012345678-x1+3x一、問題的提出例6（P142例4）某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（點(diǎn)）Ai供選擇。規(guī)定

在東區(qū)，由A1,A2,A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4,A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6,A7兩個(gè)點(diǎn)中至少選一個(gè)。如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇那幾個(gè)點(diǎn)可使年利潤為最大？則0-1規(guī)劃模型為：第四節(jié)0-1整數(shù)線性規(guī)劃28一、問題的提出例6（P142例4）某公司擬在市東、西、南三區(qū)0-1整數(shù)線性規(guī)劃的一般形式290-1整數(shù)線性規(guī)劃的一般形式293.不斷更換過濾條件1.把目標(biāo)函數(shù)的系數(shù)按升序排列[max]，約束條件做相應(yīng)調(diào)整2.把所有的解按一定的次序排列例7（P144例6）用隱枚舉法求解下列0-1規(guī)劃問題二、隱枚舉法求解0-1整數(shù)線性規(guī)劃的思路303.不斷更換過濾條件1.把目標(biāo)函數(shù)的系數(shù)按升序排列[max]解：目標(biāo)函數(shù)的系數(shù)按升序排列31解：目標(biāo)函數(shù)的系數(shù)按升序排列31通過試探可行解(x1,x2,x3)=(1,0,0)引入下列過濾條件：點(diǎn)(x2,x1,x3)條件是否滿足條件Z值

(0)

(1)

(2)

(3)

(4)

(0,0,0)(0,0,1)

05

-1

1

0

1

否是

0532通過試探可行解(x1,x2,x3)=(1,0,0)改進(jìn)過濾條件：點(diǎn)(x2,x1,x3)條件是否滿足條件Z值

(0‘)

(1)

(2)

(3)

(4)

(0,1,0)(0,1,1)

38

0

2

1

1否是

833改進(jìn)過濾條件：點(diǎn)條改進(jìn)過濾條件：點(diǎn)(x2,x1,x3)條件是否滿足條件Z值

(0‘)

(1)

(2)

(3)

(4)

(1,0,0)(1,0,1)(1,1,0)(1,1,1)

-2316

否否否否

34改進(jìn)過濾條件：點(diǎn)條1.結(jié)論任何一個(gè)非負(fù)整數(shù)y都可表示為2.0-1規(guī)劃與全、純整數(shù)線性規(guī)劃的轉(zhuǎn)換1)0-1規(guī)劃問題就是全、純整數(shù)線性規(guī)劃問題2)全、純整數(shù)線性規(guī)劃問題可以利用上述結(jié)論轉(zhuǎn)化為0-1規(guī)劃問題三、0-1規(guī)劃與全、純整數(shù)線性規(guī)劃的轉(zhuǎn)換351.結(jié)論任何一個(gè)非負(fù)整數(shù)y都可表示為2.0-1規(guī)劃與例8解：把代入純整數(shù)規(guī)劃的目標(biāo)函數(shù)和約束條件即可。36例8解：把代入純整數(shù)規(guī)劃的目標(biāo)函數(shù)和約束條件即可。36一、問題的提出例9

有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如下表所示，問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？第五節(jié)指派問題任務(wù)工時(shí)人員ABCD人員甲乙丙丁109785877546523451111任務(wù)111137一、問題的提出例9有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任解：設(shè)則此指派問題的模型為：指派問題的一般形式：38解：設(shè)則此指派問題的模型為：指派問題的一般形式：38二、求解指派問題的理論依據(jù)定理1

在原指派問題的效率矩陣中同行或同列加上某一常數(shù)，所得指派問題與原問題同解。定理2

方陣中獨(dú)立零元素的最多個(gè)數(shù)等于覆蓋所有零元素的最少直線數(shù)。定理1的證明：39二、求解指派問題的理論依據(jù)定理1在原指派問題的效率矩陣以例1的求解為例：第一步：變換效率矩陣，使每行每列至少有一個(gè)零行變換：找出每行最小元素，從該行各元素中減去之列變換：找出每列最小元素，從該列各元素中減去之三、匈牙利法步驟()()()()()40以例1的求解為例：第一步：變換效率矩陣，使每行每列至少有一個(gè)第二步：試指派1.逐行檢查，若該行只有一個(gè)未標(biāo)記的零，對(duì)其加()標(biāo)記，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該行有二個(gè)或以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一行檢查，直到所有行檢查完；

2.逐列檢查，若該列只有一個(gè)未標(biāo)記的零，對(duì)其加()標(biāo)記，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該列有二個(gè)或以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一列檢查，直到所有列檢查完；()*()*()*41第二步：試指派1.逐行檢查，若該行只有一個(gè)未標(biāo)記的零，對(duì)重復(fù)1、2后，可能出現(xiàn)三種情況：情況a：每行都有一個(gè)(0)，顯然已找到最優(yōu)解，令對(duì)應(yīng)(0)位置的xij=1；情況b：仍有零元素未標(biāo)記，此時(shí)，一定存在某些行和列同時(shí)有多個(gè)零，稱為僵局狀態(tài)，因?yàn)闊o法采用1、2中的方法繼續(xù)標(biāo)記。情況c：所有零都已標(biāo)記，但標(biāo)有()的零的個(gè)數(shù)少于n；劃線過程：對(duì)沒有標(biāo)記()的行打

對(duì)打行上所有其它零元素對(duì)應(yīng)的列打

再對(duì)打列上有()標(biāo)記的零元素對(duì)應(yīng)的行打

重復(fù)以上步驟，直至無法繼續(xù)對(duì)沒有打的行劃橫線，對(duì)所有打的列劃豎線

3.打破僵局。令未標(biāo)記零對(duì)應(yīng)的同行同列上其它未標(biāo)記零的個(gè)數(shù)為該零的指數(shù)，選指數(shù)最小的先標(biāo)記()；采用這種方法直至所有零都被標(biāo)記，此時(shí)或出現(xiàn)情況a，或出現(xiàn)情況c。42重復(fù)1、2后，可能出現(xiàn)三種情況：劃線過程：3.打破僵局。令未

劃線后會(huì)出現(xiàn)兩種情況：(1)標(biāo)記()的零少于n個(gè)，但劃有n條直線，說明矩陣中已存在n個(gè)不同行不同列的零，但打破僵局時(shí)選擇不合理，沒能找到?；氐絙重新標(biāo)記；(2)少于n條直線，到第三步；43劃線后會(huì)出現(xiàn)兩種情況：43第三步：調(diào)整在未劃線的元素中找最小者，設(shè)為

對(duì)未被直線覆蓋的各元素減去

對(duì)兩條直線交叉點(diǎn)覆蓋的元素加上

只有一條直線覆蓋的元素保持不變（以上步驟實(shí)際上仍是利用定理1）第四步：重新指派抹除所有標(biāo)記，回到第二步，重新做標(biāo)記；44第三步：調(diào)整第四步：重新指派44答：最優(yōu)分配方案為x13=x21=x34=x42=1，其余為0，即甲

C，乙A，丙D，丁B，OBJ=20()*()**()*()45答：最優(yōu)分配方案為x13=x21=x34=x42要求所有cij0若某些

cij<0

，則利用定理1進(jìn)行變換，使所有

cij’

0要求目標(biāo)函數(shù)為min型對(duì)于max型目標(biāo)函數(shù)，將效率矩陣中所有

cij反號(hào)，則等效于求min型問題；再利用定理1進(jìn)行變換，使所有

cij’0。例如：某公司要指派3名推銷員去3個(gè)地區(qū)推銷某種產(chǎn)品，各推銷員在各地區(qū)推銷該產(chǎn)品的預(yù)期收益見下表（單位：萬元），試給出總收益最大的指派方案。

地區(qū)收益人員ABC甲乙丙151821192322261716注意46要求所有cij0例如：某公司要指派3名推銷員去3個(gè)地區(qū)推例10（P149例8）求下列指派問題的最優(yōu)解解：第一步，變換()()()()()47例10（P149例8）求下列指派問題的最優(yōu)解解：第一步，變換第二步，試指派

()*()*()**()*48第二步，試指派()*()*()**(第三步，調(diào)整第四步，重新指派()*()*()*49第三步，調(diào)整第四步，重新指派()*()*(答：最優(yōu)分配方案為x12=x23=x35=x44=x51=1，其余為0，

Z*=7+6+9+6+4=32()**()50答：最優(yōu)分配方案為x12=x23=x35=x441.任務(wù)多、人少的情況分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如下表所示（單位：小時(shí)）。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可以完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間最少的指派方案。思考任務(wù)時(shí)間人員ABCDE甲乙丙丁2529314237393826203334272840322442362345511.任務(wù)多、人少的情況分配甲、乙、丙、丁四個(gè)人假設(shè)增加一個(gè)人，記為戊，他完成各項(xiàng)工作的時(shí)間取甲、乙