[拼音]：fenzhi xianjiefa

[外文]：branch and bound method

一種求解離散最優(yōu)化問題的計(jì)算分析方法，又稱分枝定界法。它是由R.J.達(dá)金和蘭德－多伊格在20世紀(jì)60年代初提出的。這種方法通常僅需計(jì)算和分析部分允許解，即可求得最優(yōu)解。因此在求解分派問題和整數(shù)規(guī)劃問題時(shí)常用此法。

基本方法

求解一個(gè)約束條件較多的問題A,可以暫緩考慮部分條件，變換成問題B,先求B的最優(yōu)解。B的最優(yōu)解一定比 A的好（或相當(dāng)）。再將原來暫緩考慮的部分條件逐步插入問題B中，得到B的若干子問題，稱為分枝。求解這些子問題，淘汰較差的解，直到所有暫緩考慮的部分條件全部插入為止。這時(shí)求得的最優(yōu)解就是問題A的最優(yōu)解。

分派問題

設(shè)生產(chǎn)任務(wù)Ⅰ、Ⅱ、Ⅲ和Ⅳ,皆可在4臺(tái)不同設(shè)備A、B、C和D上去完成。由于設(shè)備性能和技術(shù)要求等不同，在不同設(shè)備上完成各項(xiàng)任務(wù)所需的費(fèi)用（或時(shí)間）均不相同，下表列出某一具體問題的任務(wù)、設(shè)備和費(fèi)用的數(shù)量關(guān)系。規(guī)定每臺(tái)設(shè)備只能安排一項(xiàng)生產(chǎn)任務(wù)。要求分派這4項(xiàng)生產(chǎn)任務(wù)，使總費(fèi)用為最少。

首先分析在所有分派方案中，以何種分派方案的費(fèi)用為最低。由表可知，當(dāng)分派方案是(I-D)（即任務(wù)I交由D設(shè)備去完成時(shí)，下同）,(Ⅱ-A)，(Ⅲ-C)，(Ⅳ-D)時(shí)，即得總費(fèi)用

為最小。它稱為下界。但這樣的分派方案要由 D設(shè)備去完成Ⅰ、Ⅳ兩項(xiàng)任務(wù)，不符合題意要求。所以稱這個(gè)解為非允許解。為此必須加以改進(jìn)。接著，規(guī)定任務(wù)Ⅰ交由A去完成，其他任務(wù)則選擇費(fèi)用最小的設(shè)備去完成,則由表可知，其總費(fèi)用為

該方案恰好滿足一臺(tái)設(shè)備完成一項(xiàng)任務(wù)的規(guī)定，因此總費(fèi)用193的解稱為允許解。依次計(jì)算(I-B),(I-C),(I-D)各分派方案的解,如圖1所示。分析1～4的分派方案后可知,要求的最優(yōu)解一定在164和148之間，即上界是164，下界是148。這時(shí),只要在方案4這個(gè)分枝上繼續(xù)進(jìn)行組合即可。用同樣計(jì)算方法得圖2所示的分派方案。由分派方案5～7可知，方案5的總費(fèi)用為156，但是非允許解，方案6的總費(fèi)用是157，是允許解。所以方案6是最優(yōu)解。其具體分派組合是:(I-D),(Ⅱ-B),(Ⅲ-C)，(Ⅳ-A)。上述計(jì)算過程可歸納如圖3所示。

參考書目

1. 李德等編：《運(yùn)籌學(xué)》，清華大學(xué)出版社,北京,1982。

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：分枝限界法

版權(quán)聲明：本文采用知識(shí)共享 署名4.0國(guó)際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《分枝限界法》

文章鏈接：http://www.kaputelugumatrimony.com/14590.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識(shí)整合。如若侵權(quán)請(qǐng)通過投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。