線性規(guī)劃問題中約束方程系數(shù)敏感性分析方法對比

姜 屏 周倩倩

(紹興文理學(xué)院 土木工程學(xué)院，浙江 紹興312000)

0 引言

參數(shù)敏感性分析是線性規(guī)劃問題研究的一個重要內(nèi)容，在線性規(guī)劃問題中包含目標(biāo)函數(shù)系數(shù)cij、約束條件右端項系數(shù)bj和約束方程系數(shù)aij.其中cij和bj的敏感性分析已經(jīng)形成了比較成熟的計算方法，并已經(jīng)在教科書中有所闡述[1].而在土木工程領(lǐng)域有許多問題需要研究參數(shù)aij的變化對線性規(guī)劃問題的最優(yōu)解和目標(biāo)函數(shù)的影響規(guī)律.比如在泥漿處理中，泥漿的脫水速率和電滲壓力以及泥漿比重之間的關(guān)系[2-3]；軟土地區(qū)深基坑開挖穩(wěn)定性評價時，開挖深度、支護結(jié)構(gòu)類型、地下水位等因素對基坑穩(wěn)定性影響[4-6]；纖維增強水泥土，纖維長度、水泥含量和孔隙比對其無側(cè)限抗壓強度的影響[7]；進行直剪試驗時，巖土材料的剪切強度與豎向應(yīng)力之間的線性關(guān)系等諸多工程問題[8].在研究參數(shù)敏感性時可以將其轉(zhuǎn)化為一般線性規(guī)劃問題，參數(shù)aij的敏感性分析是進行這些工程問題分析的關(guān)鍵.羅世莊推導(dǎo)出了利用當(dāng)前基解和系數(shù)矩陣A的行(或列)增向量直接計算新基解及其檢驗數(shù)的計算公式，并分析了保持最優(yōu)基解不變時的變化范圍[9]，但是沒有分析最優(yōu)解目標(biāo)函數(shù)值的變化規(guī)律.動態(tài)規(guī)劃算法根據(jù)研究對象的特征，可將求解過程劃分為若干階段，通過計算決策變量和狀態(tài)函數(shù)以尋找目標(biāo)最優(yōu)解[10-11].根據(jù)線性規(guī)劃問題的特征，將每一個變量的求解看成是一個階段，目標(biāo)函數(shù)可以作為狀態(tài)函數(shù)來進行求解[12].若能在各階段求解過程中綜合考慮aij的影響，即能實現(xiàn)參數(shù)aij的敏感性分析.本文擬采用一線性規(guī)劃問題(兩個變量)的算例，采用圖解法、單純形法和動態(tài)規(guī)劃算法對參數(shù)aij的敏感性分析方法進行對比分析.

1 參數(shù)aij的敏感性分析

為了研究參數(shù)aij對線性規(guī)劃問題最優(yōu)解和目標(biāo)函數(shù)的影響，在此結(jié)合兩變量線性規(guī)劃問題(式(1))采用圖解法、單純形法和動態(tài)規(guī)劃算法對參數(shù)aij的敏感性進行分析，即對式(1)中參數(shù)a進行敏感性分析.

(1)

1.1 圖解法

針對問題只有兩個變量可采用圖解法進行求解，將目標(biāo)函數(shù)進行變換如式(2).

x2=z-2x1.

(2)

將目標(biāo)函數(shù)和各約束方程確定的直線在坐標(biāo)系中繪出，如圖1.方程(2)確定的直線為ij，那么目標(biāo)函數(shù)值z即為ij在x2上的截距，通過在可行域上平移ij即可得到z的最大值z*，最優(yōu)解為可行域的頂點.

圖1 圖解法計算簡圖

方程ax1+2x2=24在x1、x2上的截距分別為24/a和12，根據(jù)圖解法的基本原理[1]，可分為三種情況討論a對最優(yōu)解和目標(biāo)函數(shù)的影響，具體計算過程如表1.

表1 圖解法計算結(jié)果

a的取值范圍可行域最優(yōu)解z*0

1.2 單純形法

