運(yùn)籌學(xué)課件 第四章整數(shù)規(guī)劃

第四章整數(shù)規(guī)劃4.1整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1.1問題的提出例1、某廠生產(chǎn)A1和A2兩種產(chǎn)品，需要經(jīng)過B1,B2,B3三道工序加工。單件工時(shí)和利潤(rùn)以及各工序每周工時(shí)限額見下表。問工廠應(yīng)如何安排生產(chǎn)，才能使總利潤(rùn)最大？2/7/202312/7/20232解：設(shè)工廠每周生產(chǎn)A1產(chǎn)品x1件,A2產(chǎn)品x2件,則該問題的數(shù)學(xué)模型為這是一個(gè)純整數(shù)規(guī)劃問題。2/7/20233例2、某服務(wù)部門各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)見下表；按規(guī)定，服務(wù)員連續(xù)工作8小時(shí)（即四個(gè)時(shí)段）為一班。現(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門服務(wù)員總數(shù)最少。2/7/20234

解：設(shè)在第j時(shí)段開始時(shí)上班的服務(wù)員人數(shù)為xj(由于第j時(shí)段開始時(shí)上班的服務(wù)員將在第j+3時(shí)段結(jié)束時(shí)下班,故決策變量只需要考慮x1,x2,x3,x4,x5

問題的數(shù)學(xué)模型為2/7/20235這也是一個(gè)純整數(shù)規(guī)劃問題。2/7/202364、1、2整數(shù)規(guī)劃的數(shù)學(xué)模型

2/7/20237整數(shù)規(guī)劃（IntegerProgramming）問題的一般形式2/7/20238整數(shù)規(guī)劃與其松弛問題當(dāng)放棄整數(shù)約束時(shí)得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問題。整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立。2/7/202394、2整數(shù)規(guī)劃問題的解法4、2、1圖解法例、考慮下面的整數(shù)規(guī)劃問題2/7/202310例.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。貨物每件體積（立方英尺）每件重量（百千克）每件利潤(rùn)（百元）甲乙19527344023托運(yùn)限制1365140

2/7/202311解：設(shè)x1、

x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問題。利用圖解法2/7/202312得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標(biāo)函數(shù)值為14。性質(zhì)：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=62/7/2023134、2、1

---分枝定界方法分枝：當(dāng)不符合整數(shù)要求時(shí)，構(gòu)造兩個(gè)約束條件：加入松弛問題分別形成兩個(gè)子問題（分枝）定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個(gè)可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個(gè)界限2/7/202314分枝定界法基本思想：首先不考慮變量的整數(shù)約束，求解相應(yīng)的線性規(guī)劃問題：Maxz=CXAX=bX0OACDxr

IrIr+1Maxz=CXAX=bxr

Ir

X0Maxz=CXAX=bxr

Ir+1

X0…...…...…...…...分枝每一次分枝得到的子問題的最優(yōu)目標(biāo)函數(shù)值都要比上一層問題的最優(yōu)目標(biāo)函數(shù)值小，或者相等。z0z11z12z21z22z23z24整數(shù)解下界定界利用定界，可以終止許多不必要的分枝過程。如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值大于已記錄的下界，則應(yīng)將較大的整數(shù)解的目標(biāo)函數(shù)值代替原來的下界。2/7/202315當(dāng)所有最低一層子問題出現(xiàn)以下三種情況時(shí)，分枝定界法終止：1.子問題無(wú)可行解；2.子問題已獲得整數(shù)解；3.子問題的目標(biāo)函數(shù)值未達(dá)到下界。2/7/202316例132X254X1231S解S得：2/7/202317132X254X1231S2對(duì)S分枝：構(gòu)造約束：和形成分枝問題S1和S2，得解B和CS12/7/202318SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/92/7/202319132X254X1231S2對(duì)S1分枝：構(gòu)造約束：和形成分枝問題S11和S12，得解DS12S11無(wú)可行解2/7/202320SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/142/7/202321132X254X1231S2對(duì)S12分枝：構(gòu)造約束：和形成分枝問題S121和S122，得解E和FS121S1222/7/202322SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=42/7/202323例用分枝定界法求解整數(shù)規(guī)劃Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0且x1,x2為整數(shù)解:(一)先求出以下線性規(guī)劃的解：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0得z1=14.66,x1=2.44,x2=3.26(二)確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*初始上界和下界z。分析后，知道=14.66，由觀察法得下界z=13（當(dāng)x1=2,x2=3時(shí)）。2/7/202324(三)將一個(gè)線性規(guī)劃問題分為兩枝，并求解。可由x1≤2或x1≥3中取值。將線性規(guī)劃1分解為兩支，如下：線性規(guī)劃2：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1≤2x1,x2≥0解得z2=13.90,x1=2,x2=3.30線性規(guī)劃3：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1≥3x1,x2≥0解得z3=14.58,x1=3,x2=2.862/7/202325(四)修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。經(jīng)分析，將上界

=14.66修改為

=14.58，z=13。(五)在線性規(guī)劃2和線性規(guī)劃3中選擇一個(gè)上界最大的線性規(guī)劃，即線性規(guī)劃3，進(jìn)行分枝。線性規(guī)劃3分解為線性規(guī)劃4和線性規(guī)劃5，如下：線性規(guī)劃4：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1≥3x2≤2x1,x2≥0解得z4=14,x1=4,x2=2

線性規(guī)劃5：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≥3x2≥3x1,x2≥0無(wú)可行解2/7/202326(六)進(jìn)一步修改整數(shù)規(guī)劃最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界。從線性規(guī)劃2，4，5中修改上下界。分析后，可得

=14，z=14。都取線性規(guī)劃2，4，5中的整數(shù)可行解的目標(biāo)函數(shù)值的最大值。性質(zhì)：當(dāng)整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界等于其下界z時(shí)，該整數(shù)規(guī)劃的最優(yōu)解已經(jīng)被求出。這個(gè)整數(shù)的最優(yōu)解即為其目標(biāo)函數(shù)值取此下界的對(duì)應(yīng)線性規(guī)劃的整數(shù)可行解。2/7/202327用圖表示求解過程與求解結(jié)果線性規(guī)劃1Z1=14.66X1=2.44X2=3.26z=13,

=14.66線性規(guī)劃2Z2=13.90X1=2X2=3.30線性規(guī)劃3Z3=14.58X1=3X2=2.86線性規(guī)劃4Z4=14.00X1=4X2=2線性規(guī)劃5無(wú)可行解X1≤2X1≥3X2≤2X2≥3z=13,

=14.58z=14,

=142/7/202328

從以上解題過程可得用分枝定界法求解目標(biāo)函數(shù)值最大的整數(shù)規(guī)劃的步驟，我們將求解的整數(shù)規(guī)劃問題稱為A，將與其相對(duì)應(yīng)的線性規(guī)劃問題稱為B：第一步：求解問題B，可得以下情況之一：1.B沒有可行解，則A也沒有可行解，求解過程停止。2.B有最優(yōu)解，且符合問題A的整數(shù)條件，則B的最優(yōu)解即為A的最優(yōu)解，求解過程停止。3.B有最優(yōu)解，但不符合A的整數(shù)條件，記其目標(biāo)函數(shù)值為z1。第二步：確定A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，其上界即為z1,=z1,再用觀察法找到A的一個(gè)整數(shù)可行解，求其目標(biāo)函數(shù)值作為z*的下界，記為z。第三步：判斷

是否等于z

。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標(biāo)函數(shù)值等于z的A的那個(gè)整數(shù)可行解；否則進(jìn)行第四步。2/7/202329

第四步：在B的最優(yōu)解中選一個(gè)最遠(yuǎn)離整數(shù)要求的變量，不妨設(shè)此變量為xj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造以下兩個(gè)約束條件，并加入問題B，得到B的兩個(gè)分枝B1和B2。xj

≤[bj]和xj

≥[bj]+1第五步：求解B1和B2。修改A問題的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，

和z。第六步：比較和剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中若有小于z者，則剪掉這枝（用打Х表示），即以后不再考慮了。若大于

，則不符合整數(shù)條件，則重復(fù)第三步至第六步，直至

=z，求出最優(yōu)解為止。對(duì)于求目標(biāo)函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。2/7/202330例、用分枝定界法求解下列整數(shù)規(guī)劃問題maxf(x)=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0且為整數(shù)2/7/202331解：先不考慮整數(shù)條件，即解相應(yīng)線性規(guī)劃的松弛問題，得最優(yōu)解為：x1=4.81x2=1.82f(x)0=356可見它不符合整數(shù)條件，這時(shí)f(x)0=356是原問題的最優(yōu)目標(biāo)函數(shù)值的上界。分枝定界法的解法，首先注意其中一個(gè)非整數(shù)變量的解，如x1=4.81，于是對(duì)原問題增加兩個(gè)約束條件2/7/202332x1≤4，x1≥5可將原向題分解為兩個(gè)子問題B1和B2（即兩枝），給每枝增加一個(gè)約束條件。這并不影響原問題的可行域，不考慮整數(shù)條件解問題B1和B2。得到最優(yōu)解為：?jiǎn)栴}B1：x1=4.00x2=2.10f(x)1=349問題B2：x1=5.00x2=1.57f(x)2=341顯然沒有得到全部變量是整數(shù)的解。2/7/202333繼續(xù)對(duì)問題B1和問題B2進(jìn)行分解，因f(x)1＞f(x)2，故先分解B1為兩枝。增加條件x2≤2，稱為問題B3；增加條件x2≥3者稱為問題B4。解問題B3得到最優(yōu)解為：x1=4.00x2=2.00f(x)3=340解問題B4得到最優(yōu)解為：x1=1.42x2=3.00f(x)4=327可見問題B3的解已都是整數(shù)，它的目標(biāo)函數(shù)值f(x)3=340，而它大于f(x)4=327，所以再分解問題B4已無(wú)必要。2/7/202334而問題問題B2的f(x)2＝341，所以問題B2可能在[340，341]之間有整數(shù)解。于是對(duì)問題B2進(jìn)行分解，得問題B5、B6。解問題B5、B6。而問題B5為非整數(shù)解，且f(x)5＝308，而問題B6無(wú)可行解．于是可以斷定問題B3的解為最優(yōu)整數(shù)解：x1=4.00x2=2.00f(x)=3402/7/2023352/7/202336例maxZ=5x1+8x2x1+x2≤65x1+9x2≤45x1,x2≥0x1,x2取整數(shù)2/7/202337第一步,不考慮變量的整數(shù)約束,求相應(yīng)LP(問題1)的最優(yōu)解：

