最優(yōu)化方法簡(jiǎn)明教程—centre.doc

華中科技大學(xué)學(xué)習(xí)筆記系列 作者：centre 1 圖與網(wǎng) 破圈法：任取一個(gè)圈，去掉一條權(quán)最大的邊，直到最小樹(shù)。 避圈法：選最小權(quán)的邊，避圈前進(jìn)，直到最小樹(shù)。 最短路算法：Dijkstra法：從Vs給定P標(biāo)號(hào)T標(biāo)號(hào)標(biāo)號(hào)（T標(biāo)號(hào)變?yōu)镻標(biāo)號(hào)標(biāo)號(hào)記位置）反向追蹤：列表，d1(V1,Vj)dk(V1,Vj)=min(ij+dk(V1,Vi)據(jù)最小權(quán)反向追蹤 網(wǎng)絡(luò)優(yōu)化：最小截集最大流：找到最小截集（弧的集合）標(biāo)號(hào)法：開(kāi)始，為的標(biāo)號(hào)，最小費(fèi)用最大流：郵遞員問(wèn)題：通過(guò)消滅奇點(diǎn)，找歐拉回路 網(wǎng)絡(luò)計(jì)劃圖：最早開(kāi)始最晚開(kāi)始機(jī)動(dòng)時(shí)間最早結(jié)束最晚結(jié)束自由時(shí)差工期優(yōu)化：人力，費(fèi)用，工期優(yōu)化。費(fèi)用率=（最短時(shí)間費(fèi)用-正常時(shí)間費(fèi)用）/（正常時(shí)間-最短時(shí)間）2 排隊(duì)論（保證服務(wù)質(zhì)量，又減少費(fèi)用）顧客源（排隊(duì)規(guī)則）隊(duì)列（服務(wù)規(guī)則）服務(wù)機(jī)構(gòu)離去服務(wù)規(guī)則：FCFS，LCFS，隨機(jī)服務(wù)，PRM(顧客到達(dá))|A(服務(wù)時(shí)間)|1(服務(wù)臺(tái)數(shù))|（容量）|（顧客源）N(t)隊(duì)長(zhǎng)Nq(t)排隊(duì)長(zhǎng)T(t)顧客逗留時(shí)間Tq(t)顧客等待時(shí)間L平均隊(duì)長(zhǎng)Lq平均等待隊(duì)長(zhǎng)W平均逗留時(shí)間Wq平均等待時(shí)間R為系統(tǒng)利用率 泊松流(M)：無(wú)后效性；平穩(wěn)性；單個(gè)性；P1(t,t+t)=t+o(t)；o(t)=Pn(t,t+t);E=D=t（t時(shí)刻n個(gè)顧客的概率） 負(fù)指數(shù)分布(M)：無(wú)記憶性(P(Tt+s/ts)=P(Tt);0,t)至少到達(dá)一個(gè)顧客1-P0(t）=1-e-t,t0 愛(ài)爾朗分布(EK)：（相當(dāng)于泊松流到達(dá)后被k個(gè)服務(wù)臺(tái)均分顧客形成）(其中，t0,E(T)=1/,Var(T)=1/2k）K=1為M，k=定長(zhǎng)分布D,k30正態(tài)分布近似 G表示一般相互獨(dú)立的隨機(jī)分布Little 公式：（四者知一即可） r服務(wù)率：=/(為到達(dá)為服務(wù))排隊(duì)系統(tǒng)分析： M|M|1|（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） 空閑：P0=1-.有k個(gè)顧客：Pk=（1-）k. L=（1-） M|M|1|N|（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） P0=(1-)/(1-)N+1.Pk=(1-)k/(1-)N+1. L=（1-）-(N+1)N+1/(1-)N+1 M|M|1|m（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） P0=1/nm!/(m-i)!.Pk=m!/(m-k)!/m!/(m-i)!. L=m-(1-P)/ M|M|c|（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布）s=/c=/c，Lq=()CsP0/c!(1-s)2. M|M|c|N|（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） M|M|c|m（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布）其中， M|G|1（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） M|D|1（到達(dá)服從泊松過(guò)程，服務(wù)服從負(fù)指數(shù)分布） M|M|1（最優(yōu)服務(wù)率）& M|M|C（最優(yōu)服務(wù)臺(tái)數(shù)C）Z(c*)z(c*-1)&Z(c*)z(c*+1)3 存儲(chǔ)論存儲(chǔ)費(fèi)用，訂貨費(fèi)用，生產(chǎn)費(fèi)用，缺貨費(fèi)用 經(jīng)濟(jì)訂購(gòu)批量： 不允許缺貨，備貨快：C(t)=C3/t+kR+C1Rt/2;dC/dt=0t0=sqrt(2C3/C1R),Q0=Rt0. 允許缺貨，備貨快:C(t)=C3/t+C1(P-R)Tt/2t;dC/dt=0t0=sqrt(2C3P/C1R(P-R),Q0=Rt0. 允許缺貨，生產(chǎn)需要時(shí)間：C(t,S)=(C3+S2C1/2R+(Rt-S)2C2/2R)/t;dC/dt=dC/dS=0t0=sqrt(2C3(C1+ C2)/C1R(P-R),S0=sqrt(2C3C2R/C1(C1+C2),Q0=Rt0. 需求隨機(jī)離散：C(Q)C(Q+1)，C(Q)C(Q-1)P(r)k/(k+h)P(r) 需求隨機(jī)連續(xù)：E(C(Q)=P(r-Q)(r)dr+C1(Q-r)(r)dr+kQdE/dQ=0F(Q)=(r)dr=(P-k)/(C1+P)C2P時(shí)，F(xiàn)(Q)=(C2-k)/(C1+C2) （s,S）型存儲(chǔ)策略： 需求為連續(xù)的隨機(jī)變量（貨物成本K/單位，存儲(chǔ)費(fèi)C1/單位，缺貨費(fèi)C2/單位，訂購(gòu)費(fèi)C3/單位，需求密度（r）,S=I+Q，其中I表示原始積累，Q表示進(jìn)貨數(shù)量）C(S)=C3+KQ+C1(S-r)（r）dr+C2(r-S)（r）drC(S)=0 （r）dr=(C2-K)/(C1+C2)查表可得S 需求為離散的隨機(jī)變量C(S)=C3+KQ+C1(S-r)（r）dr+C2(r-S)（r）drC(Si+1)C(Si)&C(Si)C(Si-1)求得S 需求備貨時(shí)間都隨機(jī)離散：（t時(shí)間內(nèi)需求量r隨機(jī)t（r），t時(shí)間內(nèi)平均需求為t,備貨時(shí)間x隨機(jī)，概率為p(x),存儲(chǔ)費(fèi)C1/單位.年，缺貨費(fèi)C2/單位.階段，訂購(gòu)費(fèi)C3，年需求D，緩沖存量B）先通過(guò)確定性模型求Q0=E.O.Q=,N0=(每年訂購(gòu)N0次每次訂Q0)L=+B,PL=p(x)FX(L)則：C(L,B)=(B+Q0/2)C1+PLC2PL.求極值4 決策論（單目標(biāo)決策） 戰(zhàn)略決策(全局性，長(zhǎng)遠(yuǎn)問(wèn)題)、策略決策(為完成目標(biāo)而定)、執(zhí)行決策(執(zhí)行方案選擇)；定量決策、定性決策；確定型決策、風(fēng)險(xiǎn)決策、不確定型決策；單項(xiàng)決策、貫序決策；程序決策(可重復(fù)，有章可循)、非程序決策(憑直覺(jué)應(yīng)變) 面向過(guò)程（預(yù)決策決策決策后）面向結(jié)果(確定目標(biāo)收集信息提出方案方案選優(yōu)決策) 不確定型決策：n 悲觀主義準(zhǔn)則：(aij)n 樂(lè)觀主義準(zhǔn)則：(aij)n 等可能準(zhǔn)則：(E(Si)n 最小機(jī)會(huì)準(zhǔn)則：(aik)n 折中主義準(zhǔn)則：Hi=aimax+(1-)aimin。 風(fēng)險(xiǎn)決策：n EMV:Pjaij(適用于以此決策多次重復(fù)進(jìn)行)n EOL:Pjaij(EOLi+EMVi=K表明決策結(jié)果一致)n EVPI:EPPL-EMV*=EVPI0(滿足此條件時(shí)沒(méi)白花錢(qián)) 主觀概率：直接估計(jì)法：要求參加者直接給出概率間接軌跡法：參加者通過(guò)排隊(duì)或相互比較等給出概率 修正概率方法：貝葉斯公式先由過(guò)去的經(jīng)驗(yàn)或?qū)＜夜烙?jì)獲得事前概率；再調(diào)查得條件概率；由貝葉斯公式得到時(shí)候概率：P(Bi/A)=P(Bi)P(A/Bi)/P(Bi)P(A/Bi) 效用理論：將要考慮的因素都折合為效用值，選綜合效用值最大的方案。直接提問(wèn)法、對(duì)比提問(wèn)法得到效用值，再用效用曲線進(jìn)行擬合。 靈敏度分析：轉(zhuǎn)折概率P=(a12-a22)/(a12-a22+a21-a11)5 對(duì)策論 G=S1,S2;A為矩陣對(duì)策，S1=1m，S2=1n,A=(aij)mn, if aij=aij=ai*j* 記VG=ai*j*則VG為G的值，(i*,j*)為G在純策略意義下的解，i*，j*分別為的最優(yōu)化策略。 G=S1,S2;A純策略意義有解純局勢(shì)(i*,j*),ST aij*ai*j*ai*j. ai*j*是矩陣A的一個(gè)鞍點(diǎn)。 f(x,y),xA,yB,IFx*A,y*BxA,yB,有f(x,y*)f(x*,y*)f(x*,y)則(x*,y*)為f的一個(gè)鞍點(diǎn)。 無(wú)差別性，可交換性（對(duì)于鞍點(diǎn)的橫坐標(biāo)與縱坐標(biāo)） 混合策略：G=S1,S2;A記S1*=xEm|xi0,i=1m,xi=1，S2*=xEn|yj0,i=1n,yj=1，S1*，S2*分別為的混合策略集.的贏得函數(shù)E(x,y)=XAY:保證自己贏的期望值不少于v1=E(x,y)保證自己失的期望值最多為v2=E(x,y)v1v2. G*=S1*,S2*;E是G=S1,S2;A的混合擴(kuò)充,if v1=v2,記vG,為對(duì)策G*的值.(x*,y*)為G在混合策略意義下的解，x*,y*分別為的最優(yōu)混合策略。 G=S1,S2;A混合策略意義下有解x*S1*，y*S2* ST E(x,y*)E(x*,y*)E(x*,y) 基本定理： 記E(i,y)=yj,E(x,j)=xi,則E(x,y)=xiyj= E(i,y)xj =E(x,j)yi. (x*,y*)是G的解i,j,E(i,y*)E(x*,y*)E(x*,j) v ST,x*,y*分別是下列方程組的解且v=vG.xiv,j=1n yjv,j=1mxi=1 yj=1xi0,i=1m yj0,i=1m G=S1,S2;A一定存在混合策略意義下的解（證:上述方程組互為對(duì)偶的線性規(guī)劃，分別存在最優(yōu)解(x*,v*)(y*,v*)） 定理：(x*,y*)是G的解，v=vG則If,xi*0,then yj*=v;Ifyj*0,then xi*=v;Ifxi*v,thenyj*0 運(yùn)算：G1=S1,S2;(aij) G2=S1,S2;(aij+L)則vG2=vG1+L,T（G1）=T（G2）. G2=S1,S2;(aij)則vG2=vG1,T（G1）=T