運籌學(xué)-隨機規(guī)劃課件

隨機規(guī)劃隨機規(guī)劃隨機規(guī)劃在確定性數(shù)學(xué)規(guī)劃問題中,要求目標函數(shù)是確定性函數(shù),約束條件確定的集合是一個確定的可行域.但是，數(shù)學(xué)規(guī)劃問題中目標函數(shù)或約束條件中的系數(shù)往往是隨機變(向)量.含有隨機變(向)量的數(shù)學(xué)規(guī)劃問題被稱為隨機規(guī)劃.隨機規(guī)劃這一學(xué)科的理論和計算方法還不完善和成熟,但已在管理科學(xué)、經(jīng)濟學(xué)、最優(yōu)控制等學(xué)科和應(yīng)用中顯示了越來越強的生命力,已成為運籌學(xué)的一個重要分支.隨機規(guī)劃在確定性數(shù)學(xué)規(guī)劃問題中,要求目標函數(shù)是確定性函數(shù),隨機規(guī)劃模型及研究模式設(shè)有標準線性規(guī)劃問題假設(shè)模型中系數(shù)A,b,c或它們的一部分分量可能是隨機向量,不妨設(shè)是定義在概率空間上的隨機向量.有隨機線性規(guī)劃模型實際上，這個數(shù)學(xué)規(guī)劃模型是沒有定義的，由于隨機變量的出現(xiàn)，使得min和約束條件的意義并不明確！隨機規(guī)劃模型及研究模式設(shè)有標準線性規(guī)劃問題假設(shè)模型中系數(shù)A,有幾種方式理解隨機規(guī)劃模型以適合于不同的實際背景.期望值模型：取隨機變量對應(yīng)的函數(shù)的數(shù)學(xué)期望,把隨機規(guī)劃轉(zhuǎn)化為一個確定數(shù)學(xué)規(guī)劃問題.隨機規(guī)劃模型及研究模式稱這種在期望值約束下,使目標函數(shù)的期望值達到最優(yōu)的確定數(shù)學(xué)規(guī)劃為期望值模型.有幾種方式理解隨機規(guī)劃模型以適合于不同的實際背景.期望值模型報童問題：設(shè)一報童每天清晨去批發(fā)報紙來零售,每天可以售出報紙份數(shù)為隨機變量b(假設(shè)根據(jù)他長期賣報的經(jīng)驗,b的概率分布是已知的).根據(jù)規(guī)定,如果報童沒有賣完當(dāng)天的報紙,賣不完的報紙不能退回.設(shè)所訂購的報紙數(shù)量為x份,每份報紙的批發(fā)價為p分,售價為a分.報童所面臨的決策問題為,清晨,他應(yīng)批發(fā)多少份報紙最好?期望值模型報童問題：期望值模型收益函數(shù)是隨機變量,考慮其期望收益這里E表示期望值算子,表示需求量b的概率密度函數(shù).報童問題就是尋找最優(yōu)的訂購數(shù)量x,使期望收益E(f(x,b))達到最大值.這是一個典型的期望值模型.期望值模型解：由于每天可以售出報紙份數(shù)為隨機變量b.若x≥b,則每天報紙的剩余量為x-b;否則為0.于是,報童的收益為收益函數(shù)是隨機變量,考慮其期望收益這期望值模型一般的，單目標的期望值模型可以表示如下：期望值模型一般的，單目標的期望值模型可以表示如下：期望值模型期望值模型的確是隨機優(yōu)化問題中常用且有效的方法，但我們并不總是關(guān)心極大化期望值收益問題或極小化期望值費用問題。實際上，有時可能更要考慮所謂的風(fēng)險問題。給定兩種不同的投資方案，它們的期望收益相同而風(fēng)險不同。有些人(稱為風(fēng)險愛好者)可能為追求最大效益而選擇風(fēng)險較大的方案，而另一些人(稱為風(fēng)險厭惡者)可能為躲避風(fēng)險而選擇風(fēng)險較小的投資方案，也可能有些人不太在乎風(fēng)險，認為哪一種方案都可以接受，這也是期望值模型的理論基礎(chǔ)。期望值模型期望值模型的確是隨機優(yōu)化問題中常用且有效的方法，但期望值模型如果決策者希望在給定的期望收益水平下實現(xiàn)風(fēng)險的極小化,則有如下風(fēng)險最小模型如果決策者希望同時考慮期望收益和風(fēng)險，則有如下兩目標規(guī)劃模型期望值模型如果決策者希望在給定的期望收益水平下實現(xiàn)風(fēng)險的極小在有些情況下,使用期望值模型會顯得不太合理,如圣彼得堡悖論.例：某化工廠生產(chǎn)過程中需要A,B兩種化學(xué)成分,現(xiàn)有甲、已兩種原料可提供選用.其中原料甲中化學(xué)成分A的單位含量為a/10,B的單位含量為b/3;原料乙中化學(xué)成分A的單位含量為1/10,B的單位含量為1/3.根據(jù)生產(chǎn)要求,化學(xué)成分A的總含量不得少于7/10個單位,B的總含量不得少于4/3個單位.甲、乙兩種原料的價格相同.由于某種原因,原料甲中化學(xué)成分A,B的單位含量不穩(wěn)定,其中是矩形內(nèi)均勻分布的隨機變量.問如何采購原料,使得既滿足生產(chǎn)要求,又使得成本最低?期望值模型在有些情況下,使用期望值模型會顯得不太合理,如圣彼得堡悖解：設(shè)原料甲和原料乙的采購數(shù)量分別為x1,x2,則有線性規(guī)劃模型(LP)期望值模型解：設(shè)原料甲和原料乙的采購數(shù)量分別為x1,x2,則有線性期望值模型(LP1)有惟一最優(yōu)解(LP1)的最優(yōu)解x*位于D的概率僅為0.25!(LP)的期望值模型為期望值模型(LP1)有惟一最優(yōu)解(LP1)的最優(yōu)解x*位于D期望值模型凸性是數(shù)學(xué)規(guī)劃中經(jīng)常討論的課題，如果一個數(shù)學(xué)規(guī)劃模型的目標函數(shù)和可行域都是凸的，則該規(guī)劃模型稱為凸規(guī)劃。對期望值模型，在凸性方面有如下結(jié)論：期望值模型凸性是數(shù)學(xué)規(guī)劃中經(jīng)常討論的課題，如果一個數(shù)學(xué)規(guī)劃模期望值模型從數(shù)學(xué)觀點來看,確定性優(yōu)化問題和期望值模型并沒有什么區(qū)別,唯一的區(qū)別是后者存在多重積分.隨機模擬,也稱為MonteCarlo模擬,是一種實現(xiàn)隨機(或確定)系統(tǒng)抽樣實驗的技術(shù),其基礎(chǔ)是從給定的概率分布中抽取隨機變量.隨機模擬的應(yīng)用范圍非常廣泛，可以用來求解數(shù)學(xué)、物理、工程技術(shù)以及生產(chǎn)管理等方面的問題。期望值模型從數(shù)學(xué)觀點來看,確定性優(yōu)化問題和期望值模型并沒有估計隨機積分期望值模型估計隨機積分期望值模型Liu和Iwamura提出用基于隨機模擬的遺傳算法求解一般的期望值模型.第0步,輸入?yún)?shù)pop_size,Pc及Pm第1步,初始產(chǎn)生pop_size個染色體,其中可能使用隨機模擬計算約束函數(shù)中的多重積分;第2步,對染色體進行交叉及變異操作,其中可能使用隨機模擬技術(shù)檢驗后代的可行性;第3步,使用隨機模擬技術(shù)計算所有染色體的目標值;第4步,根據(jù)目標值,使用基于序的評價函數(shù)計算每個染色體的適應(yīng)度;第5步,旋轉(zhuǎn)賭輪,選擇染色體;第6步,重復(fù)步驟2到步驟5,直到完成給定的循環(huán)次數(shù);第7步,給出最好的染色體作為最優(yōu)解.期望值模型基于隨機模擬的遺傳算法Liu和Iwamura提出用基于隨機模擬的遺傳算法求解一般的(2)機會約束規(guī)劃(ChanceConstrainedProgramming,簡稱CCP).