x1=2+/4，x2=3+3/4，Z1=41+1/4第二步,定界過程上界41+1/4；下界為0。第三步，分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x1≤2，x1≥32/7/202338問題2：maxZ=

5x1+8x2問題3：maxZ=

5x1+8x2x1+x2≤6x1+x2≤65x1+9x2≤455x1+9x2≤45x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)

求解問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=2，x2=3+8/9，Z2=41+1/9求解問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2=3，Z3=39第四步，定界過程下界39；上界41+1/9。第五步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：x2≤3，x2≥4

2/7/202339問題4：maxZ=

5x1+8x2問題5：maxZ=

5x1+8x2x1+x2≤9x1+x2≤95x1+9x2≤455x1+9x2≤45x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)

求解問題4相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=2，x2=3，Z4=34求解問題5相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=1+4/5，x2=4，Z5=41

第六步，定界過程下界39；上界41。第七步，分枝過程

將不滿足整數(shù)約束的變量x1進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x1≤1，x1≥2

2/7/202340問題6：maxZ=

5x1+8x2問題7：maxZ=

5x1+8x2x1+x2≤6x1+x2≤65x1+9x2≤455x1+9x2≤45x1≤2x1≤2x2≥4x2≥4x1≤1x1≥2x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)

求解問題6相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=1，x2=4+4/9，Z6=40+5/9求解問題7相應(yīng)的線性規(guī)劃的最優(yōu)解：無(wú)可行解第八步，定界過程LP7的無(wú)最優(yōu)解，不必再分枝，下界39；上界為40+5/9。第九步，分枝過程