根據(jù)單純形法的基本思路，首先將線性規(guī)劃問題標(biāo)準(zhǔn)化，然后進行單純形法的迭代[1].可得到最終單純形表如表2.

表2 計算所得最終單純形表

cj→21000CB基bx1x2x3x4x50x315051000x424-5a02-a01-a2x1511001cj-zj0-100-2

考慮參數(shù)a的取值對其展開討論:

(1)0

(2)a≥24/5時，在表2的基礎(chǔ)上需采用對偶單純形法繼續(xù)進行迭代，迭代結(jié)果如表3.

表3 a≥24/5對偶單純形法計算結(jié)果

cj→21000CB基bx1x2x3x4x50x3(10a-90)/(2-a)001-5/(2-a)5a/(2-a)1x2(24-5a)/(2-a)0101/(2-a)-a/(2-a)2x1-14/(2-a)100-1/(2-a)2/(2-a)cj-zj0001/(2-a)(a-4)/(2-a)

根據(jù)表3計算結(jié)果發(fā)現(xiàn)，24/5≤a<9時，表3已經(jīng)滿足最優(yōu)解條件，故最優(yōu)解為

(3)a≥9，需采用對偶單純形法對表3繼續(xù)進行迭代，迭代結(jié)果見表4.

表4 a≥9對偶單純形法計算結(jié)果

cj→21000CB基bx1x2x3x4x50x5(2a-18)/a00(2-a)/5a-1/a11x23011/5002x118/a10-2/5a1/a0cj-zj00(4-a)/5a-2/a0

1.3 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法能夠根據(jù)約束條件的特征，以變量個數(shù)n為階段進行動態(tài)分析并求解.根據(jù)算例的特征可將求解過程分成2個階段，考慮到第一個約束條件只對x2進行了約束，在第1階段可不考慮x2，在第2階段可用包含x2的表達式來表示x1，采用逆序解法首先求解x2然后求解x1.可將約束條件右端項用Sn(R1,R2,R3)表示，以fn表示目標(biāo)函數(shù)值.

那么，S1=(15,24-2x2,5-x2)，S2=(15,24,5)

(3)

(4)

n=1時，由(3)可得x1*=min{R2/a,R3}，即

f1*(R1,R2,R3)=2min{R2/a,R3}

(5)

將S1(R1,R2,R3)=(15,24-2x2,5-x2)代入(5)，可得

f1*(15,24-2x2,5-x2)=2min{R2/a,R3}=2min{(24-2x2)/a,5-x2}

(6)

將(6)代入(4)可得

(7)

令24-2x2/a=5-x2，可得

(8)

將0≤x2≤3代入(8)可得24/5≤a≤9.于是可按如下三種情況進行討論：

f2*(15,24,5)=10-x2

(9)

n=2時，x2*=0，f2*(R1,R2,R3)=10此時，x1*=5-0=5，z*=10；

(2)當(dāng)24/5≤a<9時，

(10)

將(10)代入(7)可得

(11)

(12)

2 三種方法對比分析

從以上分析可以得出a不同取值時圖解法、單純形法和動態(tài)規(guī)劃算法都可以對a進行敏感性分析，下面針對a的不同取值范圍對三種方法進行對比分析.

(1)0

表5 0

求解方法對比分析圖解法見圖1,可行域為OBAD,直線ij平移到D點時,目標(biāo)函數(shù)達到最大值,即x1*=5,x2*=0,z*=10單純形法見表2,x1為換入變量,x5為換出變量,cj-zj≤0,目標(biāo)函數(shù)達到最大值,即x1*=5,x2*=0,z*=10動態(tài)規(guī)劃算法min{(24-2x2)/a,5-x2}=5-x2,由(9)可得x1*=5,x2*=0,z*=10

(2)24/5≤a<9，分析結(jié)果見表6

表6 24/5≤a<9時三種方法的對比分析

求解方法對比分析圖解法見圖1,可行域為OBAC1D1,直線ij平移到C1點時,目標(biāo)函數(shù)達到最大值即x1*=14a-2,x2*=5a-24a-2,z*=5a+4a-2單純形法見表3,x2為換入變量,x4為換出變量,bj≥0,目標(biāo)函數(shù)達到最大值即x1*=14a-2,x2*=5a-24a-2,z*=5a+4a-2動態(tài)規(guī)劃算法見(10)和(11)x2=5a-24a-2時,f2*取得最大值,由此可得x1*=14a-2,x2*=5a-24a-2,z*=5a+4a-2

