雙層規(guī)劃

1、1雙層規(guī)劃雙層規(guī)劃一、一、雙層規(guī)劃的定義及背景雙層規(guī)劃的定義及背景雙層規(guī)劃（BilevelProgrammingProblem，簡稱BLPP）是一種具有二層遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，上層問題和下層問題都有各自的決策變量、約束條件和目標(biāo)函數(shù)。雙層系統(tǒng)優(yōu)化研究的是具有兩個(gè)層次系統(tǒng)的規(guī)劃與管理問題。上層決策者只是通過自己的決策去指導(dǎo)下層決策者，并不直接干涉下層的決策；而下層決策者只需要把上層的決策作為參數(shù)，他可以在自己的可能范圍內(nèi)自由決策。這種

2、決策機(jī)制使得上層決策者在選擇策略以優(yōu)化自己的目標(biāo)達(dá)成時(shí)，必須考慮到下層決策者可能采取的策略對自己的不利影響。首先提出層次規(guī)劃模型的是H.VStackelberg，上世紀(jì)50年代，為了更好的描述現(xiàn)實(shí)中的經(jīng)濟(jì)模式，H.VStackelberg在他的專著中首次提出了層次規(guī)劃這種概念，雖然多層規(guī)劃與之有共同點(diǎn)，但各層決策者依次做出決策，并且各自的策略集也不必再是分離的。20世紀(jì)60年代，Dantaig和Wolfe提出了大規(guī)模線性規(guī)劃的分解算法，

3、承認(rèn)有一個(gè)核心決策者，它的目標(biāo)高于一切，但與多層規(guī)劃有很大區(qū)別，多層規(guī)劃承認(rèn)有最高決策者，大不是絕對的，他允許下層決策者有各自不同的利益。20世紀(jì)70年代發(fā)展起來的多目標(biāo)規(guī)劃通常尋求的是一個(gè)決策者的互相矛盾的多個(gè)目標(biāo)額折衷解，而多層規(guī)劃強(qiáng)調(diào)下層決策對上層目標(biāo)的影響，并且多層規(guī)劃問題通常不能逐層獨(dú)立求解。上世紀(jì)70年代以來，在解決實(shí)際問題的過程中，人們才逐漸形成多層規(guī)劃的概念和方法。多層規(guī)劃（MultilevelProgramming）一

4、詞是Cler和Nton在奶制品工業(yè)模型和墨西哥農(nóng)業(yè)模型的研究報(bào)告中首先提出來的。上世紀(jì)70年代，人們對多目標(biāo)規(guī)劃進(jìn)行了深入的研究，也形成了一些求解多目標(biāo)規(guī)劃的有效方法，如分層優(yōu)化技術(shù)，這種技術(shù)也可以用來求解層次問題，但這種技術(shù)建立在下層的決策不影響上層的目標(biāo)基礎(chǔ)上，而多層規(guī)劃正是強(qiáng)調(diào)下層決策對上層目標(biāo)的影響。因此多層規(guī)劃同城不同于多目標(biāo)規(guī)劃。在過去的幾十年中，多層規(guī)劃的理論、方法及應(yīng)用都有了很大的發(fā)展，并且已經(jīng)成為規(guī)劃論中的一個(gè)新的重要

5、分支，而在多多層規(guī)劃的研究中，雙層規(guī)劃是一個(gè)重要的研究對象，這是因?yàn)殡p層規(guī)劃是多層規(guī)劃中的一個(gè)特例，同時(shí)多層規(guī)劃可以看作是一系列的雙層規(guī)劃的復(fù)合。雙層規(guī)劃是在研究非平衡經(jīng)濟(jì)市場競爭時(shí)首先提出的，1973年，在Bracken和Mcgill的文章中，出現(xiàn)了雙層規(guī)劃的數(shù)學(xué)模型。1977年，在Cler和Nton的科學(xué)報(bào)告中正式出現(xiàn)了雙層規(guī)劃和多層規(guī)劃名詞。雙層規(guī)劃研究的是兩個(gè)各具目標(biāo)函數(shù)的決策者之間按有序的和非合作方式進(jìn)行的相互作用，上層決策者

6、優(yōu)先做出決策，下層決策者在上層決策信息下按自己的利益做出反應(yīng)，由于一方的行為影響另一方策略的選擇和目標(biāo)的實(shí)現(xiàn)，并且任何一方又不能完全控制另一方的選擇行為，因此上層決策者要根據(jù)下層的反應(yīng)做出符合自身利益的最終決策。根據(jù)上述定義，雙層規(guī)劃具有以下一些主要特點(diǎn)：（1）層次性。研究的系統(tǒng)是分層管理的，各層決策者依次做出決策，下層服從上層。（2）獨(dú)立性。各層決策者各自控制一部分決策變量，以優(yōu)化各自的目標(biāo)。（3）沖突性。各層決策者有各自不同的目標(biāo)，

7、且這些目標(biāo)往往是相互矛盾的。（4）優(yōu)先性。上層決策者優(yōu)先做出決策，而下層決策者在優(yōu)化自己的目標(biāo)而選擇決策3線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對于某些具體問題，常要求解答必須是整數(shù)。例如，所求解是機(jī)器的臺(tái)數(shù)，工作的人數(shù)或裝貨的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只要把已得的非整數(shù)解舍入化整就可以了。實(shí)際上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應(yīng)該有特殊的方法來求解整數(shù)規(guī)劃。在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱為純整

8、數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃。（4）非線性雙層規(guī)劃雙層規(guī)劃（NonlinearBilevelProgramming，簡稱NLBP）的一般形式為：yXxyxF)(min?（a）解其中yyxGts0)(..?（b）yyxf)(min（c)0)(..?yxgts（d）其中，，。則上層變量，下層變量。同樣，函數(shù)1nxR?2nyR?1nxR?2nyR?、分別是上層、下層目標(biāo)函數(shù)，而向量值函數(shù)12:nnFRRR??12:n

9、nfRRR??、分別是上層、下層約束條件。上層約束條件中121:nnmGRRR??122:nnmgRRR??包含著來自兩層變量（與用表示的約束不同）是一個(gè)特殊的角色，因?yàn)檫@些條件不能約X束下層決策者，它們不直接的被強(qiáng)制執(zhí)行。如果上下層目標(biāo)函數(shù)、至少有一個(gè)非線性的，稱之為非線性雙層規(guī)劃。()Fxy()fxy此外，如果上下層變量在增加整數(shù)約束，稱之為證書雙層規(guī)劃。三、三、常見雙層規(guī)劃的模型及其應(yīng)用常見雙層規(guī)劃的模型及其應(yīng)用在雙層規(guī)劃模型中，

10、不同的決策者控制著相應(yīng)的決策變量，并優(yōu)化各自的目標(biāo)函數(shù)。下層決策者首先進(jìn)行決策，這樣上層決策者必須預(yù)測到下層可能的反應(yīng)。下層根據(jù)上層的決策進(jìn)行反應(yīng)，以優(yōu)化個(gè)人的目標(biāo)函數(shù)。因?yàn)殡p方可供選擇的策略集是相互依賴的，上層的決策會(huì)影響下層可選的決策和目標(biāo)的實(shí)現(xiàn)，反之亦然。設(shè)上層決策者控制的變量為；下層決策者控制的變量為12(...)TnnxxxxXR???。12(...)TnnyyyyYR???（a）下層以最優(yōu)解反饋到上層的雙層規(guī)劃數(shù)學(xué)模型為：（