《整數(shù)規(guī)劃的數(shù)學(xué)模型分枝定界法割平面法型整數(shù)規(guī)ppt課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《整數(shù)規(guī)劃的數(shù)學(xué)模型分枝定界法割平面法型整數(shù)規(guī)ppt課件.ppt（68頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、2022/8/29,1.整數(shù)規(guī)劃的數(shù)學(xué)模型2.分枝定界法3.割平面法4.0-1型整數(shù)規(guī)劃5.指派問題,第五章 整數(shù)規(guī)劃,2022/8/29,整數(shù)規(guī)劃的數(shù)學(xué)模型,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 + amn xn (=,) bmx1n 0 且取整數(shù)純整數(shù)規(guī)劃: 所有變量都有取整約束混合整數(shù)規(guī)劃: 只有部分變量有取整約束,2022/8/29,分枝定界法,1.分枝定界法的基本思路2.第65頁(yè)例5-13.練習(xí)題,2022

2、/8/29,分枝定界法的基本思路,2022/8/29,分枝定界法的基本思路,2022/8/29,第65頁(yè)例5-1,max z = 40 x1 + 90 x2 9x1 + 7x2 56 7x1 +20 x2 70 x1，x2 0且取整,2022/8/29,用分枝定界法解例5-1,1.求解相應(yīng)的線性規(guī)劃L0max z = 40 x1 + 90 x2 9x1 + 7x2 56 7x1 +20 x2 70 x1，x2 0,2022/8/29,用分枝定界法解例5-1,x2 5 9x1+7x2=56 4 3 2 7x1+20 x2=70 1 0 1 2 3 4 5 6 7 8 9 10 x1L0 : x*

3、 = (4.81, 1.82), Z* =356,2022/8/29,用分枝定界法解例5-1,2.將L0分解為L(zhǎng)1和L2L1 ：max z = 40 x1 + 90 x2 9x1 + 7x2 56 7x1 +20 x2 70 x1 4 x1，x2 0,L2 ：max z = 40 x1 + 90 x2 9x1 + 7x2 56 7x1 +20 x2 70 x1 5 x1，x2 0,L1 ：X* = (4, 2.10), Z* = 349 L2 ：X* = (5, 1.57), Z* = 341 ,2022/8/29,用分枝定界法解例5-1,3.分解L1形成L3、L4，其中： L3 = L1,

4、x22 L4 = L1, x23 L3 : X* = (4, 2), Z* = 340 L4 : X* = (1.42, 3), Z* = 327(1)取下界min=340(L3);(2)舍棄L4,2022/8/29,用分枝定界法解例5-1,4.分解L2形成L5、L6，其中： L5 = L2, x21 L6 = L2, x22 L5 : X* = (5.44, 1), Z* = 308 L6 : 無(wú)可行解(1)舍棄L5、L6；(2)得最優(yōu)解X* = (4, 2), Z* = 340。,2022/8/29,例5-1求解過(guò)程示意圖,2022/8/29,練習(xí)題,max z = 2x1 + 5x2 +

5、 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x13 0且取整,2022/8/29,求解練習(xí)題,首先求解線性規(guī)劃L0 :max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x16 0,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,2022/8/29,割平面法,1.割平面法的基本思路2.例3.練習(xí)題,2022/8/29,

6、割平面法的基本思路,同分枝定界法一樣，割平面法也是一種利用連續(xù)模型求解非連續(xù)問題的常用方法。割平面法的基本思路是：當(dāng)?shù)玫降慕獠粷M足取整約束時(shí)，就設(shè)法在問題上增加一個(gè)約束條件，把包含這個(gè)非整數(shù)解的一部分可行域從原來(lái)的可行域中割除，但不割掉任何一個(gè)整數(shù)可行解。這個(gè)新增加的約束條件就稱為割平面。,2022/8/29,例,max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1，x2 0且取整,2022/8/29,用割平面法解例,1.求解相應(yīng)的線性規(guī)劃L0max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1，x2 0,2022/8/29,用割平面

