【正文】 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 小結：對偶單純形方法的解題過程一般分為四步 （ 1） 寫出與已有的初始基 B對應的初始單純形表 。 根據模型的標準型 ， 若右邊項的數字都為非負 ， 且檢驗數都為非正 ， 則已得到最優(yōu)解 ， 計算結束；否則 ， 若右邊項中至少有一個負分量 ， 且檢驗數也仍然非正 ， 則進行如下計算 。 （ 2） 確定出基變量 。 若有： 則以對應的變量 xr為出基變量 。 ? ? riii bBbBbB )(0)()(m in 111 ??? ?? （ 3） 確定入基變量 。 在單純形表中觀察 xr所在行的各系數 arj，若所有的 arj≥0， 則無可行解 ， 停止計算；否則若存在： rkkkrjrjjjj azcaazc ???????????? ??? 0m in? ， 則以 xk為入基變量 。 （ 4） 以 ark為主元按原始單純形方法的迭代方法進行迭代 ，得到新的單純形表。 對偶單純形方法的顯著優(yōu)點： （ 1） 初始解可以是不可行解 ， 當檢驗數都非正時 ， 即可以進行基的變換 ， 這時不需要引進人工變量 ， 因此就簡化了計算 。 （ 2） 對于變量個數多于約束方程個數的線性規(guī)劃問題 ，采用對偶單純形法計算量較少 。 因此對于 變量較少 、 約束較多 的線性規(guī)劃問題 , 可以先將它轉化成對偶問題 ， 然后用對偶單純形方法求解 。 167。 影子價格 從對偶問題的基本性質可以看出，在單純形法的每步迭代中有目標函數 ?????? miiinjjj ybxcz11 其中 bi代表第 i種資源的擁有量；對偶變量 yi代表第 i種資源的估價。此時的估價不是市場價格，而是根據資源在生產中的貢獻而作的估價。 此時的定價區(qū)別于市場價格稱為影子價格。 ? 說明 市場價格主要隨市場供求變化；而它的影子價格有賴于資源的利用情況。 生產任務、結構的改變會影響影子價格。 影子價格是一種邊際價格。 iiybz ??? yi代表 bi每增加一個單位， 目標函數 z的增量 maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 +1 （ 1） z*=42 不變， A的邊際價格為 0 +1 （ 2） x*=(10/3,13/2) z*=， B的邊際價格為 +1 （ 3） x*=(13/3,6) z*=43， C的邊際價格為 1 x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B(8,3) C(4,6) D ??? miii ybz1? 說明 資源的影子價格實際上是一種機會成本。 市場價格低于影子價格時，可以買進這種資源。 市場價格高于影子價格時，可以賣出這種資源。 隨著資源的買進和賣出，它的影子價格也隨之發(fā)生變化。 生產過程中，如果某種資源 bi未得到充分利用時，該種資源的影子價格為 0； 某種資源的影子價格不為 0時，表明該種資源已經耗盡。 由對偶互補松弛定理即可說明 靈敏度分析 ，是指對系統或事物因周圍條件變化所表現出的敏感性程度的分析。 在前面講的線性規(guī)劃問題中，通常都是假定問題中的 aij， bi， cj系數是已知的常數 ,但實際上這些參數都是一些估計或預測的數字。 在現實中，如果市場條件變化， cj值就會發(fā)生變化；如果工藝技術條件改變，則 aij就會變化；如果資源的可用量發(fā)生變化，則 bi也會發(fā)生變化。 167。 靈敏度分析 問題： 參數發(fā)生變化時，問題的最優(yōu)解會有什么變化？ 參數多大的范圍內變化時 ,原最優(yōu)解保持不變。 解決方法： 當參數變化時，用單純形法從頭計算，看最優(yōu)解有無變化，但這樣做既麻煩又沒有必要。 把個別參數的變化直接在獲得最優(yōu)解的 最終單純形表 上反映出來。這樣就不需要從頭計算，而只需對獲得最優(yōu)解的單純形表進行審查，看一些數字變化后是否仍滿足最優(yōu)解的條件 ,如果不滿足的話 ,再從這個表開始進行迭代計算，求得最優(yōu)解即可。 這也就是靈敏度分析。 靈敏度分析的步驟如下： 參數的改變 計算反映到最終單純形表上來 △ b*=B1 △ b 具體計算方法是，按下列公式計算出由參數 aij、 bi、 cj的變化而引起的最終單純形表上有關數字的變化： △ Pi*=B1 △ Pi △ (cjzi)*= △ (cjzi) ∑aijyi* ；即 右端常數是否大于 0 ；即 檢驗數是否小于 0 。 常數項 bi的改變量 系數 aij的改變量 目標函數系數 cj的改變量 解的情況判定表 原問題 對偶問題 結論或繼續(xù)計算的步驟可行解 可行解 仍為問題最優(yōu)解可行解 非可行解 用單純法繼續(xù)迭代求最優(yōu)解非可行解 可行解 用對偶單純法繼續(xù)迭代求最優(yōu)解非可行解 非可行解 引進人工變量，編制新的單純形表重新計算一、分析 cj變化的影響 目標函數中的系數 cj的變化僅僅影響到檢驗數 (cjzi)的變化。所以將 cj 的變化直接反映到最終單純形表中，只可能出現表中的前兩種情況。 【 例 】 已知線性規(guī)劃問題： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 用單純形法求得最終單純形表如下 最終單純形表 Cj 比 值 CB XB b 檢驗數 ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2