(3)9≤a，分析結(jié)果見表7

表7 9≤a時三種方法的對比分析

求解方法對比分析圖解法見圖1,可行域為OBC2D2,直線ij平移到C2點時,目標(biāo)函數(shù)達到最大值即x1*=18a,x2*=3,z*=3a+36a單純形法見表4,x5為換入變量,x3為換出變量,bj≥0,目標(biāo)函數(shù)達到最大值即x1*=18a,x2*=3,z*=3a+36a動態(tài)規(guī)劃算法見(12)x2=3時,f2*取得最大值,由此可得x1*=18a,x2*=3,z*=3a+36a

綜合表5～7的分析結(jié)果，可看出圖解法、單純形法和動態(tài)規(guī)劃算法具有相同的計算結(jié)果，圖解法比較直觀，只適合兩個變量的情況，單純形法和動態(tài)規(guī)劃算法適用于兩個或兩個以上變量的情況，能為三個或三個以上變量的一般線性規(guī)劃問題參數(shù)aij敏感性分析方法提供參考.

3 結(jié)論

采用圖解法、單純形法和動態(tài)規(guī)劃算法分別分析了一線性規(guī)劃問題(兩變量)參數(shù)aij的敏感性，三種方法計算結(jié)果一致，說明對于兩變量線性規(guī)劃問題此三種方法均能適用，其中圖解法最簡單.單純形法和動態(tài)規(guī)劃算法分析案例aij敏感性的基本思路能為三個或三個以上變量的線性規(guī)劃問題參數(shù)aij敏感性分析方法提供參考.

參考文獻：

[1]胡運權(quán).運籌學(xué)基礎(chǔ)及應(yīng)用[M].6版.北京:高等教育出版社,2014.

[2]SHANG J Q. Electrokinetic Dewatering of Clay Slurries as Engineered Soil Covers[J].Canadian Geotechnical Journal,1997,34(1):78-86.

[3]譚林立,許航,劉珊,等.真空電滲給水污泥脫水機理的研究[J].環(huán)境科技,2017,30(1):1-4.

[4]FU Y, ZHANG X Y , LI Y P, et al. Holding capacity of dynamically installed anchors in normally consolidated clay under inclined loading[J]. Can Geotech J, 2017(54):1257-1271.

[5]ZHANG G,CAO J R, CHENG X S,et al. Experimental study on the artificial recharge of semiconfined aquifers involved in deep excavation[J]. Journal of Hydrology,2018(557):868-877.

[6]應(yīng)宏偉,張金紅,周建,等.基于空心圓柱儀試驗的各向異性軟黏土基坑抗隆起穩(wěn)定分析[J].巖土力學(xué),2016,37(5):1237-1242,1248.

[7]FESFUGATO L,MENGER E,BENEZRA F,et al. Fibre-reinforced cemented soils compressive and tensile strength assessment as a function of filament length[J]. Geotextiles and Geomembranes,2017,45(1):77-82.

[8]CONSOLI N C, SILVALOPES L D J, CONSOLI B S,et al. Mohr-Coulomb failure envelopes of lime-treated soils[J]. Géotechnique,2014,64(2):165-170.

[9]羅世莊.線性規(guī)劃約束方程系數(shù)矩陣的敏感性分析[J].應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)學(xué)報,1997(1):65-70.

[10]PFERSCHY U,SCATAMACCHIA R.Improved Dynamic Programming and Approximation Results for the Knapsack Problem with Setups[J].International Transactions in Operational Research,2018,25(2):667-682.

[11]LOXTON R,LIN Q . Pptimal Fleet Composition Via Dynamic Programming and Golden Section Search[J]. Journal of Industrial and Management Optimization,2011,7(4):875-890.

[12]弗雷德里克·S，希利爾.運籌學(xué)導(dǎo)論[M].10版.北京：清華大學(xué)出版社，2015.