數(shù)學(xué)建模算法非線性規(guī)劃及數(shù)學(xué)建模算法大全排隊論

第三章非線性規(guī)劃§1非線性規(guī)劃1.1非線性規(guī)劃的實例與定義如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍。下面通過實例歸納出非線性規(guī)劃數(shù)學(xué)模型的一般形式，介紹有關(guān)非線性規(guī)劃的基本概念。例1（投資決策問題）某企業(yè)有個項目可供選擇投資，并且至少要對其中一個項目投資。已知該企業(yè)擁有總資金元，投資于第個項目需花資金元，并預(yù)計可收益元。試選擇最佳投資方案。解設(shè)投資決策變量為，，則投資總額為，投資總收益為。因為該公司至少要對一個項目投資，并且總的投資金額不能超過總資金，故有限制條件另外，由于只取值0或1，所以還有最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個最佳投資決策問題歸結(jié)為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數(shù)學(xué)模型為：s.t.上面例題是在一組等式或不等式的約束下，求一個函數(shù)的最大值（或最小值）問題，其中至少有一個非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題?？筛爬橐话阈问?NP)其中稱為模型（NP）的決策變量，稱為目標(biāo)函數(shù)，和稱為約束函數(shù)。另外，稱為等式約束，稱為不等式的約束。對于一個實際問題，在把它歸結(jié)成非線性規(guī)劃問題時，一般要注意如下幾點：（=1\*romani）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來表示它們。（=2\*romanii）提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。（=3\*romaniii）給出價值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它。（=4\*romaniv）尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。1.2線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點上達(dá)到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點達(dá)到。1.3非線性規(guī)劃的Matlab解法Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式,其中是標(biāo)量函數(shù)，是相應(yīng)維數(shù)的矩陣和向量，是非線性向量函數(shù)。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量，其中FUN是用M文件定義的函數(shù)；X0是的初始值；A,B,Aeq,Beq定義了線性約束，如果沒有線性約束，則A=[],B=[],Aeq=[],Beq=[]；LB和UB是變量的下界和上界，如果上界和下界沒有約束，則LB=[]，UB=[]，如果無下界，則LB=-inf，如果無上界，則UB=inf；NONLCON是用M文件定義的非線性向量函數(shù)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求下列非線性規(guī)劃（=1\*romani）編寫M文件fun1.mfunctionf=fun1(x);f=x(1)^2+x(2)^2+8;和M文件fun2.mfunction[g,h]=fun2(x);g=-x(1)^2+x(2);h=-x(1)-x(2)^2+2;%等式約束（=2\*romanii）在Matlab的命令窗口依次輸入options=optimset('largescale','off');[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[],...'fun2',options)就可以求得當(dāng)時，最小值。1.4求解非線性規(guī)劃的基本迭代格式記（NP）的可行域為。若，并且則稱是（NP）的整體最優(yōu)解，是(NP)的整體最優(yōu)值。如果有則稱是（NP）的嚴(yán)格整體最優(yōu)解，是(NP)的嚴(yán)格整體最優(yōu)值。若，并且存在的鄰域，使，則稱是（NP）的局部最優(yōu)解，是(NP)的局部最優(yōu)值。如果有則稱是（NP）的嚴(yán)格局部最優(yōu)解，是(NP)的嚴(yán)格局部最優(yōu)值。由于線性規(guī)劃的目標(biāo)函數(shù)為線性函數(shù)，可行域為凸集，因而求出的最優(yōu)解就是整個可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時求出的某個解雖是一部分可行域上的極值點，但卻并不一定是整個可行域上的全局最優(yōu)解。對于非線性規(guī)劃模型(NP)，可以采用迭代方法求它的最優(yōu)解。迭代方法的基本思想是：從一個選定的初始點出發(fā)，按照某一特定的迭代規(guī)則產(chǎn)生一個點列，使得當(dāng)是有窮點列時，其最后一個點是(NP)的最優(yōu)解；當(dāng)是無窮點列時，它有極限點，并且其極限點是(NP)的最優(yōu)解。設(shè)是某迭代方法的第輪迭代點，是第輪迭代點，記（1）這里，并且的方向是從點向著點的方向。式（1）就是求解非線性規(guī)劃模型(NP)的基本迭代格式。通常，我們把基本迭代格式（1）中的稱為第輪搜索方向，為沿方向的步長，使用迭代方法求解(NP)的關(guān)鍵在于，如何構(gòu)造每一輪的搜索方向和確定適當(dāng)?shù)牟介L。設(shè)，若存在，使，稱向量是在點處的下降方向。設(shè)，若存在，使，稱向量是點處關(guān)于的可行方向。一個向量，若既是函數(shù)在點處的下降方向，又是該點關(guān)于區(qū)域的可行方向，稱之為函數(shù)在點處關(guān)于的可行下降方向?，F(xiàn)在，我們給出用基本迭代格式（1）求解(NP)的一般步驟如下：0°選取初始點，令。1°構(gòu)造搜索方向，依照一定規(guī)劃，構(gòu)造在點處關(guān)于的可行下降方向作為搜索方向。2°尋求搜索步長。以為起點沿搜索方向?qū)で筮m當(dāng)?shù)牟介L，使目標(biāo)函數(shù)值有某種意義的下降。3°求出下一個迭代點。按迭代格式（1）求出。若已滿足某種終止條件，停止迭代。4°以代替，回到1°步。1.5凸函數(shù)、凸規(guī)劃設(shè)為定義在維歐氏空間中某個凸集上的函數(shù)，若對任何實數(shù)以及中的任意兩點和，恒有則稱為定義在上的凸函數(shù)。若對每一個和恒有則稱為定義在上的嚴(yán)格凸函數(shù)?？紤]非線性規(guī)劃假定其中為凸函數(shù)，為凸函數(shù)，這樣的非線性規(guī)劃稱為凸規(guī)劃?？梢宰C明，凸規(guī)劃的可行域為凸集，其局部最優(yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個凸集。當(dāng)凸規(guī)劃的目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)時，其最優(yōu)解必定唯一（假定最優(yōu)解存在）。由此可見，凸規(guī)劃是一類比較簡單而又具有重要理論意義的非線性規(guī)劃?！?無約束問題2.1一維搜索方法當(dāng)用迭代法求函數(shù)的極小點時，常常用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點。一維搜索的方法很多，常用的有：（1）試探法（“成功—失敗”，斐波那契法，0.618法等）；（2）插值法（拋物線插值法，三次插值法等）；（3）微積分中的求根法（切線法，二分法等）?？紤]一維極小化問題（2）若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長度，來搜索得（2）的近似最優(yōu)解的兩個方法。為了縮短區(qū)間，逐步搜索得（2）的最優(yōu)解的近似值，我們可以采用以下途徑：在中任取兩個關(guān)于是對稱的點和（不妨設(shè)，并把它們叫做搜索點），計算和并比較它們的大小。對于單峰函數(shù)，若，則必有，因而是縮短了的單峰區(qū)間；若，則有，故是縮短了的單峰區(qū)間；若，則和都是縮短了的單峰。因此通過兩個搜索點處目標(biāo)函數(shù)值大小的比較，總可以獲得縮短了的單峰區(qū)間。對于新的單峰區(qū)間重復(fù)上述做法，顯然又可獲得更短的單峰區(qū)間。如此進(jìn)行，在單峰區(qū)間縮短到充分小時，我們可以取最后的搜索點作為（2）最優(yōu)解的近似值。應(yīng)該按照怎樣的規(guī)則來選取探索點，使給定的單峰區(qū)間的長度能盡快地縮短？Fibonacci法如用表示計算個函數(shù)值能縮短為單位長區(qū)間的最大原區(qū)間長度，可推出滿足關(guān)系數(shù)列稱為Fibonacci數(shù)列，稱為第個Fibonacci數(shù)，相鄰兩個Fibonacci數(shù)之比稱為Fibonacci分?jǐn)?shù)。當(dāng)用斐波那契法以個探索點來縮短某一區(qū)間時，區(qū)間長度的第一次縮短率為，其后各次分別為。由此，若和是單峰區(qū)間中第1個和第2個探索點的話，那么應(yīng)有比例關(guān)系，從而，（3）它們關(guān)于確是對稱的點。如果要求經(jīng)過一系列探索點搜索之后，使最后的探索點和最優(yōu)解之間的距離不超過精度，這就要求最后區(qū)間的長度不超過，即（4）據(jù)此，我們應(yīng)按照預(yù)先給定的精度，確定使（4）成立的最小整數(shù)作為搜索次數(shù)，直到進(jìn)行到第個探索點時停止。用上述不斷縮短函數(shù)的單峰區(qū)間的辦法，來求得問題（2）的近似解，是Kiefer(1953年)提出的，叫做Finbonacci法，具體步驟如下：1°選取初始數(shù)據(jù)，確定單峰區(qū)間，給出搜索精度，由（4）確定搜索次數(shù)。2°，計算最初兩個搜索點，按（3）計算和。3°whileifelseendend4°當(dāng)進(jìn)行至?xí)r，這就無法借比較函數(shù)值和的大小確定最終區(qū)間，為此，取其中為任意小的數(shù)。在和這兩點中，以函數(shù)值較小者為近似極小點，相應(yīng)的函數(shù)值為近似極小值。并得最終區(qū)間或。由上述分析可知，斐波那契法使用對稱搜索的方法，逐步縮短所考察的區(qū)間，它能以盡量少的函數(shù)求值次數(shù)，達(dá)到預(yù)定的某一縮短率。例3試用斐波那契法求函數(shù)的近似極小點，要求縮短后的區(qū)間不大于區(qū)間的0.08倍。程序留作習(xí)題。2.1.20.618法若，滿足比例關(guān)系稱之為黃金分割數(shù)，其值為。黃金分割數(shù)和Fibonacci分?jǐn)?shù)之間有著重要的關(guān)系，它們是1°，為偶數(shù)，，為奇數(shù)。2°?，F(xiàn)用不變的區(qū)間縮短率0.618，代替斐波那契法每次不同的縮短率，就得到了黃金分割法（0.618法）。這個方法可以看成是斐波那契法的近似，實現(xiàn)起來比較容易，效果也相當(dāng)好，因而易于為人們所接受。用0.618法求解，從第2個探索點開始每增加一個探索點作一輪迭代以后，原單峰區(qū)間要縮短0.618倍。計算個探索點的函數(shù)值可以把原區(qū)間連續(xù)縮短次，因為每次的縮短率均為，故最后的區(qū)間長度為這就是說，當(dāng)已知縮短的相對精度為時，可用下式計算探索點個數(shù)：當(dāng)然，也可以不預(yù)先計算探索點的數(shù)目，而在計算過程中逐次加以判斷，看是否已滿足了提出的精度要求。0.618法是一種等速對稱進(jìn)行試探的方法，每次的探索點均取在區(qū)間長度的0.618倍和0.382倍處。2.2二次插值法對極小化問題（2），當(dāng)在上連續(xù)時，可以考慮用多項式插值來進(jìn)行一維搜索。它的基本思想是：在搜索區(qū)間中，不斷用低次（通常不超過三次）多項式來近似目標(biāo)函數(shù)，并逐步用插值多項式的極小點來逼近（2）的最優(yōu)解。

