不確定優(yōu)化問題的建模和處理方法

1、LOGO不確定優(yōu)化問題的不確定優(yōu)化問題的建模和處理方法建模和處理方法信息管理與信息系統(tǒng)系信息管理與信息系統(tǒng)系 劉劉 波波主要內(nèi)容主要內(nèi)容u不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域u靈敏度分析靈敏度分析u隨機規(guī)劃隨機規(guī)劃u模糊規(guī)劃模糊規(guī)劃u魯棒優(yōu)化魯棒優(yōu)化u智能優(yōu)化算法智能優(yōu)化算法1不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域在運籌學(xué)、管理科學(xué)、信息科學(xué)、工業(yè)工程、航天技術(shù)以及軍事等眾多領(lǐng)域都存在人為的或客觀的不確定性，表現(xiàn)形式也多種多樣，如隨機性、模糊性、粗糙性以及多重不確定性。辯證的看，不確定性是絕對的，確定性是相不確定性是絕對的，確定性是相對的。所以，不

2、確定性是系統(tǒng)的固有屬性，對于任何一個對的。所以，不確定性是系統(tǒng)的固有屬性，對于任何一個組織或系統(tǒng)來說，對不確定性問題都是最為重要的任務(wù)之組織或系統(tǒng)來說，對不確定性問題都是最為重要的任務(wù)之一。一。在決策制定領(lǐng)域，為了得到科學(xué)的決策結(jié)果，通常的做法是對決策問題進行抽象建模，然后采用相應(yīng)優(yōu)化手段進行求解。1不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域在傳統(tǒng)的優(yōu)化問題數(shù)學(xué)表達式中，優(yōu)化模型的結(jié)構(gòu)和參數(shù)是確定的。但是，在實際當中,不確定性無處不在，其不確定因素主要來源于主要來源于：1、系統(tǒng)內(nèi)部潛在的本質(zhì)決定的不確定性；2、對于系統(tǒng)的實際機理不可能完全了解；3、模型建立前收集數(shù)據(jù)時，數(shù)據(jù)采

3、集（包括數(shù)據(jù)測量和數(shù)據(jù)統(tǒng)計預(yù)處理）過程中不可避免的存在測量工具和測量本身的誤差或錯誤；4、對模型的簡化處理，比如用一個簡單的模型來近似比較復(fù)雜的系統(tǒng)；5、影響所建模型的未來因素不確定；6、在計算過程中，對模型的離散化處理；7、解決方案付諸實際時，由于種種原因還需要不斷的修正等。1不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域不確定優(yōu)化問題的來源及應(yīng)用領(lǐng)域這些不確定因素可能對優(yōu)化模型的結(jié)構(gòu)和參數(shù)產(chǎn)生影響，從而使得優(yōu)化模型的解不再滿足約束條件，同樣，優(yōu)化模型的最優(yōu)目標值也就不成立。因此，對于這些含有不確定性的對于這些含有不確定性的決策優(yōu)化問題，經(jīng)典的優(yōu)化理論通常是無能為力的決策優(yōu)化問題，經(jīng)典的優(yōu)化理論通常是無能為

4、力的。處理不確定優(yōu)化問題的方法一般有：概率論與數(shù)理統(tǒng)計、概率論與數(shù)理統(tǒng)計、可能性理論、模糊理論、灰集理論、粗糙集理論、區(qū)間代數(shù)、可能性理論、模糊理論、灰集理論、粗糙集理論、區(qū)間代數(shù)、集對理論等集對理論等, ,當然這些理論之間存在著互相交叉。選擇何種方當然這些理論之間存在著互相交叉。選擇何種方法取決于所能獲得的信息和決策者的態(tài)度及目的。法取決于所能獲得的信息和決策者的態(tài)度及目的。下面介紹幾種常用的優(yōu)化理論和方法。1靈敏度分析靈敏度分析1.靈敏度分析的基本方法靈敏度分析源于統(tǒng)計、預(yù)測、估計或假設(shè)等一些不確定靈敏度分析源于統(tǒng)計、預(yù)測、估計或假設(shè)等一些不確定的建模中，分析不確定性數(shù)據(jù)的變化給模型的輸出

