1、第 5 章模糊線性規(guī)劃,5.1 普通線性規(guī)劃,線性規(guī)劃是最優(yōu)化方法中理論完整、方法成熟、應(yīng)用廣泛的一個重要分支 .,線性規(guī)劃問題的數(shù)學(xué)模型是將實際問題轉(zhuǎn)化為一組線性不等式或等式約束下求線性目標(biāo)函數(shù)的最小(大)值問題, 它都可以化為如下標(biāo)準(zhǔn)(矩陣)形式：,單純形解法,典型線性規(guī)劃問題：,的單純形解法是引入m個松弛變量xn+1 , , xn+m將原問題化成如下標(biāo)準(zhǔn)形式：,大M單純形解法,不難將一般的線性規(guī)劃問題化成如下標(biāo)準(zhǔn)形式：,大M單純形解法是引入m個人工變量xn+1 , , xn+m將原問題變?yōu)?大M單純形解法中的M為足夠大的正數(shù), 起“懲罰”作用, 以便排除人工變量.,5.2 模糊線性規(guī)劃,

2、普通線性規(guī)劃其約束條件和目標(biāo)函數(shù)都是確定的，但在一些實際問題中，約束條件可能帶有彈性，目標(biāo)函數(shù)可能不是單一的，必須借助模糊集的方法來處理. 模糊線性規(guī)劃是將約束條件和目標(biāo)函數(shù)模糊化，引入隸屬函數(shù)，從而導(dǎo)出一個新的線性規(guī)劃問題，它的最優(yōu)解稱為原問題的模糊最優(yōu)解.,設(shè)普通線性規(guī)劃的標(biāo)準(zhǔn)形式為,若約束條件帶有彈性，即右端常數(shù)bi可能取 (bi di , bi + di ) 內(nèi)的某一個值，這里的di0，它是決策人根據(jù)實際問題選擇的伸縮指標(biāo). 這樣的規(guī)劃稱為模糊線性規(guī)劃.,把約束條件帶有彈性的模糊線性規(guī)劃記為,這里的ti (x) = bi, di 表示當(dāng)di = 0(普通約束)時, ti (x) = b

3、i；當(dāng)di0(模糊約束)時, ti (x) 取(bi - di, bi + di )內(nèi)的某一個值.,下面將約束條件和目標(biāo)函數(shù)模糊化.,將(2)中帶有彈性的約束條件(di0)的隸屬函數(shù)定義為,而將(2)中普通約束條件(di = 0)的隸屬函數(shù)定義為 Ai (x) = 1, ti (x) = bi .,其圖形如右圖,由Ai (x)定義可知，0, 1,設(shè)普通線性規(guī)劃(1)和(3)的最優(yōu)值分別為 f0, f1 , 記 d0 = f 0 - f 1 , 則d00, 它為模糊線性規(guī)劃(2)中目標(biāo)函數(shù)的伸縮指標(biāo)，d0也可由決策人確定.,定義模糊線性規(guī)劃(2)中目標(biāo)函數(shù)的隸屬函數(shù)為,由Gi (x)定義可知，0

4、, 1,Gi (x) t0 (x) + d0 f0,要求模糊線性規(guī)劃(2)的模糊最優(yōu)解x*，則要求使所有約束條件及目標(biāo)函數(shù)的隸屬函數(shù)盡可能達(dá)到最大，即求x* 滿足 Ai (x)及G(x)， 且使達(dá)到最大值,相當(dāng)于求解普通線性規(guī)劃問題,i = 1, 2, , m.,設(shè)普通線性規(guī)劃(4)的最優(yōu)解為x*, , 則模糊線性規(guī)劃(2)的模糊最優(yōu)解為x*, 最優(yōu)值為t0 (x*).,所以，求解模糊線性規(guī)劃(2)相當(dāng)于求解普通線性規(guī)劃(1), (3), (4). 此外，再補(bǔ)充兩點說明： 若要使某個模糊約束條件盡可能滿足，只需將其伸縮指標(biāo)降低直至為0； 若模糊線性規(guī)劃(2)中的目標(biāo)函數(shù)為求最大值，或模糊約束條

5、件為近似大(小)于等于，其相應(yīng)的隸屬函數(shù)可類似地寫出.,例1 解模糊線性規(guī)劃問題(P275)：,多目標(biāo)線性規(guī)劃,在相同的條件下,要求多個目標(biāo)函數(shù)都得到最好的滿足,這便是多目標(biāo)規(guī)劃. 若目標(biāo)函數(shù)和約束條件都是線性的,則為多目標(biāo)線性規(guī)劃.,一般來說,多個目標(biāo)函數(shù)不可能同時達(dá)到其最優(yōu)值,因此只能求使各個目標(biāo)都比較“滿意”的模糊最優(yōu)解.,例2 解多目標(biāo)線性規(guī)劃問題(P280)：,解普通線性規(guī)劃問題：,得最優(yōu)解為x1 = 0, x2 = 2, x3 = 2, 最優(yōu)值為2，此時 f 2 = 8.,解普通線性規(guī)劃問題：,得最優(yōu)解為x1 = 10, x2 = 0, x3 = 0, 最優(yōu)值為20，此時f 1 = 10.,線性規(guī)劃問題的最優(yōu)解為 x1 = 0, x2 = 2, x3 = 2, 最優(yōu)值為2,此時 f 2 = 8. 線性規(guī)劃問題的最優(yōu)解為 x1 = 10, x2 = 0, x3 = 0, 最優(yōu)值為20，此時f 1 = 10.,同時考慮兩個目標(biāo)，合理的方案是使 f 1 2, 10 , f 2 8, 20 , 可取伸縮指標(biāo)分別為 d1 = 10 - 2 = 8, d2 = 20 - 8 = 12. 如果認(rèn)為目標(biāo) f 1更重要,可單獨縮小d1; 如果認(rèn)為目標(biāo) f 2更重要，可單獨縮小d2.,再分別將兩個目標(biāo)函