2.3無約束極值問題的解法無約束極值問題可表述為（5）求解問題（5）的迭代法大體上分為兩點：一是用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)，稱為解析法。另一是僅用到函數(shù)值，稱為直接法。2.3.1解析法2.3.1.1梯度法（最速下降法）對基本迭代格式（6）我們總是考慮從點出發(fā)沿哪一個方向，使目標(biāo)函數(shù)下降得最快。微積分的知識告訴我們，點的負(fù)梯度方向，是從點出發(fā)使下降最快的方向。為此，稱負(fù)梯度方向為在點處的最速下降方向。按基本迭代格式（6），每一輪從點出發(fā)沿最速下降方向作一維搜索，來建立求解無約束極值問題的方法，稱之為最速下降法。這個方法的特點是，每輪的搜索方向都是目標(biāo)函數(shù)在當(dāng)前點下降最快的方向。同時，用或作為停止條件。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點，給定終止誤差，令。2°求梯度向量。計算，若，停止迭代，輸出。否則，進(jìn)行3°。3°構(gòu)造負(fù)梯度方向。取.4°進(jìn)行一維搜索。求，使得令轉(zhuǎn)2°。例4用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點。解：（=1\*romani）編寫M文件detaf.m如下function[f,df]=detaf(x);f=x(1)^2+25*x(2)^2;df(1)=2*x(1);df(2)=50*x(2);（=2\*romanii）編寫M文件zuisu.mclcx=[2;2];[f0,g]=detaf(x);whilenorm(g)>0.000001p=-g'/norm(g);t=1.0;f=detaf(x+t*p);whilef>f0t=t/2;f=detaf(x+t*p);endx=x+t*p[f0,g]=detaf(x)end2.3.1.2Newton法考慮目標(biāo)函數(shù)在點處的二次逼近式假定Hesse陣正定。由于正定，函數(shù)的駐點是的極小點。為求此極小點，令，即可解得.對照基本迭代格式（1），可知從點出發(fā)沿搜索方向。并取步長即可得的最小點。通常，把方向叫做從點出發(fā)的Newton方向。從一初始點開始，每一輪從當(dāng)前迭代點出發(fā)，沿Newton方向并取步長為1的求解方法，稱之為Newton法。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點，給定終止誤差，令。2°求梯度向量。計算，若，停止迭代，輸出。否則，進(jìn)行3°。3°構(gòu)造Newton方向。計算，取.4°求下一迭代點。令，轉(zhuǎn)2°。例5用Newton法求解，選取。解：（=1\*romani）編寫M文件nwfun.m如下：function[f,df,d2f]=nwfun(x);f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;df=[4*x(1)^3+2*x(1)*x(2)^2;100*x(2)^3+2*x(1)^2*x(2)];d2f=[2*x(1)^2+2*x(2)^2,4*x(1)*x(2)4*x(1)*x(2),300*x(2)^2+4*x(1)^2];（=2\*romanii）編寫M文件：clcx=[2;2];[f0,g1,g2]=nwfun(x)whilenorm(g1)>0.00001p=-inv(g2)*g1x=x+p[f0,g1,g2]=nwfun(x)end如果目標(biāo)函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。為了提高計算精度，我們在迭代時可以采用變步長計算上述問題，程序如下：clcx=[2;2];[f0,g1,g2]=nwfun(x)whilenorm(g1)>0.00001p=-inv(g2)*g1,p=p/norm(p)t=1.0,f=nwfun(x+t*p)whilef>f0t=t/2,f=nwfun(x+t*p),endx=x+t*p[f0,g1,g2]=nwfun(x)endNewton法的優(yōu)點是收斂速度快；缺點是有時不好用而需采取改進(jìn)措施，此外，當(dāng)維數(shù)較高時，計算的工作量很大。2.3.1.3變尺度法變尺度法（VariableMetricAlgorithm）是近20多年來發(fā)展起來的，它不僅是求解無約束極值問題非常有效的算法，而且也已被推廣用來求解約束極值問題。由于它既避免了計算二階導(dǎo)數(shù)矩陣及其求逆過程，又比梯度法的收斂速度快，特別是對高維問題具有顯著的優(yōu)越性，因而使變尺度法獲得了很高的聲譽。下面我們就來簡要地介紹一種變尺度法—DFP法的基本原理及其計算過程。這一方法首先由Davidon在1959年提出，后經(jīng)Fletcher和Powell加以改進(jìn)。我們已經(jīng)知道，牛頓法的搜索方向是，為了不計算二階導(dǎo)數(shù)矩陣及其逆陣，我們設(shè)法構(gòu)造另一個矩陣，用它來逼近二階導(dǎo)數(shù)矩陣的逆陣，這一類方法也稱擬牛頓法（Quasi-NewtonMethod）。下面研究如何構(gòu)造這樣的近似矩陣，并將它記為。我們要求：每一步都能以現(xiàn)有的信息來確定下一個搜索方向；每做一次選代，目標(biāo)函數(shù)值均有所下降；這些近似矩陣最后應(yīng)收斂于解點處的Hesse陣的逆陣。當(dāng)是二次函數(shù)時，其Hesse陣為常數(shù)陣，任兩點和處的梯度之差為或?qū)τ诜嵌魏瘮?shù)，仿照二次函數(shù)的情形，要求其Hesse陣的逆陣的第次近似矩陣滿足關(guān)系式（7）這就是常說的擬Newton條件。若令（8）則式（7）變?yōu)?，?）現(xiàn)假定已知，用下式求（設(shè)和均為對稱正定陣）；（10）其中稱為第次校正矩陣。顯然，應(yīng)滿足擬Newton條件（9），即要求或（11）由此可以設(shè)想，的一種比較簡單的形式是(12)其中和為兩個待定列向量。將式（12）中的代入（11），得這說明，應(yīng)使（13）考慮到應(yīng)為對稱陣，最簡單的辦法就是?。?4）由式（13）得（15）若和不等于零，則有（16）于是，得校正矩陣(17)從而得到（18）上述矩陣稱為尺度矩陣。通常，我們?nèi)〉谝粋€尺度矩陣為單位陣，以后的尺度矩陣按式（18）逐步形成?？梢宰C明：（=1\*romani）當(dāng)不是極小點且正定時，式（17）右端兩項的分母不為零，從而可按式（18）產(chǎn)生下一個尺度矩陣；（=2\*romanii）若為對稱正定陣，則由式（18）產(chǎn)生的也是對稱正定陣；（=3\*romaniii）由此推出DFP法的搜索方向為下降方向。現(xiàn)將DFP變尺度法的計算步驟總結(jié)如下。1°給定初始點及梯度允許誤差。2°若，則即為近似極小點，停止迭代，否則，轉(zhuǎn)向下一步。3°令（單位矩陣），在方向進(jìn)行一維搜索，確定最佳步長：如此可得下一個近似點4°一般地，設(shè)已得到近似點，算出，若則即為所求的近似解，停止迭代；否則，計算：并令，在方向上進(jìn)行一維搜索，得，從而可得下一個近似點5°若滿足精度要求，則即為所求的近似解，否則，轉(zhuǎn)回4°，直到求出某點滿足精度要求為止。2.3.2直接法在無約束非線性規(guī)劃方法中，遇到問題的目標(biāo)函數(shù)不可導(dǎo)或?qū)Ш瘮?shù)的解析式難以表示時，人們一般需要使用直接搜索方法。同時，由于這些方法一般都比較直觀和易于理解，因而在實際應(yīng)用中常為人們所采用。下面我們介紹Powell方法。這個方法主要由所謂基本搜索、加速搜索和調(diào)整搜索方向三部分組成，具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點，個線性無關(guān)初始方向，組成初搜索方向組。給定終止誤差，令。2°進(jìn)行基本搜索。令，依次沿中的方向進(jìn)行一維搜索。對應(yīng)地得到輔助迭代點，即3°構(gòu)造加速方向。令，若，停止迭代，輸出。否則進(jìn)行4°。4°確定調(diào)整方向。按下式找出。若成立，進(jìn)行5°。否則，進(jìn)行6°。5°調(diào)整搜索方向組。令.同時，令，，轉(zhuǎn)2°。6°不調(diào)整搜索方向組。令，轉(zhuǎn)2°。2.4Matlab求無約束極值問題在Matlab工具箱中，用于求解無約束極值問題的函數(shù)有fminunc和fminsearch，用法介紹如下。求函數(shù)的極小值其中可以為標(biāo)量或向量。Matlab中fminunc的基本命令是[X,FVAL,EXITFLAG,OUTPUT,GRAD,HESSIAN]=FMINUNC(FUN,X0,OPTIONS,P1,P2,...)其中的返回值X是所求得的極小點，F(xiàn)VAL是函數(shù)的極小值，其它返回值的含義參見相關(guān)的幫助。FUN是一個M文件，當(dāng)FUN只有一個返回值時，它的返回值是函數(shù)；當(dāng)FUN有兩個返回值時，它的第二個返回值是的梯度向量；當(dāng)FUN有三個返回值時，它的第三個返回值是的二階導(dǎo)數(shù)陣（Hessian陣）。X0是向量的初始值，OPTIONS是優(yōu)化參數(shù)，可以使用確省參數(shù)。P1，P2是可以傳遞給FUN的一些參數(shù)。例6求函數(shù)的最小值。解：編寫M文件fun2.m如下：function[f,g]=fun2(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];在Matlab命令窗口輸入options=optimset('GradObj','on');fminunc('fun2',rand(1,2),options)即可求得函數(shù)的極小值。在求極值時，也可以利用上二階導(dǎo)數(shù)，編寫M文件fun3.m如下：function[f,df,d2f]=fun3(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;df=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];d2f=[-400*x(2)+1200*x(1)^2+2,-400*x(1)-400*x(1),200];在Matlab命令窗口輸入options=optimset('GradObj','on','Hessian','on');fminunc('fun3',rand(1,2),options)即可求得函數(shù)的極小值。求多元函數(shù)的極值也可以使用Matlab的fminsearch命令，其使用格式為：[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)例7求函數(shù)取最小值時的值。解編寫的M文件fun4.m如下：functionf=fun4(x);f=sin(x)+3;在命令窗口輸入x0=2;[x,y]=fminsearch(@fun4,x0)即求得在初值2附近的極小點及極小值?！?約束極值問題帶有約束條件的極值問題稱為約束極值問題，也叫規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡單問題的其它方法。庫恩—塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點為最優(yōu)點的必要條件，但一般說它并不是充分條件（對于凸規(guī)劃，它既是最優(yōu)點存在的必要條件，同時也是充分條件）。二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學(xué)模型可表述如下：這里是實對稱矩陣，是列向量，是相應(yīng)維數(shù)的矩陣。Matlab中求解二次規(guī)劃的命令是[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量，F(xiàn)VAL的返回值是目標(biāo)函數(shù)在X處的值。（具體細(xì)節(jié)可以參看在Matlab指令中運行helpquadprog后的幫助）。例8求解二次規(guī)劃解編寫如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))求得。罰函數(shù)法利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡記為

