第六章隨機(jī)規(guī)劃

1、第七章隨機(jī)規(guī)劃1第七章隨機(jī)規(guī)劃第六章隨機(jī)規(guī)劃第一節(jié)問題的提出隨機(jī)規(guī)劃所研究的對象是含有隨機(jī)因素的數(shù)學(xué)規(guī)劃問題。例如，我們 熟悉的線性規(guī)劃問題min f (X) =CX(6.1)則稱其為隨機(jī)A， b，C的元AX =bX _0如果其中的A，b，C的元素中部分的或全部的是隨機(jī)變量， 線性規(guī)劃問題。在數(shù)學(xué)規(guī)劃中引入隨機(jī)性是很自然的事情。在模型中的 素常常代表價(jià)格、成本、需求量、資源數(shù)量、經(jīng)濟(jì)指標(biāo)等參數(shù)。由于各種 不確定性因素的影響，這些參數(shù)經(jīng)常出現(xiàn)波動(dòng)。例如，市場上對某種商品 的需求量一般無法精確的預(yù)知，只能作出大致的預(yù)測，某種產(chǎn)品的生產(chǎn)成 本往往受原材料價(jià)格、勞動(dòng)生產(chǎn)率等各種因素的影響而經(jīng)常變化，這

2、些變 化與波動(dòng)，在許多場合可以用一定的概率分布去描述。因此，在數(shù)學(xué)規(guī)劃 中引入隨機(jī)變量，能夠使模型更加符合實(shí)際情況，從而是的決策更加合理。例1某化工廠生產(chǎn)過程中需要A，B兩種化學(xué)成分，現(xiàn)有甲、乙兩種 原材料可供選用。其中原料甲中化學(xué)成分A的單位含量為a/10，B的單位含 量為a/3 ;原料乙中化學(xué)成分A的單位含量為1/10，B的單位含量為1/3。根 據(jù)生產(chǎn)要求，化學(xué)成分A的總含量不得少于7/10個(gè)單位，化學(xué)成分A的總含 量不得少于4/3個(gè)單位。甲、乙兩種原料的價(jià)格相同，問如何采購原料，使 得即滿足生產(chǎn)要求，又是的成本最低？顯而易見，這個(gè)問題可以用線性規(guī)劃模型來描述。根據(jù)題意，設(shè)原料 甲的采購數(shù)

3、量為人，原料乙的采購數(shù)量為X2，容易得到如下線性模型：min f (X)二片 x2ax-! x2 - 7bx-! x2 -4( 6.2)% - 0, x2 - 0于是只要知道a和b的值，立即可以求得最優(yōu)解但是，如果由于某種原因，原料甲中化學(xué)成分A、B的單位含量不穩(wěn)定，其中E=（a,b）T是矩形H蘭4, - <1內(nèi)的均勻分布隨機(jī)向量，則問題（7.2）3就成為隨機(jī)線性規(guī)劃問題了。由于引入了隨機(jī)量，隨機(jī)規(guī)劃問題的分析與求解比普通數(shù)學(xué)規(guī)劃問題 要復(fù)雜大多。在處理隨機(jī)規(guī)劃問題時(shí)，人們最容易想到的方法也許是將模 型中的隨機(jī)變量用它們的期望值來代，從而得到確定性的數(shù)學(xué)規(guī)劃模型， 再去求解。事實(shí)上，過去

4、許多確定性數(shù)學(xué)規(guī)劃正是這樣建立起來的，但是 應(yīng)當(dāng)指出，這種處理方法在實(shí)際問題中并不總可行的。為了說明這一點(diǎn)， 我們不妨用此方法試解例1中的問題。容易求得E（ ） =E（a,b）T二（5/2, 2/3）T，（6.3）將此值代入問題（7.2），得到確定線性規(guī)劃模型如下：min f（X） = % x25x1 x2 _ 722捲 X2 一4（ 6.4）3%=0,x2 丄 0可以求得此問題的唯一最優(yōu)解為X =（X1 ,X2）t =（18/11, 32/11）t，（ 6.5）于是以此X*作為原隨機(jī)線性規(guī)劃問題（7.2）的最優(yōu)解?？墒?，由于問題（7.2） 中的（a,b）T是隨機(jī)向量，我們自然希望知道，上述X

5、*是問題（7.2）的最優(yōu)解 這一事件的概率有多大？是問題（7.2）的可行解這一事件的概率有多大？ 然而，我們發(fā)現(xiàn)，丁*P（a,b） ax1 +X2 Z7, bx1 +x?去 4T ，（ 6.6）= P（a,b）T|a 工5/2,沁2/3=1/4也即，X*對問題（7.2）是可行解以0.75的概率是不可能的，只有0.25的 可能性，這個(gè)解顯然是不可用的。這個(gè)例子說明，用上述方法處理隨機(jī)規(guī)劃問題時(shí)應(yīng)當(dāng)十分謹(jǐn)慎。隨機(jī)規(guī)劃問題可以大致分為兩種類型：被動(dòng)型和主動(dòng)型。被動(dòng)型即所 謂“等待且看到(wait and se&”模型，即決策者等待著觀察問題中隨機(jī)變 量的實(shí)現(xiàn)，然后適當(dāng)?shù)乩眠@些實(shí)現(xiàn)的信息作出

