運籌學基礎對偶線性規(guī)劃(1)-展示頁
2025-05-14 22:31本頁面
【正文】 79/4 0 0 0 7/8 1/4 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 5 0 0 0 15 0 5 1 0 0 4 1 1/3 0 1/6 0 1 0 2/3 0 1/6 1 x3 x1 x5 0 5 0 20 0 1/6 0 5/6 0 即得新最優(yōu)解 x1=4， x2=0， x3=15， x4=0 ， x5=1 此時 MaxZ=20 【 解 】 (b)將目標函數(shù)系數(shù)的變化直接反映到最終單純形表中 為使表中解為最優(yōu)，應該有 1/41/4l??， 1/2+1/2l?? 即得 ： 1? l?? 檢驗數(shù) ?jbX BC B比值Cj檢驗數(shù)比值x5x4x3x2x100012 1 5 / 25 /41001 5 /2 1 /21 /40017 /23 /2 1 /40103 /2x2x1x312+ l0 1 /2 1 /4000 1 7 /22+l 1 0 0 0 0 2+l 1 17/2 l 0 0 1/4 1/2 17/27/2l 0 0 1/41/4l 1/2+1/2l 即： 1? l??時，最優(yōu)解不變； 二、分析 bi變化的影響 bi的變化 在實際問題中表明可用資源的數(shù)量發(fā)生變化，其變化 △ b反映到最終單純形表上 只引起基變量列數(shù)字變化 △ b*。 常數(shù)項 bi的改變量 系數(shù) aij的改變量 目標函數(shù)系數(shù) cj的改變量 解的情況判定表 原問題 對偶問題 結(jié)論或繼續(xù)計算的步驟可行解 可行解 仍為問題最優(yōu)解可行解 非可行解 用單純法繼續(xù)迭代求最優(yōu)解非可行解 可行解 用對偶單純法繼續(xù)迭代求最優(yōu)解非可行解 非可行解 引進人工變量，編制新的單純形表重新計算一、分析 cj變化的影響 目標函數(shù)中的系數(shù) cj的變化僅僅影響到檢驗數(shù) (cjzi)的變化。 這也就是靈敏度分析。 把個別參數(shù)的變化直接在獲得最優(yōu)解的 最終單純形表 上反映出來。 靈敏度分析 問題： 參數(shù)發(fā)生變化時，問題的最優(yōu)解會有什么變化？ 參數(shù)多大的范圍內(nèi)變化時 ,原最優(yōu)解保持不變。 在現(xiàn)實中，如果市場條件變化， cj值就會發(fā)生變化；如果工藝技術條件改變，則 aij就會變化；如果資源的可用量發(fā)生變化，則 bi也會發(fā)生變化。 由對偶互補松弛定理即可說明 靈敏度分析 ，是指對系統(tǒng)或事物因周圍條件變化所表現(xiàn)出的敏感性程度的分析。 隨著資源的買進和賣出，它的影子價格也隨之發(fā)生變化。 市場價格低于影子價格時，可以買進這種資源。 影子價格是一種邊際價格。 ? 說明 市場價格主要隨市場供求變化；而它的影子價格有賴于資源的利用情況。此時的估價不是市場價格，而是根據(jù)資源在生產(chǎn)中的貢獻而作的估價。 167。 （ 2） 對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題 ，采用對偶單純形法計算量較少 。 （ 4） 以 ark為主元按原始單純形方法的迭代方法進行迭代 ，得到新的單純形表。 ? ? riii bBbBbB )(0)()(m in 111 ??? ?? （ 3） 確定入基變量 。 （ 2） 確定出基變量 。 2560 24 14 0 0 Z 16 2/5 1/10 0 1 0 12 1/5 3/10 1 0 0 相當于：直到對偶問題的解可行為止 相當于：即直到原問題的解可行為止 用對偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標準型是： minZ=2x1+3x2+4x3 x1+ 2x2+x3 ≥ 3 2x1 x2 +3x3 ≥4 x1 , x2 , x3 ≥ 0 maxZ’= 2x13x24x3 +0x4 +0x5 x1+ 2x2+x3 x4 = 3 2x1 x2 +3x3 x5 =4 x1 , x2 , x3 , x4 , x5 ≥ 0 maxw’= 2x13x24x3 +0x4 +0x5 x1 2x2 x3 +x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 應用對偶單純形方法之矩陣法 0 0 4 3 2 W’ 4 1 3 1 2 0 3 0 1 2 1 0 0 0 1 ～ 4 1 1 4 0 W’ 2 1/2 3/2 1/2 1 0 1 1/2 1/2 5/2 0 0 0 0 1 ～ 28/5 1/5 3/5 0 0 W’ 11/5 2/5 7/5 0 1 0 2/5 1/5 1/5 1 0 0 8/5 1/5 2/5 最優(yōu)解 :Y*=(11/5,2/5,0,0,0)T， Maxw’ =28/5 maxw’= 2x13x24x3 +0x4 +0x5 x1 2x2 x3 +x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 MinZ* = 28/5 小結(jié)：對偶單純形方法的解題過程一般分為四步 （ 1） 寫出與已有的初始基 B對應的初始單純形表 。 CyA ? 0?? yAC 所以 ,對偶單純形方法實質(zhì) 就是在保證對偶問題可行的條件下向原問題可行的方向迭代。與對偶單純形方法相對應，原已有的單純形方法稱 原始單純形方法 。167。 對偶單純形方法 原問題是： 原問題的標準型是： minZ=15y1+24y2+5y3 6y2+y3 ≥ 2 5y1 +2y2 +y3 ≥1 y1 , y2 , y3 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2+y3 y4 = 2 5y1 +2y2 +y3 y5 =1 y1 , y2 , y3 , y4 , y5 ≥ 0 利用單純形法： maxw’= 15y124y25y3 +0y4 +0y5My6My7 6y2+y3 y4 +y6
范文總結(jié)相關推薦
鄂ICP備17016276號-1