模糊線性分式規(guī)劃的標(biāo)準(zhǔn)型及其最優(yōu)值區(qū)間

吳　麗， 孫玉華

(北京科技大學(xué) 數(shù)理學(xué)院， 北京 100083)

0　引　言

分式規(guī)劃在實(shí)際問(wèn)題中有著廣泛的應(yīng)用. 例如， 在經(jīng)濟(jì)管理領(lǐng)域中， 若分母表示總生產(chǎn)成本， 分子表示總產(chǎn)值， 則目標(biāo)函數(shù)表示產(chǎn)出率； 若分母表示投資額， 分子表示總收益， 則目標(biāo)函數(shù)表示盈利率. 此外， 分式規(guī)劃在運(yùn)輸問(wèn)題、 經(jīng)濟(jì)效應(yīng)問(wèn)題、 排隊(duì)論、 聚簇分析等問(wèn)題中也有著廣泛的應(yīng)用. 而且， 在處理雙目標(biāo)規(guī)劃時(shí)， 分式規(guī)劃也是一種很好的選擇， 它不僅可以將雙目標(biāo)問(wèn)題轉(zhuǎn)化為比例目標(biāo)問(wèn)題， 避免了給各個(gè)目標(biāo)直接或者間接地設(shè)置權(quán)重， 還為平衡兩個(gè)目標(biāo)之間的關(guān)系提供了更多有價(jià)值的關(guān)鍵信息[1]. 目前， 分式規(guī)劃方法已經(jīng)在很多領(lǐng)域得到了較多的應(yīng)用. 例如： Lara等[2]開發(fā)了一個(gè)應(yīng)用于農(nóng)業(yè)系統(tǒng)的多目標(biāo)線性分式規(guī)劃(MLFP)模型， 其目標(biāo)是獲得單位用水量下系統(tǒng)利潤(rùn)的最大值. Gomez等[3]將分式規(guī)劃模型應(yīng)用于古巴森林采伐作業(yè)調(diào)度問(wèn)題的研究中， 來(lái)平衡該地區(qū)木材年齡層的分布問(wèn)題. 此外， Zhu等[4-5]在2013年和2014年分別討論了動(dòng)態(tài)隨機(jī)分式規(guī)劃(DSFP)模型和區(qū)間參數(shù)分式規(guī)劃(IMIF-EP)模型， 并應(yīng)用于電力系統(tǒng)規(guī)劃中.

在線性分式規(guī)劃的求解問(wèn)題上， 何文漢等[6]提出了一個(gè)直接處理一般形式線性分式規(guī)劃的算法， 并且證明了算法在有限步后終止于原問(wèn)題的最優(yōu)解. 時(shí)凌[7]討論了線性分式規(guī)劃問(wèn)題的最優(yōu)性條件， 證明了它的局部最優(yōu)解一定是整體最優(yōu)解， 并且局部最優(yōu)解一定在約束條件的基本可行解處達(dá)到. 謝政[8]介紹了線性分式規(guī)劃的原始單純形法， 說(shuō)明了LFP性質(zhì)， 并引進(jìn)了Gilmore-Gomory方法和Charnes-Cooper方法. Rafael Caballero和Monica Hernandez[9]用一種簡(jiǎn)單可行的檢驗(yàn)方法驗(yàn)證了線性分式目標(biāo)規(guī)劃問(wèn)題是否有解， 如果存在解， 怎樣通過(guò)線性規(guī)劃問(wèn)題找到最優(yōu)解. 薛聲家等[10]使用多面集的表示定理， 導(dǎo)出了線性分式規(guī)劃最優(yōu)解集的結(jié)構(gòu)， 給出了確定全部最優(yōu)解的計(jì)算步驟. 郭曉芳等[11]針對(duì)一類上層為線性規(guī)劃、 下層為線性分式規(guī)劃的區(qū)間系數(shù)雙層規(guī)劃問(wèn)題， 提出了一種基于系數(shù)取值區(qū)間搜索的遺傳算法. 王國(guó)棟等[12]針對(duì)一類非光滑多目標(biāo)分式優(yōu)化問(wèn)題， 建立了此類優(yōu)化問(wèn)題有效解的必要條件和充分條件， 并研究了其Mond-Weir對(duì)偶模型. 汪春峰等[13]針對(duì)極大極小分式規(guī)劃問(wèn)題， 給出了一個(gè)新的線性松弛化技巧， 構(gòu)造了一種新的分支定界算法.