將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x2≤4，x2≥5

2/7/202341問題8：maxZ=

5x1+8x2問題9：maxZ=

5x1+8x2x1+x2≤6x1+x2≤65x1+9x2≤455x1+9x2≤45x1≤2x1≤2x2≥4x2≥4x1≤1x1≤1x2≤4x2≥5x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)

求解問題8相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=1，x2=4，Z8=37求解問題9相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=0，x2=5，Z9=40

第十步，定界過程下界為40；上界為40。上界=下界，得整數(shù)規(guī)劃問題的最優(yōu)解：x1=0，x2=5，Z=402/7/202342分枝定界過程x1≤2x1≥3x2≤3x2≥4x1≤1x1≥2x2≤4x2≥52/7/202343x2≤3x2≥4x1≤1x1≥2x2≤4x2≥52/7/202344練習(xí)用分枝定界法求解下列整數(shù)規(guī)劃問題1、maxf(x)=x1+x2s.t.2x1+5x2≤16

6x1+5x2≤30x1,x2≥0且為整數(shù)2/7/2023452、maxf(x)=3x1+2x2s.t.2x1+3x2≤14x1+0.5x2≤4.5x1,x2≥0且為整數(shù)2/7/2023461、（4，1）（5，0）（3，2）2、（4，1）2/7/2023474、2、2

