最優(yōu)化方法簡明教程

爹9?w’華中科技大學(xué).?????學(xué)習(xí)筆記系列 作者：centre圖與網(wǎng)=破圈法：任取一個圈，去掉一條權(quán)最大的邊，直到最小樹。=避圈法：選限小權(quán)的邊，避圈前進(jìn)，直到最小樹。n最短路算法：Dijkstra法：從Vs給定P標(biāo)號T標(biāo)號入標(biāo)號（T標(biāo)號變?yōu)镻標(biāo)號入標(biāo)號記位置）反向追蹤：列表，di（V1,Vj）^dk（V1,Vj）=min（wij+dk（V1,Vi））據(jù)最小權(quán)反向追蹤n網(wǎng)絡(luò)優(yōu)化：最小截集最大流：找到最小截集（弧的集合）標(biāo)號法：開始，為的標(biāo)號，最小費用最大流：郵遞員問題：通過消滅奇點，找歐拉回路n網(wǎng)絡(luò)計劃圖：最早開始 最晚開始機動時間最早結(jié)束 最晚結(jié)束自由時差工期優(yōu)化：人力，費用，工期優(yōu)化。費用率=（最短時間費用-正常時間費用）/（正常時間-最短時間）排隊論（保證服務(wù)質(zhì)量，又減少費用）顧客源-（排隊規(guī)則）隊列f（服務(wù)規(guī)則）服務(wù)機構(gòu)一離去服務(wù)規(guī)則：FCFS,LCFS，隨機服務(wù)，PR

”華中科技大學(xué)……學(xué)習(xí)筆記系列 作者：centreM(顧客到達(dá))|A(服務(wù)時間)|1(服務(wù)臺數(shù))|8(容量)|8(顧客源)N(t)隊長Nq(t)排隊長T(t)顧客逗留時間Tq(t)顧客等待時間L平均隊長Lq平均等待隊長W平均逗留時間Wq平均等待時間R為系統(tǒng)利用率」泊松流(M):無后效性；平穩(wěn)性；單個性；P1(t,t+At)=AAt+o(At);o(At)=Z；Pn(t,t+At);E「D「入t(t時刻n個顧客的概率)=負(fù)指數(shù)分布(M):無記憶性(P(T>t+s/t>s)=P(T>t));[0,t)至少到達(dá)一 個1—e一如,0,t>0t1—e一如,0,t>0t<0(i=1,2,…)v(t)=e/夸KE七⑺二k K! K=0,1,2,…％=愛爾朗分布(Ek):(相當(dāng)于泊松流到達(dá)后被k個服務(wù)臺均分顧客形成)(其中，t>0,E(T)=1/p,Var(T)=1/M2k)f(t)業(yè)(舊)k一1e-K(k-1)!K=1為M,k=8定長分布D,炬30正志分布近似—G表示一般相互獨立的隨機分布Little公式：(四者知一即可)W=.+「L=xwL=xWL=L+Pqq qL=ZnPL=Z(n-s)P=ZnPn=0 n=s n=0口服務(wù)率：p=g(入為到達(dá)口為服務(wù))排隊系統(tǒng)分析:（建9nM|M|1|8|8（到達(dá)服從入泊松過程，服務(wù)服從M負(fù)指數(shù)分布）空閑：P0=1-p.有k個顧客：Pk=（1-p）pk.L=（1-p）pnM|M|1|N|8（到達(dá)服從入泊松過程，服務(wù)服從M負(fù)指數(shù)分布）Po=(1-p)/(1-p)N+1.Pk=(1-p)pk/(1-p)N+1.L=(1-p)p-(N+1)pN+1/(1-p)N+1=M|M|1|8|m(到達(dá)服從入泊松過程，服務(wù)服從M負(fù)指數(shù)分布)Po=1/Zmpnm!/(m-i)!.Pk=m!/(m-k)!/Zmm!/(m-i)!.L=m-（1-P）/p—M|M|cg|8（到達(dá)服從入泊松過程，服務(wù)服從m負(fù)指數(shù)分布）:!PnPo(n<c)1PnP(n>c):!PnPo(n<c)1PnP(n>c)、c!cn-c 0吒（i）k+c；-左-（5）TP=

