本文是《最優化理論與算法（第2版）》的學習筆記
本次學習的内容是分支定界法，在學習分支定界法之前，有必要回顧一下運籌學（最優化理論）學習筆記 | 單純形法，單純形法這篇推文，小編講得不全，因為本次推文還會用到單純形法中的大M法，是以各位小夥伴還需看書學習一下大M法，如果不想看書也沒關系，小編把大M法的求解過程也寫了下來。
首先，我們需要明确一點，什麼時候才會用到分支定界法？
答：整數規劃的時候，因為整數規劃會要求部分變量必須取整數。
求解整數規劃的正常步驟是：
STEP1：将整數規劃去掉整數性限制，得到線性規劃，俗稱松弛。
整數規劃P與松弛問題P1有如下關系
(1)若松弛問題沒有可行解，則整數規劃無可行解；
(2)松弛問題的最小值給出整數規劃的最小值的下界（PS：其實就是整數規劃相當于給松弛問題加上了整數限制，加上限制得到的最優解一定小于等于無整數限制的松弛問題的最優解）；
(3)若松弛問題的最優解是整數規劃的可行解，則也是整數規劃的最優解。
STEP2：分解
STEP3：探測
這兩步就不詳細講解了，下面用書中的執行個體讓大家更好的了解分支定界法。
用分支定界法求解整數規劃（P）
首先給出求解這個問題的流程，先讓大家對分支定界法有一個直覺上的感受。
對單純形表陌生的小夥伴可以看運籌學（最優化理論）學習筆記 | 單純形法複習一下
微網誌：随心390