機會約束規(guī)劃模型由Charnes和Cooper提出，該模型主要針對約束條件中含有隨機變量，且必須在貫徹到隨機變量的實現(xiàn)之前作出決策的情況.隨機規(guī)劃模型及研究模式考慮帶隨機變量的數(shù)學(xué)規(guī)劃其中x是一個n維決策變量，(2)機會約束規(guī)劃(ChanceConstrained機會約束規(guī)劃考慮到所做的決策在不利情況發(fā)生時可能不滿足約束條件，(CCP)模型采取如下一種原則—即允許所作決策在一定的程度上不滿足約束條件,但該決策應(yīng)使約束條件成立的概率不小于某一事先給定的置信水平α(0<α<1).其中P表示事件成立的概率,為事先給定的約束條件成立的置信水平值.機會約束規(guī)劃考慮到所做的決策在不利情況發(fā)生時可能不滿一般的,考慮目標函數(shù)和約束條件中同時帶隨機變量的數(shù)學(xué)規(guī)劃機會約束規(guī)劃Liu對機會約束規(guī)劃模型提出了如下形式的擴展模型：其中P表示事件成立的概率,分別為事先給定的約束條件和目標函數(shù)的置信水平.聯(lián)合機會約束一般的,考慮目標函數(shù)和約束條件中同時帶隨機變量的數(shù)學(xué)規(guī)劃機聯(lián)合機會約束有時可以分成幾個獨立的機會約束，可行點：點x為可行點當(dāng)且僅當(dāng)事件的概率測度不小于,即違反約束條件的概率小于.機會約束規(guī)劃聯(lián)合機會約束有時可以分成幾個獨立的機會約束，可行點：點x為可機會約束規(guī)劃Max-max機會約束規(guī)劃機會約束規(guī)劃Max-max機會約束規(guī)劃機會約束規(guī)劃在隨機環(huán)境中，在機會約束條件下，想極大化在給定置信水平值處的悲觀值，有如下minimaxCCP模型：機會約束規(guī)劃在隨機環(huán)境中，在機會約束條件下，想極大化在給定置從極小化目標值的觀點來看,所要的目標值應(yīng)該是目標函數(shù)在保證置信水平至少是時所取的最小值,即機會約束規(guī)劃對應(yīng)的,機會約束規(guī)劃模型有如下形式的擴展模型：Min-min模型從極小化目標值的觀點來看,所要的目標值應(yīng)該是機會約束規(guī)劃作為單目標機會約束規(guī)劃的推廣,多目標機會約束規(guī)劃可以表示成如下形式機會約束規(guī)劃作為單目標機會約束規(guī)劃的推廣,多目標機會約束規(guī)機會約束規(guī)劃根據(jù)決策者的優(yōu)先結(jié)構(gòu)和目標信息,機會約束目標規(guī)劃模型可以表示為如下形式機會約束規(guī)劃根據(jù)決策者的優(yōu)先結(jié)構(gòu)和目標信息,機會約束目標規(guī)求解機會約束規(guī)劃的傳統(tǒng)方法是根據(jù)事先給定的置信水平,把機會約束轉(zhuǎn)化為各自的確定等價類,然后傳統(tǒng)的非線性規(guī)劃的算法可以用來解決這類問題.但對較復(fù)雜的機會約束規(guī)劃問題,通常很難做到這一點.一些革新算法如遺傳算法等的提出,使復(fù)雜的機會約束規(guī)劃可不必通過轉(zhuǎn)化而直接得到解決.機會約束規(guī)劃求解機會約束規(guī)劃的傳統(tǒng)方法是根據(jù)事先給定的置信水平,把機會考慮如下機會約束條件：機會約束規(guī)劃—確定等價類考慮如下機會約束條件：機會約束規(guī)劃—確定等價類機會約束規(guī)劃—確定等價類例：考慮機會約束機會約束規(guī)劃—確定等價類例：考慮機會約束考慮如下機會約束條件：機會約束規(guī)劃—確定等價類考慮如下機會約束條件：機會約束規(guī)劃—確定等價類考慮如下機會約束條件：機會約束規(guī)劃—確定等價類考慮如下機會約束條件：機會約束規(guī)劃—確定等價類機會約束規(guī)劃—確定等價類例：假設(shè)機會約束有如下形式P{a1x1+a2x2+a3x3≤b}≥0.95其中a1,a2,a3和b分別服從正態(tài)分布N(1,1),N(2,1),N(3,1)和N(4,1),于是，得到該機會約束條件的確定等價類為

x1+2x2+3x3+1.645(x12+x22+x32+1)1/2≤4機會約束規(guī)劃—確定等價類例：假設(shè)機會約束有如下形式于是，得到如果能夠方便地計算出及其梯度的值,則任何非線性規(guī)劃算法都可用來求解機會約束規(guī)劃問題.但在實際問題中和的計算大都是很不容易的.到目前為止,能夠求出數(shù)值解的,基本上只局限于下述類型的問題:機會約束規(guī)劃—數(shù)值解法如果能夠方便地計算出機會約束規(guī)劃與確定性規(guī)劃的區(qū)別在于前者存在機會約束，因此討論的重點在于如何處理機會約束.如果機會約束比較容易處理，則可以將機會約束轉(zhuǎn)化為各自的確定等價類，否則可以使用隨機模擬技術(shù)處理復(fù)雜的機會約束.考慮如下機會約束規(guī)劃模型1)檢驗隨機系統(tǒng)約束2)計算目標值機會約束規(guī)劃—數(shù)值解法機會約束規(guī)劃與確定性規(guī)劃的區(qū)別在于前者存在機會約束，因此討論1)檢驗隨機系統(tǒng)約束由大數(shù)定律知,可以用頻率N’/N估計此概率.因此,機會約束成立當(dāng)且僅當(dāng)頻率機會約束規(guī)劃—數(shù)值解法從概率分布中產(chǎn)生N個彼此相互獨立的隨機變量設(shè)N’表示N次實驗中1)檢驗隨機系統(tǒng)約束由大數(shù)定律知,可以用頻率N’/N估機會約束規(guī)劃—數(shù)值解法步驟1：置N’=0.步驟2：由概率分布生成隨機變量.步驟3：如果則令N’=N’+1.步驟4：重復(fù)步驟2和步驟3共N次.步驟5：如果返回“成立”,否則返回“不成立”。機會約束規(guī)劃—數(shù)值解法步驟1：置N’=0.步驟2：由概率分布機會約束規(guī)劃—數(shù)值解法例:估計如下事件發(fā)生的概率