7、法解例,非整數(shù)解，為建立割平面，首先考慮非整數(shù)解中余數(shù)最大的基變量，此例中x1、 x2的余數(shù)均為3/4，不妨選取x2 ： x2 +3/4 x3 +1/4 x4 =7/4,2022/8/29,用割平面法解例,x2 +3/4 x3 +1/4 x4 =7/4現(xiàn)將各系數(shù)分成整數(shù)和非負(fù)真分?jǐn)?shù)兩部分，從而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4)將整數(shù)部分的變量移至等式右端有： 3/4 x3 +1/4 x4 =3/4+（1- x2 ）非負(fù)整數(shù)解(1- x2)為整數(shù)，左端非負(fù)故有： 3/4 x3 +1/4 x4 =3/4+非負(fù)整數(shù)從而： 3/4 x3 +1/4 x4

8、 3/4 或 x2 1以x2 1為割平面可使可行域減少一個(gè)包括A點(diǎn)在內(nèi)的三角形。,2022/8/29,x2 A 1 0 1 x1,用割平面法解例,2022/8/29,用割平面法解例,2022/8/29,練習(xí)題,max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x13 0且取整,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,選取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或 x2 7

9、,2022/8/29,求解練習(xí)題,2022/8/29,求解練習(xí)題,2022/8/29,0-1型整數(shù)規(guī)劃,1.0-1規(guī)劃： 0-1規(guī)劃是整數(shù)規(guī)劃的特例，是所有決策變量?jī)H取0和1的整數(shù)規(guī)劃問題。2.引例 （1）第69頁(yè)例5-3 （2）引例 23. 0-1規(guī)劃的隱枚舉法 （1）隱枚舉法的基本步驟 （2）第70頁(yè)例5-4 （3）第71頁(yè)例5-5,2022/8/29,第69頁(yè)例5-3,某公司擬在東、西、南三個(gè)區(qū)建立銷售門市部，擬議中有7個(gè)場(chǎng)點(diǎn)A17可供選擇。東區(qū)的三個(gè)點(diǎn)A13 最多選兩個(gè)，西區(qū)的兩個(gè)點(diǎn)A45 最少選一個(gè)，南區(qū)的兩個(gè)點(diǎn)A67 最少選一個(gè)。如果建設(shè) Ai 點(diǎn)，需要投資 bi 元，年可獲利 c

10、i 元，公司可籌集到的投資總額為B元，問應(yīng)如何決策才能使年利潤(rùn)最大。,2022/8/29,例5-3,令xi = 0 或 1，其中： xi = 0 表示第I個(gè)點(diǎn)未被選取 xi = 1表示第I個(gè)點(diǎn)被選取其數(shù)學(xué)模型為： x1+ x2 + x3 2 x4+ x5 1 x6+ x7 1,2022/8/29,引例2,兩種運(yùn)輸方式的限制條件分別為： 6x1 + 4x2 30 7x1 + 3x2 40互斥的約束統(tǒng)一于一個(gè)模型中： 6x1 + 4x2 30 + Mx3 7x1 + 3x2 40 + M(1-x3) 其中x3 為0-1變量。,2022/8/29,隱枚舉法的基本步驟,1.目標(biāo)函數(shù)極小化；2.目標(biāo)函數(shù)

11、系數(shù)非負(fù)化，如果xj 的系數(shù)為負(fù)數(shù)，可令 xj=1- xj ；3.決策變量按其目標(biāo)函數(shù)系數(shù)的大小排列；4.令所有變量為“0”，檢查該解的可行性，如果可行此解即為最優(yōu)解，如果不可行進(jìn)入下一步；5.按變量的順序依次令各變量分別取“0”或“1”，根據(jù)分枝定界的原理進(jìn)行剪枝，直至結(jié)束。,2022/8/29,第70頁(yè)例5-4,Max z= 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1+ 4x2 + x3 4 x13 =0或1第一步：Min w= -3x1 + 2x2 - 5x3 x1 + 2x2 - x3 2 x1+ 4x2 + x3 4 x13 =0或1,2022/8/29,例

