運籌學基礎對偶線性規(guī)劃(1)(存儲版)
【正文】 中表明可用資源的數(shù)量發(fā)生變化，其變化 △ b反映到最終單純形表上 只引起基變量列數(shù)字變化 △ b*。 【 例 】 上例中， c2=3， x2的系數(shù)向量變?yōu)?P2=(8， 4， 1)T，試分析最優(yōu)解的變化。否則，將新增約束直接反映到最終表中，再進行分析。 4M 5+24M 0 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x’2 x3 x4 x5 x6 2 3 0 0 0 3 3/8 0 0 1/24 1/6 1 1/24 11/4 1 0 1/12 1/3 0 1/12 15/8 0 1 1/8 0 0 1/8 x5 x1 x’2 0 2 3 89/8 0 0 5/24 2/3 0 M+5/24 新的最優(yōu)值為 maxz*=89/8 得到新最優(yōu)解： x1=11/4， x2=15/8， x3=0， x4=0， x5=3/8， x6=0 五、增加一個約束條件的分析 增加一個約束條件，在實際問題中相當于增添一道工序。6PCj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 因 ?6=10 ,故用單純形法繼續(xù)計算 70 21 3 x6 增加變量 x6，有 c6=3, P6=(3,4,2)T，試分析最優(yōu)解的變化。 常數(shù)項 bi的改變量 系數(shù) aij的改變量 目標函數(shù)系數(shù) cj的改變量 解的情況判定表 原問題 對偶問題 結(jié)論或繼續(xù)計算的步驟可行解 可行解 仍為問題最優(yōu)解可行解 非可行解 用單純法繼續(xù)迭代求最優(yōu)解非可行解 可行解 用對偶單純法繼續(xù)迭代求最優(yōu)解非可行解 非可行解 引進人工變量，編制新的單純形表重新計算一、分析 cj變化的影響 目標函數(shù)中的系數(shù) cj的變化僅僅影響到檢驗數(shù) (cjzi)的變化。 在現(xiàn)實中，如果市場條件變化， cj值就會發(fā)生變化；如果工藝技術條件改變，則 aij就會變化；如果資源的可用量發(fā)生變化，則 bi也會發(fā)生變化。 影子價格是一種邊際價格。 （ 2） 對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題 ，采用對偶單純形法計算量較少 。 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對應的初始單純形表 。 對偶單純形方法 原問題是： 原問題的標準型是： 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 = 2 5y1 +2y2 +y3 y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7≥ 0 一、 用對偶單純形方法解線性規(guī)劃 對偶單純形方法 是使用對偶原理求解原問題解的一種方法，而不是求解對偶問題解的單純形方法。 若有： 則以對應的變量 xr為出基變量 。 影子價格 從對偶問題的基本性質(zhì)可以看出，在單純形法的每步迭代中有目標函數(shù) ?????? miiinjjj ybxcz11 其中 bi代表第 i種資源的擁有量；對偶變量 yi代表第 i種資源的估價。 市場價格高于影子價格時，可以賣出這種資源。 解決方法： 當參數(shù)變化時，用單純形法從頭計算，看最優(yōu)解有無變化，但這樣做既麻煩又沒有必要。因此靈敏度分析的步驟為： △ b*=B1△ b算出 △ b*， 將其加到最終表基變量列的數(shù)字上； （ 檢驗行沒變 ） ， 故只需檢查原問題是否仍為可行解 ， 再按相應步驟進行 。 【 解
范文總結(jié)相關推薦
鄂ICP備17016276號-1