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

1、2024/3/3,1.整數(shù)規(guī)劃的數(shù)學模型2.分枝定界法3.割平面法4.0-1型整數(shù)規(guī)劃5.指派問題,第五章 整數(shù)規(guī)劃,2024/3/3,整數(shù)規(guī)劃的數(shù)學模型,max(min)(c1 x1+ c2 x2 +…+ cn xn )a11 x1+ a12 x2 +…+ a1n xn ? (=,?) b1a21 x1+ a22 x2 +…+ a2n xn ? (=,?) b2……...am1 x1+ am2 x2 +…+ a

2、mn xn ? (=,?) bmx1~n ? 0 且取整數(shù)純整數(shù)規(guī)劃: 所有變量都有取整約束混合整數(shù)規(guī)劃: 只有部分變量有取整約束,,2024/3/3,分枝定界法,1.分枝定界法的基本思路2.第65頁例5-13.練習題,,2024/3/3,分枝定界法的基本思路,?,2024/3/3,,分枝定界法的基本思路,2024/3/3,第65頁例5-1,max z = 40x1 + 90x2 9x1 + 7x2 ?

3、56 7x1 +20x2 ? 70 x1，x2 ? 0且取整?,,2024/3/3,用分枝定界法解例5-1,1.求解相應的線性規(guī)劃L0max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1，x2 ? 0,2024/3/3,用分枝定界法解例5-1,x2 5 9x1+7x2=5

4、6 4 3 2 7x1+20x2=70 1 0 1 2 3 4 5 6 7 8 9 10 x1L0 : x* = (4.81, 1.82), Z* =356?,,,,,,,,,,,,,,,,,,,,,,,

5、,,,,,,,,,,2024/3/3,用分枝定界法解例5-1,2.將L0分解為L1和L2L1 ：max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1 ? 4 x1，x2 ? 0,L2 ：max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2

6、 ? 70 x1 ? 5 x1，x2 ? 0,L1 ：X* = (4, 2.10), Z* = 349 L2 ：X* = (5, 1.57), Z* = 341 ?,,,2024/3/3,用分枝定界法解例5-1,3.分解L1形成L3、L4，其中： L3 = {L1, x2?2} L4 = {L1, x2?3} L3 : X* = (4, 2), Z* =

7、 340 L4 : X* = (1.42, 3), Z* = 327(1)取下界min=340(L3);(2)舍棄L4,2024/3/3,用分枝定界法解例5-1,4.分解L2形成L5、L6，其中： L5 = {L2, x2?1} L6 = {L2, x2?2} L5 : X* = (5.44, 1), Z* = 308 L6 : 無可行解(1)舍棄L5、L6；(2)得最優(yōu)解X* = (

8、4, 2), Z* = 340。?,2024/3/3,例5-1求解過程示意圖,,2024/3/3,練習題,max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 ? 12 x1 + 2x2 ? 15 4x1 + 5x3 ? 26 x1~3 ? 0且取整,,2024/3/3,求解練習題,首先求解線性規(guī)劃L0 :m

9、ax z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x1~6 ? 0,,2024/3/3,求解練習題,?,2024/3/3,求解練習題,?,2024/3/3,求解練習題,?,2024/3/3,求解練習題,?,2024/3

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

11、 = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0且取整?,,2024/3/3,用割平面法解例,1.求解相應的線性規(guī)劃L0max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0?,,2024/3/3,用割平面法解例,非整數(shù)解，為建立割平面，首先考慮非整數(shù)解中余

12、數(shù)最大的基變量，此例中x1、 x2的余數(shù)均為3/4，不妨選取x2 ： x2 +3/4 x3 +1/4 x4 =7/4,2024/3/3,用割平面法解例,x2 +3/4 x3 +1/4 x4 =7/4現(xiàn)將各系數(shù)分成整數(shù)和非負真分數(shù)兩部分，從而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4)將整數(shù)部分的變量移至等式右端有： 3/4 x3 +1/4

13、 x4 =3/4+（1- x2 ）非負整數(shù)解?(1- x2)為整數(shù)，左端非負故有： 3/4 x3 +1/4 x4 =3/4+非負整數(shù)從而： 3/4 x3 +1/4 x4 ?3/4 或 x2 ? 1以x2 ? 1為割平面可使可行域減少一個包括A點在內的三角形。?,2024/3/3,x2 A 1