---Gomory割平面方法

割平面法是通過生成一系列的平面割掉非整數(shù)部分來得到最優(yōu)整數(shù)解的方法。目前，割平面法有分?jǐn)?shù)割平面法，原始割平面法，對(duì)偶整數(shù)割平面法，混合割平面法等。我們介紹Gomory割平面法（純整數(shù)規(guī)劃割平面法）2/7/202348例：求解整數(shù)規(guī)劃2/7/202349132X2X122.5154整數(shù)點(diǎn)松弛問題最優(yōu)解2/7/202350松弛問題的最優(yōu)解2/7/202351Gomory割平面法求解思路在松弛問題的最優(yōu)單純形表中，假如有一常數(shù)項(xiàng)不是整數(shù)，且對(duì)應(yīng)的方程為：分解和成最大整數(shù)與正分?jǐn)?shù)之和：2/7/202352則包含了整數(shù)規(guī)劃的所有整數(shù)可行解，但不包括松弛問題的最優(yōu)解2/7/202353例題求解選擇第一個(gè)方程：分解為：2/7/202354在原松弛問題中加入約束：即形成松弛問題22/7/2023552/7/202356132X2X122.5154整數(shù)點(diǎn)松弛問題2的最優(yōu)解割平面2/7/202357選擇第四個(gè)方程（具有最大分?jǐn)?shù)部分）：分解為：2/7/202358在松弛問題2中加入約束：即形成松弛問題32/7/202359得到最優(yōu)解2/7/202360割平面：132X2X122.5154松弛問題3的最優(yōu)解松弛問題2的最優(yōu)解2/7/202361如果選擇第二個(gè)方程：分解為：2/7/202362在松弛問題2中加入約束：即形成松弛問題32/7/202363沒有找到整數(shù)解，繼續(xù)做下去2/7/202364例

求下列問題：MaxZ=2x1+3x2s.t.2x1+4x225x1