SUMT(SequentialUnconstrainedMinizationTechnique)。罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)作出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。主要有兩種形式，一種叫外罰函數(shù)法，另一種叫內(nèi)罰函數(shù)法，下面介紹外罰函數(shù)法?？紤]（NL）問題：s.t.取一個充分大的數(shù)，構(gòu)造函數(shù)（或這里，，，Matlab中可以直接利用、和sum函數(shù)。）則以增廣目標(biāo)函數(shù)為目標(biāo)函數(shù)的無約束極值問題的最優(yōu)解也是原問題的最優(yōu)解。例9求下列非線性規(guī)劃解(=1\*romani)編寫M文件test.mfunctiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)...+M*abs(-x(1)-x(2)^2+2);或者是利用Matlab的求矩陣的極小值和極大值函數(shù)編寫test.m如下：functiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*sum(min([x';zeros(1,2)]))-M*min(x(1)^2-x(2),0)...+M*abs(-x(1)-x(2)^2+2);我們也可以修改罰函數(shù)的定義，編寫test.m如下：functiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*min(min(x),0)-M*min(x(1)^2-x(2),0)+M*abs(-x(1)-x(2)^2+2);(=2\*romanii)在Matlab命令窗口輸入[x,y]=fminunc('test',rand(2,1))即可求得問題的解。3.3Matlab求約束極值問題在Matlab優(yōu)化工具箱中，用于求解約束最優(yōu)化問題的函數(shù)有：fminbnd、fmincon、quadprog、fseminf、fminimax，上面我們已經(jīng)介紹了函數(shù)fmincon和quadprog。3.3.1fminbnd函數(shù)求單變量非線性函數(shù)在區(qū)間上的極小值Matlab的命令為[X,FVAL]=FMINBND(FUN,x1,x2,OPTIONS)，它的返回值是極小點和函數(shù)的極小值。這里fun是用M文件定義的函數(shù)或Matlab中的單變量數(shù)學(xué)函數(shù)。例10求函數(shù)的最小值。解編寫M文件fun5.mfunctionf=fun5(x);f=(x-3)^2-1;在Matlab的命令窗口輸入[x,y]=fminbnd('fun5',0,5)即可求得極小點和極小值。3.3.2fseminf函數(shù)求其中都是向量函數(shù)；是附加的向量變量，的每個分量都限定在某個區(qū)間內(nèi)。上述問題的Matlab命令格式為X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)其中FUN用于定義目標(biāo)函數(shù)；X0為的初始值；NTHETA是半無窮約束的個數(shù)；函數(shù)SEMINFCON用于定義非線性不等式約束，非線性等式約束和半無窮約束的每一個分量函數(shù)，函數(shù)SEMINFCON有兩個輸入?yún)⒘縓和S，S是推薦的取樣步長，也許不被使用。例11求函數(shù)取最小值時的值,約束為：，解（1）編寫M文件fun6.m定義目標(biāo)函數(shù)如下：functionf=fun6(x,s);f=sum((x-0.5).^2);（2）編寫M文件fun7.m定義約束條件如下：function[c,ceq,k1,k2,s]=fun7(x,s);c=[];ceq=[];ifisnan(s(1,1))s=[0.2,0;0.20];end%取樣值w1=1:s(1,1):100;w2=1:s(2,1):100;%半無窮約束k1=sin(w1*x(1)).*cos(w1*x(2))-1/1000*(w1-50).^2-sin(w1*x(3))-x(3)-1;k2=sin(w2*x(2)).*cos(w2*x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;%畫出半無窮約束的圖形plot(w1,k1,'-',w2,k2,'+');（3）調(diào)用函數(shù)fseminf在Matlab的命令窗口輸入[x,y]=fseminf(@fun6,rand(3,1),2,@fun7)即可。3.3.3fminimax函數(shù)求解其中。上述問題的Matlab命令為X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)例12求函數(shù)族取極大極小值時的值。其中：解（1）編寫M文件fun8.m定義向量函數(shù)如下：functionf=fun8(x);f=[2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304-x(1)^2-3*x(2)^2x(1)+3*x(2)-18-x(1)-x(2)x(1)+x(2)-8];（2）調(diào)用函數(shù)fminimax[x,y]=fminimax(@fun8,rand(2,1))3.3.4利用梯度求解約束優(yōu)化問題例13已知函數(shù)，且滿足非線性約束：求分析：當(dāng)使用梯度求解上述問題時，效率更高并且結(jié)果更準(zhǔn)確。題目中目標(biāo)函數(shù)的梯度為：解（1）編寫M文件fun9.m定義目標(biāo)函數(shù)及梯度函數(shù)：function[f,df]=fun9(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);df=[exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+8*x(1)+6*x(2)+1);exp(x(1))*(4*x(2)+4*x(1)+2)];（2）編寫M文件fun10.m定義約束條件及約束條件的梯度函數(shù)：function[c,ceq,dc,dceq]=fun10(x);c=[x(1)*x(2)-x(1)-x(2)+1.5;-x(1)*x(2)-10];dc=[x(2)-1,-x(2);x(1)-1,-x(1)];ceq=[];dceq=[];（3）調(diào)用函數(shù)fmincon%采用標(biāo)準(zhǔn)算法options=optimset('largescale','off');%采用梯度options=optimset(options,'GradObj','on','GradConstr','on');[x,y]=fmincon(@fun9,rand(2,1),[],[],[],[],[],[],@fun10,options)§4飛行管理問題在約10，000m高空的某邊長160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行。區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)，以便進(jìn)行飛行管理。當(dāng)一架欲進(jìn)入該區(qū)域的飛機到達(dá)區(qū)域邊緣時，記錄其數(shù)據(jù)后，要立即計算并判斷是否會與區(qū)域內(nèi)的飛機發(fā)生碰撞。如果會碰撞，則應(yīng)計算如何調(diào)整各架（包括新進(jìn)入的）飛機飛行的方向角，以避免碰撞。現(xiàn)假定條件如下：1）不碰撞的標(biāo)準(zhǔn)為任意兩架飛機的距離大于8km;2）飛機飛行方向角調(diào)整的幅度不應(yīng)超過30度；3）所有飛機飛行速度均為每小時800km;4）進(jìn)入該區(qū)域的飛機在到達(dá)區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在60km以上；5）最多需考慮6架飛機；6）不必考慮飛機離開此區(qū)域后的狀況。請你對這個避免碰撞的飛行管理問題建立數(shù)學(xué)模型，列出計算步驟，對以下數(shù)據(jù)進(jìn)行計算（方向角誤差不超過0.01度），要求飛機飛行方向角調(diào)整的幅度盡量小。設(shè)該區(qū)域4個頂點的座標(biāo)為(0,0)，(160,0)，(160,160)，(0,160)。記錄數(shù)據(jù)為：飛機編號橫座標(biāo)縱座標(biāo)方向角（度）1150140243285852363150155220.54145501595130150230新進(jìn)入0052注：方向角指飛行方向與軸正向的夾角。試根據(jù)實際應(yīng)用背景對你的模型進(jìn)行評價與推廣。提示：，，其中為飛機的總架數(shù)，為時刻第架飛機的坐標(biāo)，分別表示第架飛機飛出正方形區(qū)域邊界的時刻。這里，，；，，；其中為飛機的速度，分別為第架飛機的初始方向角和調(diào)整后的方向角。令其中，則兩架飛機不碰撞的條件是。習(xí)題三1.用最速下降法（梯度法）求函數(shù)：的極大點。給定初始點。2.試用牛頓法求解：取初始點，并將采用變步長和采用固定步長時的情形做比較。3.某工廠向用戶提供發(fā)動機，按合同規(guī)定，其交貨數(shù)量和日期是：第一季度末交40臺，第二季末交60臺，第三季末交80臺。工廠的最大生產(chǎn)能力為每季100臺，每季的生產(chǎn)費用是（元），此處為該季生產(chǎn)發(fā)動機的臺數(shù)。若工廠生產(chǎn)的多，多余的發(fā)動機可移到下季向用戶交貨，這樣，工廠就需支付存貯費，每臺發(fā)動機每季的存貯費為4元。問該廠每季應(yīng)生產(chǎn)多少臺發(fā)動機，才能既滿足交貨合同，又使工廠所花費的費用最少（假定第一季度開始時發(fā)動機無存貨）。4.用Matlab的非線性規(guī)劃命令fmincon求解飛行管理問題。5.用罰函數(shù)法求解飛行管理問題。6.求下列問題的解s.t.第四章動態(tài)規(guī)劃§1引言1.1動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容動態(tài)規(guī)劃（dynamicprogramming）是運籌學(xué)的一個分支，是求解決策過程（decisionprocess）最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)性原理（principleofoptimality），把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法—動態(tài)規(guī)劃。1957年出版了他的名著《DynamicProgramming》，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進(jìn)行具體分析處理。因此，在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。例1最短路線問題下面是一個線路網(wǎng)，連線上的數(shù)字表示兩點之間的距離（或費用）。試尋求一條由到距離最短（或費用最?。┑穆肪€。例2生產(chǎn)計劃問題工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調(diào)查，市場對該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產(chǎn)品需付存儲費，每季每千件的存儲費為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一個生產(chǎn)計劃，即安排每個季度的產(chǎn)量，使一年的總費用（生產(chǎn)成本和存儲費）最少。1.2決策過程的分類根據(jù)過程的時間變量是離散的還是連續(xù)的，分為離散時間決策過程（discrete-timedecisionprocess）和連續(xù)時間決策過程（continuous-timedecisionprocess）；根據(jù)過程的演變是確定的還是隨機的，分為確定性決策過程（deterministicdecisionprocess）和隨機性決策過程（stochasticdecisionprocess），其中應(yīng)用最廣的是確定性多階段決策過程。§2基本概念、基本方程和計算方法2.1動態(tài)規(guī)劃的基本概念和基本方程一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。2.1.1階段階段(step)是對整個過程的自然劃分。通常根據(jù)時間順序或空間順序特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用表示。在例1中由出發(fā)為，由出發(fā)為，依此下去從出發(fā)為，共個階段。在例2中按照第一、二、三、四季度分為，共四個階段。2.1.2狀態(tài)狀態(tài)（state）表示每個階段開始時過程所處的自然狀況。它應(yīng)能描述過程的特征并且無后效性，即當(dāng)某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量（statevariable）。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用表示第階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用表示第階段的允許狀態(tài)集合。在例1中可取，或?qū)⒍x為，則或，而。 個階段的決策過程有個狀態(tài)變量，表示演變的結(jié)果。在例1中取，或定義為，即。根據(jù)過程演變的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計算的方便有時將連續(xù)變量離散化；為了分析的方便有時又將離散變量視為連續(xù)的。狀態(tài)變量簡稱為狀態(tài)。2.1.3決策當(dāng)一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策（decision），在最優(yōu)控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decisionvariable），變量允許取值的范圍稱允許決策集合（setofadmissibledecisions）。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡稱決策。2.1.4策略決策組成的序列稱為策略（policy）。由初始狀態(tài)開始的全過程的策略記作，即.由第階段的狀態(tài)開始到終止?fàn)顟B(tài)的后部子過程的策略記作，即，.類似地，由第到第階段的子過程的策略記作.可供選擇的策略有一定的范圍，稱為允許策略集合(setofadmissiblepolicies)，用表示。2.1.5.狀態(tài)轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程（equationofstatetransition）表示這種演變規(guī)律，寫作（1）在例1中狀態(tài)轉(zhuǎn)移方程為。2.1.6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)(objectivefunction)是衡量過程優(yōu)劣的數(shù)量指標(biāo)，它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)，用表示，。指標(biāo)函數(shù)應(yīng)具有可分離性，即可表為的函數(shù)，記為并且函數(shù)對于變量是嚴(yán)格單調(diào)的。過程在第階段的階段指標(biāo)取決于狀態(tài)和決策，用表示。指標(biāo)函數(shù)由組成，常見的形式有：階段指標(biāo)之和，即，階段指標(biāo)之積，即，階段指標(biāo)之極大（或極?。?，即.這些形式下第到第階段子過程的指標(biāo)函數(shù)為。根據(jù)狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)還可以表示為狀態(tài)和策略的函數(shù)，即。在給定時指標(biāo)函數(shù)對的最優(yōu)值稱為最優(yōu)值函數(shù)（optimalvaluefunction），記為，即，其中可根據(jù)具體情況取或。2.1.7最優(yōu)策略和最優(yōu)軌線使指標(biāo)函數(shù)達(dá)到最優(yōu)值的策略是從開始的后部子過程的最優(yōu)策略，記作。是全過程的最優(yōu)策略，簡稱最優(yōu)策略（optimalpolicy）。從初始狀態(tài)出發(fā)，過程按照和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列稱最優(yōu)軌線（optimaltrajectory）。2.1.8遞歸方程如下方程稱為遞歸方程（2）在上述方程中，當(dāng)為加法時??；當(dāng)為乘法時，取。動態(tài)規(guī)劃遞歸方程是動態(tài)規(guī)劃的最優(yōu)性原理的基礎(chǔ)，即：最優(yōu)策略的子策略，構(gòu)成最優(yōu)子策略。用狀態(tài)轉(zhuǎn)移方程（1）和遞歸方程（2）求解動態(tài)規(guī)劃的過程，是由逆推至，故這種解法稱為逆序解法。當(dāng)然，對某些動態(tài)規(guī)劃問題，也可采用順序解法。這時，狀態(tài)轉(zhuǎn)移方程和遞歸方程分別為：，縱上所述，如果一個問題能用動態(tài)規(guī)劃方法求解，那么，我們可以按下列步驟，首先建立起動態(tài)規(guī)劃的數(shù)學(xué)模型：（=1\*romani）將過程劃分成恰當(dāng)?shù)碾A段。（=2\*romanii）正確選擇狀態(tài)變量，使它既能描述過程的狀態(tài)，又滿足無后效性，同時確定允許狀態(tài)集合。（=3\*romaniii）選擇決策變量，確定允許決策集合。（=4\*romaniv）寫出狀態(tài)轉(zhuǎn)移方程。（=5\*romanv）確定階段指標(biāo)及指標(biāo)函數(shù)的形式（階段指標(biāo)之和，階段指標(biāo)之積，階段指標(biāo)之極大或極小等）。（=6\*romanvi）寫出基本方程即最優(yōu)值函數(shù)滿足的遞歸方程，以及端點條件?！?逆序解法的計算框圖以自由終端、固定始端、指標(biāo)函數(shù)取和的形式的逆序解法為例給出計算框圖，其它情況容易在這個基礎(chǔ)上修改得到。一般化的自由終端條件為(3)其中為已知。固定始端條件可表示為。如果狀態(tài)和決策是連續(xù)變量，用數(shù)值方法求解時需按照精度要求進(jìn)行離散化。設(shè)狀態(tài)的允許集合為.決策的允許集合為.狀態(tài)轉(zhuǎn)移方程和階段指標(biāo)應(yīng)對的每個取值和的每個取值計算，即，。最優(yōu)值函數(shù)應(yīng)對的每個取值計算?；痉匠炭梢员頌椋?）按照（3），（4）逆向計算出，為全過程的最優(yōu)值。記狀態(tài)的最優(yōu)決策為，由和按照狀態(tài)轉(zhuǎn)移方程計算出最優(yōu)狀態(tài)，記作。并得到相應(yīng)的最優(yōu)決策，記作。于是最優(yōu)策略為。算法程序的框圖如下。圖的左邊部分是函數(shù)序列的遞推計算，可輸出全過程最優(yōu)值，如果需要還可以輸出后部子過程最優(yōu)值函數(shù)序列和最優(yōu)決策序列。計算過程中存是備計算之用，在算完后可用將替換掉；存是備右邊部分讀之用。圖的右邊部分是最優(yōu)狀態(tài)和最優(yōu)決策序列的正向計算，可輸出最優(yōu)策略和最優(yōu)軌線?！?動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系動態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。動態(tài)規(guī)劃可以看作求決策使指標(biāo)函數(shù)達(dá)到最優(yōu)（最大或最小）的極值問題，狀態(tài)轉(zhuǎn)移方程、端點條件以及允許狀態(tài)集、允許決策集等是約束條件，原則上可以用非線性規(guī)劃方法求解。一些靜態(tài)規(guī)劃只要適當(dāng)引入階段變量、狀態(tài)、決策等就可以用動態(tài)規(guī)劃方法求解。下面用例子說明。例3用動態(tài)規(guī)劃解下列非線性規(guī)劃；s.t..其中為任意的已知函數(shù)。解按變量的序號劃分階段，看作段決策過程。設(shè)狀態(tài)為，取問題中的變量為決策。狀態(tài)轉(zhuǎn)移方程為取為階段指標(biāo)，最優(yōu)值函數(shù)的基本方程為（注意到）；；.按照逆序解法求出對應(yīng)于每個取值的最優(yōu)決策，計算至后即可利用狀態(tài)轉(zhuǎn)移方程得到最優(yōu)狀態(tài)序列和最優(yōu)決策序列。與靜態(tài)規(guī)劃相比，動態(tài)規(guī)劃的優(yōu)越性在于：（=1\*romani）能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求出全局最優(yōu)解。而動態(tài)規(guī)劃方法把全過程化為一系列結(jié)構(gòu)相似的子問題，每個子問題的變量個數(shù)大大減少，約束集合也簡單得多，易于得到全局最優(yōu)解。特別是對于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問題，可以對每個子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對于這類問題，動態(tài)規(guī)劃通常是求全局最優(yōu)解的唯一方法。（=2\*romanii）可以得到一族最優(yōu)解。與非線性規(guī)劃只能得到全過程的一個最優(yōu)解不同，動態(tài)規(guī)劃得到的是全過程及所有后部子過程的各個狀態(tài)的一族最優(yōu)解。有些實際問題需要這樣的解族，即使不需要，它們在分析最優(yōu)策略和最優(yōu)值對于狀態(tài)的穩(wěn)定性時也是很有用的。當(dāng)最優(yōu)策略由于某些原因不能實現(xiàn)時，這樣的解族可以用來尋找次優(yōu)策略。（=3\*romaniii）能夠利用經(jīng)驗提高求解效率。如果實際問題本身就是動態(tài)的，由于動態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動態(tài)特征，在計算中可以利用實際知識和經(jīng)驗提高求解效率。如在策略迭代法中，實際經(jīng)驗?zāi)軌驇椭x擇較好的初始策略，提高收斂速度。動態(tài)規(guī)劃的主要缺點是：（=1\*romani）沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個問題能否構(gòu)造動態(tài)規(guī)劃模型的準(zhǔn)則。這樣就只能對每類問題進(jìn)行具體分析，構(gòu)造具體的模型。對于較復(fù)雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應(yīng)用上的局限性。（=2\*romanii）用數(shù)值方法求解時存在維數(shù)災(zāi)（curseofdimensionality）。若一維狀態(tài)變量有個取值，那么對于維問題，狀態(tài)就有個值，對于每個狀態(tài)值都要計算、存儲函數(shù)，對于稍大（即使）的實際問題的計算往往是不現(xiàn)實的。目前還沒有克服維數(shù)災(zāi)的有效的一般方法?！?若干典型問題的動態(tài)規(guī)劃模型5.1最短路線問題對于例1一類最短路線問題（shortestPathProblem），階段按過程的演變劃分，狀態(tài)由各段的初始位置確定，決策為從各個狀態(tài)出發(fā)的走向，即有，階段指標(biāo)為相鄰兩段狀態(tài)間的距離，指標(biāo)函數(shù)為階段指標(biāo)之和，最優(yōu)值函數(shù)是由出發(fā)到終點的最短距離（或最小費用），基本方程為利用這個模型可以算出例l的最短路線為，相應(yīng)的最短距離為18。5.2生產(chǎn)計劃問題對于例2一類生產(chǎn)計劃問題（Productionplanningproblem），階段按計劃時間自然劃分，狀態(tài)定義為每階段開始時的儲存量，決策為每個階段的產(chǎn)量，記每個階段的需求量（已知量）為，則狀態(tài)轉(zhuǎn)移方程為(5)設(shè)每階段開工的固定成本費為，生產(chǎn)單位數(shù)量產(chǎn)品的成本費為，每階段單位數(shù)量產(chǎn)品的儲存費為，階段指標(biāo)為階段的生產(chǎn)成本和儲存費之和，即(6)指標(biāo)函數(shù)為之和。最優(yōu)值函數(shù)為從第段的狀態(tài)出發(fā)到過程終結(jié)的最小費用，滿足其中允許決策集合由每階段的最大生產(chǎn)能力決定。若設(shè)過程終結(jié)時允許存儲量為，則終端條件是（7）（5）~（7）構(gòu)成該問題的動態(tài)規(guī)劃模型。5.3資源分配問題一種或幾種資源（包括資金）分配給若干用戶，或投資于幾家企業(yè)，以獲得最大的效益。資源分配問題（resourceallocatingProblem）可以是多階段決策過程，也可以是靜態(tài)規(guī)劃問題，都能構(gòu)造動態(tài)規(guī)劃模型求解。下面舉例說明。例4機器可以在高、低兩種負(fù)荷下生產(chǎn)。臺機器在高負(fù)荷下的年產(chǎn)量是，在低負(fù)荷下的年產(chǎn)量是，高、低負(fù)荷下機器的年損耗率分別是和（）?，F(xiàn)有臺機器，要安排一個年的負(fù)荷分配計劃，即每年初決定多少臺機器投入高、低負(fù)荷運行，使年的總產(chǎn)量最大。如果進(jìn)一步假設(shè)，（），即高、低負(fù)荷下每臺機器的年產(chǎn)量分別為和，結(jié)果將有什么特點。解年度為階段變量。狀態(tài)為第年初完好的機器數(shù)，決策為第年投入高負(fù)荷運行的臺數(shù)。當(dāng)或不是整數(shù)時，將小數(shù)部分理解為一年中正常工作時間或投入高負(fù)荷運行時間的比例。機器在高、低負(fù)荷下的年完好率分別記為和，則，，有。因為第年投入低負(fù)荷運行的機器臺數(shù)為，所以狀態(tài)轉(zhuǎn)移方程是（8）階段指標(biāo)是第年的產(chǎn)量，有（9）指標(biāo)函數(shù)是階段指標(biāo)之和，最優(yōu)值函數(shù)滿足(10)及自由終端條件（11）當(dāng)中的用較簡單的函數(shù)表達(dá)式給出時，對于每個可以用解析方法求解極值問題。特別，若，，（10）中的將是的線性函數(shù)，最大值點必在區(qū)間的左端點或右端點取得，即每年初將完好的機器全部投入低負(fù)荷或高負(fù)荷運行?！?具體的應(yīng)用實例例5設(shè)某工廠有1000臺機器，生產(chǎn)兩種產(chǎn)品，若投入臺機器生產(chǎn)產(chǎn)品，則純收入為，若投入臺機器生產(chǎn)種產(chǎn)品，則純收入為，又知：生產(chǎn)種產(chǎn)品機器的年折損率為20%，生產(chǎn)產(chǎn)品機器的年折損率為10%，問在5年內(nèi)如何安排各年度的生產(chǎn)計劃，才能使總收入最高？解年度為階段變量。令表示第年初完好機器數(shù)，表示第年安排生產(chǎn)種產(chǎn)品的機器數(shù)，則為第年安排生產(chǎn)種產(chǎn)品的機器數(shù)，且。則第年初完好的機器數(shù)（12）令表示第年的純收入，表示第年初往后各年的最大利潤之和。顯然（13）則（14）（1）時，由（13）、（14）式得關(guān)于求導(dǎo)，知其導(dǎo)數(shù)大于零，所以在等于處取得最大值，即時，。（2）時，由（12）、（14）式得當(dāng)時，（3）時，當(dāng)時，（4）時，當(dāng)時，。（5）時，當(dāng)時，。因為（臺）所以由（12）式，進(jìn)行回代得（臺）（臺）（臺）（臺）注：臺中的0.4臺應(yīng)理解為有一臺機器只能使用0.4年將報廢。求解下面問題解：按問題的變量個數(shù)劃分階段，把它看作為一個三階段決策問題。設(shè)狀態(tài)變量為，并記；取問題中的變量為決策變量；各階段指標(biāo)函數(shù)按乘積方式結(jié)合。令最優(yōu)值函數(shù)表示第階段的初始狀態(tài)為，從階段到3階段所得到的最大值。設(shè)，，則有，，用逆推解法，從后向前依次有及最優(yōu)解由，得和（舍去）又，而，故為極大值點。所以及最優(yōu)解。同樣利用微分法易知，最優(yōu)解。由于已知，因而按計算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。即，由所以，由所以，因此得到最優(yōu)解為：，，；最大值為：。習(xí)題四1.用Matlab編程求例5的解。2.有四個工人，要指派他們分別完成4項工作，每人做各項工作所消耗的時間如下表：工作工人甲乙丙丁15192619182317212122162324181917問指派哪個人去完成哪項工作，可使總的消耗時間為最??？試對此問題用動態(tài)規(guī)劃方法求解。3.為保證某一設(shè)備的正常運轉(zhuǎn)，需備有三種不同的零件。若增加備用零件的數(shù)量，可提高設(shè)備正常運轉(zhuǎn)的可靠性，但增加了費用，而投資額僅為8000元。已知備用零件數(shù)與它的可靠性和費用的關(guān)系如下表所示。備件數(shù)增加的可靠性設(shè)備的費用（千元）0.30.40.50.20.50.90.10.20.7123356234現(xiàn)要求在既不超出投資額的限制，又能盡量提高設(shè)備運轉(zhuǎn)的可靠性的條件下，問各種零件的備件數(shù)量應(yīng)是多少為好？4.某工廠購進(jìn)100臺機器，準(zhǔn)備生產(chǎn)=1\*ROMANI、=2\*ROMANII兩種產(chǎn)品，若生產(chǎn)產(chǎn)品=1\*ROMANI，每臺機器每年可收入45萬元，損壞率為65％；若生產(chǎn)產(chǎn)品=2\*ROMANII，每臺機器每年收入為35萬元，損壞率為35％，估計三年后將有新型機器出現(xiàn)，舊的機器將全部淘汰。試問每年應(yīng)如何安排生產(chǎn)，使在三年內(nèi)收入最多？第六章排隊論模型排隊論起源于1909年丹麥電話工程師A.K．愛爾朗的工作，他對電話通話擁擠問題進(jìn)行了研究。1917年，愛爾朗發(fā)表了他的著名的文章—“自動電話交換中的概率理論的幾個問題的解決”。排隊論已廣泛應(yīng)用于解決軍事、運輸、維修、生產(chǎn)、服務(wù)、庫存、醫(yī)療衛(wèi)生、教育、水利灌溉之類的排隊系統(tǒng)的問題，顯示了強大的生命力。排隊是在日常生活中經(jīng)常遇到的現(xiàn)象，如顧客到商店購買物品、病人到醫(yī)院看病常常要排隊。此時要求服務(wù)的數(shù)量超過服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員等）的容量。也就是說，到達(dá)的顧客不能立即得到服務(wù)，因而出現(xiàn)了排隊現(xiàn)象。這種現(xiàn)象不僅在個人日常生活中出現(xiàn)，電話局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏導(dǎo)，故障機器的停機待修，水庫的存貯調(diào)節(jié)等都是有形或無形的排隊現(xiàn)象。由于顧客到達(dá)和服務(wù)時間的隨機性?？梢哉f排隊現(xiàn)象幾乎是不可避免的。排隊論（QueuingTheory）也稱隨機服務(wù)系統(tǒng)理論，就是為解決上述問題而發(fā)展的一門學(xué)科。它研究的內(nèi)容有下列三部分：（=1\*romani）性態(tài)問題，即研究各種排隊系統(tǒng)的概率規(guī)律性，主要是研究隊長分布、等待時間分布和忙期分布等，包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。（=2\*romanii）最優(yōu)化問題，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設(shè)計。后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營。（=3\*romaniii）排隊系統(tǒng)的統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合于那種模型，以便根據(jù)排隊理論進(jìn)行分析研究。這里將介紹排隊論的一些基本知識，分析幾個常見的排隊模型?！?基本概念1.1排隊過程的一般表示下圖是排隊論的一般模型。服務(wù)機構(gòu)（服務(wù)時間隨機）顧客排隊顧客隨機達(dá)到顧客離去服務(wù)機構(gòu)（服務(wù)時間隨機）顧客排隊圖中虛線所包含的部分為排隊系統(tǒng)。各個顧客從顧客源出發(fā)，隨機地來到服務(wù)機構(gòu)，按一定的排隊規(guī)則等待服務(wù)，直到按一定的服務(wù)規(guī)則接受完服務(wù)后離開排隊系統(tǒng)。凡要求服務(wù)的對象統(tǒng)稱為顧客，為顧客服務(wù)的人或物稱為服務(wù)員，由顧客和服務(wù)員組成服務(wù)系統(tǒng)。對于一個服務(wù)系統(tǒng)來說，如果服務(wù)機構(gòu)過小，以致不能滿足要求服務(wù)的眾多顧客的需要，那么就會產(chǎn)生擁擠現(xiàn)象而使服務(wù)質(zhì)量降低。因此，顧客總希望服務(wù)機構(gòu)越大越好，但是，如果服務(wù)機構(gòu)過大，人力和物力方面的開支也就相應(yīng)增加，從而會造成浪費，因此研究排隊模型的目的就是要在顧客需要和服務(wù)機構(gòu)的規(guī)模之間進(jìn)行權(quán)衡決策，使其達(dá)到合理的平衡。1.2排隊系統(tǒng)的組成和特征一般的排隊過程都由輸入過程、排隊規(guī)則、服務(wù)過程三部分組成，現(xiàn)分述如下：1.2.1輸入過程輸入過程是指顧客到來時間的規(guī)律性，可能有下列不同情況：（=1\*romani）顧客的組成可能是有限的，也可能是無限的。（=2\*romanii）顧客到達(dá)的方式可能是一個—個的，也可能是成批的。（=3\*romaniii）顧客到達(dá)可以是相互獨立的，即以前的到達(dá)情況對以后的到達(dá)沒有影響；否則是相關(guān)的。（=4\*romaniv）輸入過程可以是平穩(wěn)的，即相繼到達(dá)的間隔時間分布及其數(shù)學(xué)期望、方差等數(shù)字特征都與時間無關(guān)，否則是非平穩(wěn)的。1.2.2排隊規(guī)則排隊規(guī)則指到達(dá)排隊系統(tǒng)的顧客按怎樣的規(guī)則排隊等待，可分為損失制，等待制和混合制三種。（=1\*romani）損失制（消失制）。當(dāng)顧客到達(dá)時，所有的服務(wù)臺均被占用，顧客隨即離去。（=2\*romanii）等待制。當(dāng)顧客到達(dá)時，所有的服務(wù)臺均被占用，顧客就排隊等待，直到接受完服務(wù)才離去。例如出故障的機器排隊等待維修就是這種情況。（=3\*romaniii）混合制。介于損失制和等待制之間的是混合制，即既有等待又有損失。有隊列長度有限和排隊等待時間有限兩種情況，在限度以內(nèi)就排隊等待，超過一定限度就離去。排隊方式還分為單列、多列和循環(huán)隊列。1.2.3服務(wù)過程（=1\*romani）服務(wù)機構(gòu)。主要有以下幾種類型：單服務(wù)臺；多服務(wù)臺并聯(lián)（每個服務(wù)臺同時為不同顧客服務(wù)）；多服務(wù)臺串聯(lián)（多服務(wù)臺依次為同一顧客服務(wù)）；混合型。（=2\*romanii）服務(wù)規(guī)則。按為顧客服務(wù)的次序采用以下幾種規(guī)則：①先到先服務(wù)，這是通常的情形。②后到先服務(wù)，如情報系統(tǒng)中，最后到的情報信息往往最有價值，因而常被優(yōu)先處理。③隨機服務(wù)，服務(wù)臺從等待的顧客中隨機地取其一進(jìn)行服務(wù)，而不管到達(dá)的先后。④優(yōu)先服務(wù)，如醫(yī)療系統(tǒng)對病情嚴(yán)重的病人給予優(yōu)先治療。1.3排隊模型的符號表示排隊模型用六個符號表示，在符號之間用斜線隔開，即。第一個符號表示顧客到達(dá)流或顧客到達(dá)間隔時間的分布；第二個符號表示服務(wù)時間的分布；第三個符號表示服務(wù)臺數(shù)目；第四個符號是系統(tǒng)容量限制；第五個符號是顧客源數(shù)目；第六個符號是服務(wù)規(guī)則，如先到先服務(wù)FCFS，后到先服務(wù)LCFS等。并約定，如略去后三項，即指的情形。我們只討論先到先服務(wù)FCFS的情形，所以略去第六項。表示顧客到達(dá)間隔時間和服務(wù)時間的分布的約定符號為：—指數(shù)分布（是Markov的字頭，因為指數(shù)分布具有無記憶性，即Markov性）；—確定型（Deterministic）；—階愛爾朗(Erlang)分布；—一般（general）服務(wù)時間的分布；—一般相互獨立（GeneralIndependent）的時間間隔的分布。例如，表示相繼到達(dá)間隔時間為指數(shù)分布、服務(wù)時間為指數(shù)分布、單服務(wù)臺、等待制系統(tǒng)。表示確定的到達(dá)時間、服務(wù)時間為指數(shù)分布、個平行服務(wù)臺（但顧客是一隊）的模型。1.4排隊系統(tǒng)的運行指標(biāo)為了研究排隊系統(tǒng)運行的效率，估計其服務(wù)質(zhì)量，確定系統(tǒng)的最優(yōu)參數(shù)，評價系統(tǒng)的結(jié)構(gòu)是否合理并研究其改進(jìn)的措施，必須確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標(biāo)，這些數(shù)量指標(biāo)通常是：(=1\*romani)平均隊長：指系統(tǒng)內(nèi)顧客數(shù)（包括正被服務(wù)的顧客與排隊等待服務(wù)的顧客）的數(shù)學(xué)期望，記作。(=2\*romanii)平均排隊長:指系統(tǒng)內(nèi)等待服務(wù)的顧客數(shù)的數(shù)學(xué)期望，記作。(=3\*romaniii)平均逗留時間：顧客在系統(tǒng)內(nèi)逗留時間（包括排隊等待的時間和接受服務(wù)的時間）的數(shù)學(xué)期望，記作。（=4\*romaniv）平均等待時間：指一個顧客在排隊系統(tǒng)中排隊等待時間的數(shù)學(xué)期望，記作。（=5\*romanv）平均忙期：指服務(wù)機構(gòu)連續(xù)繁忙時間（顧客到達(dá)空閑服務(wù)機構(gòu)起，到服務(wù)機構(gòu)再次空閑止的時間）長度的數(shù)學(xué)期望，記為。還有由于顧客被拒絕而使企業(yè)受到損失的損失率以及以后經(jīng)常遇到的服務(wù)強度等，這些都是很重要的指標(biāo)。計算這些指標(biāo)的基礎(chǔ)是表達(dá)系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)的狀態(tài)即指系統(tǒng)中顧客數(shù)，如果系統(tǒng)中有個顧客就說系統(tǒng)的狀態(tài)是，它的可能值是（=1\*romani）隊長沒有限制時，，（=2\*romanii）隊長有限制，最大數(shù)為時，，（=3\*romaniii）損失制，服務(wù)臺個數(shù)是時，。這些狀態(tài)的概率一般是隨時刻而變化，所以在時刻、系統(tǒng)狀態(tài)為的概率用表示。穩(wěn)態(tài)時系統(tǒng)狀態(tài)為的概率用表示?！?輸入過程與服務(wù)時間的分布排隊系統(tǒng)中的事件流包括顧客到達(dá)流和服務(wù)時間流。由于顧客到達(dá)的間隔時間和服務(wù)時間不可能是負(fù)值，因此，它的分布是非負(fù)隨機變量的分布。最常用的分布有泊松分布、確定型分布，指數(shù)分布和愛爾朗分布。2.1泊松流與指數(shù)分布設(shè)表示在時間區(qū)間內(nèi)到達(dá)的顧客數(shù)（），令表示在時間區(qū)間內(nèi)有個顧客到達(dá)的概率，即當(dāng)合于下列三個條件時，我們說顧客的到達(dá)形成泊松流。這三個條件是：1o在不相重疊的時間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨立的，我們稱這性質(zhì)為無后效性。2o對充分小的，在時間區(qū)間內(nèi)有一個顧客到達(dá)的概率與無關(guān)，而約與區(qū)間長成正比，即（1）其中，當(dāng)時，是關(guān)于的高階無窮小。是常數(shù)，它表示單位時間有一個顧客到達(dá)的概率，稱為概率強度。3o對于充分小的，在時間區(qū)間內(nèi)有兩個或兩個以上顧客到達(dá)的概率極小，以致可以忽略，即（2）在上述條件下，我們研究顧客到達(dá)數(shù)的概率分布。由條件2o，我們總可以取時間由0算起，并簡記。由條件1o和2o，有由條件2o和3o得因而有，.在以上兩式中，取趨于零的極限，當(dāng)假設(shè)所涉及的函數(shù)可導(dǎo)時，得到以下微分方程組：，.取初值，，容易解出；再令，可以得到及其它所滿足的微分方程組，即，.由此容易解得.正如在概率論中所學(xué)過的，我們說隨機變量服從泊松分布。它的數(shù)學(xué)期望和方差分別是；。當(dāng)輸入過程是泊松流時，那么顧客相繼到達(dá)的時間間隔必服從指數(shù)分布。這是由于內(nèi)呼叫次數(shù)為零那么，以表示的分布函數(shù)，則有而分布密度函數(shù)為.對于泊松流,表示單位時間平均到達(dá)的顧客數(shù),所以就表示相繼顧客到達(dá)平均間隔時間，而這正和的意義相符。對一顧客的服務(wù)時間也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，有時也服從指數(shù)分布。這時設(shè)它的分布函數(shù)和密度函數(shù)分別是，我們得到這表明，在任何小的時間間隔內(nèi)一個顧客被服務(wù)完了（離去）的概率是。表示單位時間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率，而表示一個顧客的平均服務(wù)時間。2.2常用的幾種概率分布及其產(chǎn)生2.2.1常用的連續(xù)型概率分布我們只給出這些分布的參數(shù)、記號和通常的應(yīng)用范圍，更詳細(xì)的內(nèi)容參看專門的概率論書籍。（=1\*romani）均勻分布區(qū)間內(nèi)的均勻分布記作。服從分布的隨機變量又稱為隨機數(shù)，它是產(chǎn)生其它隨機變量的基礎(chǔ)。如若為分布，則服從。（=2\*romanii）正態(tài)分布以為期望，為方差的正態(tài)分布記作。正態(tài)分布的應(yīng)用十分廣泛。正態(tài)分布還可以作為二項分布一定條件下的近似。（=3\*romaniii）指數(shù)分布指數(shù)分布是單參數(shù)的非對稱分布，記作，概率密度函數(shù)為：它的數(shù)學(xué)期望為，方差為。指數(shù)分布是唯一具有無記憶性的連續(xù)型隨機變量，即有，在排隊論、可靠性分析中有廣泛應(yīng)用。（=4\*romaniv）Gamma分布Gamma分布是雙參數(shù)的非對稱分布，記作，期望是。時蛻化為指數(shù)分布。個相互獨立、同分布（參數(shù)）的指數(shù)分布之和是Gamma分布（。Gamma分布可用于服務(wù)時間，零件壽命等。Gamma分布又稱愛爾朗分布。（=5\*romanv）Weibull分布Weibull分布是雙參數(shù)的非對稱分布，記作。時蛻化為指數(shù)分布。作為設(shè)備、零件的壽命分布在可靠性分析中有著非常廣泛的應(yīng)用。（=6\*romanvi）Beta分布Beta分布是區(qū)間內(nèi)的雙參數(shù)、非均勻分布，記作。2.2.2常用的離散型概率分布（=1\*romani）離散均勻分布（=2\*romanii）Bernoulli分布（兩點分布）Bernoulli分布是處取值的概率分別是和的兩點分布，記作。用于基本的離散模型。（=3\*romaniii）泊松（Poisson）分布泊松分布與指數(shù)分布有密切的關(guān)系。當(dāng)顧客平均到達(dá)率為常數(shù)的到達(dá)間隔服從指數(shù)分布時，單位時間內(nèi)到達(dá)的顧客數(shù)服從泊松分布，即單位時間內(nèi)到達(dá)位顧客的概率為記作。反過來也是這樣。泊松分布在排隊服務(wù)、產(chǎn)品檢驗、生物與醫(yī)學(xué)統(tǒng)計、天文、物理等領(lǐng)域都有廣泛應(yīng)用。（=4\*romaniv）二項分布在獨立進(jìn)行的每次試驗中，某事件發(fā)生的概率為，則次試驗中該事件發(fā)生的次數(shù)服從二項分布，即發(fā)生次的概率為.記作。二項分布是個獨立的Bernoulli分布之和。它在產(chǎn)品檢驗、保險、生物和醫(yī)學(xué)統(tǒng)計等領(lǐng)域有著廣泛的應(yīng)用。當(dāng)