1整數(shù)規(guī)劃的數(shù)學模型2分枝定界法3割平面法40-1型整數(shù)規(guī)課件

1.整數(shù)規(guī)劃的數(shù)學模型2.分枝定界法3.割平面法4.0-1型整數(shù)規(guī)劃5.指派問題第五章整數(shù)規(guī)劃2023/10/5整數(shù)規(guī)劃的數(shù)學模型max(min)(c1

x1+c2x2+…+

cnxn)a11

x1+a12x2+…+a1nxn(=,)

b1a21

x1+a22x2+…+a2nxn(=,)

b2……...am1

x1+am2x2+…+amnxn(=,)

bmx1~n

0

且取整數(shù)純整數(shù)規(guī)劃:所有變量都有取整約束混合整數(shù)規(guī)劃:只有部分變量有取整約束2023/10/5分枝定界法1.分枝定界法的基本思路2.第65頁例5-13.練習題2023/10/5分枝定界法的基本思路

2023/10/5分枝定界法的基本思路2023/10/5第65頁例5-1maxz=40x1+90x29x1+7x2567x1+20x270x1，x20且取整

2023/10/5用分枝定界法解例5-11.求解相應的線性規(guī)劃L0maxz=40x1+90x29x1+7x2567x1+20x270x1，x202023/10/5用分枝定界法解例5-1

x2

59x1+7x2=56

4

3

27x1+20x2=70

1

0

12345678910

x1L0:x*=(4.81,1.82),Z*=356

2023/10/5用分枝定界法解例5-12.將L0分解為L1和L2L1：maxz=40x1+90x29x1+7x2567x1+20x270

x1

4x1，x20L2：maxz=40x1+90x29x1+7x2567x1+20x270

x1

5x1，x20L1：X*=(4,2.10),Z*=349

L2：X*=(5,1.57),Z*=341

2023/10/5用分枝定界法解例5-13.分解L1形成L3、L4，其中：

L3={L1,x22}L4={L1,x23}

L3:X*=(4,2),Z*=340

L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)舍棄L42023/10/5用分枝定界法解例5-14.分解L2形成L5、L6，其中：

L5={L2,x21}L6={L2,x22}

L5:X*=(5.44,1),Z*=308

L6:無可行解(1)舍棄L5、L6；(2)得最優(yōu)解X*=(4,2),Z*=340。

2023/10/5例5-1求解過程示意圖L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6無可行解2023/10/5練習題maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整2023/10/5求解練習題首先求解線性規(guī)劃L0:maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~602023/10/5求解練習題

2023/10/5求解練習題

2023/10/5求解練習題

2023/10/5求解練習題

2023/10/5求解練習題L0（0，15/2，9/2）111/2

L1（0，7，5）55

L2無可行解2023/10/5割平面法1.割平面法的基本思路2.例3.練習題2023/10/5割平面法的基本思路同分枝定界法一樣，割平面法也是一種利用連續(xù)模型求解非連續(xù)問題的常用方法。割平面法的基本思路是：當?shù)玫降慕獠粷M足取整約束時，就設法在問題上增加一個約束條件，把包含這個非整數(shù)解的一部分可行域從原來的可行域中割除，但不割掉任何一個整數(shù)可行解。這個新增加的約束條件就稱為割平面。2023/10/5例maxz=x1+x2-x1+x213x1+x24x1，x20且取整

2023/10/5用割平面法解例1.求解相應的線性規(guī)劃L0maxz=x1+x2-x1+x213x1+x24x1，x20

2023/10/5用割平面法解例非整數(shù)解，為建立割平面，首先考慮非整數(shù)解中余數(shù)最大的基變量，此例中x1、x2的余數(shù)均為3/4，不妨選取x2：x2+3/4x3+1/4x4=7/4

2023/10/5用割平面法解例

x2+3/4x3+1/4x4=7/4現(xiàn)將各系數(shù)分成整數(shù)和非負真分數(shù)兩部分，從而可得：(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)將整數(shù)部分的變量移至等式右端有：3/4x3+1/4x4=3/4+（1-x2）非負整數(shù)解(1-x2)為整數(shù)，左端非負故有：3/4x3+1/4x4=3/4+非負整數(shù)從而：3/4x3+1/4x4

3/4或x2

1以x2

1為割平面可使可行域減少一個包括A點在內的三角形。

2023/10/5x2A1

01x1用割平面法解例

2023/10/5用割平面法解例2023/10/5練習題maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2023/10/5求解練習題

2023/10/5求解練習題選取x2：1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+（7-x2）

于是有割平面：1/2x1+1/2x5

1/2或

x272023/10/5求解練習題

2023/10/5求解練習題2023/10/50-1型整數(shù)規(guī)劃1.0-1規(guī)劃：0-1規(guī)劃是整數(shù)規(guī)劃的特例，是所有決策變量僅取0和1的整數(shù)規(guī)劃問題。2.引例（1）第69頁例5-3（2）引例23.0-1規(guī)劃的隱枚舉法（1）隱枚舉法的基本步驟（2）第70頁例5-4（3）第71頁例5-52023/10/5第69頁例5-3

某公司擬在東、西、南三個區(qū)建立銷售門市部，擬議中有7個場點A1~7可供選擇。東區(qū)的三個點A1~3最多選兩個，西區(qū)的兩個點A4~5最少選一個，南區(qū)的兩個點A6~7最少選一個。如果建設Ai點，需要投資bi元，年可獲利ci元，公司可籌集到的投資總額為B元，問應如何決策才能使年利潤最大。