目前對(duì)線性分式規(guī)劃的研究一般僅限于確定型問(wèn)題， 然而在實(shí)際問(wèn)題中， 由于數(shù)據(jù)的非精確性與模糊性， 很多信息往往無(wú)法精確得到， 對(duì)于這類更具有柔性與現(xiàn)實(shí)意義的不確定型線性分式規(guī)劃的研究則更有意義. 本文在模糊數(shù)的最佳逼近區(qū)間的基礎(chǔ)上， 提出了一種新的求解模糊線性分式規(guī)劃的方法. 首先， 提出了模糊數(shù)的最好最優(yōu)解、 最差最優(yōu)解及其最優(yōu)值區(qū)間的定義， 將模糊線性分式規(guī)劃問(wèn)題轉(zhuǎn)化為基于模糊數(shù)最佳逼近區(qū)間的區(qū)間線性分式規(guī)劃問(wèn)題. 其次， 將區(qū)間線性分式規(guī)劃問(wèn)題的最優(yōu)值求解轉(zhuǎn)化為求解4個(gè)確定型的線性分式規(guī)劃問(wèn)題， 進(jìn)而利用Gilmore-Gomory算法求解. 最后給出該方法在實(shí)際中的數(shù)值算例， 驗(yàn)證了該方法的有效性與可行性.

1　預(yù)備知識(shí)

定義1[14]設(shè)R為實(shí)數(shù)域， 稱閉區(qū)間[aL,aR]為區(qū)間數(shù)， 其中aL,aR∈R,aL≤aR, 用A來(lái)表示A=[aL,aR],aL,aR分別稱為A的左端點(diǎn)和右端點(diǎn), 當(dāng)aL=aR=a時(shí)， 區(qū)間數(shù)A就退化為實(shí)數(shù)a.

定義2[14]對(duì)于兩個(gè)區(qū)間數(shù)A=[aL,aR],B=[bL,bR],k為確定數(shù)， 定義

A+B=[aL+bL,aR+bR],

A-B=[aL-bR,aR-bL],

定義3[15]對(duì)區(qū)間數(shù)A=[aL,aR],B=[bL,bR], 記len(A)=aR-aL,len(B)=bR-bL, 則稱

P(A≤B)=

為A≤B的可能度； 考慮約束條件Ax≤B， 則稱λ=P(Ax≤B) 為約束條件下的滿意水平.

定義4[16]設(shè)U為論域， 則U上的一個(gè)模糊集合A由U上的一個(gè)實(shí)值函數(shù)

μA∶U→[0,1],

u|μA(u)

來(lái)表示. 對(duì)于u∈U， 函數(shù)值μA(u)稱為u對(duì)于A的隸屬度， 而μA稱為A的隸屬函數(shù). 當(dāng)論域U為無(wú)限集時(shí)，U上的模糊集合A可表示為

考慮如下形式的線性分式規(guī)劃(LFP):

s.t.Ax=b,x≥0,

其中，A為m×n矩陣,p,q,x∈En,b∈E1. 不失一般性， 可設(shè)rank(A)=m≤n. 記(LFP)的可行集為S.

給出Gilmore-Gomory算法[18]：

Step 1給定一個(gè)初始可行基B， 寫出相應(yīng)的單純形表；

Step 2計(jì)算r(xN)， 如果r(xN)≥0， 則關(guān)于B的基本可行解x*為最優(yōu)解， 停止計(jì)算； 否則， 轉(zhuǎn)Step 3；

Step 3確定進(jìn)基變量. 令

-rk=max{-rj|rj<0,j∈N}

則xk以為進(jìn)基變量；

Step 4確定離基變量. 由

確定xr為離基變量；

2　模糊線性分式規(guī)劃模型的建立

本文定義如下一種標(biāo)準(zhǔn)類型的模糊線性分式規(guī)劃(FLFP)：

xj≥0,j=1,2,…,n.

對(duì)于求解模糊規(guī)劃問(wèn)題， 一般做法是利用模糊隸屬函數(shù)的α-截集， 將模糊數(shù)轉(zhuǎn)化為區(qū)間數(shù)， 從而求解區(qū)間規(guī)劃. 然而， 由于α取值不同， 結(jié)果往往也不同， 為此需要考慮最優(yōu)的解. 基于文獻(xiàn)[17]中模糊數(shù)最佳逼近區(qū)間的定義， 首先把模糊線性分式規(guī)劃轉(zhuǎn)化為如下區(qū)間線性分式規(guī)劃(ILFP)：

xj≥0,j=1,2,…,n,