6、決策，分布問題即屬于此 種類型。主動(dòng)型即所謂“這里且現(xiàn)在(here and now)”模型，決策者必須在 沒有機(jī)變量的實(shí)現(xiàn)的信息的情況下就作出決策，二階段問題和機(jī)會約束規(guī) 劃均屬于這種類型。第二節(jié)分布問題一、分布問題的提法例1設(shè)某工廠生產(chǎn)幾種產(chǎn)品，需要用 m種原料。第j種產(chǎn)品對第i種原 料的單位需要量為色，第i種原料的擁有量為b，第j種產(chǎn)品的單位利潤為 5，試問如何安排各產(chǎn)品的生產(chǎn)量Xj( j=1,., n)，以使的在現(xiàn)有條件下利 潤最大？容易列出這個(gè)問題的線性規(guī)劃模型為nmax f (X) - ' CjXjjmn(6.7)aijxj -bi, i 二 1,., mj tXj 0, j

7、 =1,，n進(jìn)一步考慮后，發(fā)現(xiàn)上述模型中的系數(shù)aj總存在誤差，故認(rèn)為aj是服從正態(tài)分布的隨機(jī)變量；而單位利潤系數(shù)Cj亦可能隨市場價(jià)格波動(dòng)而變化，此外原料擁有量b也可能因運(yùn)輸、保管等原因而發(fā)生短缺。于是，上述系數(shù)均 可視為隨機(jī)變量，記為 a0 (w)， Cj (w)，bi(w) ，w '1 ( i =1,.,m; j = 1,., n )。 為了合理安排生產(chǎn)，顯然希望知道，在各種可能的情況下，maxf(X)的值是 什么，也即希望知道m(xù)ax f (X )的分布如何，或者希望知道m(xù)ax f (X)的數(shù)學(xué)期 望是多少。也就是說，對于每個(gè)樣本w. i 求解一個(gè)線性規(guī)劃問題nmax f (X)八

8、q (w)Xjnv aj(w)Xj 二bj(w),i =1,mj 二，(6.8)Xj 亠 0,j =1,，n然后再求maxf(X)的分布。這就是本節(jié)將要討論的分部問題。般地，所謂分布問題就是對于每個(gè)樣本 w -求解一個(gè)線性規(guī)劃問題(w) = min C(w)X(6.9)A(w)X =b(w)X _0并求(w )的分布函數(shù)或其他概率特征。上述問題中，A(w)為隨機(jī)矩陣，b(w)和c(w)分別隨機(jī)向量。顯然為使上 述分布問題在數(shù)學(xué)上有意義，首先要求(w)必須是一個(gè)隨機(jī)變量，即(w)是 概率空間(JP,P)上的Borel可測函數(shù)。對此有如下定理。定理1在上述分部問題中，最優(yōu)目標(biāo)函數(shù)值(w)是一個(gè)隨機(jī)

9、變量，并且適當(dāng)選擇后可以找到該問題的一個(gè)最優(yōu)解X * (w)為隨機(jī)向量。隨著w的變化，問題(7.9)的最優(yōu)目標(biāo)函數(shù)值(w)可能有限，也可能 為無窮大。如果(w)取、活一：的概率大于0,則(w)的數(shù)學(xué)期望及其它概 率特征均不存在，從而該問題在許多情況下將無實(shí)際意義。因此，我們感 興趣的是：P(w : -2 ”匚(W):： ：) 1的情況，此時(shí)問題的最優(yōu)值稱為無缺陷的 分布。對于分部問題可以像對待普通線性規(guī)劃那樣按照參數(shù)規(guī)劃的思路來討 論和求解，比如單純形法、靈敏度分析等。第三節(jié)期望值模型在期望約束下，使得目標(biāo)函數(shù)的期望值達(dá)到最優(yōu)的數(shù)學(xué)規(guī)劃稱為期望 值模型。期望值模型是數(shù)學(xué)規(guī)劃中常見的形式之一，如

10、期望費(fèi)用極小化， 期望值模型極大化問題等等。首先考慮報(bào)童問題。報(bào)童需要每天提前到郵局定購報(bào)紙并確定所定購 的報(bào)紙數(shù)量x分，每份價(jià)格為c元。已經(jīng)知道每份報(bào)紙的售價(jià)為 a元。如果 報(bào)童沒有賣完當(dāng)天的報(bào)紙，則回收中心以極低的價(jià)格b元回收報(bào)紙。假設(shè)每 天報(bào)紙的需求量為，若x，則每天報(bào)紙的剩余量為x ，否則為0。這 樣報(bào)童的受益為(6.10)” (ac)x,x 蘭巴f(X,)=：(bc)x+(ab)C, x>，在實(shí)際問題中，報(bào)童的需求量通常是隨機(jī)變量，從而導(dǎo)致效益函數(shù)f(x,)也是隨機(jī)變量。既然不能準(zhǔn)確地預(yù)測出訂購x份報(bào)紙的實(shí)際收益，一個(gè)自然的方法就是考慮期望收益x:Ef(x, ) = (b-c)