12、5-4,第二步：令x1 =1- x1， x3 =1- x3Min w= 3x1 + 2x2 + 5x3 - 8 -x1 + 2x2 + x3 2 -x1 + 4x2 - x3 2 x13 =0或1第三步：Min w= 2x2 + 3x1 + 5x3 - 8 2x2 - x1 + x3 2 4x2 - x1 - x3 2 x13 =0或1第四步： 令所有變量為“0”，得可行解，所以原問題的最優(yōu)解為（1，0，1），最優(yōu)值為8。,2022/8/29,max z= 8x1 + 2x2 - 4x3 - 7x4 - 5x5 3x1 + 3x2 + x3 +2x4 +3x5 4 5x1 + 3x2 - 2x

13、3 - x4 + 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頁(yè)例5-5,2022/8/29,例5-5,2022/8/29,例5-5,w=-4 4 (可行解) w=-8 x3=1 x2=1 2 w= -10 x3=0 w= -3 1 5 x2=0 w= -6 3,2022/8/29,例5-5,w= -6 x5=1 8 w= -1 x3=1

14、 6 x5=0w= -6 9 w=1 w=2 3 x3=0 w= -5 x4=1 12 w= -5 x5=1 10 7 x5=0 w= -3 x4=0 w=3 11 13,2022/8/29,指派問題,1.指派問題的內(nèi)涵2.指派問題的數(shù)學(xué)模型3.指派問題的求解4.指派問題的擴(kuò)展,2022/8/29,指派問題的內(nèi)涵,有m 項(xiàng)工作，恰好有m 個(gè)人來(lái)完成，一個(gè)人只完成一項(xiàng)工作，一項(xiàng)工作只由一個(gè)人來(lái)完成，由于個(gè)人的專長(zhǎng)不同，完成任務(wù)的效率也就不同，于是產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使完成m 項(xiàng)任務(wù)的總效率最高的問題，此類問題稱為指派問題或分派問題。指派問題同運(yùn)輸問題一樣，是具有一定模型特征一類

15、問題的總稱，如m 項(xiàng)加工任務(wù)如何在m 臺(tái)機(jī)床上分配；m 條航線如何指定m 艘船去航行等等。指派問題是運(yùn)輸問題的特例，也是0-1規(guī)劃問題的特例。這一點(diǎn)可由指派問題的數(shù)學(xué)模型體現(xiàn)出來(lái)。,2022/8/29,指派問題的數(shù)學(xué)模型,2022/8/29,指派問題的求解匈牙利法,2.匈牙利法的基本步驟 (1)第73頁(yè)例5-6 (2)第74頁(yè)例5-7 (3)基本步驟總結(jié),2022/8/29,指派問題的擴(kuò)展,1. 人員與工作不匹配：引入假想的工作或人員 由于假想的工作或人員代表的是剩余的工作或人員，所以其對(duì)應(yīng)的效率矩陣元素全都為零。 例2. 目標(biāo)函數(shù)求極大值：效率矩陣的每一元素乘“-1”，并進(jìn)一步使其非負(fù)化。

16、第73頁(yè)例5-6,2022/8/29,第73頁(yè)例5-6,2022/8/29,例5-6,2022/8/29,第74頁(yè)例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,例5-7,2022/8/29,基本步驟總結(jié),1.每行減去一個(gè)最小元素；2.每列減去一個(gè)最小元素；經(jīng)此兩步，效率矩陣每行、列都至少有一個(gè)“0”。3.每行、列若只有一個(gè)“0”元素，打上“（）”，同時(shí)劃去與其同列、行的其它零元素，先前已被劃去的零元素不計(jì)算在內(nèi)，如果出現(xiàn)零元素的閉合回路，則任選一個(gè)零元素打上“（）”，同時(shí)劃掉與其同行和同列的零元素。經(jīng)過(guò)第三步可能出現(xiàn)兩種結(jié)果：(1)每行均有打“( )”的零元素,此時(shí)已得最優(yōu)解; (2)并非每行均有打“( )”的零元素，進(jìn)入第四步。4.給沒有“( 0 )”的行做標(biāo)記“”；5.在做 “”標(biāo)記的行上對(duì)所有“0”所在的列做標(biāo)記“”；6.覆蓋掉沒有“”標(biāo)記行上的所有元素和有 “”標(biāo)記列上的所有元素。經(jīng)過(guò)此步矩陣中的所有“0”均被覆蓋掉