假設(shè)(ILFP)目標(biāo)函數(shù)的分母大于零， 否則可將目標(biāo)函數(shù)的分子分母同時(shí)乘以-1.

由引理1， 在約束條件滿意度為λi的情況下， (ILFP)問(wèn)題可以轉(zhuǎn)化為

xj≥0,j=1,2,…,n.

3　模糊線性分式規(guī)劃問(wèn)題的求解

i=1,2,…,m,xj≥0,j=1,2,…,n.

下面給出模糊線性分式規(guī)劃(FLFP)的最優(yōu)值區(qū)間定義以及最好最優(yōu)值、 最差最優(yōu)值的求解．

定義10設(shè)(FLFP)問(wèn)題的最優(yōu)值集合為S， 稱ZL=min{Z|Z∈S}為(FLFP)問(wèn)題的最好最優(yōu)值； 稱ZR=max{Z|Z∈S}為(FLFP)問(wèn)題的最差最優(yōu)值； 稱[ZL,ZR]為(FLFP)問(wèn)題的最優(yōu)值區(qū)間.

定理1(FLFP)的最好最優(yōu)值在(ILFP)的目標(biāo)函數(shù)分子取左端點(diǎn)， 分母取左端點(diǎn)或右端點(diǎn)處達(dá)到.

由定理1， (FLFP)的最好最優(yōu)值可以轉(zhuǎn)化為求解如下兩個(gè)確定型的線性分式規(guī)劃

j=1,2,…,n,(1)

j=1,2,…,n.(2)

將式(1)和式(2)中的不等式約束通過(guò)增加松弛變量使其變?yōu)榈仁剑?再利用修改的凸單純形法分別進(jìn)行求解， 取較小的最優(yōu)值作為(FLFP)的最好最優(yōu)值.

定理2(FLFP)的最差最優(yōu)值在(ILFP)的目標(biāo)函數(shù)分子取右端點(diǎn)， 分母取左端點(diǎn)或右端點(diǎn)處達(dá)到.

證明與定理1類似,此處略.

由定理2， (FLFP)的最差最優(yōu)值可以轉(zhuǎn)化為求解如下兩個(gè)確定型的線性分式規(guī)劃

j=1,2,…,n.(3)

j=1,2,…,n.(4)

將式(3)和式(4)中的不等式約束通過(guò)增加松弛變量使其變?yōu)榈仁剑?再利用修改的凸單純形法分別進(jìn)行求解， 取較大的最優(yōu)值作為(FLFP)的最差最優(yōu)值.

4　數(shù)值算例

下面通過(guò)數(shù)值算例檢驗(yàn)?zāi)Ｐ秃退惴ǖ挠行耘c可行性.

如下是一個(gè)實(shí)際問(wèn)題中的簡(jiǎn)化模型

xi≥0,i=1,2,3,(5)

其中， 模糊數(shù)

s.t. [5,6.25]x1+[2.2,3.2]x2+

[2.6,3.1]x3<0.8[9.4,12.4],

[8.6,10.6]x1+[2.3,3.3]x2+[4.5,9.5]x3≤

0.7[9.7,10.7],xi≥0,i=1,2,3.(6)

1) 根據(jù)定理1， 求解式(5)的最好最優(yōu)值可以轉(zhuǎn)化為求解如下兩個(gè)確定型線性分式規(guī)劃

用Gilmore-Gomory算法[18]解式(7)， 得最優(yōu)單純形表如表 1 所示.

表 1　最優(yōu)單純形表Tab.1　The best simplex table

2) 根據(jù)定理2， 求解式(5)的最差最優(yōu)值可以轉(zhuǎn)化為求解如下兩個(gè)確定型線性分式規(guī)劃

5　結(jié)　論

線性分式規(guī)劃問(wèn)題在現(xiàn)實(shí)生活中具有廣泛的應(yīng)用， 特別是在經(jīng)濟(jì)問(wèn)題， 運(yùn)輸問(wèn)題以及排隊(duì)問(wèn)題上， 而具有柔性的模糊線性分式規(guī)劃則具有更為廣泛的現(xiàn)實(shí)意義. 本文定義了模糊線性分式規(guī)劃的標(biāo)準(zhǔn)型及其最優(yōu)值區(qū)間， 并給出了一種新的求解模糊線性分式規(guī)劃的方法. 然而對(duì)于模糊線性分式規(guī)劃的其他求解方法以及模糊非線性分式規(guī)劃的求解問(wèn)題， 還有待進(jìn)一步探討.