2023/10/5例5-3

令xi=0或1，其中：

xi=0表示第I個點未被選取

xi=1表示第I個點被選取其數(shù)學模型為：

x1+x2+x32x4+x51

x6+x71

2023/10/5引例2

兩種運輸方式的限制條件分別為：6x1+4x2307x1+3x240互斥的約束統(tǒng)一于一個模型中：6x1+4x230+Mx37x1+3x240+M(1-x3)

其中x3為0-1變量。2023/10/5隱枚舉法的基本步驟

1.目標函數(shù)極小化；2.目標函數(shù)系數(shù)非負化，如果xj的系數(shù)為負數(shù)，可令xj=1-xj

；3.決策變量按其目標函數(shù)系數(shù)的大小排列；4.令所有變量為“0”，檢查該解的可行性，如果可行此解即為最優(yōu)解，如果不可行進入下一步；5.按變量的順序依次令各變量分別取“0”或“1”，根據分枝定界的原理進行剪枝，直至結束。2023/10/5第70頁例5-4Maxz=3x1-2x2+5x3

x1+2x2-x32x1+4x2+x34x1~3=0或1第一步：Minw=-3x1+2x2-5x3

x1+2x2-x32x1+4x2+x34x1~3=0或1

2023/10/5例5-4第二步：令x1=1-x1，x3=1-x3Minw=3x1+2x2+5x3

-8-x1+2x2+x32-x1+4x2-x32x1~3=0或1第三步：Minw=2x2+3x1+5x3

-8

2x2-x1+x32

4x2-x1-x32x1~3=0或1第四步：令所有變量為“0”，得可行解，所以原問題的最優(yōu)解為（1，0，1），最優(yōu)值為8。2023/10/5maxz=8x1+2x2-4x3-7x4-5x5

3x1+3x2+x3+2x4+3x54

5x1+3x2-2x3-x4+x54

x1~5=0或1經前三步有：令x1=1-x1，x2=1-x2minw=2x2+

4x3+5x5+7x4+8x1-10

3x2-x3-3x5-2x4+3x12

3x2+2x3-x5+x4+5x14

x1~5=0或1

第71頁例5-52023/10/5

例5-5

w=-8

x2=12

w=-101

x2=0

w=-63

2023/10/5

例5-5

w=-44(可行解)

w=-8x3=1x2=12w=-10x3=0w=-315x2=0w=-632023/10/5例5-5

w=-6x5=18w=-1x3=16x5=0w=-69w=1w=23x3=0w=-5x4=112w=-5x5=1107x5=0w=-3x4=0w=311132023/10/5指派問題

1.指派問題的內涵2.指派問題的數(shù)學模型3.指派問題的求解4.指派問題的擴展2023/10/5指派問題的內涵

有m項工作，恰好有m個人來完成，一個人只完成一項工作，一項工作只由一個人來完成，由于個人的專長不同，完成任務的效率也就不同，于是產生了應指派哪個人去完成哪項任務，才能使完成m

項任務的總效率最高的問題，此類問題稱為指派問題或分派問題。指派問題同運輸問題一樣，是具有一定模型特征一類問題的總稱，如m項加工任務如何在m臺機床上分配；m

條航線如何指定m

艘船去航行等等。指派問題是運輸問題的特例，也是0-1規(guī)劃問題的特例。這一點可由指派問題的數(shù)學模型體現(xiàn)出來。2023/10/5指派問題的數(shù)學模型2023/10/5指派問題的求解－匈牙利法2.匈牙利法的基本步驟(1)第73頁例5-6(2)第74頁例5-7(3)基本步驟總結2023/10/5指派問題的擴展

1.人員與工作不匹配：引入假想的工作或人員由于假想的工作或人員代表的是剩余的工作或人員，所以其對應的效率矩陣元素全都為零。

例2.目標函數(shù)求極大值：效率矩陣的每一元素乘“-1”，并進一步使其非負化。

第73頁例5-62023/10/5第73頁例5-6

2023/10/5例5-62023/10/5第74頁例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-7

2023/10/5例5-72023/10/5基本步驟總結

1.每行減去一個最小元素；2.每列減去一個最小元素；經此兩步，效率矩陣每行、列都至少有一個“0”。3.每行、列若只有一個“0”元素，打上“（）”，同時劃去與其同列、行的其它零元素，先前已被劃去的零元素不計算在內，如果出現(xiàn)零元素的閉合回路，則任選一個零元素打上“（）”，同時劃掉與其同行和同列的零元素。經過第三步可能出現(xiàn)兩種結果：(1)每行均有打“()”的零元素,此時已得最優(yōu)解;(2)并非每行均有打“()”的零元素，進入第四步。4.給沒有“(0)”的行做標記“”；5.在做“”標記的行上對所有“0”所在的列做標記“”；6.覆蓋掉沒有“”標記行上的所有元素和有“”標記列上的所有元素。經過此步矩陣中的所有“0”均被覆蓋掉了，只留下了部分非零元素。7.每一非零元素減去它們中的最小值，并給同時處在被覆蓋掉行和被覆蓋掉列的元素加上這一最小值。8.重復3~7直至得到最優(yōu)解。2023/10/5例1279798966671712141215146610

2023/10/5例127979896667171214121514661000000

2023/10/5例5(0)20223(0)00(0)10575980(0)40000(0)方案1:甲-B、乙-C、丙-A、丁-D工作E剩余，minz=26

2023/10/5例502(0)22300(0)