第一、二節(jié)提出問題及分枝與定界

1、第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 在許多線性規(guī)劃問題中,要求最優(yōu)解必須取整數(shù). 例如所求的解是機(jī)器的臺(tái)數(shù)、人數(shù)、車輛和船只數(shù)等. 如果所得的解中有分?jǐn)?shù)或小數(shù)則不符合實(shí)際問題的要求. 對(duì)于一個(gè)線性規(guī)劃問題,如果要求全部決策變量都取整數(shù),稱為純(或全)整數(shù)規(guī)劃; 如果僅要求部分決策變量取整數(shù),稱為混合整數(shù)規(guī)劃問題. 有的問題要求決策變量僅取0或l兩個(gè)值,稱為0-1規(guī)劃問題. 第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃5.15.1 整數(shù)規(guī)劃問題的提出5.25.2 分枝定界法5.35.3 割平面法5.45.4 0 0-1 1規(guī)劃及隱枚舉法5.55.5 指派問題* *5.1 5.1 整數(shù)規(guī)劃問題的提出自學(xué)5.25.2

2、 分枝定界法整數(shù)規(guī)劃（A）松弛問題（B）1maxnjjjSc x 1(1,)nijjija xb im 0jx 且為整數(shù)且為整數(shù)1maxnjjjSc x 1(1,)nijjija xb im 0jx 則必有：（A）的可行域 （B）的可行域 （A）的最優(yōu)值 （B）的最優(yōu)值 例如例如 求解整數(shù)規(guī)劃問題12121212max58 65945,0Sxxxxxxxx 且為整數(shù)()A()B12121212max58 65945,0Sxxxxxxxx 的可行域()B1234561234567891x2x12 6xx 12 5945xx (2.25,3.75)()B12121212max58 65945,0S

3、xxxxxxxx 的可行域()A1234561234567891x2x12 6xx 12 5945xx (2.25,3.75)12121212max58 65945,0Sxxxxxxxx 且為整數(shù)()A的可行域()A1234561234567891x2x12 6xx 12 5945xx (6,0)(5,1)(5,0)(4,2)(4,1)(4,0)(3,3)(3,2)(3,1)(3,0)(2,3)(2,2)(2,1)(2,0)(0,5)(0,4)(0,3)(0,2)(0,1)(0,0)(1,4)(1,3)(1,2)(1,1)(1,0)(2.25,3.75)12max58 Sxx 顯然，對(duì)于整數(shù)規(guī)

4、劃問題來說 ，先求其松弛問題的最優(yōu)解是一個(gè)正確的方向 但是，用“舍入取整法”，把松弛問題的最優(yōu)解臨近的整數(shù)解作為原問題的最優(yōu)解是不對(duì)的 分支定界法是解決整數(shù)規(guī)劃比較有效的一個(gè)方法例例1 1 求解整數(shù)規(guī)劃問題12121212max58 65945,0Sxxxxxxxx 且為整數(shù)()A0()B12121212max58 65945,0Sxxxxxxxx 解（1 1）用圖解法或單純形法求解問題 ， 得最優(yōu)解為0()B1202.25,3.75,41.25xxS 下界 上界S S *041.25AS 121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max5

5、8 2059454,0Sxxxxxxxxx 1()B的最優(yōu)解為0()B1202.25,3.75,41.25xxS 將問題 分解為 和 兩個(gè)子問題23.75x 0()B1()B2()B23.753x 選 進(jìn)行分枝，增加約束條件23.7514x 和121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B1213,3,39xxS 1221.8,4,41xxS 041.25SS 取新的下界,新的上界39S 41S 接下來對(duì)問題 進(jìn)行分枝2()B11.81x 增加約束條件11.812x 和將問題 分解為

6、和 兩個(gè)子問題4()B3()B2()B4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 無可行解4()B取新的上界5409S 3941SS 接下來對(duì)問題 進(jìn)行分枝3()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B123451,4,4099xxS 24x 增加約束條件25x 和將問題 分解為 和 兩個(gè)子問題6()B5()B3()B6()B12121221212max58 205945414,0Sxxxxx

7、xxxxxx 5()B12121221212max58 205945415,0Sxxxxxxxxxxx 1251437xxS 1260540 xxS 3941SS 都是整數(shù)解56() ()BB、而 , 故為最優(yōu)值.6SSS 分支定界法的主要內(nèi)容就是分枝和定界而定界是指通過求解松弛問題及其子問題，確定原問題的上下界，并不斷縮小其范圍，最終得到原問題的最優(yōu)值及最優(yōu)解所謂分枝，就是通過不斷增加約束條件，將松弛問題分成若干個(gè)子問題整數(shù)規(guī)劃（A）松弛問題（B）1maxnjjjSc x 1(1,)nijjija xb im 0jx 且為整數(shù)1maxnjjjSc x 1(1,)nijjija xb im 0

8、jx 回到一般問題上： 首先，求解(B)，確定(A)的最優(yōu)值的初始上下界，有三種情況： （1）若(B)無可行解，則(A)也無可行解,停止計(jì)算； （2）若(B)有最優(yōu)解，且為整數(shù)，則(B)的最優(yōu)解也是(A)的最優(yōu)解，停止計(jì)算； （3）若(B)有最優(yōu)解，但不全為整數(shù)，這時(shí)(B)的最優(yōu)解不是(A)的可行解，但是(B)的最優(yōu)值是(A)的最優(yōu)值的上界分枝定界法的主要步驟設(shè)(B)的最優(yōu)值為， (A)的最優(yōu)值為*BS*AS則必有*0ABSS 定初始上界 ，初始下界*=BS S=0S即*ASSS 接下來通過分枝與定界不斷提高下界，降低上界，縮小范圍，最終確定的值*AS設(shè)（B）的最優(yōu)解為：若其中不是整數(shù)，則必有

