首先，我們需要明確一點，什么時候才會用到分支定界法？

答：整數規劃的時候，因為整數規劃會要求部分變量必須取整數。

 

求解整數規劃的常規步驟是：

STEP1：將整數規劃去掉整數性約束，得到線性規劃，俗稱松弛。

 

整數規劃P與松弛問題P1有如下關系

(1)若松弛問題沒有可行解，則整數規劃無可行解；

(2)松弛問題的最小值給出整數規劃的最小值的下界（PS：其實就是整數規劃相當于給松弛問題加上了整數約束，加上約束得到的最優解一定小于等于無整數約束的松弛問題的最優解）；

(3)若松弛問題的最優解是整數規劃的可行解，則也是整數規劃的最優解。

 

STEP2：分解

STEP3：探測

這兩步就不詳細講解了，下面用書中的實例讓大家更好的理解分支定界法。

 

用分支定界法求解整數規劃（P）

 

總結

以上是生活随笔為你收集整理的运筹学（最优化理论）学习笔记 | 分支定界法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。