區(qū)間線性規(guī)劃的最優(yōu)解與強(qiáng)最優(yōu)解

(杭州電子科技大學(xué)運(yùn)籌與控制研究所，浙江 杭州310018)

0 引 言

在實(shí)際的決策過程中，線性規(guī)劃問題中的參數(shù)通常不是固定的，即為區(qū)間線性規(guī)劃問題。如何確定區(qū)間規(guī)劃問題的最優(yōu)解在理論上和實(shí)踐中都具有十分重要的意義。文獻(xiàn)1 對(duì)區(qū)間規(guī)劃的應(yīng)用進(jìn)行了討論，文獻(xiàn)2，3 提出了區(qū)間規(guī)劃的理論研究，文獻(xiàn)4 中給出了比文獻(xiàn)6 中更為一般的模型，通過引入兩個(gè)關(guān)鍵概念:最優(yōu)解和強(qiáng)最優(yōu)解，并給出了最優(yōu)解或強(qiáng)最優(yōu)解的充要條件，但其中的理論存在一定的缺陷，文獻(xiàn)5 對(duì)區(qū)間規(guī)劃理論進(jìn)行了系統(tǒng)分析，文獻(xiàn)7 討論了如何解MOLP 問題，文獻(xiàn)8研究了多目標(biāo)規(guī)劃問題，文獻(xiàn)10 運(yùn)用對(duì)偶理論討論對(duì)稱型區(qū)間線性規(guī)劃的最優(yōu)解與最優(yōu)值的關(guān)系。目前對(duì)于區(qū)間規(guī)劃問題的最優(yōu)化條件的討論的并不多，還需要進(jìn)行深入討論。本文在文獻(xiàn)4所提出的理論的基礎(chǔ)之上，得出了區(qū)間線性規(guī)劃的最優(yōu)解與強(qiáng)最優(yōu)解的充要條件。最后，通過一個(gè)簡(jiǎn)單的例子說明相關(guān)理論的可行性。

1 區(qū)間線性規(guī)劃問題的最優(yōu)解與強(qiáng)最優(yōu)解的定義

引理1 檢驗(yàn)區(qū)間線性規(guī)劃問題的最優(yōu)解與強(qiáng)最優(yōu)解是NP 難的[4]。

+時(shí)，問題將可以通過下面給出的方法得到較好的解決，并給出最優(yōu)解與強(qiáng)最優(yōu)解的充要條件。

2 區(qū)間線性規(guī)劃問題的最優(yōu)解與強(qiáng)最優(yōu)解的充要條件

引理3 設(shè)u∈Rk是正權(quán)值向量，則y∈X是有效的當(dāng)且僅當(dāng)存在u≥使得y是問題maxuΤQx s.t.x∈X的解，其中Q∈Rk×n[7]。

命題1 假設(shè)x 非負(fù)，即p?Rn+，假設(shè)是MOLP 問題的Pareto 最優(yōu)解，則是區(qū)間線性規(guī)劃問題的最優(yōu)解。

由引理2，3可知命題1 顯然成立，且對(duì)任意象限都成立，本文只考慮p?Rn+的情況。

定理1 假設(shè)p =Rn+，∈p是區(qū)間線性規(guī)劃問題的最優(yōu)解當(dāng)且僅當(dāng)存在(y+，y-，c)，使得(，y+，y-，c)滿足下列不等式:

證明 x∈Rn+是區(qū)間線性規(guī)劃問題的最優(yōu)解當(dāng)且僅當(dāng)存在一個(gè)向量且，而由引理2的證明知x∈X 當(dāng)且僅當(dāng)滿足式1。因此由線性規(guī)劃理論中的KKT條件知當(dāng)且僅當(dāng)存在(y+，y-，c)，使得，y+，y-，c)滿足式1—4。

3 算例

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

本文將研究區(qū)間線性規(guī)劃問題的最優(yōu)解轉(zhuǎn)換為研究MOLP 問題的最優(yōu)解，而MOLP 問題的最優(yōu)解或強(qiáng)最優(yōu)解問題可以用KKT條件加以研究，從而得到了區(qū)間線性規(guī)劃問題的最優(yōu)解或強(qiáng)最優(yōu)解的充要條件。然而，本文討論的是弱可行的情況下討論某個(gè)解是區(qū)間線性規(guī)劃問題的最優(yōu)解或強(qiáng)最優(yōu)解的充要條件，在強(qiáng)可行的情況下如何得出最優(yōu)解或強(qiáng)最優(yōu)解的充要條件，還值得深入研究。

[1]Wei Li.Learning from Data by Interval Linear Programming[J].Key Engineering Materials，2010，43(9):710-714.

[2]Wei Li，Xiaoli Tian.Fault Detection in Discrete Dynamic Systems with Uncertainty Based on Interval Optimization[J].Mathematical Modelling and Analysis，2011，16(4):549-557.

[3]Wei Li，Xiaoli Tian.Numerical solution method for general interval quadratic programming[J].Applied Mathematics and Computation，2008，20(2):589-595.

[4]Soleimani-damaneh M，Jahanshahlo G R.Optimal and strongly optimal solutions for linear programming models with variable parameters[J].Applied Mathematics Letters，2007，20(10):1 052-1 056.

[5]Fiedler M，nedoma J，ramík J，etal.linear optimization problems with inexact data[M].New York:Springer，2006:35-74.

[6]Serafini P.Linear programming with variable matrix entries[J].Oper Res Lett，2005，33 (2):165-170.

[7]Jahanshahloo G R，F(xiàn)oroughi A A.Finding a weights-restricted efficient (extreme)point and using it for solving MOLP problems[J].Appl Math Comput，2004，15(1):203-211.

[8]Tu T V.Optimization over the efficient set of a parametric multiple objective linear programming problem[J].European J Oper Res，2000，22(3):570-583.

[9]Bazaraa M S，Jarvis J J，Sherali H D.Linear Programming and Network Flows[M].Canada:John Wiley and Sons，1990:68-69.

[10]李婭，李煒.對(duì)稱型區(qū)間線性規(guī)劃的對(duì)偶理論[J].杭州電子科技大學(xué)學(xué)報(bào)，2011，31(3):78-81.