運籌學課件第5章整數(shù)線性規(guī)劃-第1-4節(jié)(編輯修改稿)
2024-11-14 21:04 本頁面
【文章內(nèi)容簡介】 如在域 R′上求解①～④，而得到的最優(yōu)解又恰巧在 C點就得到原問題的整數(shù)解，所以解法的關鍵就是怎樣構造一個這樣的“ 割平面 ” CD，盡管它可能不是唯一的，也可能不是一步能求到的。下面仍就本例說明： ? 在原問題的前兩個不等式中增加非負松弛變量 x x4， 使兩式變成等式約束： ? x1+x2+x3 =1 ⑥ ? 3x1+x2 +x4=4 ⑦ 不考慮條件 ⑤ ， 用單純形表解題 ， 見表 52。 表 52 c j 1 1 0 0 C B X B b x 1 x 2 x 3 x 4 0 0 x 3 x 4 1 4 1 3 1 1 1 0 0 1 初始計算表 c j z j 0 1 1 0 0 1 1 x 1 x 2 3/4 7/4 1 0 0 1 1 /4 3/4 1/4 1/5 最終計算表 cj z j 5/2 0 0 1/2 1/2 從表 52的最終計算表中，得到非整數(shù)的最優(yōu)解： x1=3/4， x2=7/4， x3=x4=0， max z=5/2 不能滿足整數(shù)最優(yōu)解的要求。為此考慮將帶有分數(shù)的最優(yōu)解的可行域中分數(shù)部分割去，再求最優(yōu)解。就可以得到整數(shù)的最優(yōu)解。 可從 最終計算表中得到 非整數(shù) 變量 對應 的關系式： 474143434141432431??????xxxxxx為了得到整數(shù)最優(yōu)解。將上式變量的系數(shù)和常數(shù)項都分解成整數(shù)和非負真分數(shù)兩部分之和 ? (1+0)x1+(1+3/4)x3+1/4x4=0+3/4 ? x2+(3/4)x3+(1/4)x4=1+3/4 ? 然后將整數(shù)部分與分數(shù)部分分開 ， 移到等式左右兩邊 ， 得到 ： ????????????????????43243314143431414343xxxxxxx現(xiàn)考慮整數(shù)條件⑤ ? 要求 x x2都是非負整數(shù)，于是由條件⑥、⑦可知 x x4也都是非負整數(shù) ,這一點對以下推導是必要的，如不都是整數(shù)，則應在引入 xx4之前乘以適當常數(shù)，使之都是整數(shù)。在上式中 (其實只考慮一式即可 )從等式左邊看是整數(shù)； 等式右邊也應是整數(shù) 。但在等式右邊的 ()內(nèi)是正數(shù)；所以等式右邊必是 非正數(shù) 。就是說，右邊的整數(shù)值最大是零。于是 整數(shù)條件⑤可由下式所代替； 0414343 43 ??? xx? 即 3x3x4≤ 3 ⑧ 這就得到一個切割方程 (或稱為切割約束 )，將它作為增加約束條件 ， 再解例 3。 ? 引入松弛變量 x5， 得到等式 ? 3x3x4+x5=3 ? 將這新的約束方程加到表 52的最終計算表，得表 53。 0414343 43 ??? xx表 53 c j 1 1 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 1 1 0 x 1 x 2 x 5 3/4 7/4 3 1 0 0 0 1 0 1/4 3/4 3 1/4 1/4 1 0 0 1 c j z j 5/2 0 0 1/2 1/2 0 從表 53的 b列中可看到，這時得到的是非可行解，于是需要用對偶單純形法繼續(xù)進行計算 ? 選擇 x5為換出變量 ， 計算 61121,321m i n0m i n ????????????????????????????? ljljjjjaazc?將 x3做為換入變量，再按原單純形法進行迭代，得表 54。 c j 1 1 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 1 1 0 x 1 x 2 x 3 1 1 1 1 0 0 0 1 0 0 0 1 1/3 0 1/3 1/12 1/4 1/3 c j z j 2 0 0 0 1/3 1/6 由于 x 1 、 x 2 的值已都是整數(shù)，解題已完成。 注意：新得到的約束條件⑧ 3x3x4≤ 3 ? 如用 x x2表示，由⑥、⑦式得 ? 3(1+x1x2)+(43x1x2)≥3 ? x2≤1 ? 這就是 (x1， x2)平面 內(nèi)形成新的可行域 ， 即包括平行于 x1軸的直線 x2=1和這直線下的可行區(qū)域 ， 整數(shù)點也在其中 ， 沒有切割掉 。 直觀地表示在圖 57中 。 但從解題過程來看 ， 這一步是不必要的 。 圖 57 現(xiàn)把求一個切割方程的步驟歸納為： (1) 令 xi是相應線性規(guī)劃最優(yōu)解中為分數(shù)值的一個基變量 ， 由單純形表的最終表得到 ? ???kikiki bxax )45(其中 i∈Q(Q 指構成基變量號碼的集合 ) K k∈K(K 指構成非基變量號碼的集合 ) (2) 將 bi和 α ik都分解成整數(shù)部分 N與非負真分數(shù) f之和，即 ? bi=Ni+fi， 其中 0＜ fi＜ 1 ? α ik=Nik+fik，其中 0≤f ik＜ 1 (55) ? 而 N表示不超過 b的最大整數(shù) 。 例如： ? 若 b=， 則 N=2， f= ? 若 b=， 則 N=1,f= ? 代入 (54)式得 ? ? ?????k k kikiikikixffNxNx )65((3) 現(xiàn)在提出變量 (包括松弛變量，參
教學課件相關推薦
鄂ICP備17016276號-1