5、帶來的的建模中，分析不確定性數(shù)據(jù)的變化給模型的輸出帶來的影響。影響。在對線性規(guī)劃進行靈敏度分析時，是在得到線性規(guī)劃問題的最優(yōu)解之后，對要研究這個問題中各個系數(shù)的單獨變化對目前最優(yōu)解的影響。1靈敏度分析靈敏度分析1.靈敏度分析的基本方法運用靈敏度分析，我們可以得到兩方面的運用靈敏度分析，我們可以得到兩方面的結(jié)論：一是數(shù)據(jù)的變化對最優(yōu)解的影響；二結(jié)論：一是數(shù)據(jù)的變化對最優(yōu)解的影響；二是保持最優(yōu)解不變時是保持最優(yōu)解不變時, ,各參數(shù)的變化范圍。靈各參數(shù)的變化范圍。靈敏度分析主要依賴于線性規(guī)劃的對偶特性，敏度分析主要依賴于線性規(guī)劃的對偶特性，并且是分析部分參數(shù)變化時的情況。靈敏度并且是分析部分參數(shù)變化

6、時的情況。靈敏度分析是在優(yōu)化計算已經(jīng)完成，得到最優(yōu)結(jié)果分析是在優(yōu)化計算已經(jīng)完成，得到最優(yōu)結(jié)果之后進行的，因此又被稱為優(yōu)化后分析。之后進行的，因此又被稱為優(yōu)化后分析。1靈敏度分析靈敏度分析2.靈敏度分析的局限性1.采用確定性的模型，即便是參數(shù)不能完全知道的時候，一般會采用最好的估計值,或者用均值。也就是說,實際上在建模時幾乎不考慮不確定性的存在。2.在得到最優(yōu)結(jié)果后進行分析，來確定不確定因素所帶來的影響，從某種角度來說，屬于一種被動的行為，因為并不在事先主動考慮不確定性。3.一般嚴格依賴于最優(yōu)解,或者最優(yōu)解的求解方法。1隨機規(guī)劃隨機規(guī)劃概率論和數(shù)理統(tǒng)計是處理不確定問題的常用理論工具。在概率論和數(shù)

7、理統(tǒng)計是處理不確定問題的常用理論工具。在處理優(yōu)化問題的過程中，往往有一些參數(shù)以隨機變量的形式處理優(yōu)化問題的過程中，往往有一些參數(shù)以隨機變量的形式出現(xiàn)在模型中，就形成了所謂的隨機規(guī)劃模型出現(xiàn)在模型中，就形成了所謂的隨機規(guī)劃模型。建立模型的目的是要找出滿足約束條件的“最好”解作為最終決策。但是, 模型中不確定因素的存在,使得模型的數(shù)學(xué)定義變得不明確。因而對于“最好”解的選擇不再是單純的數(shù)學(xué)優(yōu)化問題，還成為一種決策問題,決策者不同決策態(tài)度以及周圍的一些環(huán)境因素將影響對結(jié)果的選擇。而且一般這種定義不明確的模型需要轉(zhuǎn)換成確定型模型，才能運用各種數(shù)學(xué)方法進行求解。1隨機規(guī)劃隨機規(guī)劃隨機規(guī)劃模型主要有以下幾

8、種類型：期望值模型：在期望約束下，使目標函數(shù)的期望值達到最優(yōu)的數(shù)學(xué)規(guī)劃，在期望約束下，使目標函數(shù)的期望值達到最優(yōu)的數(shù)學(xué)規(guī)劃，稱為期望值模型稱為期望值模型。這種模型是隨機規(guī)劃中最為常見的形式。相對于原始模型(l.5.4),其期望值模型如下式。如果模型中的隨機變量和決策變量呈線性關(guān)系，且相互獨立,則模型可以簡化。因此在實際使用中，我們經(jīng)常直接以決策變量的期望值取代該隨機參數(shù)直接建模，得到一種期望值意義下的確定性模型。1隨機規(guī)劃隨機規(guī)劃隨機規(guī)劃模型主要有以下幾種類型：機會約束規(guī)劃模型：機會約束規(guī)劃又被稱為概率規(guī)劃，機會約束規(guī)劃又被稱為概率規(guī)劃，形式有很多，比如劉寶旋提出的Maximax機會約束規(guī)劃，