82x210x1,x20,且取整數(shù)值2/7/202365化成標(biāo)準(zhǔn)問題MaxZ=2x1+3x2s.t.2x1+4x2+x3=25x1+x4=82x2+x5=10xj0,且取整數(shù)值2/7/202366松馳問題(P)MaxZ=2x1+3x2s.t.2x1+4x2+x3=25x1+x4=82x2+x5=10xj02/7/202367最終單純形表:最優(yōu)解（8,9/4,0,0,11/2）Z=91/42/7/202368松馳問題(P)用單純形法求解得到最優(yōu)解：B（8，9/4）Z=91/4但不是原問題（IP）的解。2/7/202369X2相應(yīng)的方程：x2+(1/4)x3–(1/2)x4=9/42/7/202370

x2+(1/4)x3–(1/2)x4=9/4把所有系數(shù)分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和。x2+(1/4)x3–

x4+(1/2)x4=2+1/4x2–

x4–

2=(1/4)-(1/4)x3-(1/2)x4令(1/4)-(1/4)x3-(1/2)x40（*）加松馳變量：(1/4)-(1/4)x3-(1/2)x4+x6=02/7/202371

(1/4)-(1/4)x3-(1/2)x4+x6=0(1/4)x3-(1/2)x4+x6=-(1/4)插入原最終表中，繼續(xù)計(jì)算。2/7/202372

原始不可行，對(duì)偶可行，用對(duì)偶單純形法計(jì)算2/7/202373

2/7/202374

第四行乘上（-2）2/7/202375

第一、二行減去第四行，第三行加上第四行的1/2倍2/7/202376

最優(yōu)解（15/2，5/2，0，1/2，5）Z=45/22/7/202377

進(jìn)行第二次切割：2/7/202378

進(jìn)行第二次切割：X1-(1/2)x3+2x6=15/22/7/202379

X1-(1/2)x3+2x6=15/2X1-x3+(1/2)x3+2x6-7=(1/2)X1-x3+2x6-7=(1/2)-(1/2)x3令(1/2)-(1/2)x30（**）-(1/2)x3-(1/2)加松馳變量：-(1/2)x3+x7=-(1/2)插入上表中，繼續(xù)計(jì)算。2/7/202380

2/7/202381

2/7/202382

得到最優(yōu)解（8,2,1,0,6,)Z=222/7/202383例求下列問題：MaxZ=x1+x2s.t.-x1+x213x1+x24x1,x20,且取整數(shù)值2/7/202384標(biāo)準(zhǔn)問題：MaxZ=x1+x2s.t.-x1+x2+x3=13x1+x2+x4=4x1,x2,x3,x40,取整數(shù)值2/7/202385

初始單純形表2/7/202386

最終單純形表，最優(yōu)解（3/4，7/4）Z=5/22/7/202387

X1-(1/4)x3+(1/4)x4=3/4X2+(3/4)x3+(1/4)x4=7/42/7/202388

X1-x3=3/4-(3/4)x3-(1/4)x4X2-1

=3/4-(3/4)x3-(1/4)x4令3/4-(3/4)x3-(1/4)x40

-3x3-x4-3-3x3-x4+x5=-3得到第一個(gè)切割方程，插入原最優(yōu)表，繼續(xù)計(jì)算。2/7/202389

原始不可行，對(duì)偶可行，用對(duì)偶單純形法計(jì)算2/7/202390

2/7/202391

第三行乘（-1/3）2/7/202392

第一行加第三行乘（1/4）2/7/202393

第二行加第三行乘（-3/4）2/7/202394

得到最優(yōu)解(1,1,1)Z=22/7/2023954.30—1型整數(shù)規(guī)劃Binaryintegerprogramming2/7/2023961.0—1型整數(shù)規(guī)劃概述

在整數(shù)規(guī)劃模型中，若每一變量只取0或1，即為0-1型整數(shù)規(guī)劃。0-1規(guī)劃模型因其特殊性，又不同于整數(shù)規(guī)劃的解法。若含有n個(gè)變量，則可以產(chǎn)生2n個(gè)可能的變量組合。當(dāng)n較大時(shí)，采用完全枚舉法解題幾乎是不可能的。已有的求解0--1型整數(shù)規(guī)劃的方法一般都屬于隱枚舉法。2/7/2023972.求解0—1型整數(shù)規(guī)劃的方法---隱枚舉法