11、x (a-b) ( )d (a-c)x ( )d ,(6.11)0x其中E表示期望值算子，()表示需求量 的概率密度函數(shù)。報(bào)童問題就是 尋找最優(yōu)的定購數(shù)量x使期望收益Ef(x,)達(dá)到最大值，這是一個(gè)典型的期 望值模型。、期望算子(6.12)假設(shè)t維隨機(jī)向量的概率密度函數(shù)為()，則隨機(jī)向量的期望值定義 為E ( )d，通常也稱其為均值設(shè)f為定義在氏上的實(shí)函數(shù)，則f()是一個(gè)隨機(jī)變量，其期望值E(f()(6.13)可以通過下式來計(jì)算:Ef( )H Rtf( ) ( )d ，（6.15）E i （ i = 1,2,., n）（6.16）（6.17）期望值算子有如下的基本性質(zhì)：若b，其中a和b是常數(shù)，

12、則E =aE b，(6.14)更一般的情況，設(shè)1, 2,., n是n個(gè)隨機(jī)變量，且期望值E i ( i=1,2,n )存 在，則有E 12. n二 E i E 2. E n，設(shè)1, 2,., n是門個(gè)相互獨(dú)立的隨機(jī)變量，且期望值 存在，則有E 1. 2. nHE 1.E 2.E n，二、期望值模型單目標(biāo)期望值模型的一般形式為” maxEf(X,r)s.t Egj(X, )0, j =1,2,., p， Eg(X, ) =0, k =1,2,.,q其中X是一個(gè)n維決策向量，堤一個(gè)t維隨機(jī)向量，其概率密度函數(shù)為()， f(X,)是目標(biāo)函數(shù)，gj(X,)和 hk(X,)是隨機(jī)約束函數(shù),j -1,2,

13、., p，k=1,2,.,q 由于Ef(X, )H Rt f(X, ) ( )dEgj(X, )H Rtgj(X, ) ( )d -，j =1,2,., p，(6.18)Ehk(X, )H Rthk(X, ) ( )d ，k=1,2,.,q一個(gè)可行解X*是期望模型最優(yōu)解，如果對于任意的可行解X ,有Ef(X*, ) Ef(X,)成立。第四節(jié)機(jī)會約束規(guī)劃作為第二種隨機(jī)規(guī)劃，機(jī)會約束規(guī)劃(Chanee Constrained Programming 主要是針對約束條件中含有隨機(jī)變量，且必須在觀察到隨機(jī)變量的實(shí)現(xiàn)之 前作出決策的情況?？紤]到所做的決策在不利情況發(fā)生時(shí)可能不滿足約束 條件，而采用一種原

14、則：即允許所作決策在一定程度上不滿足約束條件， 但是該決策應(yīng)使約束條件成立的概率不小于某一個(gè)置信水平：。求解機(jī)會約束規(guī)劃的傳統(tǒng)方法是根據(jù)事先給定的置信水平，把機(jī)會約 束規(guī)劃化為各自的確定等價(jià)類，然后用傳統(tǒng)的方法求解其等價(jià)的確定性模 型。對一些特殊的情況，機(jī)會約束規(guī)劃問題確實(shí)可以化為確定性數(shù)學(xué)規(guī)劃 問題，但對較復(fù)雜的機(jī)會約束規(guī)劃問題，通常很難做到這一點(diǎn)。然而，隨 著計(jì)算機(jī)的高速發(fā)展，一些革新算法如遺傳算法的提出，使得復(fù)雜的機(jī)會 約束規(guī)劃問題可以不必通過轉(zhuǎn)化為確定性數(shù)學(xué)規(guī)劃而直接得到解決。一、機(jī)會約束規(guī)劃模型考慮帶有隨機(jī)參數(shù)的數(shù)學(xué)規(guī)劃模型(6.19)max f(X)stg(X,E) ", j =1,2，p其中X是一個(gè)n維決策向量，堤一個(gè)隨機(jī)向量，f (X,)是目標(biāo)函數(shù)，gj(X,) 是隨機(jī)約束函數(shù)，j =1,2,., p。但是這個(gè)模型由于還有隨機(jī)參數(shù)，意義不很明確。機(jī)會約束規(guī)劃模型max f(6.20)stP f(Xp f > PPgj(X,©", j =1,2,，其中和分別是事先給定的置信水平。一個(gè)點(diǎn)X是可