割平面法

出自 MBA智库百科(https://wiki.mbalib.com/)

　　割平面法是1958年由美國學者高莫利(R.E.GoMory)提出的求解全整數規劃的一種比較簡單的方法。其基本思想和分枝定界法大致相同，即先不考慮變數的取整約束，用單純形法求解相應的線性規劃。如果所得的最優解為整數解，那麼它也是原整數規劃問題的最優解3如果最優解不是整數解，那麼分枝定界法是任取一個取分數值的變數X_k = b_k將原整數規劃分成兩枝，其實質是用兩個垂直於坐標軸的平行平面X_k = [b_k]和X_k = [b_k] + 1將原可行域R分成兩個可行域R₁和R₂，並將兩個平行平面之間的不合有整數解的那一部分可行域去掉，以縮小可行域。而割平面法是用一張平面(不一定垂直於某個坐標軸)，將含有最優解的點但不含任何整數可行解的那一部分可行域切割掉，這隻要在原整數規劃基礎上增加適當的線性不等式約束(我們稱之為切割不等式；當切割不等式取等號時，叫做割平面)。然後繼續解這個新的整數規劃，再在這個新的整數規劃的基礎上增加適當的線性不等式約束，直至求得最優整數解為止。也就是說，通過構造一系列平面來切割掉不含有任何整數可行解的部分，最終獲得一個具有整數坐標的頂點的可行域，而該頂點恰好是原整數規劃的最優解。

　　割平面法的關鍵在於，如何構造切割不等式，使增加該約束後能達到真正的切割而且沒有切割掉任何整數可行解。

　　(1)先不考慮變數的取整約束，用單純形法求解相應的線性規劃問題，如果該問題沒有可行解或最優解已是整數則停止，否則轉下步。

　　在求解相應的線性規劃時，首先要將原問題的數學模型進行標準化。這裡的“標準化”有兩個含義：第一是將所有的不等式約束全部轉化成等式約束，這是因為要採用單純形表進行計算的緣故。第二是將整數規劃中所有非整數繫數全部轉換成整數，這是出於構造“切割不等式”的需要。

　　(2)求一個“切割不等式”及添加到整數規劃的約束條件中去，即對上述線性規劃問題的可行域進行“切割”，然後返回步驟1。

　　用割平面法求解整數規劃的基本思路是：先不考慮整數約束條件，求鬆弛問題的最優解，如果獲得整數最優解，即為所求，運算停止．如果所得到最優解不滿足整數約束條件，則在此非整數解的基礎上增加新的約束條件重新求解．這個新增加的約束條件的作用就是去切割相應鬆弛問題的可行域，即割去鬆弛問題的部分非整數解(包括原已得到的非整數最優解)．而把所有的整數解都保留下來，故稱新增加的約束條件為割平面．當經過多次切割後，就會使被切割後保留下來的可行域上有一個坐標均為整數的頂點，它恰好就是所求問題的整數最優解．即切割後所對應的鬆弛問題，與原整數規劃問題具有相同的最優解。