分枝限界法
branchandboundmethod
分支界限法一種求解離散最最佳化問題的計算分析方法，又稱分枝定界法。它是由R.J.達金和蘭德－多伊格在20世紀60年代初提出的。這種方法通常僅需計算和分析部分允許解，即可求得最優解。因此在求解分派問題和整數規劃問題時常用此法。
基本方法
求解一個約束條件較多的問題A,可以暫緩考慮部分條件，變換成問題B,先求B的最優解。B的最優解一定比 A的好（或相當）。再將原來暫緩考慮的部分條件逐步插入問題B中，得到B的若干子問題，稱為分枝。求解這些子問題，淘汰較差的解，直到所有暫緩考慮的部分條件全部插入為止。這時求得的最優解就是問題A的最優解。
最常見的兩種方式
1).佇列式（FIFO）分支限界法：將活結點表組織成一個佇列， 並按佇列的先進先出原則選取下一個結點作為當前擴展結點。
2).優先佇列式分支限界法：將活結點表組織成一個優先佇列， 並按優先佇列給結點規定的優先權選取優先權最高的下一個結點作為當前擴展結點。 佇列式分支限界法的搜尋解空間樹的方式類似於解空間樹的寬 度優先搜尋，不同的是佇列式分支限界法不搜尋以不可行結點（已經 被判定不能導致可行解或不能導致最優解的結點）為根的子樹。這是因為，按照規則，這樣的結點未被列入活結點表。優先佇列式分支限界法的搜尋方式是根據活結點的優先權確定 下一個擴展結點。結點的優先權常用一個與該結點有關的數值p來表示。最大優先佇列規定p值較大的結點點的優先權較高。在算法實現時通常用一個最大堆來實現最大優先佇列，用最大堆的Deletemax運算抽取堆中的下一個結點作為當前擴展結點，體現最大效益優先的原則。類似地，最小優先佇列規定p值較小的結點的優先權較高。在算法實現時，常用一個最小堆來實現，用最小堆的Deletemin運算抽取堆中下一個結點作為當前擴展結點，體現最小優先的原則。採用優先佇列式分支定界算法解決具體問題時，應根據問題的特點選用最大優先或最小優先佇列，確定各個結點點的p值。
分派問題
設生產任務Ⅰ、Ⅱ、Ⅲ和Ⅳ,皆可在4台不同設備A、B、C和D上去完成。由於設備性能和技術要求等不同，在不同設備上完成各項任務所需的費用（或時間）均不相同，下表列出某一具體問題的任務、設備和費用的數量關係。規定每台設備只能安排一項生產任務。要求分派這4項生產任務，使總費用為最少。
首先分析在所有分派方案中，以何種分派方案的費用為最低。由表可知，當分派方案是(I-D)（即任務I交由D設備去完成時，下同）,(Ⅱ-A)，(Ⅲ-C)，(Ⅳ-D)時，即得總費用
該方案恰好滿足一台設備完成一項任務的規定，因此總費用193的解稱為允許解。依次計算(I-B),(I-C),(I-D)各分派方案的解,如圖1所示。
分析1～4的分派方案後可知,要求的最優解一定在164和148之間，即上界是164，下界是148。這時,只要在方案4這個分枝上繼續進行組合即可。
用同樣計算方法得圖2所示的分派方案。由分派方案5～7可知，方案5的總費用為156，但是非允許解，方案6的總費用是157，是允許解。
所以方案6是最優解。其具體分派組合是:(I-D),(Ⅱ-B),(Ⅲ-C)，(Ⅳ-A)。上述計算過程可歸納如圖3所示。
分枝限界法
分枝限界法
分枝限界法