9、Minimax機會約束規(guī)劃機會約束規(guī)劃，及隨機相關(guān)機會規(guī)劃隨機相關(guān)機會規(guī)劃等。1機會約束規(guī)劃模型：隨機規(guī)劃隨機規(guī)劃對于機會約束來說，計算是非常困難的。這是因為我對于機會約束來說，計算是非常困難的。這是因為我們需要知道隨機變量的概率密度函數(shù)以及反函數(shù)，而且們需要知道隨機變量的概率密度函數(shù)以及反函數(shù)，而且不同的隨機變量，隨概率密度函數(shù)又是多種多樣的不同的隨機變量，隨概率密度函數(shù)又是多種多樣的。因此其計算的復(fù)雜性來自于，當用連續(xù)的概率分布函數(shù)來描述不確定性時需要復(fù)雜的組合技術(shù)和方法，這是制約隨機模型應(yīng)用的一個主要原因。當然,在工程上可以采用近似的方法，比如采用隨機模擬的方法,但這樣也將會增加計算的負

10、擔。1模糊規(guī)劃模糊規(guī)劃與隨機規(guī)劃類似，模糊規(guī)劃是另一類重要的解決不與隨機規(guī)劃類似，模糊規(guī)劃是另一類重要的解決不確定優(yōu)化問題的方法。二者的區(qū)別在于對不確定因素的確定優(yōu)化問題的方法。二者的區(qū)別在于對不確定因素的描述和建模方面。在隨機規(guī)劃中，不確定參數(shù)通過離散描述和建模方面。在隨機規(guī)劃中，不確定參數(shù)通過離散或連續(xù)的概率密度函數(shù)來描述或連續(xù)的概率密度函數(shù)來描述, ,在模糊規(guī)劃不確定參數(shù)在模糊規(guī)劃不確定參數(shù)被看作是模糊數(shù)被看作是模糊數(shù), ,約束被當作模糊集合來處理。約束被當作模糊集合來處理。其中的一些約束允許被違背，并定義約束的滿意度作為約束的隸屬函數(shù)。1魯棒優(yōu)化魯棒優(yōu)化魯棒優(yōu)化是不確定優(yōu)化研究中的一個

11、新的研究主題，它源自魯棒控制,應(yīng)用領(lǐng)域非常廣泛。魯棒優(yōu)化作為一個含有不確定輸入的優(yōu)化問題的建模方法，是隨機規(guī)劃和靈敏度分析的補充替換，其目的是尋求一個對于所有不確定輸入都有良好性能的解。該方法不同于隨機規(guī)劃，魯棒優(yōu)化對不確定參數(shù)沒有分布假定魯棒優(yōu)化對不確定參數(shù)沒有分布假定( (每個可能的值都同每個可能的值都同等重要等重要) )，當面向最壞情況時，它代表著一個保守的解，當面向最壞情況時，它代表著一個保守的解。1魯棒優(yōu)化是在不確定環(huán)境下研究系統(tǒng)結(jié)構(gòu)內(nèi)部的參數(shù)變化魯棒優(yōu)化是在不確定環(huán)境下研究系統(tǒng)結(jié)構(gòu)內(nèi)部的參數(shù)變化以及外部環(huán)境有擾動變量的條件下，如何對系統(tǒng)進行優(yōu)化的以及外部環(huán)境有擾動變量的條件下，如何

