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

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

2.ILP問題與一般LP問題的區(qū)別在例1中，ILP問題實際上，此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ù)分支所得到的解進行比較。9二、分支規(guī)則情況2,4,5找到最優(yōu)解9滿足要求?結束分支YN三、運算步驟解松弛問題10滿足要求?結束分支YN三、運算步驟解松弛問題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)解可能存在兩個分支都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分支，直到有整數(shù)解出現(xiàn)，就可以進行定界過程。當存在很多變量有整數(shù)約束時，分支即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解。分支問題的松弛解貨物問題I問題IIx1x229/431Z212212問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個分支都是非方法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一、一個符號的說明適用范圍：全整數(shù)線性規(guī)劃第三節(jié)割平面法18一、一個符號的說明適用范圍：全整數(shù)線性規(guī)劃第三節(jié)割平面法二、Gomory約束的推導cj6400CBXBbx1x2x3x44x22011/3-1/36x15/210-1/62/3σj-2300-1/3-8/3例如1.令xi是松弛問題最優(yōu)解中取值為分數(shù)的一個基變量，由最優(yōu)單純形表可得：19二、Gomory約束的推導cj6400CBXBbx1x2x把(2)(3)代入(1)并移項得：20把(2)(3)代入(1)并移項得：20例4

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

為整數(shù)?結束寫出Gomory約束，并進行靈敏度分析YN例5三、計算步驟解松弛問題22Allxi為整數(shù)?結束寫出Gomory約束，并進行解：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解：由單純形法計算得松弛問題的最優(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用對偶單純形法進行計算，可得如下最優(yōu)表24cj790cj

790000

CBXBb

x1x2

x3

x4x5

x6

9x2

7x1

0x30x43414

0100101000-110010-4100016-7

-55

0000-2-7同樣用對偶單純形法進行計算，可得如下最優(yōu)表，此時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個位置（點）Ai供選擇。規(guī)定

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

(0‘)

(1)

(2)

(3)

(4)

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

38

0

2

1

1否是

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

(0‘)

(1)

(2)

(3)

(4)

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

-2316

否否否否

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

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

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

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

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

對打行上所有其它零元素對應的列打

再對打列上有()標記的零元素對應的行打

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

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

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

對未被直線覆蓋的各元素減去

對兩條直線交叉點覆蓋的元素加上

只有一條直線覆蓋的元素保持不變（以上步驟實際上仍是利用定理1）第四步：重新指派抹除所有標記，回到第二步，重新做標記；44第三步：調整第四步：重新指派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進行變換，使所有

cij’

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

cij反號，則等效于求min型問題；再利用定理1進行變換，使所有

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

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

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

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