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

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

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

x1+2x2+3x3+1.645(x12+x22+x32+1)1/2≤4機(jī)會(huì)約束規(guī)劃—確定等價(jià)類例：假設(shè)機(jī)會(huì)約束有如下形式于是，得到如果能夠方便地計(jì)算出及其梯度的值,則任何非線性規(guī)劃算法都可用來求解機(jī)會(huì)約束規(guī)劃問題.但在實(shí)際問題中和的計(jì)算大都是很不容易的.到目前為止,能夠求出數(shù)值解的,基本上只局限于下述類型的問題:機(jī)會(huì)約束規(guī)劃—數(shù)值解法如果能夠方便地計(jì)算出機(jī)會(huì)約束規(guī)劃與確定性規(guī)劃的區(qū)別在于前者存在機(jī)會(huì)約束，因此討論的重點(diǎn)在于如何處理機(jī)會(huì)約束.如果機(jī)會(huì)約束比較容易處理，則可以將機(jī)會(huì)約束轉(zhuǎn)化為各自的確定等價(jià)類，否則可以使用隨機(jī)模擬技術(shù)處理復(fù)雜的機(jī)會(huì)約束.考慮如下機(jī)會(huì)約束規(guī)劃模型1)檢驗(yàn)隨機(jī)系統(tǒng)約束2)計(jì)算目標(biāo)值機(jī)會(huì)約束規(guī)劃—數(shù)值解法機(jī)會(huì)約束規(guī)劃與確定性規(guī)劃的區(qū)別在于前者存在機(jī)會(huì)約束，因此討論1)檢驗(yàn)隨機(jī)系統(tǒng)約束由大數(shù)定律知,可以用頻率N’/N估計(jì)此概率.因此,機(jī)會(huì)約束成立當(dāng)且僅當(dāng)頻率機(jī)會(huì)約束規(guī)劃—數(shù)值解法從概率分布中產(chǎn)生N個(gè)彼此相互獨(dú)立的隨機(jī)變量設(shè)N’表示N次實(shí)驗(yàn)中1)檢驗(yàn)隨機(jī)系統(tǒng)約束由大數(shù)定律知,可以用頻率N’/N估機(jī)會(huì)約束規(guī)劃—數(shù)值解法步驟1：置N’=0.步驟2：由概率分布生成隨機(jī)變量.步驟3：如果則令N’=N’+1.步驟4：重復(fù)步驟2和步驟3共N次.步驟5：如果返回“成立”,否則返回“不成立”。機(jī)會(huì)約束規(guī)劃—數(shù)值解法步驟1：置N’=0.步驟2：由概率分布機(jī)會(huì)約束規(guī)劃—數(shù)值解法例:估計(jì)如下事件發(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.機(jī)會(huì)約束規(guī)劃—數(shù)值解法例:估計(jì)如下事件發(fā)生的概率模擬結(jié)果為從概率分布中產(chǎn)生N個(gè)彼此相互獨(dú)立的隨機(jī)變量2)計(jì)算目標(biāo)值這樣得到序列取N’為的整數(shù)部分.由大數(shù)定律可知，中的第N’個(gè)最大的元素可以作為的估計(jì).機(jī)會(huì)約束規(guī)劃—數(shù)值解法步驟1：從概率分布生成N個(gè)隨機(jī)向量從概率分布中產(chǎn)生N個(gè)彼此相互獨(dú)立的隨機(jī)變量例:求使下式成立的最大的f0P{ξ1+ξ22+ξ33≥f0}≥0.8其中ξ1服從均勻分布U(1,3),ξ2服從指數(shù)分布exp(1),ξ3服從正態(tài)分布N(2,1).抽樣1000次,其第800個(gè)最大元素為4.988,于是f0的估計(jì)值為4.988.機(jī)會(huì)約束規(guī)劃—數(shù)值解法例:求使下式成立的最大的f0抽樣1000次,其第8004)基于隨機(jī)模擬的遺傳算法機(jī)會(huì)約束規(guī)劃—數(shù)值解法Liu和Iwamura提出使用基于隨機(jī)模擬的遺傳算法求解一般的機(jī)會(huì)約束規(guī)劃.第0步,輸入?yún)?shù)pop_size,Pc及Pm第1步,初始產(chǎn)生pop_size個(gè)染色體,其中可能使用隨機(jī)模擬技術(shù)檢驗(yàn)染色體的可行性;第2步,對(duì)染色體進(jìn)行交叉及變異操作,其中可能使用隨機(jī)模擬技術(shù)檢驗(yàn)后代的可行性;第3步,使用隨機(jī)模擬技術(shù)計(jì)算所有染色體的目標(biāo)值;第4步,根據(jù)目標(biāo)值,使用基于序的評(píng)價(jià)函數(shù)計(jì)算每個(gè)染色體的適應(yīng)度;第5步,旋轉(zhuǎn)賭輪,選擇染色體;第6步,重復(fù)步驟2到步驟5,直到完成給定的循環(huán)次數(shù);第7步,給出最好的染色體作為最優(yōu)解.4)基于隨機(jī)模擬的遺傳算法機(jī)會(huì)約束規(guī)劃—數(shù)值解法Liu和I基于隨機(jī)模擬的遺傳算法是解決復(fù)雜的機(jī)會(huì)約束規(guī)劃模型(包括機(jī)會(huì)約束多目標(biāo)規(guī)劃和機(jī)會(huì)約束目標(biāo)規(guī)劃)的有力工具.基于隨機(jī)模擬的遺傳算法的有效性已被大量實(shí)驗(yàn)所證實(shí).優(yōu)點(diǎn)：（1）能夠很好地得到全局最優(yōu)解；（2）不需要把機(jī)會(huì)約束轉(zhuǎn)化為它們各自的確定性等價(jià)類,從而保證可處理更加一般的機(jī)會(huì)約束規(guī)劃模型.缺點(diǎn)：計(jì)算費(fèi)用較高，耗時(shí)較多。機(jī)會(huì)約束規(guī)劃—數(shù)值解法基于隨機(jī)模擬的遺傳算法是解決復(fù)雜的機(jī)會(huì)約束規(guī)劃模型(包括機(jī)會(huì)機(jī)會(huì)約束規(guī)劃—數(shù)值解法例：考慮一個(gè)簡(jiǎn)單的機(jī)會(huì)約束規(guī)劃模型：機(jī)會(huì)約束規(guī)劃—數(shù)值解法例：考慮一個(gè)簡(jiǎn)單的機(jī)會(huì)約束規(guī)劃模型：機(jī)會(huì)約束規(guī)劃—數(shù)值解法例：考慮單目標(biāo)機(jī)會(huì)約束規(guī)劃模型：機(jī)會(huì)約束規(guī)劃—數(shù)值解法例：考慮單目標(biāo)機(jī)會(huì)約束規(guī)劃模型：機(jī)會(huì)約束規(guī)劃—數(shù)值解法機(jī)會(huì)約束規(guī)劃—數(shù)值解法例：某煉油廠冶煉兩種原油(分別記為raw1和raw2),需要提前制定一周的生產(chǎn)計(jì)劃,以便為天燃?xì)夤咎峁┨烊細(xì)?記為prod1)和為火力發(fā)電廠提供燃料用油(記為prod2).假定原料raw1所能生產(chǎn)出的天燃?xì)獾漠a(chǎn)量π(raw1,prod1)和原料raw2所能生產(chǎn)出的燃料用油的產(chǎn)量π(raw2,prod2)是隨機(jī)變化的,而所生產(chǎn)的其他產(chǎn)品的產(chǎn)量卻是固定的.這里假設(shè)其中為服從均勻分布的隨機(jī)變量，為服從參數(shù)的負(fù)值數(shù)分布的隨機(jī)變量。機(jī)會(huì)約束規(guī)劃應(yīng)用已知用戶(天然氣公司和火力發(fā)電廠)對(duì)天然氣一周的需求量h1和對(duì)燃料的需求量h2也是隨機(jī)變化的,可以分別表示和是分別服從正態(tài)分布N(0,12)和N(0,9)的隨機(jī)變量.例：某煉油廠冶煉兩種原油(分別記為raw1和raw2),需假設(shè)x1和x2分別是原料raw1和raw2的一周使用量,單價(jià)分別為c1=2,c2=3,生產(chǎn)能力(即原材料的最大消耗量)假設(shè)為100.試建立此問題的隨機(jī)規(guī)劃模型.機(jī)會(huì)約束規(guī)劃應(yīng)用x1+x2

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

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