θ=P{ξ1+ξ22≥3，ξ3+ξ42≤9}其中ξ1服從均勻分布U(2,5),ξ2服從指數(shù)分布exp(3),ξ3和ξ4分別服從正態(tài)分布N(3,2)和N(1,1).模擬結(jié)果為0.85，即上述事件發(fā)生的概率為0.85.機會約束規(guī)劃—數(shù)值解法例:估計如下事件發(fā)生的概率模擬結(jié)果為從概率分布中產(chǎn)生N個彼此相互獨立的隨機變量2)計算目標值這樣得到序列取N’為的整數(shù)部分.由大數(shù)定律可知，中的第N’個最大的元素可以作為的估計.機會約束規(guī)劃—數(shù)值解法步驟1：從概率分布生成N個隨機向量從概率分布中產(chǎn)生N個彼此相互獨立的隨機變量例:求使下式成立的最大的f0P{ξ1+ξ22+ξ33≥f0}≥0.8其中ξ1服從均勻分布U(1,3),ξ2服從指數(shù)分布exp(1),ξ3服從正態(tài)分布N(2,1).抽樣1000次,其第800個最大元素為4.988,于是f0的估計值為4.988.機會約束規(guī)劃—數(shù)值解法例:求使下式成立的最大的f0抽樣1000次,其第8004)基于隨機模擬的遺傳算法機會約束規(guī)劃—數(shù)值解法Liu和Iwamura提出使用基于隨機模擬的遺傳算法求解一般的機會約束規(guī)劃.第0步,輸入?yún)?shù)pop_size,Pc及Pm第1步,初始產(chǎn)生pop_size個染色體,其中可能使用隨機模擬技術(shù)檢驗染色體的可行性;第2步,對染色體進行交叉及變異操作,其中可能使用隨機模擬技術(shù)檢驗后代的可行性;第3步,使用隨機模擬技術(shù)計算所有染色體的目標值;第4步,根據(jù)目標值,使用基于序的評價函數(shù)計算每個染色體的適應(yīng)度;第5步,旋轉(zhuǎn)賭輪,選擇染色體;第6步,重復(fù)步驟2到步驟5,直到完成給定的循環(huán)次數(shù);第7步,給出最好的染色體作為最優(yōu)解.4)基于隨機模擬的遺傳算法機會約束規(guī)劃—數(shù)值解法Liu和I基于隨機模擬的遺傳算法是解決復(fù)雜的機會約束規(guī)劃模型(包括機會約束多目標規(guī)劃和機會約束目標規(guī)劃)的有力工具.基于隨機模擬的遺傳算法的有效性已被大量實驗所證實.優(yōu)點：（1）能夠很好地得到全局最優(yōu)解；（2）不需要把機會約束轉(zhuǎn)化為它們各自的確定性等價類,從而保證可處理更加一般的機會約束規(guī)劃模型.缺點：計算費用較高，耗時較多。機會約束規(guī)劃—數(shù)值解法基于隨機模擬的遺傳算法是解決復(fù)雜的機會約束規(guī)劃模型(包括機會機會約束規(guī)劃—數(shù)值解法例：考慮一個簡單的機會約束規(guī)劃模型：機會約束規(guī)劃—數(shù)值解法例：考慮一個簡單的機會約束規(guī)劃模型：機會約束規(guī)劃—數(shù)值解法例：考慮單目標機會約束規(guī)劃模型：機會約束規(guī)劃—數(shù)值解法例：考慮單目標機會約束規(guī)劃模型：機會約束規(guī)劃—數(shù)值解法機會約束規(guī)劃—數(shù)值解法例：某煉油廠冶煉兩種原油(分別記為raw1和raw2),需要提前制定一周的生產(chǎn)計劃,以便為天燃氣公司提供天燃氣(記為prod1)和為火力發(fā)電廠提供燃料用油(記為prod2).假定原料raw1所能生產(chǎn)出的天燃氣的產(chǎn)量π(raw1,prod1)和原料raw2所能生產(chǎn)出的燃料用油的產(chǎn)量π(raw2,prod2)是隨機變化的,而所生產(chǎn)的其他產(chǎn)品的產(chǎn)量卻是固定的.這里假設(shè)其中為服從均勻分布的隨機變量，為服從參數(shù)的負值數(shù)分布的隨機變量。機會約束規(guī)劃應(yīng)用已知用戶(天然氣公司和火力發(fā)電廠)對天然氣一周的需求量h1和對燃料的需求量h2也是隨機變化的,可以分別表示和是分別服從正態(tài)分布N(0,12)和N(0,9)的隨機變量.例：某煉油廠冶煉兩種原油(分別記為raw1和raw2),需假設(shè)x1和x2分別是原料raw1和raw2的一周使用量,單價分別為c1=2,c2=3,生產(chǎn)能力(即原材料的最大消耗量)假設(shè)為100.試建立此問題的隨機規(guī)劃模型.機會約束規(guī)劃應(yīng)用x1+x2

≤100.分析：由原材料的最大消耗量可知，有如下約束條件由于每周的生產(chǎn)計劃(x1,x2)是提前制定的,且一周內(nèi)不能改變,同時在相應(yīng)的周內(nèi)客戶希望他們的實際需要得到滿足,即此約束中含有隨機變量，一種可行的方法是使用機會約束,對兩個用戶分別給予置信水平有假設(shè)x1和x2分別是原料raw1和raw2的一周使用量,單由于希望在滿足用戶需求的機會約束下盡可能地降低總費用,把這個生產(chǎn)計劃問題建模為機會約束規(guī)劃模型當(dāng)置信水平分別取為0.8和0.7時,使用基于隨機模擬的遺傳算法,經(jīng)過500代以后,得到的最優(yōu)生產(chǎn)計劃為(x1*,x2*)=(31.95,22.65),其總費用為f(x1*,x2*)=131.85.更進一步,有機會約束規(guī)劃應(yīng)用由于希望在滿足用戶需求的機會約束下盡可能地降低總費用,把這隨機資源分配考慮水資源供給系統(tǒng),有3處水資源和4個用戶,水資源供給網(wǎng)絡(luò)如下機會約束規(guī)劃應(yīng)用input1input2input3output1output2output3output4隨機資源分配機會約束規(guī)劃應(yīng)用input1input2inpu機會約束規(guī)劃應(yīng)用機會約束規(guī)劃應(yīng)用例：設(shè)某工廠生產(chǎn)n種產(chǎn)品,需m種原料.第j種產(chǎn)品對第i種原料的單位需求量為aij,第i種原料的擁有量為bi,第j種產(chǎn)品的單位利潤為cj.試問如何安排各產(chǎn)品的生產(chǎn)量xj(j=1,2,…,n),以使得在現(xiàn)有條件下利潤最大?設(shè)系數(shù)均為隨機變量,記為aij(w),bi(w),cj(w),分布問題：希望知道在各種可能情況下,maxz的值是什么,即maxz的分布如何,或maxz的數(shù)學(xué)期望是多少.分布問題例：設(shè)某工廠生產(chǎn)n種產(chǎn)品,需m種原料.第j種產(chǎn)品對第i種對任一樣本，求解如下線性規(guī)劃問題然后再求maxz(w)的分布函數(shù).分布問題對任一樣本，求解如下線性規(guī)劃問題然后再求并求最優(yōu)值z(w)的分布函數(shù)Fz(t)及有關(guān)的均值E(z)、方差Var(z)等.分布問題就是對每一樣本點求解線性規(guī)劃問題分布問題最優(yōu)目標函數(shù)值z(w)的取值可能有如下三種情況：(1)z(w)=-∞(當(dāng)其對偶問題的可行解集為空集時);(2)z(w)=+∞(當(dāng)原問題的可行解集為空集時);(3)z(w)為有限值(當(dāng)上述兩個可行解集均非空時).并求最優(yōu)值z(w)的分布函數(shù)Fz(t)及有關(guān)的均值E(z)、分布問題分布問題的算法實際計算中并不真的需要解N個線性規(guī)劃問題,因為由(A(i),b(i),c(i))求zi時,可能它的最優(yōu)可行基也是其他(A(k),b(k),c(k))的最優(yōu)可行基,這時求相應(yīng)的zk會是非常方便的.分布問題分布問題的算法實際計算中并不真的需要解N個線性規(guī)劃問分布問題236468(2,4)(2,6)(2,8)(3,4)(3,6)(3,8)(6,6)(6,8)(6,4)分布問題236分布問題(2,4)(2,6)(2,8)(3,4)(3,6)(3,8)(6,6)(6,8)(6,4)進一步,由此容易求出Fz(t)和E(z).分布問題(2,4)(2,6)分布問題分布問題分布問題分布問題分布問題分布問題報童問題(續(xù))：根據(jù)假設(shè),決策x要在知道當(dāng)天能賣出的份數(shù)b(w)實現(xiàn)之前作出,所以報童面臨的規(guī)劃問題為當(dāng)決策x作出后,b(w)可能會出現(xiàn)二種情況;(1)b(w)<x:多余y-份,報童遭受損失py-;(2)b(w)>x:

缺少y+份,報童遭受損失0y+;有補償?shù)亩A段問題報童問題(續(xù))：當(dāng)決策x作出后,b(w)可能會出現(xiàn)二種情報童的凈收入為(-p+a)x-Q(x,w).(Q(x,w)為隨機變量)報童面臨的真正決策問題是報童應(yīng)該考慮使由于約束條件不被滿足而造成的損失最小,即有補償?shù)亩A段問題W稱為補償矩陣q稱為懲罰向量報童的凈收入為(-p+a)x-Q(x,w).(Q(x,w)一般的，考慮如下隨機線性規(guī)劃其中為確定性約束，c為確定性向量，A(w)為型隨機矩陣，b(w)為m