運(yùn)籌學(xué)基礎(chǔ)對偶線性規(guī)劃(1)-在線瀏覽
2025-06-22 22:31本頁面
【正文】 = 2 5y1 +2y2 +y3 y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7≥ 0 一、 用對偶單純形方法解線性規(guī)劃 對偶單純形方法 是使用對偶原理求解原問題解的一種方法，而不是求解對偶問題解的單純形方法。 用對偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標(biāo)準(zhǔn)型是： 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 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 對偶單純形方法 Cj 比 值 CB XB b 檢驗數(shù) ?j y1 y2 y3 y4 y5 15 24 5 0 0 2 0 6 1 1 0 1 5 2 1 0 1 y4 Y5 0 0 0 15 24 5 0 0 檢驗數(shù) ?j 1/3 0 1 1/6 1/6 0 1/3 5 0 2/3 1/3 1 Y2 y5 24 0 8 15 0 1 4 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 檢驗數(shù) ?j 1/4 5/4 1 0 1/4 1/4 1/2 15/2 0 1 1/2 3/2 Y2 y3 24 5 17/2 15/2 0 0 7/2 3/2 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， maxw*=17/2 – 4 5 3 – 12 MinZ=17/2 應(yīng)用對偶單純形方法之矩陣法 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 0 0 5 24 15 W’ 1 1 1 2 5 0 2 0 1 6 0 0 0 0 1 ～ 8 0 1 0 15 W’ 1/3 1 2/3 0 5 0 1/3 0 1/6 1 0 0 4 1/3 1/6 ～ 17/2 3/2 0 0 15/2 W’ 1/2 3/2 1 0 15/2 0 1/4 0 0 1 5/4 0 7/2 1/2 1/4 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， max w*=17/2 Min Z=17/2 兩種方法的主要 區(qū)別 在于： 而對偶單純形方法在整個迭代過程中，則是始終保持 對偶問題的可行性 即 亦即 , ，也就是全部檢驗數(shù) ≤0，最后達(dá)到全部右邊項所有負(fù)分量逐步變?yōu)槿坑疫呿?≥0,即滿足原問題的可行性時為止。 ABCC B 1?? 0?? yAC 原始單純形方法在整個迭代過程中，始終是保持 原問題的可行性 ， 最后達(dá)到檢驗數(shù) 即 即 maxZ取得最優(yōu)值時為止。 根據(jù)模型的標(biāo)準(zhǔn)型 ， 若右邊項的數(shù)字都為非負(fù) ， 且檢驗數(shù)都為非正 ， 則已得到最優(yōu)解 ， 計算結(jié)束；否則 ， 若右邊項中至少有一個負(fù)分量 ， 且檢驗數(shù)也仍然非正 ， 則進(jìn)行如下計算 。 若有： 則以對應(yīng)的變量 xr為出基變量 。 在單純形表中觀察 xr所在行的各系數(shù) arj，若所有的 arj≥0， 則無可行解 ， 停止計算；否則若存在： rkkkrjrjjjj azcaazc ???????????? ??? 0m in? ， 則以 xk為入基變量 。 對偶單純形方法的顯著優(yōu)點： （ 1） 初始解可以是不可行解 ， 當(dāng)檢驗數(shù)都非正時 ， 即可以進(jìn)行基的變換 ， 這時不需要引進(jìn)人工變量 ， 因此就簡化了計算 。 因此對于 變量較少 、 約束較多 的線性規(guī)劃問題 , 可以先將它轉(zhuǎn)化成對偶問題 ， 然后用對偶單純形方法求解 。 影子價格 從對偶問題的基本性質(zhì)可以看出，在單純形法的每步迭代中有目標(biāo)函數(shù) ?????? miiinjjj ybxcz11 其中 bi代表第 i種資源的擁有量；對偶變量 yi代表第 i種資源的估價。 此時的定價區(qū)別于市場價格稱為影子價格。 生產(chǎn)任務(wù)、結(jié)構(gòu)的改變會影響影子價格。 iiybz ??? yi代表 bi每增加一個單位， 目標(biāo)函數(shù) 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? 說明 資源的影子價格實際上是一種機(jī)會成本。 市場價格高于影子價格時，可以賣出這種資源。 生產(chǎn)過程中，如果某種資源 bi未得到充分利用時，該種資源的影子價格為 0； 某種資源的影子價格不為 0時，表明該種
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1