不確定優(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隨機(jī)規(guī)劃隨機(jī)規(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)域在運(yùn)籌學(xué)、管理科學(xué)、信息科學(xué)、工業(yè)工程、航天技術(shù)以及軍事等眾多領(lǐng)域都存在人為的或客觀的不確定性，表現(xiàn)形式也多種多樣，如隨機(jī)性、模糊性、粗糙性以及多重不確定性。辯證的看，不確定性是絕對(duì)的，確定性是相不確定性是絕對(duì)的，確定性是相對(duì)的。所以，不

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

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

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

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

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

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

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

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

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

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

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

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

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