14、 0 1 x1,用割平面法解例,?,,,,,,,,,2024/3/3,用割平面法解例,,2024/3/3,練習題,max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 ? 12 x1 + 2x2

15、 ? 15 4x1 + 5x3 ? 26 x1~3 ? 0且取整?,,2024/3/3,求解練習題,?,2024/3/3,求解練習題,選取x2： 1/2 x1+x2+1/2 x5 =15/2 1/2 x1+1/2 x5 =1/2 +（7- x2 ） 于是有割平面： 1/2 x1+1/2 x5 ? 1/2或

16、 x2 ? 7,2024/3/3,求解練習題,?,2024/3/3,求解練習題,,2024/3/3,0-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-5,,2024/3/3,第69頁例5-3,某公司擬在東、西

17、、南三個區(qū)建立銷售門市部，擬議中有7個場點A1~7可供選擇。東區(qū)的三個點A1~3 最多選兩個，西區(qū)的兩個點A4~5 最少選一個，南區(qū)的兩個點A6~7 最少選一個。如果建設 Ai 點，需要投資 bi 元，年可獲利 ci 元，公司可籌集到的投資總額為B元，問應如何決策才能使年利潤最大。?,2024/3/3,例5-3,令xi = 0 或 1，其中： xi = 0 表示第I個點未被選取 xi = 1表示

18、第I個點被選取其數(shù)學模型為： x1+ x2 + x3 ? 2 x4+ x5 ? 1 x6+ x7 ? 1,,2024/3/3,引例2,兩種運輸方式的限制條件分別為： 6x1 + 4x2 ? 30 7x1 + 3x2 ? 40互斥的約束統(tǒng)一于一個模型中：

19、 6x1 + 4x2 ? 30 + Mx3 7x1 + 3x2 ? 40 + M(1-x3) 其中x3 為0-1變量。,,2024/3/3,隱枚舉法的基本步驟,1.目標函數(shù)極小化；2.目標函數(shù)系數(shù)非負化，如果xj 的系數(shù)為負數(shù)，可令 xj=1- xj ；3.決策變量按其目標函數(shù)系數(shù)的大小排列；4.令所有變量為“0”，檢查該解的可行性，如果可行此解即為最優(yōu)解，如果不可行進入下一步；5.按變量的順序

20、依次令各變量分別取“0”或“1”，根據(jù)分枝定界的原理進行剪枝，直至結束。,,2024/3/3,第70頁例5-4,Max z= 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 ? 2 x1+ 4x2 + x3 ? 4 x1~3 =0或1第一步：Min w= -3x1 + 2x2 - 5x3 x1 + 2x2 - x3 ? 2 x1+ 4

21、x2 + x3 ? 4 x1~3 =0或1?,2024/3/3,例5-4,第二步：令x1 =1- x1， x3 =1- x3Min w= 3x1 + 2x2 + 5x3 - 8 -x1 + 2x2 + x3 ? 2 -x1 + 4x2 - x3 ? 2 x1~3 =0或1第三步：Min w= 2x2 + 3x1 + 5x3 - 8 2x2 -

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

23、 + x5 ? 4 x1~ 5 = 0或1經(jīng)前三步有：令x1 =1- x1， x2 =1- x2min w= 2x2 + 4x3 + 5x5 + 7x4 + 8x1 - 10 3x2 - x3 - 3x5 - 2x4 + 3x1 ? 2 3x2 +2x3 - x5 + x4 + 5x1 ? 4 x1~ 5 = 0或1?,第71

24、頁例5-5,2024/3/3,?,例5-5,2024/3/3,,,,,,?,例5-5,w=-4 4 (可行解) w=-8 x3=1 x2=1 2

25、w= -10 x3=0 w= -3 1 5 x2=0 w= -6 3,,,,,202

26、4/3/3,例5-5,w= -6 x5=1 8 w= -1 x3=1 6 x5=0w= -6 9 w=1 w=2 3 x3=0 w= -5 x4=1

27、 12 w= -5 x5=1 10 7 x5=0 w= -3 x4=0 w=3 11 13,,