f*c?p尸*P=0DM|M|c|N|8（到達(dá)服膈泊松過程，服務(wù)服從m負(fù)指數(shù)分布）PnpPnp0<n<cnroP=V、急PocC<N0但匹+Pc(1-PNEY1〔n=on； c；(1-Pc)J仔1普+嚀(N-c+1)I n； c! JI、n=0 /-1Pc=1L=￡（n-c）p=cDM|M|cg|m（到達(dá)服從入泊松過程，服務(wù)服從m負(fù)指數(shù)分布）P0=P0=?肱；# 1 (CP)+CcA1 (P)?0K!(M-K)!、M C! c+1(M-K)!、MP=V

nP=V

nm! 5(m-n)!n!(—"0,(。<”<c)m! 5m； ()nP,(c+1<n<m),(m一n)!c!cn-c— 0_j_ ^Q人 *V*n其中p=_—,L=￡mnP=M|G|1（到達(dá)服從入泊松過程，服務(wù)服從M負(fù)指數(shù)分布）P2+人2。2L=q2（1-p）=M|D|1（到達(dá)服從入泊松過程，服務(wù)服從M負(fù)指數(shù)分布）p2L=p+p——2(1-p)nM|M|i(最優(yōu)服務(wù)率口)z=cp+c.人人孚=0口*=舄+(DM|M|C（最優(yōu)服務(wù)臺數(shù)C）Z(c*)Mz(c*-1)&Z(c*)Mz(c*+1)fL(c*)一L(c^+1)-cs1cw-Lc*T)-L(c"*)存儲論存儲費用，訂貨費用，生產(chǎn)費用，缺貨費用經(jīng)濟(jì)訂購批量：D不允許快貨，備貨快：C(t)=C3/t+kR+C1Rt/2;dC/dt=0—t0=sqrt(2C3/C1R),Q0=Rt0.D允許快貨，備貨快：C(t)=C3/t+C1(P-R)Tt/2t;dC/dt=0—t0=sqrt(2C3P/C1R(P-R)),Q0=Rt0.=允許快貨，生產(chǎn)需要時間：C(t,S)=(C3+S2C1/2R+(Rt-S)2C2/2R)/t;dC/dt=dC/dS=0-t0=sqrt(2C3(C1+C2)/C1R(P-R)),S0=sqrt(2C3C2R/C1(C1+C2)),Q0=Rt°.D需求隨機離散：C(Q)MC(Q+1),C(Q)《C(Q-1)—￡q-1P(r)Mk/(k+h)M?P(r)0 0=需求隨機連續(xù)：E(C(Q))=PM(r-Q)Q(r)dr+C1』Q(Q-r)^(r)dr+kQO'華中科技大學(xué)……學(xué)習(xí)筆記系列dE/dQ=0—F(Q)=』:Q(r)dr=(P-k)/(C1+P)C2＞P時，F(xiàn)(Q)=(C2-k)/(C1+C2)n(s,S)型存儲策略：＞需求為連續(xù)的隨機變量(貨物成本K/單位，存儲費C1/單位，缺貨費C2/單位，訂購費C3/單位，需求密度Q(r),S=I+Q，其中I表示原始積累，Q表示進(jìn)貨數(shù)量)C(S)=C3+KQ++JsC1(S-r)^(r)dr+f-C2(r-S)^(r)drC'(S)=0-ff^(r)dr=(C2-K)/(C1+C2)?表可得S0＞需求為離散的隨機變量C(S)=C3+KQ++￡C1(S-r)Q(r)dr+￡C2(r-S)^(r)drYS r〉SC(Si+1)ZC(Si)&&C(Si)MC(Si.1)求得S=需求備貨時間都隨機離散：(t時間內(nèi)需求量r隨機Q(r),t時間內(nèi)平均需求為pt,備貨時間x隨機，概率為p(x)^儲費C1/單位.年，缺貨費C2/單位.階段，訂購費C3，年需求D,緩沖存量B)先通過確定性模型求Q0=E.O.Q=\2CP,N0=D(每年訂購N0次每次訂Q。)L=mp+B,Pl=￡p(x)Fx(L)X則：C(L,B)=(B+Q0/2)C1+PLC2PL.求極值決策論(單目標(biāo)決策)＞戰(zhàn)略決策(全局性，長遠(yuǎn)問題)、策略決策(為完成目標(biāo)而定)、執(zhí)行決策(執(zhí)行方案選擇)；定量決策、定性決策；確定型決策、風(fēng)險決策、不確定型決策;--華中科技大學(xué)……學(xué)習(xí)筆記系列 作者：centre單項決策、貫序決策；程序決策（可重復(fù)，有章可循）、非程序決策（憑直覺應(yīng)變）＞面向過程（預(yù)決策―決策一決策后）面向結(jié)果（確定目標(biāo)一收集信息一提出方案-方案選優(yōu)―決策）＞不確定型決策：■悲觀主義準(zhǔn)則：maxmin島）■樂觀主義準(zhǔn)則：maxmln域）■等可能準(zhǔn)則：max（E（sj）i■最小機會準(zhǔn)則：max（aik）i■折中主義準(zhǔn)則：HFqmax+d-a&n。＞風(fēng)險決策：EMV:maxEP.aij（g用于以此決策多次重復(fù)進(jìn)行）EOL:minEPjaij'（EOLi+EMVi=K表明決策結(jié)果一致）iJEVPI:EPPL-EMV*=EVPI2O（滿足此條件時沒白花錢）＞主觀概率：直接估計法：要求參加者直接給出概率間接軌跡法：參加者通過排隊或相互比較等給出概率＞修正概率方法：貝葉斯公式先由過去的經(jīng)驗或?qū)＜夜烙嫬@得事前概率；再調(diào)查得條件概率；由貝葉斯公式得到時候概率：P（B^A）=P（Bi）P（A/Bi）/EP（Bi）P（A/Bi）＞效用理論：將要考慮的因素都折合為效用值，選綜合效用值最大的方案。直接提問法、對比提問法得到效用值，再用效用曲線進(jìn)行擬合。＞靈敏度分析：轉(zhuǎn)折概率P=（a12-a22）/（a12-a22+a21-a11）--華中科技大學(xué)……學(xué)習(xí)筆記系列 作者：centre對策論G={S「S2；A}為矩陣對策，S1=(a1……am},S2={p1……pn},A=(aij)mn,ifmaxmina廣minmaxaij=ai*j*記VG=aj則VG為G的值，(a'j)為ij jiG在純策略意義下的解,ai*,§*分別為的III最優(yōu)化策略。G={S1,S2;A}純策略意義有解 。3純局勢(ai*,pj*),STaij*^ai*j*^ai*j.。并丁是矩陣A的一個鞍點。f(x,y),xeA,yeB,IF3x*eA,y*eBvxeA,yeB,有f(x,y*)Mf(x*,y*)Mf(x*,y)則(x*,y*)為f的一個鞍點。>無差別性，可交換性(對于鞍點的橫坐標(biāo)與縱坐標(biāo))>混合策略：G={S1,S2;A}記S1*={xgEm|xiZ0,i=1…m,Zmxi=1},S2*={xeEn|yjN0,i=1…n,目yj=1},S1*,S2*分別為Ill的混合策略集.I的贏得函數(shù)E(x,y)=XAY:I保證自己贏的期望值不少于v1=maxminE(x,y)xes； yes2*Il保證自己失的期望值最多為v2=minmaxE(x,y)yes： xes?*v1%>G*={S1*,S2*;E}是G={S1,S2;A}的混合擴充,ifv1=v2,記vG,為對策G*的值.(x*,y*)為G在混合策略意義下的解，x*,y*分別為Ill的最優(yōu)混合策略。>G={S1,S2;A}混合策略意義下有解。3x*eS1*,y*eS2*STE(x,y*)ME(x*,y*)ME(x*,y)>基本定理：￡a.xiyj=￡E(i,y)xjj i?記￡a.xiyj=￡E(i,y)xjj ij i i參拶*華中科技大學(xué).?????學(xué)習(xí)筆記系列E(x,j)y「=￡E(x,j)y「j(x*,y*)是G(x*,y*)是G的解。Vi,j,E(i,y*)ME(x*,y*)ME(x*,j)。3仁agj=1...nii<￡為=1i為20」=1…mvST,x*,y*分別是下列方程組的解且v=vG.AyjNv,j=1...m:￡yj=ij%20」=1…mvG=(S1,S2;A}-定存在混合策略意義下的解(證:上述方程組互為對偶的線性規(guī)劃，分別存在最優(yōu)解(x*,v*)(y*,v*))＞定理：(x*,y*)是G的解，v=vG則lf,xi*>0,thenIf,yj*>0,then￡ayj*=v;If￡alf,xi*>0,thenIf,yj*>0,then￡axj*=v;If￡axi*>v,theny.*>0ii iii i>運算：G1=(S1，S2；(8ij)}G2={S1,S2；(aij+L)}^v