9、這時(shí)，增加約束條件 *12TnXxxx *kx* 1kkkxxx *kkxx *1kkxx 構(gòu)造（B）的兩個(gè)子問題 和1()B2().B 和子問題的解可能有如下三種情況：1.有整數(shù)最優(yōu)解，但其最優(yōu)值小于原來的下界2.有整數(shù)最優(yōu)解，其最優(yōu)值大于原來的下界3.無整數(shù)最優(yōu)解則將其剪枝剪掉，不再考慮則將其值作為新的下界否則，選取最優(yōu)值較大者作為新的上界，然后重復(fù)上述步驟，繼續(xù)分枝若其最優(yōu)值小于原來的下界，則將其剪掉； 如果某一個(gè)子問題無可行解或者最優(yōu)值小于原來的下界，則稱這個(gè)分支已經(jīng)查清，將該枝剪掉，不再計(jì)算，所謂“剪枝”例例1 1 求解整數(shù)規(guī)劃問題12121212max58 65945,0Sxxxx

10、xxxx 且為整數(shù)()A0()B12121212max58 65945,0Sxxxxxxxx 解（1 1）用圖解法或單純形法求解問題 ， 得最優(yōu)解為0()B1202.25,3.75,41.25xxS 取下界,上界0S 41.25S 121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B的最優(yōu)解為0()B1202.25,3.75,41.25xxS (2) (2) 分枝與定界將問題 分解為 和 兩個(gè)子問題23.75x 0()B1()B2()B23.753x 選 進(jìn)行分枝，增加約束條件23.7514

11、x 和121212212max58 2059453,0Sxxxxxxxxx 2()B121212212max58 2059454,0Sxxxxxxxxx 1()B1213,3,39xxS 1221.8,4,41xxS 041.25SS 取新的下界,新的上界39S 41S 接下來對(duì)問題 進(jìn)行分枝2()B問題 是整數(shù)解,已被查清1()B3941SS 4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 無可行解4()B11.81x 增加約束條件11.8

12、12x 和將問題 分解為 和 兩個(gè)子問題4()B3()B2()B4()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B1212122112max58 20594542,0Sxxxxxxxxxx 123451,4,4099xxS 無可行解4()B 無可行解,該問題已查清4()B3941SS 取新的上界5409S 395409SS 接下來對(duì)問題 進(jìn)行分枝3()B1212122112max58 20594541,0Sxxxxxxxxxx 3()B123451,4,4099xxS 24x 增加約束條件25x 和將問題 分解為 和 兩個(gè)子問題6()B5()B3()B

13、6()B12121221212max58 205945414,0Sxxxxxxxxxxx 5()B12121221212max58 205945415,0Sxxxxxxxxxxx 1251437xxS 1260540 xxS 都是整數(shù)解,均已查清56() ()BB、但,故將該枝剪去.5SS 而 , 故為最優(yōu)值.6SSS 395409SS 6()B5()B4()B3()B2()B1()B0()B041.252.25,3.75S （）1393,3S （）2411.8,4S （）無可行解3540941,49S （）5371,4S （）6400,5S （）()A23x 24x 11x 12x 24x

14、25x 請(qǐng)練習(xí)：請(qǐng)練習(xí)：100頁 習(xí)題三 第3題（用分枝定界法求解）答案：122,14xxZ 注意：1、每一層子問題求解出來以后，都要隨時(shí)修改上下界，不能只分支不定界；2、子問題是在上一層子問題（而不是在原始問題）的基礎(chǔ)上，再增加約束條件；3、如果同一層的兩個(gè)子問題都無整數(shù)最優(yōu)解，則選其目標(biāo)函數(shù)值較大者作為新的上界，下界不變（不能選目標(biāo)函數(shù)值較小者作為新的下界）；4、上面兩個(gè)子問題要分別再分枝求解，不能將目標(biāo)函數(shù)值較小者剪掉；用分枝定界法求解整數(shù)規(guī)劃問題12121212max 9511414123,0Zxxxxxxxx 且為整數(shù) 答案： 或122,4xxZ 123,1,4xxZ 胡運(yùn)權(quán)習(xí)題集

15、5.7(a)解：12121212max 9511414123,0Zxxxxxxxx 且為整數(shù) ()A0()B12121212max 9511414123,0Zxxxxxxxx 分枝定界過程如圖所示6()B5()B4()B3()B1()B0()AB2()B8()B7()B11x 12x 23x 22x 23x 22x 12x 13x 029 63 2,10 3Z （）110 31,7 3Z （）241 92,23 9Z （）561 1433 14,2Z （）742,2Z （）84,1Z （3 3 ）331,2Z （）0,29 6ZZ 0,41 9ZZ 3,61 14ZZ 4AZ 初次分枝選 1x

16、12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 0B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 1()B2()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B2()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B5()B12312347 81x2x121 23xx 12951 1414xx 1 4(3 2,10 3)12 Zxx 3()B7()B8()B4()B3()B1()B0()AB2()B6()B5()B24x 23x 11x 12x 22x 23x 029 63 2,10 3Z （）133 712 7Z （, ,3 3) )441 92,23 9Z （）53,2Z （1 1 ）0,29 6ZZ 0,33 7ZZ 0,41 9ZZ 4AZ 310 31,7 3Z （）8()B7()B22x 23x 761 1433 14,2Z （） 初次分枝選 2x10()B9(