最优化方法简明教程—centre

华中科技大学……学习笔记系列作者：centre----穷则投资自己，达则投资天下---①图与网破圈法：任取一个圈，去掉一条权最大的边，直到最小树。避圈法：选最小权的边，避圈前进，直到最小树。最短路算法：Dijkstra法：从Vs给定P标号T标号λ标号（T标号变为P标号λ标号记位置）反向追踪：列表，d1(V1,Vj)→dk(V1,Vj)=min(ωij+dk(V1,Vi))据最小权反向追踪网络优化：最小截集最大流：找到最小截集（弧的集合）标号法：开始，为的标号，最小费用最大流：邮递员问题：通过消灭奇点，找欧拉回路网络计划图：最早开始最晚开始机动时间最早结束最晚结束自由时差工期优化：人力，费用，工期优化。费用率=（最短时间费用-正常时间费用）/（正常时间-最短时间）②排队论（保证服务质量，又减少费用）顾客源→（排队规则）队列→（服务规则）服务机构→离去服务规则：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)=2Pn(t,t+Δt);Eξ=Dξ=λt（t时刻n个顾客的概率）负指数分布(M)：无记忆性(P(Tt+s/ts)=P(Tt));[0,t)至少到达一个顾客1-P0(t）=1-e-tλ,t0!)()(KtetVKtk,2,1,0K0,00,1)(ttetFti),2,1(i爱尔朗分布(EK)：（相当于泊松流到达后被k个服务台均分顾客形成）(其中，t0,E(T)=1/μ,Var(T)=1/μ2k）0)!1()()(1tekttftkK=1为M，k=∞定长分布D,k≥30正态分布近似G表示一般相互独立的随机分布Little公式：（四者知一即可）1qqqWLqLL华中科技大学……学习笔记系列作者：centre----穷则投资自己，达则投资天下---0nnnPLsnnmsnqnPPsnL0)(=λ/μ(λ为到达μ为服务)排队系统分析：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+1M|M|1|∞|m（到达服从λ泊松过程，服务服从μ负指数分布）P0=1/m0ρnm!/(m-i)!.Pk=m!/(m-k)!/m0m!/(m-i)!.L=m-(1-P)/ρM|M|c|∞|∞（到达服从λ泊松过程，服务服从μ负指数分布）ρs=λ/μc=ρ/c，Lq=(ρ)CρsP0/c!(1-ρs)2.1100)(11!1)(!1ckckckP)(!1)(!100cnPcccnPnPncnnnM|M|c|N|∞（到达服从λ泊松过程，服务服从μ负指数分布）Nncpcccnpnpcnnnn!0!001)1(!!1)1(!)1(!11011010ccncnccnccNccncNcncnp)(NcnnqpcnLM|M|c|∞|m（到达服从λ泊松过程，服务服从μ负指数分布）KMCCCMKMCCMCKMKMP10)()!(1!)()!(!11!10)1(,)(!)!(!)0(,)(!)!(!00nmncPccnmmcnPnnmmPncnn其中cm，m1nSnPLM|G|1（到达服从λ泊松过程，服务服从μ负指数分布）)1(2222qLM|D|1（到达服从λ泊松过程，服务服从μ负指数分布）)1(22LM|M|1（最优服务率μ）华中科技大学……学习笔记系列作者：centre----穷则投资自己，达则投资天下---wsccz&&0ddz→swcc*M|M|C（最优服务台数C）Z(c*)≤z(c*-1)&Z(c*)≤z(c*+1)→)()1(/)1()(**'**cLcLcccLcLws③存储论存储费用，订货费用，生产费用，缺货费用经济订购批量：不允许缺货，备货快：C(t)=C3/t+kR+C1Rt/2;dC/dt=0→t0=sqrt(2C3/C1R),Q0=Rt0.允许缺货，备货快: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=Rt0.需求随机离散：C(Q)≤C(Q+1)，C(Q)≤C(Q-1)→10QP(r)≤k/(k+h)≤Q0P(r)需求随机连续：E(C(Q))=PQ(r-Q)φ(r)dr+C1Q0(Q-r)φ(r)dr+kQdE/dQ=0→F(Q)=Q0φ(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++S0C1(S-r)φ（r）dr+SC2(r-S)φ（r）drC'(S)=0→S0φ（r）dr=(C2-K)/(C1+C2)查表可得S需求为离散的随机变量C(S)=C3+KQ++SrC1(S-r)φ（r）dr+SrC2(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=132CDC,N0=0QD(每年订购N0次每次订Q0)华中科技大学……学习笔记系列作者：centre----穷则投资自己，达则投资天下---L=μρ+B,PL=Xp(x)FX(L)则：C(L,B)=(B+Q0/2)C1+PLC2PL.求极值④决策论（单目标决策）战略决策(全局性，长远问题)、策略决策(为完成目标而定)、执行决策(执行方案选择)；定量决策、定性决策；确定型决策、风险决策、不确定型决策；单项决策、贯序决策；程序决策(可重复，有章可循)、非程序决策(凭直觉应变)面向过程（预决策→决策→决策后）面向结果(确定目标→收集信息→提出方案→方案选优→决策)不确定型决策：悲观主义准则：maximinj(aij)乐观主义准则：maximinj(aij)等可能准则：maxi(E(Si))最小机会准则：maxi(aik)折中主义准则：Hi=αaimax+(1-α)aimin。风险决策：EMV:maxijPjaij(适用于以此决策多次重复进行)EOL:minijPjaij'(EOLi+EMVi=K表明决策结果一致)EVPI:EPPL-EMV*=EVPI≥0(满足此条件时没白花钱)主观概率：直接估计法：要求参加者直接给出概率间接轨迹法：参加者通过排队或相互比较等给出概率修正概率方法：贝叶斯公式先由过去的经验或专家估计获得事前概率；再调查得条件概率；由贝叶斯公式得到时候概率：P(Bi/A)=P(Bi)P(A/Bi)/P(Bi)P(A/Bi)效用理论：将要考虑的因素都折合为效用值，选综合效用值最大的方案。直接提问法、对比提问法得到效用值，再用效用曲线进行拟合。灵敏度分析：转折概率P=(a12-a22)/(a12-a22+a21-a11)⑤对策论G={S1,S2;A}为矩阵对策，S1={α1……αm}，S2={β1……βn},A=(aij)mn,ifmaximinjaij=minjmaxiaij=ai*j*记VG=ai*j*则VG为G的值，(αi*,βj*)为G在纯策略意义下的解，αi*，βj*分别为的ⅠⅡ最优化策略。G={S1,S2;A}纯策略意义有解纯局势(αi*,βj*),STaij*≤ai*j*≤ai*j.ai*j*是矩阵A的一个鞍点。f(x,y),x∈A,y∈B,IFx*∈A,y*∈Bx∈A,y∈B,有f(x,y*)≤f(x*,y*)≤f(x*,y)则(x*,y*)为f的一个鞍点。华中科技大学……学习笔记系列作者：centre----穷则投资自己，达则投资天下---无差别性，可交换性（对于鞍点的横坐标与纵坐标）混合策略：G={S1,S2;A}记S1*={x∈Em|xi≥0,i=1…m,m1xi=1}，S2*={x∈En|yj≥0,i=1…n,n1yj=1}，S1*，S2*分别为ⅠⅡ的混合策略集.Ⅰ的赢得函数E(x,y)=X'AY:Ⅰ保证自己赢的期望值不少于v1=max*x1smin*2syE(x,y)Ⅱ保证自己失的期望值最多为v2=min*1symax*x2sE(x,y)v1≤v2.G*={S1*,S2*;E}是G={S1,S2;A}的混合扩充,ifv1=v2,记vG,为对策G*的值.(x*,y*)为G在混合策略意义下的解，x*,y*分别为ⅠⅡ的最优混合策略。G={S1,S2;A}混合策略意义下有解x*∈S1*，y*∈S2*STE(x,y*)≤E(x*,y*)≤E(x*,y)基本定理：记E(i,y)=jijayj,E(x,j)=iijaxi,则E(x,y)=ijijaxiyj=iE(i,y)xj=jE(x,j)yi.(x*,y*)是G的解i,j,E(i,y*)≤E(x*,y*)≤E(x*,j)vST,x*,y*分别是下列方程组的解且v=vG.iijaxi≥v,j=1…njijayj≥v,j=1…mixi=1jyj=1xi≥0,i=1…myj≥0,i=1…mG={S1,S2;A}一定存在混合策略意义下的解（证:上述方程组互为对偶的线性规划，分别存在最优解(x*,v*)(y*,v*)）定理：(x*,y*)是G的解，v=vG则If,xi*0,thenjijayj*=v;Ifjijayj*v,thenxi*=0If,yj*0,theniijaxi*=v;Ifiijaxi*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（G2）.A+A'=0,则vG=0,T1（G）=T2（G）.Ifj=1…n;aij≥akj,则Ⅰ的纯策略ai优超于ak。Ifa1被其他纯策略或它们的凸组合优超，则可去掉该纯策略，得到新的矩阵对策G',vG'=vG,(x2*…xm*)'是G'中Ⅰ的最优策略，则x*=(0,x2*…xm*)'是G的最优策略。解法：将上述不等号改为等号解方程组；图解最优化方法