運籌學-割平面法-展示頁
2024-08-20 17:39本頁面
【正文】 = 3/2 但不是整數(shù)最優(yōu)解，引入割平面。 ⑶ .若 ( LP )有最優(yōu)解，但不符合 ( IP )的整數(shù)條件，轉(zhuǎn)入下一步。（一）、計算步驟： 用單純形法求解 ( IP )對應的松弛問題 ( LP )： ⑴ .若 ( LP )沒有可行解，則 ( IP )也沒有可行解，停止計算。 ⑵ .若 ( LP )有最優(yōu)解，并符合 ( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為 ( IP )的最優(yōu)解，停止計算。 第二節(jié) 割平面法 從 (LP)的最優(yōu)解中，任選一個不為整數(shù)的分量xr,將最優(yōu)單純形表中該行的系數(shù) 和 分解為 整數(shù)部分和小數(shù)部分之和 ，并以該行為源行，按下式作割平面方程： rja? rb?? ?1 nr j j rjmf x f??? ? ?? 將所得的割平面方程作為一個新的約束條件置于最優(yōu)單純形表中（同時增加一個單位列向量），用對偶單純形法求出新的最優(yōu)解，返回 1。以 x2 為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我們已將所需要的數(shù)分解為整數(shù)和分數(shù)，所以，生成割平面的條件為 : 341 1 14 4 2xx? ? ? ?Cj 0 1 0 0 CB XB b x1 x2 x3 x4 0 x1 1 1 0 1/6 1/6 1 x2 3/2 0 1 1/4 1/4 σj 3/2 0 0 1/4 1/4 現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中： 214141143 ????? sxxCj 0 1 0 0 0 CB XB b x1 x2 x3 x4 s1 0 x1 1 1 0 1/6 1/6 0 1 x2 3/2 0 1 1/4 1/4 0 0 s1 1/2 0 0 1/4 1/4 1 σj 3/2 0 0 1/4 1/4 0 214141143 ????? sxxCB XB b x1 x2 x3 x4 s1 0 x1 2/3 1 0 0 1/3 2/3 1 x2 1 0 1 0 0 1 0 x3 2 0 0 1 1 4 σj 1 0 0 0 0 1 此時， X1 ＝ (2/3, 1), Z=1,仍不是整數(shù)解。 有以上解題過程可見，表中含有分數(shù)元素且算法過程中始終保持對偶可行性，因此，這個算法也稱為分數(shù)對偶割平面算法。以 x2 為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我們已將所需要的數(shù)分解為整數(shù)和分數(shù)，所以，生成割平面的條件為 : 341 1 14 4 2xx? ? ? ?也即： 2342342 3 41 1 34 4 21 1 114 4 21 1 11 ( )2 4 4x x xx x xx x x? ? ?? ? ? ?? ? ? ?Cj 0 1 0 0 CB XB b x1 x2 x3 x4 0 x1 1 1 0 1/6 1/6 1 x2 3/2 0 1 1/4 1/4 σj 3/2 0 0 1/4 1/4 0)4141(21 43 ???? xx????????????且為整數(shù)0,023623 m a x2121212xxxxxxxZ 21 2 31 2 412m a x 3 2 63 2 0,0Zxx x xx x xxx?? ? ???? ? ? ????? 且 為 整 數(shù)21 2 31 2 412m a x 3 2 63 2 0,0Zxx x xx x xxx?? ? ???? ? ? ?????
研究報告相關(guān)推薦
鄂ICP備17016276號-1