高小妮 孫玉華

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

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

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

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

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

2 預(yù)備知識(shí)

6 結(jié) 論

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

參考文獻(xiàn)

[1] 胡長(zhǎng)英.雙層規(guī)劃理論及其在管理中的應(yīng)用[M].北京：知識(shí)產(chǎn)權(quán)出版社，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] 王廣民，萬(wàn)仲平，王先甲.二（雙）層規(guī)劃綜述[J].數(shù)學(xué)進(jìn)展，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ī)劃的標(biāo)準(zhǔn)型及其求解[J].系統(tǒng)工程，2003，21（3）：79-82.

[7] 郭均鵬，李汶華.區(qū)間線性規(guī)劃的標(biāo)準(zhǔn)型及其最優(yōu)值區(qū)間[J].管理科學(xué)學(xué)報(bào)，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ī)劃問(wèn)題的遺傳算法[J].計(jì)算機(jī)應(yīng)用，2014，34（1）：185-188.

[11] 任愛(ài)紅.基于最近區(qū)間近似和區(qū)間規(guī)劃方法求解一類模糊雙層規(guī)劃問(wèn)題[J].模糊系統(tǒng)與數(shù)學(xué)，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.