設(shè)計(jì)一些方法，只檢查變量取值組合的一部分，就能求得問題的最優(yōu)解，這樣的方法稱為隱枚舉法。在2n個(gè)可能的變量組合中，往往只有一部分是可行解。只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其它約束條件是否可行。對(duì)于可行解，其目標(biāo)函數(shù)值也有優(yōu)劣之分。若已發(fā)現(xiàn)一個(gè)可行解，則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個(gè)過濾條件，對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性。在以后的求解過程中，每當(dāng)發(fā)現(xiàn)比原來更好的可行解，則以此替換原來的過濾條件。2/7/202398例1：求解0—1整數(shù)規(guī)劃2/7/202399最優(yōu)解（x1,x2,x3)=(1,0,1);z=8隱枚舉方法求解過程2/7/2023100在解決0-1規(guī)劃問題時(shí)，為了進(jìn)一步減少運(yùn)算量，常按目標(biāo)函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以使最優(yōu)解有可能較早出現(xiàn)。對(duì)于最大化問題，可按目標(biāo)函數(shù)中各變量系數(shù)由小到大的順序排列；對(duì)于最小化問題，可按目標(biāo)函數(shù)中各變量系數(shù)由大到小的順序排列。2/7/2023101比較例1：價(jià)值系數(shù)按遞增排列。以上方法可減少計(jì)算量。2/7/2023102討論：如何運(yùn)用求解整數(shù)規(guī)劃問題的常用方法——分枝定界法求解0-1型整數(shù)規(guī)劃問題？2/7/2023103思考題：2/7/2023104例1投資場(chǎng)所的選擇某單位有5個(gè)擬選擇的投資項(xiàng)目，其所需投資額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系，A、C、E之間必須選擇一項(xiàng)且僅需選擇一項(xiàng)；B和D之間需選擇也僅需選擇一項(xiàng)；又由于C和D兩項(xiàng)目密切相關(guān)，C的實(shí)施必須以D的實(shí)施為前提條件，該單位共籌集資金15萬(wàn)元，問應(yīng)該選擇哪些項(xiàng)目投資，使期望收益最大？3.0—1型整數(shù)規(guī)劃的應(yīng)用及計(jì)算機(jī)求解項(xiàng)目所需投資額（萬(wàn)元）期望收益（萬(wàn)元）A610B48C27D46E592/7/2023105解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng)：x1+x3+x5=1項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件：x3

x4項(xiàng)目B、D之間必須且只需選擇一項(xiàng)：x2+x4=1歸納起來，其數(shù)學(xué)模型為：2/7/2023106求解得：x1=1，x2=1，x3=0，x4=0，x5=0，最優(yōu)目標(biāo)函數(shù)值maxz=18。即應(yīng)該選擇A、B項(xiàng)目投資，可使期望收益最大，最大期望收益為18。2/7/2023107例2分布系統(tǒng)設(shè)計(jì)某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱。為了擴(kuò)大生產(chǎn)，打算在A2、A3、A4、A5地中再選擇幾個(gè)地方建廠。已知在A2、A3、A4、A5地建廠的固定成本分別為175、300、375、500千元，各產(chǎn)地的生產(chǎn)能力及各銷地的銷量及從產(chǎn)地到銷地的單位運(yùn)價(jià)如下表所示。銷地單位運(yùn)價(jià)產(chǎn)地B1B2B3

產(chǎn)能（千箱）A184330A252310A343420A497530A5104240銷量（千箱）302020（1）問應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得總固定成本和總運(yùn)輸費(fèi)用之和最??；（2）如果由于政策要求必須在A2、A3建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠？2/7/2023108解：設(shè)xij為從Ai

到Bj的運(yùn)輸量；yi=1當(dāng)Ai

廠址被選中；0當(dāng)Ai

