整数规划之解法--切面法.pptVIP

第二節　整數規劃之解法 本章介紹其中兩種較常用的方法 切面法 分枝界限法 切面法(Cutting-Plane Method) 由高默利(Gomery)提的整數形法(Method of Integer Forms)步驟如下 步驟一：求解時，首先不考慮整數之限制條件，而 依一般線性規劃單形法求解，如果所求出之決策變數均為整數時，則現階段的解即為所求之最佳解。若至少有一個決策變數為非整數時，則進入步驟二。 步驟二 若由步驟一所獲得的最佳解中只有一個決策變數之解值不為整數時，則於最佳解所在的表格中，對該基礎變數不為整數解所對應的列方程式做一些移項手續，求出Gomery的限制條件，然後將此限制條件加入原問題之最佳解表格中最後一列，再利用對偶單形法求解。此Gomery的限制條件之意義為在線性規劃之可行區域內，加入一個整數限制條件，以縮小可行區域。 若由步驟一所獲得的最佳解中，同時有數個決策變數之解值不為整數時，則考慮具有最大非負分數(將假分數化成帶分數，只考慮分數部分)之基礎變數所對應的列(依 Gomery 經驗，做此項考慮可減少反覆計算之表格數)方程式做移項手續，求出Gomery的限制條件，然後將此限制條件加入原問題之最佳解表格中最後一列，再利用對偶單形法求解。 步驟三：由步驟二所獲得的解若均為整數，則所求 的解便獲得，否則再回到步驟二直至得到最佳整數解為止。 所謂非負分數 f (Non-negative fraction)為大於或等於0，但小於 1 的正數，即為 0 ≦ f ＜1。當非整數的數值減去此一非負分數，其結果將為整數，則稱為此數的非負分數，若原數為整數時，則其負分數為零。 上表中假設 x1 至 xn 為基礎變數，由上表第 i 個基礎變數 xi 可得方程式為 (A) 且式中 ?i不全為整數，否則一般線性規劃問題已求得最佳解。令 ?i＝[ ?i ]＋fi ,i＝1,2,…,n dij＝[ dij ]＋fij ,i＝1,2,…,n ，j＝1,2,…,m 其中[ ]：為高斯符號，表示最大整數函數 [ ?i ] ≦ ?i 的最大整數 [ dij ] ≦ dij 的最大整數 fi 和 fij 為非負分數，0≦fi＜1，0≦fij＜1。 將(A)式可寫成 上式右邊第一個括號內之值為整數，所以欲使 xi 為整數值，則　　　　　　須為零或整數不可，因 fi 和 fij 為非負 分數，一非負分數減去含有分數的某數，若想成為整數的話(不可能成為正整數)，不是零便是一個負整數，故可得一個重要結論為： 再引進鬆弛變數(Slack variable) si，且令 si≧0 (B) 此即為Gomery的限制條件，此限制條件可使非整數之變數變成整數。在原線性規劃問題之最佳解表加入Gomery限制條件後，因 si 在目標函數中係數為零，所以各 cj－zj 值皆不變，仍滿足最佳解的要求，但是此時 s‘I ＝ -fi，為不可行的最佳解，故必須使用對偶單形法繼續求解。 又一次只能加入一個Gomery限制條件，不能同時加入兩個以上的限制條件，加入Gomery限制條件後，其效應會使最大問題的目標函數值減少，使最小問題之目標函數值增加。 Max z ＝ 8x1＋18x2 s.t. x1＋x2 ≦ 10 x1＋3x2≦ 15 x1, x2 ≧ 0 且為整數 作業研究．Chapter 7　整數規劃 7-* 作 業 研 究 陳坤茂　著 7 整數規劃 表7-1　假設為最佳解表 作作看4