12、對系統(tǒng)進行優(yōu)化的方法。針對系統(tǒng)內(nèi)部結(jié)構(gòu)的變動，魯棒優(yōu)化主要解決約束條方法。針對系統(tǒng)內(nèi)部結(jié)構(gòu)的變動，魯棒優(yōu)化主要解決約束條件與目標函數(shù)的參數(shù)的不確定性；對于外部環(huán)境的變化，主件與目標函數(shù)的參數(shù)的不確定性；對于外部環(huán)境的變化，主要處理外界產(chǎn)生的不確定性擾動。要處理外界產(chǎn)生的不確定性擾動。魯棒優(yōu)化所研究的問題中，不確定性參數(shù)的概率分布函數(shù)是未知的，用區(qū)間、以及相應(yīng)的集合等來描述不確定參數(shù)的變動范圍。由于在很多的情況下，參數(shù)微小的變化就會嚴重影響最優(yōu)解的最優(yōu)性，甚至使得其最優(yōu)解不可行。為了使約束條件對所有合理的數(shù)據(jù)取值都保持可行性，魯棒優(yōu)化的目的是找到一個近似最優(yōu)解，使它對任意的不確定性參數(shù)的觀測值都

13、不敏感。其最大特點是在考慮了不確最大特點是在考慮了不確定性參數(shù)值實現(xiàn)后不同目標函數(shù)值之間的差異，而不僅僅定性參數(shù)值實現(xiàn)后不同目標函數(shù)值之間的差異，而不僅僅是強調(diào)數(shù)學(xué)期望值。因此，魯棒優(yōu)化不僅繼承了隨機規(guī)劃是強調(diào)數(shù)學(xué)期望值。因此，魯棒優(yōu)化不僅繼承了隨機規(guī)劃的優(yōu)點，而且具有更強的實用性的優(yōu)點，而且具有更強的實用性。魯棒優(yōu)化魯棒優(yōu)化1魯棒優(yōu)化魯棒優(yōu)化模糊規(guī)劃與隨機規(guī)劃是兩類重要的處理不確定問題的優(yōu)化方法，兩者的主要區(qū)別在于對不確定參數(shù)的描述以及建模方法的不同。模糊規(guī)劃將不確定參數(shù)看作是模糊數(shù)，將約束當做模糊集來對待；而隨機規(guī)劃，則是把不確定參數(shù)描述為離散或者連續(xù)的概率密度函數(shù)來處理。以上不確定問題優(yōu)

14、化方法在考慮何時不確定因素對優(yōu)化產(chǎn)生影響的時機上有所區(qū)別，靈敏度分析是在得到最優(yōu)解之后，屬于事后分析；靈敏度分析是在得到最優(yōu)解之后，屬于事后分析；而模糊規(guī)劃、隨機規(guī)劃以及魯棒優(yōu)化則均屬于事前分析方法，它們的而模糊規(guī)劃、隨機規(guī)劃以及魯棒優(yōu)化則均屬于事前分析方法，它們的不同在于：模糊規(guī)劃需要建立隸屬度函數(shù)，隨機規(guī)劃需要已知參數(shù)的不同在于：模糊規(guī)劃需要建立隸屬度函數(shù)，隨機規(guī)劃需要已知參數(shù)的概率分布，魯棒優(yōu)化不需要考慮不確定參數(shù)的分布，使用更廣，更符概率分布，魯棒優(yōu)化不需要考慮不確定參數(shù)的分布，使用更廣，更符合實際情況。合實際情況。1魯棒優(yōu)化魯棒優(yōu)化通過對不確定優(yōu)化方法對比，魯棒優(yōu)化適合應(yīng)用于以下情形：1)不確定優(yōu)化問題的參數(shù)需要估計,但是有估計風險。2)優(yōu)化模型中不確定參數(shù)的任何實現(xiàn)都要滿足約束函數(shù)。3)目標函數(shù)或者優(yōu)化解對于優(yōu)化模型的參數(shù)擾動非常敏感。4)決策者不能承擔低概率事件發(fā)生后所帶來的巨大風險。1智能