廠址沒被選中Minz=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對(duì)于A2、A3、A4、A5，只有廠址被選中，才會(huì)有生產(chǎn)量x21+x22+x23

10y2

x31+x32+x33

20y3

x41+x42+x43

30y4

x51+x52+x53

40y5

各銷地的銷量限制x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=20x13+x23+x33+x43+x53=20xij

0，為整數(shù)，yi

為0—1變量（1）2/7/2023109求解得：y5

=1，x11=30，x52=20，x53=20，其余為0，最優(yōu)目標(biāo)函數(shù)值=860。（2）在上述模型上加上約束條件：y2

+y3

=1求解得：y2

=1，y4

=1，x12=10，x13=20，x22=10，x41=30，其余為0，最優(yōu)目標(biāo)函數(shù)值=940。2/7/2023110例3固定費(fèi)用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用、售價(jià)、資源單件耗量及組成三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表。要求制定一個(gè)生產(chǎn)計(jì)劃，使總收益最大。

產(chǎn)品單件耗量資源123資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)810122/7/2023111解：總收益等于銷售收入減去生產(chǎn)上述產(chǎn)品的固定費(fèi)用和可變費(fèi)用之和。建模碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應(yīng)的固定費(fèi)用是否發(fā)生。下面借助0-1變量解決這個(gè)困難。設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1,2,3,再設(shè)2/7/2023112則問題的整數(shù)規(guī)劃模型為：M為很大的正數(shù)2/7/2023113求解得：x1=100，x2=0，x3=0，y1=1，y2=0，y3=0最優(yōu)目標(biāo)函數(shù)值maxz=300。2/7/2023114思考題0-1規(guī)劃的應(yīng)用-項(xiàng)目投資預(yù)算某企業(yè)有四個(gè)可選項(xiàng)目分別為工廠擴(kuò)建、銷售網(wǎng)點(diǎn)擴(kuò)建、新生產(chǎn)流水線、新產(chǎn)品研究，其估計(jì)現(xiàn)值、資金需求及可用資金如下表所示，請(qǐng)?jiān)O(shè)計(jì)最優(yōu)決策方案。2/7/2023115模型變量假設(shè):模型:2/7/20231164.4指派問題AssignmentProblems

