含區(qū)間右端線性規(guī)劃的弱最優(yōu)性

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州310018)

0 引 言

在實(shí)際問(wèn)題中，線性規(guī)劃問(wèn)題中的系數(shù)一般是不確定的，可轉(zhuǎn)化為區(qū)間線性規(guī)劃問(wèn)題來(lái)研究。如何確定區(qū)間線性規(guī)劃問(wèn)題的弱可行解是否為弱最優(yōu)解，在理論上和實(shí)踐上都有十分重要的意義，文獻(xiàn)[1-5]都對(duì)該問(wèn)題進(jìn)行了研究。本文主要討論區(qū)間右端值線性規(guī)劃的一般約束問(wèn)題，并得出了檢驗(yàn)其弱可行解是否為弱最優(yōu)解的充要條件。

1 準(zhǔn)備知識(shí)

本文將m×n 實(shí)矩陣全體表示為Rm×n，將m×n 區(qū)間矩陣的全體表示為IRm×n。設(shè)m×n 實(shí)矩陣A，m×n 區(qū)間矩陣其中m 維實(shí)向量和區(qū)間向量可以分別看作m×1實(shí)矩陣和m×1 區(qū)間矩陣[5]?？紤]區(qū)間線性規(guī)劃問(wèn)題:

式中，A∈IRm×n，b∈IRm，c∈IRn且c是區(qū)間行向量。

令A(yù)∈A，b∈b，c∈c，則線性規(guī)劃問(wèn)題為:

稱線性規(guī)劃式(2)是區(qū)間線性規(guī)劃式(1)的一種情況。

為了方便下面的討論，給出弱可行解和弱最優(yōu)解的定義。

定義1 若存在A∈A，b∈b，使得向量x 滿足線性規(guī)劃式(2)的約束條件，則稱x是區(qū)間線性規(guī)劃式(1)的弱可行解。

定義2 若存在A∈A，b∈b，c∈c，使得向量x是線性規(guī)劃式(2)的最優(yōu)解，則稱x是區(qū)間線性規(guī)劃式(1)的弱最優(yōu)解。

引入?yún)^(qū)間右端線性規(guī)劃問(wèn)題的一般約束形式為:

式中，Aij∈Rmi×nj是mi×nj矩陣，bi∈IRmi是mi維區(qū)間列向量，cj∈Rnj是nj維行向量，xj∈Rnj是nj維列向量，i=1，2，3;j=1，2 且m1+m2+m3=m，n1+n2=n。

2 主要結(jié)論

將線性規(guī)劃的KT條件推廣到一般約束形式的線性規(guī)劃，得到下述弱最優(yōu)解判定方法。

情況1 集合F1，F(xiàn)2都為空集。

1)當(dāng)F1=φ時(shí)，令則是的解;

3)當(dāng)F2=φ時(shí)，令則是的解;

情況2 集合F1為非空集合，F(xiàn)2為空集。

F2=φ 已在情況1 中討論。下面討論F1≠φ，令則b1。當(dāng)k∈F1時(shí)，當(dāng)k?F1時(shí)所以是右式的解:由情況1 分析知，可找到滿足一般約束形式線性規(guī)劃的KT條件，并證得)即為式(3)的一個(gè)弱最優(yōu)解。

情況3 集合F1為空集，F(xiàn)2為非空集合。

F1=φ 已在情況1 中討論，F(xiàn)2≠φ時(shí)，與情況2 中對(duì)F1≠φ的討論類似，不再詳述。情況4 集合F1，F(xiàn)2都非空。

此情形是第2、第3種情況的兩種子情況，綜合可得到結(jié)果，不再詳述。

因?yàn)槭?4)是線性的，這種判定弱最優(yōu)解的方法是多項(xiàng)式時(shí)間算法，非常具有可行性。

3 結(jié)束語(yǔ)

本文通過(guò)求解一個(gè)線性系統(tǒng)，給出了區(qū)間右端值線性規(guī)劃的一般約束形式的可行解的弱最優(yōu)性的判定方法。在研究區(qū)間右端規(guī)劃解的弱最優(yōu)性問(wèn)題時(shí)，都可轉(zhuǎn)化成這種約束形式利用上述定理來(lái)求解。然而，怎樣去判定更一般的區(qū)間線性規(guī)劃的弱解是否為最優(yōu)解，目前還是一個(gè)比較困難的問(wèn)題。

[1]Gabrel V，Murat C，Remli N.Linear programming with interval right hand side[J].International Transactions in Operational Research，2010，17(3):397-408.

[2]Li W，Luo J，Wang Q，et al.Checking weak optimality of the solution to linear programming with interval right-hand side[J].Optimization Letters，2013:1-13.

[3]李煒.線性優(yōu)化及其擴(kuò)展[M].北京:國(guó)防工業(yè)出版社，2011:200-232.

[4]Hladik M.Optimal value range in interval linear programming[J]，F(xiàn)uzzy Optimization and Decision Making.2009，(8):283-294.

[5]Fiedler M，Nedoma J，Ramik J，et al.Linear optimization problems with inexact data[M]，New York:Springer，2006:35-92.