吳　麗， 孫玉華

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

0　引　言

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

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

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

1　預備知識

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

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

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

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

定義3[15]對區(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]設U為論域， 則U上的一個模糊集合A由U上的一個實值函數(shù)

μA∶U→[0,1],

u|μA(u)

來表示. 對于u∈U， 函數(shù)值μA(u)稱為u對于A的隸屬度， 而μA稱為A的隸屬函數(shù). 當論域U為無限集時，U上的模糊集合A可表示為

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

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

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

給出Gilmore-Gomory算法[18]：

Step 1給定一個初始可行基B， 寫出相應的單純形表；

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

Step 3確定進基變量. 令

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

則xk以為進基變量；

Step 4確定離基變量. 由

確定xr為離基變量；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　數(shù)值算例

下面通過數(shù)值算例檢驗模型和算法的有效性與可行性.

如下是一個實際問題中的簡化模型

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)化為求解如下兩個確定型線性分式規(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)化為求解如下兩個確定型線性分式規(guī)劃

5　結　論

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