最优化方法简明教程

爹9•w’华中科技大学.•••••学习笔记系列 作者：centre图与网=破圈法：任取一个圈，去掉一条权最大的边，直到最小树。=避圈法：选限小权的边，避圈前进，直到最小树。n最短路算法：Dijkstra法：从Vs给定P标号T标号入标号（T标号变为P标号入标号记位置）反向追踪：列表，di（V1,Vj）^dk（V1,Vj）=min（wij+dk（V1,Vi））据最小权反向追踪n网络优化：最小截集最大流：找到最小截集（弧的集合）标号法：开始，为的标号，最小费用最大流：邮递员问题：通过消灭奇点，找欧拉回路n网络计划图：最早开始 最晚开始机动时间最早结束 最晚结束自由时差工期优化：人力，费用，工期优化。费用率=（最短时间费用-正常时间费用）/（正常时间-最短时间）排队论（保证服务质量，又减少费用）顾客源-（排队规则）队列f（服务规则）服务机构一离去服务规则：FCFS,LCFS，随机服务，PR

”华中科技大学……学习笔记系列 作者：centreM(顾客到达)|A(服务时间)|1(服务台数)|8(容量)|8(顾客源)N(t)队长Nq(t)排队长T(t)顾客逗留时间Tq(t)顾客等待时间L平均队长Lq平均等待队长W平均逗留时间Wq平均等待时间R为系统利用率」泊松流(M):无后效性；平稳性；单个性；P1(t,t+At)=AAt+o(At);o(At)=Z；Pn(t,t+At);E「D「入t(t时刻n个顾客的概率)=负指数分布(M):无记忆性(P(T>t+s/t>s)=P(T>t));[0,t)至少到达一 个1—e一如,0,t>0t1—e一如,0,t>0t<0(i=1,2,…)v(t)=e/夸KE七⑺二k K! K=0,1,2,…％=爱尔朗分布(Ek):(相当于泊松流到达后被k个服务台均分顾客形成)(其中，t>0,E(T)=1/p,Var(T)=1/M2k)f(t)业(旧)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口服务率：p=g(入为到达口为服务)排队系统分析:（建9nM|M|1|8|8（到达服从入泊松过程，服务服从M负指数分布）空闲：P0=1-p.有k个顾客：Pk=（1-p）pk.L=（1-p）pnM|M|1|N|8（到达服从入泊松过程，服务服从M负指数分布）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(到达服从入泊松过程，服务服从M负指数分布)Po=1/Zmpnm!/(m-i)!.Pk=m!/(m-k)!/Zmm!/(m-i)!.L=m-（1-P）/p—M|M|cg|8（到达服从入泊松过程，服务服从m负指数分布）:!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（到达服膈泊松过程，服务服从m负指数分布）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（到达服从入泊松过程，服务服从m负指数分布）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（到达服从入泊松过程，服务服从M负指数分布）P2+人2。2L=q2（1-p）=M|D|1（到达服从入泊松过程，服务服从M负指数分布）p2L=p+p——2(1-p)nM|M|i(最优服务率口)z=cp+c.人人孚=0口*=舄+(DM|M|C（最优服务台数C）Z(c*)Mz(c*-1)&Z(c*)Mz(c*+1)fL(c*)一L(c^+1)-cs1cw-Lc*T)-L(c"*)存储论存储费用，订货费用，生产费用，缺货费用经济订购批量：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.=允许快货，生产需要时间：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=需求随机连续：E(C(Q))=PM(r-Q)Q(r)dr+C1』Q(Q-r)^(r)dr+kQO'华中科技大学……学习笔记系列dE/dQ=0—F(Q)=』:Q(r)dr=(P-k)/(C1+P)C2＞P时，F(Q)=(C2-k)/(C1+C2)n(s,S)型存储策略：＞需求为连续的随机变量(货物成本K/单位，存储费C1/单位，缺货费C2/单位，订购费C3/单位，需求密度Q(r),S=I+Q，其中I表示原始积累，Q表示进货数量)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时间内需求量r随机Q(r),t时间内平均需求为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.求极值决策论(单目标决策)＞战略决策(全局性，长远问题)、策略决策(为完成目标而定)、执行决策(执行方案选择)；定量决策、定性决策；确定型决策、风险决策、不确定型决策;--华中科技大学……学习笔记系列 作者：centre单项决策、贯序决策；程序决策（可重复，有章可循）、非程序决策（凭直觉应变）＞面向过程（预决策―决策一决策后）面向结果（确定目标一收集信息一提出方案-方案选优―决策）＞不确定型决策：■悲观主义准则：maxmin岛）■乐观主义准则：maxmln域）■等可能准则：max（E（sj）i■最小机会准则：max（aik）i■折中主义准则：HFqmax+d-a&n。＞风险决策：EMV:maxEP.aij（g用于以此决策多次重复进行）EOL:minEPjaij'（EOLi+EMVi=K表明决策结果一致）iJEVPI:EPPL-EMV*=EVPI2O（满足此条件时没白花钱）＞主观概率：直接估计法：要求参加者直接给出概率间接轨迹法：参加者通过排队或相互比较等给出概率＞修正概率方法：贝叶斯公式先由过去的经验或专家估计获得事前概率；再调查得条件概率；由贝叶斯公式得到时候概率：P（B^A）=P（Bi）P（A/Bi）/EP（Bi）P（A/Bi）＞效用理论：将要考虑的因素都折合为效用值，选综合效用值最大的方案。直接提问法、对比提问法得到效用值，再用效用曲线进行拟合。＞灵敏度分析：转折概率P=（a12-a22）/（a12-a22+a21-a11）--华中科技大学……学习笔记系列 作者：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最优化策略。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的一个鞍点。>无差别性，可交换性(对于鞍点的横坐标与纵坐标)>混合策略：G={S1,S2;A}记S1*={xgEm|xiZ0,i=1…m,Zmxi=1},S2*={xeEn|yjN0,i=1…n,目yj=1},S1*,S2*分别为Ill的混合策略集.I的赢得函数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的最优混合策略。>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参拶*华中科技大学.•••••学习笔记系列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}-定存在混合策略意义下的解(证:上述方程组互为对偶的线性规划，分别存在最优解(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