運籌學-割平面法-資料下載頁
2025-08-05 17:39本頁面
【正文】 356165432431??????xxxxxxCB XB b x1 x2 x3 x4 1 x1 5/3 1 0 5/6 － 1/6 1 x2 8/3 0 1 － 2/3 1/3 σj 13/3 0 0 － 1/6 － 1/6 383132356165432431??????xxxxxx將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和 32231)311(321)651(65432431????????????xxxxxx將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和 32231)311(321)651(65432431????????????xxxxxx 以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數(shù)相等，可任選一個考慮?，F(xiàn)選 第二個式子 ，并將真分數(shù)移到右邊得： 以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數(shù)相等，可任選一個考慮?，F(xiàn)選 第二個式子 ，并將真分數(shù)移到右邊得： )(313224332 xxxx ?????引入松弛變量 s1 后得到下式，將此約束條件加到上表中，繼續(xù)求解。 323131143 ????? sxx341 1 23 3 3xx? ? ? ?Cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 s1 1 x1 5/3 1 0 5/6 － 1/6 0 1 x2 8/3 0 1 － 2/3 1/3 0 0 s1 － 2/3 0 0 － 1/3 － 1/3 1 σj －13/3 0 0 － 1/6 － 1/6 0 323131143 ????? sxxCj 1 1 0 0 0 CB XB b x1 x2 x3 x4 s1 1 x1 5/3 1 0 5/6 － 1/6 0 1 x2 8/3 0 1 － 2/3 1/3 0 0 s1 － 2/3 0 0 － 1/3 － 1/3 1 σj －13/3 0 0 － 1/6 － 1/6 0 Cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 s1 1 x1 0 1 0 0 － 1 0 1 x2 4 0 1 0 1 － 2 0 x3 2 0 0 1 1 － 3 σj － 4 0 0 0 0 － 1/2 ﹡ Cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 s1 1 x1 0 1 0 0 － 1 0 1 x2 4 0 1 0 1 － 2 0 x3 2 0 0 1 1 － 3 σj － 4 0 0 0 0 － 1/2 ﹡ 得到整數(shù)最優(yōu)解 ， 即為整數(shù)規(guī)劃的最優(yōu)解 ， 而且此整數(shù)規(guī)劃有兩個最優(yōu)解： X＊ = (0, 4), Z = 4, 或 X＊ = (2, 2), Z = 4。 ?????????????????且為整數(shù)練習：0,421625421411m a x2121212121xxxxxxxxxxZCB XB b x1 x2 x3 x4 x5 0 x3 4 0 0 1 1/3 4/3 4 x2 4/3 0 1 0 2/9 5/9 11 x1 8/3 1 0 0 1/9 2/9 σj 0 0 0 19/9 2/9 CB XB b x1 x2 x3 x4 x5 s1 0 x3 0 0 0 1 1 0 6 4 x2 3 0 1 0 1/2 0 5/2 11 x1 2 1 0 0 0 0 1 0 x5 3 0 0 0 1/2 1 9/2 σj 0 0 0 2 0 1 （ 2 ， 3）
研究報告相關(guān)推薦
鄂ICP備17016276號-1