區(qū)間二次雙層規(guī)劃的最好最優(yōu)解

高小妮 孫玉華

摘 要 雙層規(guī)劃問題是一類具有遞階結構的優(yōu)化問題.在不確定的雙層規(guī)劃優(yōu)化問題中，目標函數(shù)系數(shù)或約束條件系數(shù)為區(qū)間數(shù)的雙層規(guī)劃模型在實際問題中有著廣泛的應用.在二次-線性雙層規(guī)劃模型的基礎上，提出了上、下層目標函數(shù)以及約束條件系數(shù)均具有區(qū)間系數(shù)的二次-線性雙層規(guī)劃模型，給出了求解其最好最優(yōu)解的方法.首先，通過選取約束條件中不同的基矩陣，求得區(qū)間二次-線性雙層規(guī)劃的可能最優(yōu)解.再比較求得的全部可能最優(yōu)解，便可得到區(qū)間二次-線性雙層規(guī)劃模型的最好最優(yōu)解.最后給出數(shù)值算例驗證該方法的有效性.

關鍵詞 運籌學與控制論;區(qū)間二次-線性雙層規(guī)劃;基矩陣;最好最優(yōu)解

中圖分類號 O221文獻標識碼 A

Abstract Bi-level programming problem is a class of optimization problems with hierarchical structure.The uncertain bi-level programming optimization problems，in which the coefficients of the objective function or the coefficients of the constraint conditions are interval coefficients，has been widely used in the actual problem.For a kind of quadratic-linear bi-level programming problems with interval coefficients in the objective function and constraint conditions，an algorithm was proposed to solve its best optimal solution on the basis of quadratic-linear bi-level programming problems.First，by choosing the different basis matrix of constraint，we can solve the possible optimal solution of quadratic-linear bi-level programming problems with interval coefficients.Second，compared with all possible optimal solution，we obtain the best optimal solution of the model.Finally，numerical examples are given to demonstrate the effectiveness of the proposed method.

Key words operational research;quadratic-linear bi-level programming with interval;basis matrix;best optimal solution

1 引 言

確定性雙層規(guī)劃問題已經廣泛的應用到經濟管理、物流領域、交通管理以及其他領域，它是一類具有遞階結構的優(yōu)化問題。非線性雙層規(guī)劃問題在工程中應用比較廣泛，其中二次雙層規(guī)劃問題是非線性雙層規(guī)劃問題中最特殊的一種數(shù)學規(guī)劃。目前，求解二次雙層規(guī)劃的主要算法有分支定界法、罰函數(shù)法、信賴域算法和遺傳算法。胡（2012）[1]討論了雙層規(guī)劃的基本理論、算法及其在實際問題中的應用。nal（1993）[2]提出用改進的單純形法求解線性雙層規(guī)劃，并指出互補旋轉算法可以看成是改進的單純形法。王等人（2007）[3]總結了二層規(guī)劃的一些性質和算法。Strekalovsky等人（2010）[4]提出了求解二次-線性雙層規(guī)劃的局部搜索方法，利用K-T條件將雙層規(guī)劃轉化為單層規(guī)劃，再通過局部搜索方法得到最優(yōu)解。Ren等人（2013）[5]提出了基于正態(tài)分布的分布估計算法，利用單純形法最優(yōu)性條件將雙層規(guī)劃轉化為單層規(guī)劃，求解了上層目標函數(shù)為二次的雙層規(guī)劃問題，提高了遺傳算法的效率。

雖然確定型雙層規(guī)劃問題得到了解決，但在實際生活中不確定性因素出現(xiàn)的幾率越來越大，所以眾多學者開始對區(qū)間規(guī)劃模型做出了研究。區(qū)間規(guī)劃是解決不確定規(guī)劃的重要方法，眾多學者已經對區(qū)間線性規(guī)劃模型做出了研究。郭等人（2003）[6]定義了區(qū)間線性規(guī)劃的標準型。郭等人（2004）[7]進一步給出了區(qū)間線性規(guī)劃最好最優(yōu)值和最差最優(yōu)值的定義，進而確定了區(qū)間線性規(guī)劃的最優(yōu)值區(qū)間。王等人（2008）[8]提出了用K次最好法求解了上、下層目標函數(shù)均帶區(qū)間系數(shù)的線性雙層規(guī)劃的最好最優(yōu)解，并分析了下層目標函數(shù)的系數(shù)的變動對最好最優(yōu)解的影響。Li等人（2013）[9]利用單純形法的最優(yōu)性條件，設計了遺傳算法，其中把約束域中下層函數(shù)的系數(shù)列向量作為初始種群，進行交叉和變異，進而求得區(qū)間線性雙層規(guī)劃最優(yōu)解。樊等人（2014）[10]提出了用雙適應度函數(shù)評估遺傳算法求解區(qū)間線性雙層規(guī)劃的算法，在一次運算中獲得最好最優(yōu)解和最差最優(yōu)解。任愛紅（2015）[11]利用最近區(qū)間近似將一類雙層模糊規(guī)劃問題轉化為區(qū)間雙層規(guī)劃問題，求解了模糊雙層規(guī)劃問題。對于區(qū)間二次規(guī)劃的研究，Liu等人（2007）[12]討論了一次項系數(shù)具有區(qū)間系數(shù)的二次規(guī)劃模型，利用對偶定理將區(qū)間規(guī)劃轉化為確定性規(guī)劃問題，并給出了數(shù)值解法求解了模型的上界和下界。Li等人（2008）[13]在Liu的基礎上提出了更具一般形式的區(qū)間二次規(guī)劃模型，設計算法求解了模型的上界和下界。Li等人（2016）[14]提出了含有等式和不等式約束的區(qū)間二次規(guī)劃模型，并提出了一種檢驗零對偶間隙簡單有效的方法，最后利用該方法求得了區(qū)間二次規(guī)劃模型的精確上界.

