運籌學(xué)第五章整數(shù)規(guī)劃.ppt

第五章 整數(shù)規(guī)劃,5.1 整數(shù)規(guī)劃問題的提出,例5-1 某廠擬用集裝箱托運甲、乙兩種貨物。每箱的體積、重量、可獲利潤以及托運所受限制如下表所示：,問兩種貨物各托運多少箱，可使獲得的利潤最大？,解：,設(shè)x1 , x2 分別為甲、乙兩種貨物的托運箱數(shù)，則模型為：,Max z = 20x1 +10x2,St. 5x1 +4x2 24,2x1 +5 x2 13,x1 ，x2 0,x1 ，x2 整數(shù),暫不考慮整數(shù)約束，求得最優(yōu)解為,x1 = 4.8 ，x2 = 0， Max z = 96,（1）若,x1 = 4.8 ，x2 = 0,x1 = 5 ，x2 = 0,不是可行解；,（2）若,x1 = 4.8 ，x2 = 0,x1 = 4，x2 = 0,是可行解，但不是最優(yōu)解,因為,x1 = 4，x2 = 0時，z = 80,而可行解,x1 = 4，x2 = 1時，z = 90,5.2 整數(shù)規(guī)劃的類型,整數(shù)規(guī)劃按變量取值的不同，可以分為以下幾類：,1. 純整數(shù)規(guī)劃：所有的變量都取整數(shù)值；,2. 混合整數(shù)規(guī)劃：部分變量取整數(shù)值；,3. 01規(guī)劃：所有變量只取0，1兩個值；,4. 01混合規(guī)劃：部分變量只取0，1兩個值。,整數(shù)規(guī)劃（Integer Programming）問題的一般形式,整數(shù)規(guī)劃與其松弛問題,當(dāng)放棄整數(shù)約束時得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問題。,整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立。,5.3.1 混合整數(shù)規(guī)劃的求解-分枝定界方法,分枝：當(dāng) 不符合整數(shù)要求時，構(gòu)造兩個約束條件：,加入松弛問題分別形成兩個子問題（分枝）,定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個界限,5.3 整數(shù)規(guī)劃的解法,分枝定界法基本思想：,首先不考慮變量的整數(shù)約束，求解相應(yīng)的線性規(guī)劃問題：,O,A,C,D,xr,Ir,Ir+1,.,.,.,.,分枝,每一次分枝得到的子問題的最優(yōu)目標(biāo)函數(shù)值都要比上一層問題的最優(yōu)目標(biāo)函數(shù)值小，或者相等。,z0,z11,z12,z21,z22,z23,z24,整數(shù)解,下界,若z21 z11，z22 z11，則無須繼續(xù)分枝,定界,利用定界，可以終止許多不必要的分枝過程。,如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值大于已記錄的下界，則應(yīng)將較大的整數(shù)解的目標(biāo)函數(shù)值代替原來的下界。,當(dāng)所有最低一層子問題出現(xiàn)以下三種情況時，分枝定界法終止：,1. 子問題無可行解；,2. 子問題已獲得整數(shù)解；,3. 子問題的目標(biāo)函數(shù)值未達(dá)到下界。,例,S,解S得：,S2,對S分枝：,構(gòu)造約束：,和,形成分枝問題S1和S2，得解B和C,S1,1,3,2,X,2,5,4,S2,對S1分枝：,構(gòu)造約束：,和,形成分枝問題S11和S12，得解D,S12,S11無可行解,1,3,2,X,2,5,4,S2,對S12分枝：,構(gòu)造約束：,和,形成分枝問題S121和S122，得解E和F,S121,S122,首先求解整數(shù)規(guī)劃（IP）對應(yīng)的松弛問題（LP），如果（LP）的最優(yōu)解不是整數(shù)解，則逐次增加一個新約束（即割平面），它能割去松弛問題可行域中不含整數(shù)解的區(qū)域.逐次切割，直到得到一個整數(shù)最優(yōu)極點（即整數(shù)解）為止。,5.3.2 純整數(shù)規(guī)劃的求解-Gomory割平面方法,基本思想：,（1）首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解；,（2）如果最優(yōu)解是一個非整數(shù)解，則構(gòu)造一個新的約束，對線性規(guī)劃問題的可行域進(jìn)行切割，切除已得到的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求解新的線性規(guī)劃問題；,（3）如果最優(yōu)解仍不是整數(shù)解，再以增加附加約束的方法將其切除，但仍保持最初可行域中所有的整數(shù)解，直至求得一個整數(shù)最優(yōu)解為止。,整數(shù)規(guī)劃的求解-Gomory割平面方法,松弛問題的最優(yōu)解,Gomory定理,在松弛問題的最優(yōu)單純形表中，假如有一常數(shù)項 不是整數(shù)，且對應(yīng)的方程為：,分解 和 成最大整數(shù)與正分?jǐn)?shù)之和：,則,包含了整數(shù)規(guī)劃的所有整數(shù)可行解，但不包括松弛問題的最優(yōu)解。,例題求解,選擇第一個方程：,分解為：,在原松弛問題中加入約束：,即,形成松弛問題2,整數(shù)點,松弛問題2的最優(yōu)解,割平面,選擇第四個方程（具有最大分?jǐn)?shù)部分）：,分解為：,在松弛問題2中加入約束：,即,形成松弛問題3,得到最優(yōu)解,割平面：,如果選擇第二個方程：,分解為：,在松弛問題2中加入約束：,即,形成松弛問題3,沒有找到整數(shù)解，繼續(xù)做下去,5.3.3 整數(shù)規(guī)劃的圖解法,x1,x2,6,4.8,2.6,6.5,*,*,*,*,*,*,*,5.3.4 整數(shù)規(guī)劃的計算機求解,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0,Max 20x1 +10x2 st 5x1 +4x2 24 2x1 +5x2 13 end gin x1 x2 (或gin 2),5.4 整數(shù)規(guī)劃的應(yīng)用,例5-2 投資場所的選擇,某公司擬在城市的東、南、西、北四區(qū)建立門市部，擬議中有10個位置Ai （i = 1,2, , 10）可供選擇，并規(guī)定： 在東區(qū)，由A1 、A2 、A3 三個點中至多選兩個； 在西區(qū)，由A4 、A5 兩個點中至少選一個； 在南區(qū)，由A6 、A7 兩個點中至少選一個； 在北區(qū)，由A8 、A9 、A10 三個點中至少選兩個。 Ai 各點的設(shè)備投資及每年可獲利潤如下表所示：,但投資總額不能超過720萬元。問應(yīng)選擇哪幾個點可使年利潤為最大？,解：,設(shè),(i = 1,2, , 10),Z = 36 x1,+ 40 x2,+ 50 x3,Max,100x1,+ 120x2,+ 150x3,720,x4 + x5 1,x1 + x2 + x3 2,x6 + x7 1,xi = 0或1,+ 22 x4,+ 20 x5,+ 30 x6,+ 25 x7,+ 48 x8,+ 58 x9,+ 61 x10,+ 80x4,+ 70x5,+ 90x6,+ 80x7,+ 140x8,+ 160x9,+ 180x10,x8 + x9 + x10 2,在東區(qū)，由A1 、A2 、A3 三個點中至多選兩個,在西區(qū)，由A4 、A5 兩個點中至少選一個,在南區(qū)，由A6 、A7 兩個點中至少選一個,在北區(qū)，由A8 、A9 、A10 三個點中至少選兩個,例5-3 資金分配問題,某集團(tuán)公司計劃新建五個工廠A1 、A2 、A3 、A4 、A5 ，所需投資分別為100、150、125、200、250萬元?，F(xiàn)僅有資金總額750萬元，又據(jù)估計，工廠建成后每年可獲利潤分別為20、25、20、40、45萬元。試決定應(yīng)建哪些工廠，使投資總額不超過現(xiàn)有資金總額，并使工廠建成后每年獲得的總利潤最大？,解：,對于工廠Ai （i = 1,2, , 5）來說，只有建或不建兩種情況，因此，可設(shè),xi =,1 當(dāng)建工廠Ai 時，（i = 1,2, , 5）,0 相反,則模型為,Max z = 20x1 + 25x2 + 20x3 +40 x4 +45 x5,st. 100x1 + 150x2 + 125x3 +200 x4 +250 x5 750,xi = 0或1 （i = 1,2, , 5）,例5-4 固定成本問題,高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如下表所示：,資源,金屬板（噸）,勞動力（人月）,機器設(shè)備（臺月）,小號容器,中號容器,大號容器,2 4 8,2 3 4,1 2 3,不考慮固定費用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人月，機器有100臺月。此外，不管每種容器制造的數(shù)量是多少，都要支付一筆固定費用：小號是100萬元，中號為150萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。,解：分析問題,設(shè)x1 、x2 、x3 分別為小號容器、中號容器、大號容器的生產(chǎn)數(shù)量；,各種容器的固定費用只有在生產(chǎn)該種容器時才投入，故設(shè)：,yi =,1 當(dāng)生產(chǎn)第 i 種容器，即 xi 0,0 當(dāng)不生產(chǎn)第 i 種容器，即 xi =0,目標(biāo)函數(shù)：為扣除了固定費用后的利潤,約束條件：金屬板、勞動力、機器設(shè)備的限制,為避免出現(xiàn)某種容器不投入固定費用就生產(chǎn)這樣一種不合理情況，必須加上如下約束：,x1 y1 M,x2 y2 M,x3 y3 M,M是充分大的數(shù)，例如，此問題中，M可取200,x1 200y1,x2 200y2,x3 200y3,線性規(guī)劃模型為：,目標(biāo)函數(shù),Max z = 4x1 + 5x2 + 6x3 100y1 150y2 200y3,金屬板限制,2x1 + 4x2 + 8x3 500,勞動力限制,2x1 + 3x2 + 4x3 300,機器設(shè)備限制,x1 + 2x2 + 3x3 100,x1 y1 M,x2 y2 M,x3 y3 M,x1 ，x2 ，x3 0,y1 ，y2 ，y3 為01變量,求解得：,x1 =100，x2 =0，x3 =0,y1 =1，y2 =0，y3 =0,例5-5 分布系統(tǒng)設(shè)計,某企業(yè)在A1 地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為30千箱。為了擴大生產(chǎn)，打算在A2 、 A3 、 A4 、 A5 地中再選擇幾個地方建廠。已知在A2 、 A3 、 A4 、 A5 地建廠的固定成本分別為175、300、375、500千元，各產(chǎn)地的產(chǎn)量及各銷地的銷量及從產(chǎn)地到銷地的單位運價如下表所示。,（1）問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得總固定成本和總運輸費用之和最小；（2）如果由于政策要求必須在A2 、 A3 建一個廠，應(yīng)在哪幾個地方建廠？,解：,設(shè) xij 為從Ai 到Bj 的運輸量；,yi =,1 當(dāng)Ai 廠址被選中；,0 當(dāng)Ai 廠址沒被選中,Min z = 175y2 +300y3 +375y4 + 500y5 + 8x11 + 4x12 + 3x13 + 5x21 + 2x22 + 3x23 + 4x31 + 3x32 + 4x33 + 9x41 + 7x42 + 5x43 + 10x51 + 4x52 + 2x53,A1 廠的產(chǎn)量限制,x11 + x12 + x13 30,對于A2 、 A3 、 A4 、 A5 ，只有廠址被選中，才會有生產(chǎn)量,x21 + x22 + x23 10 y2,x31 + x32 + x33 20 y3,x41 + x42 + x43 30 y4,x51 + x52 + x53 40 y5,各銷地的銷量限制,x11 + x21 + x31 +x41 + x51 = 30,x12 + x22 + x32 +x42 + x52 = 20,x13 + x23 + x33 +x43 + x53 = 20,xij 0，為整數(shù)， yi 為01變量,（1）,求解得：,y5 =1， x52 = 20， x53 = 20， x11 = 30，其余為0，最優(yōu)目標(biāo)函數(shù)值=860,（2）,在上述模型上加上約束條件：,y2 + y3 =1,求解得：,y2 =1， y4 =1， x22 = 10， x41 = 30， x12 = 10， x13 = 20，其余為0，最優(yōu)目標(biāo)函數(shù)值=940,0-1規(guī)劃的求解隱枚舉方法,最優(yōu)解（x1,x2,x3)=(1,0,1); z=8,隱枚舉方法求解過程,n個員工分配做n項工作，已知第i個員工做第j項工作的成本為cij，i=1,n; j=1,n。求最佳分配方案。,4.5 指派問題與匈亞利法,指派問題的數(shù)學(xué)模型,s.t.,指派問題的解應(yīng)對應(yīng)于成本矩陣的不同行與不同列，且總成本最小,對于每個指派問題，需要有效率矩陣（cij ）,（cij ）=,c11 c12 c1n,c21 c22 c2n,cn1 cn2 cnn,引入變量,xij =,1 當(dāng)指派第i 個人完成第j項任務(wù),0 當(dāng)不指派第i 個人完成第j項任務(wù),則每人的效率及目標(biāo)為,c11 x11,+c12 x12,+.,+c1n x1n,c21 x21,+c22 x22,+.,+c2n x2n,.,cn1 xn1,+cn2 xn2,+.,+cnn xnn,.,Z=,Min,n項任務(wù)，恰好有n個人承擔(dān)去完成。由于每人的專長不同，各人完成不同的任務(wù)效率也不同。于是就產(chǎn)生了應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高。,第1項任務(wù)只能由1人完成,x11 + x21 + . xn1 = 1,第2項任務(wù)只能由1人完成,x12 + x22 + . xn2 = 1,.,第j項任務(wù)只能由1人完成,x1j + x2j + . xnj = 1,.,第n項任務(wù)只能由1人完成,x1n + x2n + . xnn = 1,.,.,.,.,(j =1, 2, , n),第1個人只能完成1項任務(wù),x11 + x12 + . x1n = 1,第2個人只能完成1項任務(wù),x21 + x22 + . x2n = 1,.,.,第i個人只能完成1項任務(wù),xi1 + xi2 + . xin = 1,.,.,第n個人只能完成1項任務(wù),xn1 + xn2 + . xnn = 1,.,.,(i =1, 2, , n),故模型為,(j =1, 2, , n),第j項任務(wù)只能由1人完成,(i =1, 2, , n),第i個人只能完成1項任務(wù),xij = 0或1,滿足上述約束條件的可行解xij 可寫成矩陣形式，稱為解矩陣,（xij ）=,0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1,指派問題的求解方法,（1）計算機求解,（2）匈牙利法,（3）隱枚舉法,指派問題的性質(zhì),定理：對于指派問題，成本矩陣的任一行(或列)減去(或加上)一個相同的數(shù)得到的新指派問題與原問題同解。,定理：,系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。,匈牙利法的計算步驟為：,第一步：使系數(shù)矩陣出現(xiàn)0元素。,第二步：進(jìn)行試指派，以尋求最優(yōu)解。,第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最 多的獨立元素數(shù)。,第四步：變換矩陣增加0元素，再返回第二步。,第四步說明：調(diào)整效益矩陣，使之增加一些零元素： (1) 在沒有被直線覆蓋的元素中，找出最小元素； (2) 在沒有被直線覆蓋的元素中，減去最小元素； (3) 在直線交叉處的元素中，加上最小元素； (4) 被一條直線覆蓋的元素不變.,例4-6 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需的時間如下表所示：,問應(yīng)指派何人去完成何工作，使所需總時間最少？,解：用匈牙利法。,第一步：使系數(shù)矩陣出現(xiàn)0元素。,（cij ）=,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,2,4,9,7,0 13 11 2,6 0 10 11,0 5 7 4,0 1 4 2,4,2,0 13 7 0,6 0 6 9,0 5 3 2,0 1 0 0,=（bij ）,第二步：進(jìn)行試指派。,可見，m = n = 4，所以得最優(yōu)解為,（xij ）=,0 0 0 1,0 1 0 0,1 0 0 0,0 0 1 0,即指定甲譯俄文，乙譯日文，丙譯英文，丁譯德文，所需總時間最少。,所需時間為,例4-7 求下表所示效率矩陣的指派問題的最優(yōu)解。,解：第一輪,第一步：使系數(shù)矩陣出現(xiàn)0元素。,12 7 9 7 9,8 9 6 6 6,7 17 12 14 9,15 14 6 6 10,4 10 7 10 9,7,6,7,6,4,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,第二步：進(jìn)行試指派。,由于m = 4，n = 5，解題沒有完成。,第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多的獨立元素（不同行不同列的零元素）數(shù)。,由于 l = 4 n = 5，轉(zhuǎn)第四