最优化方法简明教程—centre.doc

华中科技大学学习笔记系列 作者：centre 1 图与网 破圈法：任取一个圈，去掉一条权最大的边，直到最小树。 避圈法：选最小权的边，避圈前进，直到最小树。 最短路算法：Dijkstra法：从Vs给定P标号T标号标号（T标号变为P标号标号记位置）反向追踪：列表，d1(V1,Vj)dk(V1,Vj)=min(ij+dk(V1,Vi)据最小权反向追踪 网络优化：最小截集最大流：找到最小截集（弧的集合）标号法：开始，为的标号，最小费用最大流：邮递员问题：通过消灭奇点，找欧拉回路 网络计划图：最早开始最晚开始机动时间最早结束最晚结束自由时差工期优化：人力，费用，工期优化。费用率=（最短时间费用-正常时间费用）/（正常时间-最短时间）2 排队论（保证服务质量，又减少费用）顾客源（排队规则）队列（服务规则）服务机构离去服务规则：FCFS，LCFS，随机服务，PRM(顾客到达)|A(服务时间)|1(服务台数)|（容量）|（顾客源）N(t)队长Nq(t)排队长T(t)顾客逗留时间Tq(t)顾客等待时间L平均队长Lq平均等待队长W平均逗留时间Wq平均等待时间R为系统利用率 泊松流(M)：无后效性；平稳性；单个性；P1(t,t+t)=t+o(t)；o(t)=Pn(t,t+t);E=D=t（t时刻n个顾客的概率） 负指数分布(M)：无记忆性(P(Tt+s/ts)=P(Tt);0,t)至少到达一个顾客1-P0(t）=1-e-t,t0 爱尔朗分布(EK)：（相当于泊松流到达后被k个服务台均分顾客形成）(其中，t0,E(T)=1/,Var(T)=1/2k）K=1为M，k=定长分布D,k30正态分布近似 G表示一般相互独立的随机分布Little 公式：（四者知一即可） r服务率：=/(为到达为服务)排队系统分析： M|M|1|（到达服从泊松过程，服务服从负指数分布） 空闲：P0=1-.有k个顾客：Pk=（1-）k. L=（1-） M|M|1|N|（到达服从泊松过程，服务服从负指数分布） P0=(1-)/(1-)N+1.Pk=(1-)k/(1-)N+1. L=（1-）-(N+1)N+1/(1-)N+1 M|M|1|m（到达服从泊松过程，服务服从负指数分布） P0=1/nm!/(m-i)!.Pk=m!/(m-k)!/m!/(m-i)!. L=m-(1-P)/ M|M|c|（到达服从泊松过程，服务服从负指数分布）s=/c=/c，Lq=()CsP0/c!(1-s)2. M|M|c|N|（到达服从泊松过程，服务服从负指数分布） M|M|c|m（到达服从泊松过程，服务服从负指数分布）其中， M|G|1（到达服从泊松过程，服务服从负指数分布） M|D|1（到达服从泊松过程，服务服从负指数分布） M|M|1（最优服务率）& M|M|C（最优服务台数C）Z(c*)z(c*-1)&Z(c*)z(c*+1)3 存储论存储费用，订货费用，生产费用，缺货费用 经济订购批量： 不允许缺货，备货快：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. 允许缺货，生产需要时间：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. 需求随机离散：C(Q)C(Q+1)，C(Q)C(Q-1)P(r)k/(k+h)P(r) 需求随机连续：E(C(Q)=P(r-Q)(r)dr+C1(Q-r)(r)dr+kQdE/dQ=0F(Q)=(r)dr=(P-k)/(C1+P)C2P时，F(Q)=(C2-k)/(C1+C2) （s,S）型存储策略： 需求为连续的随机变量（货物成本K/单位，存储费C1/单位，缺货费C2/单位，订购费C3/单位，需求密度（r）,S=I+Q，其中I表示原始积累，Q表示进货数量）C(S)=C3+KQ+C1(S-r)（r）dr+C2(r-S)（r）drC(S)=0 （r）dr=(C2-K)/(C1+C2)查表可得S 需求为离散的随机变量C(S)=C3+KQ+C1(S-r)（r）dr+C2(r-S)（r）drC(Si+1)C(Si)&C(Si)C(Si-1)求得S 需求备货时间都随机离散：（t时间内需求量r随机t（r），t时间内平均需求为t,备货时间x随机，概率为p(x),存储费C1/单位.年，缺货费C2/单位.阶段，订购费C3，年需求D，缓冲存量B）先通过确定性模型求Q0=E.O.Q=,N0=(每年订购N0次每次订Q0)L=+B,PL=p(x)FX(L)则：C(L,B)=(B+Q0/2)C1+PLC2PL.求极值4 决策论（单目标决策） 战略决策(全局性，长远问题)、策略决策(为完成目标而定)、执行决策(执行方案选择)；定量决策、定性决策；确定型决策、风险决策、不确定型决策；单项决策、贯序决策；程序决策(可重复，有章可循)、非程序决策(凭直觉应变) 面向过程（预决策决策决策后）面向结果(确定目标收集信息提出方案方案选优决策) 不确定型决策：n 悲观主义准则：(aij)n 乐观主义准则：(aij)n 等可能准则：(E(Si)n 最小机会准则：(aik)n 折中主义准则：Hi=aimax+(1-)aimin。 风险决策：n EMV:Pjaij(适用于以此决策多次重复进行)n EOL:Pjaij(EOLi+EMVi=K表明决策结果一致)n EVPI:EPPL-EMV*=EVPI0(满足此条件时没白花钱) 主观概率：直接估计法：要求参加者直接给出概率间接轨迹法：参加者通过排队或相互比较等给出概率 修正概率方法：贝叶斯公式先由过去的经验或专家估计获得事前概率；再调查得条件概率；由贝叶斯公式得到时候概率：P(Bi/A)=P(Bi)P(A/Bi)/P(Bi)P(A/Bi) 效用理论：将要考虑的因素都折合为效用值，选综合效用值最大的方案。直接提问法、对比提问法得到效用值，再用效用曲线进行拟合。 灵敏度分析：转折概率P=(a12-a22)/(a12-a22+a21-a11)5 对策论 G=S1,S2;A为矩阵对策，S1=1m，S2=1n,A=(aij)mn, if aij=aij=ai*j* 记VG=ai*j*则VG为G的值，(i*,j*)为G在纯策略意义下的解，i*，j*分别为的最优化策略。 G=S1,S2;A纯策略意义有解纯局势(i*,j*),ST aij*ai*j*ai*j. ai*j*是矩阵A的一个鞍点。 f(x,y),xA,yB,IFx*A,y*BxA,yB,有f(x,y*)f(x*,y*)f(x*,y)则(x*,y*)为f的一个鞍点。 无差别性，可交换性（对于鞍点的横坐标与纵坐标） 混合策略：G=S1,S2;A记S1*=xEm|xi0,i=1m,xi=1，S2*=xEn|yj0,i=1n,yj=1，S1*，S2*分别为的混合策略集.的赢得函数E(x,y)=XAY:保证自己赢的期望值不少于v1=E(x,y)保证自己失的期望值最多为v2=E(x,y)v1v2. G*=S1*,S2*;E是G=S1,S2;A的混合扩充,if v1=v2,记vG,为对策G*的值.(x*,y*)为G在混合策略意义下的解，x*,y*分别为的最优混合策略。 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一定存在混合策略意义下的解（证:上述方程组互为对偶的线性规划，分别存在最优解(x*,v*)(y*,v*)） 定理：(x*,y*)是G的解，v=vG则If,xi*0,then yj*=v;Ifyj*0,then xi*=v;Ifxi*v,thenyj*0 运算：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