资源描述:
《最优化方法简明教程—centre.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、① 图与网破圈法:任取一个圈,去掉一条权最大的边,直到最小树。避圈法:选最小权的边,避圈前进,直到最小树。最短路算法:Dijkstra法:从Vs给定P标号T标号λ标号(T标号变为P标号λ标号记位置)反向追踪:列表,d1(V1,Vj)→dk(V1,Vj)=min(ωij+dk(V1,Vi))据最小权反向追踪网络优化:最小截集最大流:找到最小截集(弧的集合)标号法:开始,为的标号,最小费用最大流:邮递员问题:通过消灭奇点,找欧拉回路网络计划图:最早开始最晚开始机动时间最早结束最晚结束自由时差工期优化:人力,费用,工期优化。费用率=(最短时间费用-正常时间费用)/(正常时间-最短时
2、间)② 排队论(保证服务质量,又减少费用)顾客源→(排队规则)队列→(服务规则)服务机构→离去服务规则:FCFS,LCFS,随机服务,PRM(顾客到达)
3、A(服务时间)
4、1(服务台数)
5、∞(容量)
6、∞(顾客源)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(T>t+s/t>s)=P(T>t));[0,
7、t)至少到达一个顾客1-P0(t)=1-e-tλ,t>0爱尔朗分布(EK):(相当于泊松流到达后被k个服务台均分顾客形成)(其中,t>0,E(T)=1/μ,Var(T)=1/μ2k)K=1为M,k=∞定长分布D,k≥30正态分布近似G表示一般相互独立的随机分布Little公式:(四者知一即可)r服务率:ρ=λ/μ(λ为到达μ为服务)排队系统分析:M
8、M
9、1
10、∞
11、∞(到达服从λ泊松过程,服务服从μ负指数分布)空闲:P0=1-ρ.有k个顾客:Pk=(1-ρ)ρk.L=(1-ρ)ρM
12、M
13、1
14、N
15、∞(到达服从λ泊松过程,服务服从μ负指数分布)P0=(1-ρ)/(1-ρ)N+1.Pk
16、=(1-ρ)ρk/(1-ρ)N+1.L=(1-ρ)ρ-(N+1)ρN+1/(1-ρ)N+1M
17、M
18、1
19、∞
20、m(到达服从λ泊松过程,服务服从μ负指数分布)P0=1/ρnm!/(m-i)!.Pk=m!/(m-k)!/m!/(m-i)!.L=m-(1-P)/ρM
21、M
22、c
23、∞
24、∞(到达服从λ泊松过程,服务服从μ负指数分布)ρs=λ/μc=ρ/c,Lq=(ρ)CρsP0/c!(1-ρs)2.M
25、M
26、c
27、N
28、∞(到达服从λ泊松过程,服务服从μ负指数分布)M
29、M
30、c
31、∞
32、m(到达服从λ泊松过程,服务服从μ负指数分布)其中,M
33、G
34、1(到达服从λ泊松过程,服务服从μ负指数分布)M
35、D
36、1(到
37、达服从λ泊松过程,服务服从μ负指数分布)M
38、M
39、1(最优服务率μ)&&→M
40、M
41、C(最优服务台数C)Z(c*)≤z(c*-1)&Z(c*)≤z(c*+1)→① 存储论存储费用,订货费用,生产费用,缺货费用经济订购批量:不允许缺货,备货快: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/
42、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)→P(r)≤k/(k+h)≤P(r)需求随机连续:E(C(Q))=P(r-Q)φ(r)dr+C1(Q-r)φ(r)dr+kQdE/dQ=0→F(Q)=φ(r)dr=(P-k)/(C1+P)C2>P时,F(Q)=(C2-k)/(C1+C2)(s,S)型存储策略:Ø需求为连续的随机变量(货物成本K/单位,存储费C1/单位,缺货费C2/单位,订购费C3/单位,需求密度φ(r),S
43、=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/单位.