在實際問題中，隨著遞階決策過程的復雜化，例如經濟中價格的變動，物流中配送成本的變化，生產商實際需求量的變動，都會引起收益的變化，雙層規(guī)劃中的目標函數(shù)并非都是線性函數(shù)，單純的區(qū)間線性雙層規(guī)劃模型和單層區(qū)間二次規(guī)劃模型已經不能很好的解決這些問題，所以有必要研究區(qū)間非線性雙層規(guī)劃模型。目前，對區(qū)間二次-線性雙層規(guī)劃做出的研究還很少。在線性雙層規(guī)劃的基礎上，提出一類上、下層目標函數(shù)系數(shù)以及約束條件系數(shù)均帶區(qū)間數(shù)的二次-線性雙層規(guī)劃模型。首先給出區(qū)間二次-線性雙層規(guī)劃模型，并提出最好最優(yōu)解的概念;然后借鑒區(qū)間線性雙層規(guī)劃求解最好最優(yōu)解的方法和單純形法的最優(yōu)性條件，設計了求解區(qū)間二次-線性雙層規(guī)劃最好最優(yōu)解的算法;最后給出數(shù)值算例，驗證了模型和算法的有效性.

2 預備知識

6 結 論

在經濟學和管理學中，二次雙層規(guī)劃模型的系數(shù)不能給出確定值的情況很普遍，從而采用區(qū)間數(shù)來估計系數(shù)的變化范圍。物流網絡、證券投資組合和資源配置分別是一個動態(tài)系統(tǒng)，是在不確定環(huán)境中發(fā)生的。提出的模型和算法，可以應用到物流網絡中，解決物流中總成本最小和用戶費用最低的非線性問題;也可以推廣到證券投資市場中，使得投資組合中預期收益率提高和風險率降低;也可以進一步應用到水資源等配置問題中，解決調控水價的管理者和各用水部門利益最優(yōu)問題，等等。在實際問題中，當涉及到不確定二次-線性雙層決策時，上述的模型和算法均可應用到實際問題中，解決雙層決策優(yōu)化問題。區(qū)間二次-線性雙層規(guī)劃模型和算法的提出，打破了經濟學和管理學中只用不確定線性雙層規(guī)劃模型解決實際問題的局限性，推動了非線性不確定雙層規(guī)劃的發(fā)展。但是，區(qū)間非線性雙層規(guī)劃的研究成果還很少，有待更多的學者在此領域做出更深入的研究.

參考文獻

[1] 胡長英.雙層規(guī)劃理論及其在管理中的應用[M].北京：知識產權出版社，2012.

[2] nal H.A modified simplex approach for solving bi-level linear programming problems[J].European Journal of Operational Research，1993（67）：126-135.

[3] 王廣民，萬仲平，王先甲.二（雙）層規(guī)劃綜述[J].數(shù)學進展，2007，36（5）：513-529.

[4] Strekalovsky A S，Orlov A V，Malyshev A V.Local search in a quadratic-linear bi-level programming problem[J].Numerical Analysis and Applications，2010，3（1）：59-70.

[5] Aihong REN，Yuping WANG，F(xiàn)ei JIA.A hybrid estimation of distribution algorithm and Nelder-Mead simplex method for solving a class of nonlinear bi-level programming problems[J].Journal of Applied Mathematics，2013（13）：1-10.

[6] 郭均鵬，吳育華.區(qū)間線性規(guī)劃的標準型及其求解[J].系統(tǒng)工程，2003，21（3）：79-82.

[7] 郭均鵬，李汶華.區(qū)間線性規(guī)劃的標準型及其最優(yōu)值區(qū)間[J].管理科學學報，2004，7（3）：59-63.

[8] 王建忠，杜綱.區(qū)間線性雙層規(guī)劃的最好最優(yōu)解[J].系統(tǒng)工程，2009，27（4）：100-103.

[9] Hecheng LI，F(xiàn)ang LEI.An efficient genetic algorithm for interval linear bi-level programming problems[J].Ninth International Conference on Computational Intelligence and Security，2013，41-44.

[10] 樊洋洋，李和成.一類區(qū)間系數(shù)線性雙層規(guī)劃問題的遺傳算法[J].計算機應用，2014，34（1）：185-188.

[11] 任愛紅.基于最近區(qū)間近似和區(qū)間規(guī)劃方法求解一類模糊雙層規(guī)劃問題[J].模糊系統(tǒng)與數(shù)學，2015，29（4）：139-145.

[12] ST LIU，RT WANG.A numerical solution method to interval quadratic programming[J].Applied Mathematics and Computation，2007（189）：1274-1281.

[13] W LI，X TIAN.Numerical solution method for general interval quadratic programming[J].Appl.Math.Comput，2008（202）：589-595.

[14] Wei LI，Mengxue XIA，Haohao LI.Some results on the upper bound of optimal values in interval convex quadratic programming[J].Journal of Computational and Applied Mathematics，2016（302）：38-49.