28、2024/3/3,指派問題,1.指派問題的內涵2.指派問題的數(shù)學模型3.指派問題的求解4.指派問題的擴展,,2024/3/3,指派問題的內涵,有m 項工作，恰好有m 個人來完成，一個人只完成一項工作，一項工作只由一個人來完成，由于個人的專長不同，完成任務的效率也就不同，于是產(chǎn)生了應指派哪個人去完成哪項任務，才能使完成m 項任務的總效率最高的問題，此類問題稱為指派問題或分派問題。指派問題同運輸問題一樣，是具有一定模型特征一類問題的總

29、稱，如m 項加工任務如何在m 臺機床上分配；m 條航線如何指定m 艘船去航行等等。指派問題是運輸問題的特例，也是0-1規(guī)劃問題的特例。這一點可由指派問題的數(shù)學模型體現(xiàn)出來。,,2024/3/3,指派問題的數(shù)學模型,,2024/3/3,指派問題的求解－匈牙利法,2.匈牙利法的基本步驟 (1)第73頁例5-6 (2)第74頁例5-7 (3)基本步驟總結,,2024/3/3,指派問題的擴展,1. 人員與工作不匹配：引入假想的工作或人員

30、 由于假想的工作或人員代表的是剩余的工作或人員，所以其對應的效率矩陣元素全都為零。 例2. 目標函數(shù)求極大值：效率矩陣的每一元素乘“-1”，并進一步使其非負化。 第73頁例5-6,,2024/3/3,第73頁例5-6,?,2024/3/3,例5-6,,2024/3/3,第74頁例5-7,?,2024/3/3,例

31、5-7,?,2024/3/3,例5-7,?,2024/3/3,例5-7,?,2024/3/3,例5-7,?,2024/3/3,例5-7,?,2024/3/3,例5-7,?,2024/3/3,例5-7,,2024/3/3,基本步驟總結,1.每行減去一個最小元素；2.每列減去一個最小元素；經(jīng)此兩步，效率矩陣每行、列都至少有一個“0”。3.每行、列若只有一個“0”元素，打上“（）”，同時劃去與其同列、行的其它零元素，先前已被劃去的零元素

32、不計算在內，如果出現(xiàn)零元素的閉合回路，則任選一個零元素打上“（）”，同時劃掉與其同行和同列的零元素。經(jīng)過第三步可能出現(xiàn)兩種結果：(1)每行均有打“( )”的零元素,此時已得最優(yōu)解; (2)并非每行均有打“( )”的零元素，進入第四步。4.給沒有“( 0 )”的行做標記“?”；5.在做 “?”標記的行上對所有“0?”所在的列做標記“?”；6.覆蓋掉沒有“?”標記行上的所有元素和有 “?”標記列上的所有元素。經(jīng)過此步矩陣中的所有“0”

33、均被覆蓋掉了，只留下了部分非零元素。7.每一非零元素減去它們中的最小值，并給同時處在被覆蓋掉行和被覆蓋掉列的元素加上這一最小值。8.重復3~7直至得到最優(yōu)解。,,2024/3/3,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14

34、 6 6 10?,2024/3/3,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 0 0 0 0

35、 0 ?,2024/3/3,例,5 (0) 2 0 2 2 3 (0) 0 0 (0) 10 5 7 5 9 8 0 (0) 4 0 0 0 0 (0) 方案1:甲-B、

36、乙-C、丙-A、丁-D工作E剩余，min z = 26 ?,2024/3/3,例,5 0 2 (0) 2 2 3 0 0 (0) (0) 10 5 7 5 9 8 (0) 0 4 0 (0) 0

37、 0 0 方案2:甲-D、乙-E、丙-A、丁-C工作B剩余，min z = 26 ?,2024/3/3,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10

38、 7 7 6 6 6 方案 :甲-B、乙-C和E、丙-A、丁-D min z = 32,,2024/3/3,第73頁例5-6,10 9 8 7 3 4 5 6 2 1 1 2 4 3 5 6?,202

39、4/3/3,例5-6,-10 -9 -8 -7 -3 -4 -5 -6 -2 -1 -1 -2 -4 -3 -5 -6?,2024/3/3,例5-6,0 1 2 3 3 2 1 0 0

40、 1 1 0 2 3 1 0?,2024/3/3,例5-6,(0) 0 1 3 3 1 (0) 0 0 (0) 0 0 2 2 0 (0)方案之一為：M1-W1、 M2-W3、 M3-W2、 M4-W4 ma