2/7/2023117設(shè)有n個(gè)工作，要由n個(gè)人來承擔(dān)，每個(gè)工作只能由一個(gè)人承擔(dān)，且每個(gè)人只能承擔(dān)一個(gè)工作。cij表示第i個(gè)人做第j件事的費(fèi)用,求總費(fèi)用最低的指派方案。費(fèi)用12…j…n12…i…n指派問題模型：i=1,2,…,nj=1,2,…,n第i個(gè)人做第j人件事Z表示總費(fèi)用i=1,2,…,n;j=1,2,…,n第i個(gè)人不做第j人件事1、指派問題的數(shù)學(xué)模型2/7/2023118i=1,2,…,nj=1,2,…,n當(dāng)n=4時(shí)，有16變量，8個(gè)約束方程2/7/2023119例：現(xiàn)有4份工作，4個(gè)人應(yīng)聘，由于各人技術(shù)專長(zhǎng)不同，他們承擔(dān)各項(xiàng)工作所需費(fèi)用如下表所示，且規(guī)定每人只能做一項(xiàng)工作，每一項(xiàng)工作只能由一人承擔(dān)，試求使總費(fèi)用最小的分派方案。工作人費(fèi)用123412343545676889810101091110第i人做第j件事Z表示總費(fèi)用i=1,2,3,4;j=1,2,3,4第i人不做第j件事1202/7/20231202、費(fèi)用矩陣設(shè)有n個(gè)工作，要由n個(gè)人來承擔(dān)，每個(gè)工作只能由一個(gè)人承擔(dān)，且每個(gè)人只能承擔(dān)一個(gè)工作。cij表示第i個(gè)人做第j件事的費(fèi)用,求總費(fèi)用最低的指派方案。費(fèi)用12…j…n12…i…ncij表示第i個(gè)人做第j件事的費(fèi)用費(fèi)用矩陣2/7/2023121例：現(xiàn)有4份工作，4個(gè)人應(yīng)聘，由于個(gè)人的技術(shù)專長(zhǎng)不同，他們承擔(dān)各項(xiàng)工作所需費(fèi)用如下表所示，且規(guī)定每人只能做一項(xiàng)工作，每一項(xiàng)工作只能由一個(gè)人承擔(dān)，試求使總費(fèi)用最小的分派方案。工作人收費(fèi)用1234123435456768898101010911費(fèi)用矩陣2/7/2023122定理：在費(fèi)用矩陣C=（cij）的任一行（列）中減去一個(gè)常數(shù)或加上一個(gè)常數(shù)不改變本問題的最優(yōu)解。n個(gè)人n個(gè)工作的指派問題1-b3、匈牙利法n個(gè)人n個(gè)工作的指派問題22/7/2023123i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n-b2/7/20231242/7/2023125-bi=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n2/7/2023126指派問題的最優(yōu)解：若C中有n個(gè)位于不同行不同列的零元素，則令這些零元素對(duì)應(yīng)的變量取1，其余變量取零，即得指派問題的最優(yōu)解i=1,2,3,4j=1,2,3,4可行解最優(yōu)解2/7/2023127匈牙利法的基本思路對(duì)費(fèi)用矩陣C的行和列減去某個(gè)常數(shù)，將C化成有n個(gè)位于不同行不同列的零元素，令這些零元素對(duì)應(yīng)的變量取1，其余變量取零，即得指派問題的最優(yōu)解。2/7/2023128例：有一份說明書要分別譯成英、日、德、俄四種文字，現(xiàn)交給甲、乙、丙、丁四個(gè)人去完成，每人完成一種。由于個(gè)人的專長(zhǎng)不同，翻譯成不同文字所需的時(shí)間（小時(shí)數(shù)）如右表，問應(yīng)派哪個(gè)人去完成哪個(gè)任務(wù)，可使總花費(fèi)時(shí)間最少？工作人時(shí)間英日德俄甲乙丙丁2151341041415914161378119-2-4-9-7-4-22/7/2023129-2-4-9-7-4-2最優(yōu)解的取法：從含0元素最少的行或列開始，圈出一個(gè)0元素，用○表示，然后劃去該○所在的行和列中的其余0元素，用×表示，依次類推，若能得到n個(gè)○，則得最優(yōu)解X02/7/2023130例：求費(fèi)用矩陣為右表的指派問題的最優(yōu)解工作人費(fèi)用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4得4個(gè)○，且不存在沒打×的0修改方法！2/7/2023131對(duì)n階費(fèi)用矩陣C，若C有n個(gè)位于不同行不同列的零元素，即可得最優(yōu)解X0。否則，對(duì)C進(jìn)行調(diào)整。-2+2-2最優(yōu)指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？？2/7/2023132當(dāng)C沒有n個(gè)位于不同行不同列的零元素時(shí)，對(duì)C進(jìn)行調(diào)整。第一步：做能覆蓋所有0元素的最小直線集合：1）對(duì)沒有○的行打√號(hào)2）對(duì)打√號(hào)的行上所有0元素的列打√號(hào)3）再對(duì)打√號(hào)的列上所有○的行打√號(hào)4）重復(fù)以上步驟直到得不出新的打√號(hào)為止5）對(duì)沒有打√號(hào)的行畫橫線，所有打√號(hào)的列畫縱線，所得到的直線即是覆蓋所有0元素的最小直線集合具體步驟：√√√2/7/2023133第二步：在沒有被直線覆蓋的元素中找出最小元素，讓打√號(hào)的列加上這個(gè)元素，打√號(hào)的行減去這個(gè)元素第三步：對(duì)所得到的矩陣畫○，若能得到n個(gè)○，則得最優(yōu)解，否則重復(fù)以上步驟，直至得到n個(gè)○?！獭獭?2-