一、排队论模型
排队论模型可用于多个领域,包括演唱会买票排队,就餐排队,就医排队等,排队论模型也是一种传统的模型,模型构建有套路,运行一般通过lingo软件进行运行。
◎首先进行字母定义:
Ls记为队长,指在系统中的顾客数
Lq是队列长,在系统中等待服务的顾客数,Ls=Lq+Ln,Ln是正在接受服务的顾客数
Ws是逗留时间,一个顾客在系统中的等候时间
Wq是等待时间,一个顾客在系统中排队等候的时间Ws=Wq+a,其中a为服务时间
Tb为忙期,服务机构连续工作的时间长度
Plost为损失率,由于系统的条件限制,使顾客被拒绝服务而使服务部门受到损失的概率
服务强度:绝对通过能力A,表示单位时间内被服务完顾客的均值,或称为平均服务率,相对通过能力Q,表示单位时间内被服务完的顾客数与请求服务的顾客数之比。
◎排队论的模型假设:
1. 顾客源是无限的,并且顾客流平稳,不考虑出现高峰期和空闲期的可能。
2. 顾客到达时间的间隔和服务时间是相对独立的
3. 顾客流满足泊松分布,各顾客的服务时间服从参数为u的负指数分布
4. 排队方式为单一队列,队长没有限制。
◎排队论模型建立:
确定系统在任意时刻t状态为n的概率Pn(t)
根据假设可知,当△t足够小的时候灵敏度计算,在【t,t+△t】的时间间隔内,有一个顾客到达的概率为λ△t+o(t),没有一个顾客到达的概率为1-λ△t+o(t),有一个顾客被服务完的概率为:μ△t+o(t),没有一个顾客被服务完的概率为1-μ△t+o(t),多于一个顾客到达或被服务完离开的概率为o(t)。
现在考虑在t+△t时刻下的系统中有n个顾客的概率Pn(t+△t)有以下四种可能:
1. 时刻t的顾客数为n,Pn(t+△t)=Pn(t)(1-λ△t)(1-μ△t)
2. 在t时刻顾客数为n+1,Pn(t+△t)=Pn+1(t)(1-λ△t)(μ△t)
3. 在t时刻顾客数为n-1,Pn(t+△t)=Pn-1(t)(λ△t)(1-μ△t)
4. t时刻顾客数为n:Pn(t+△t)=Pn(t)(λ△t)(μ△t)
四种情况相互独立:
Pn(t+△t)=Pn(t)(1-λ△t-μ△t)+Pn-1(t)μ△t+Pn-1(t)λ△t+o(△t)
让△t趋近与0,dPO(t)/dt=-λP0(t)+μP1(t)
dPn(t)/dt=λPn-1(t)+μPn+1(t)-(λ+μ)Pn(t)
再假设t趋于无穷,于是有dPn(t)/dt=0,Pn(t)=Pn
在平衡状态下的微分方程为:
-λP0+μP1=0,λPn-1+μPn+1-(λ+μ)Pn=0,(n>1)
令ρ=λ/μ,表示平均每单位时间内系统可以为顾客服务的时间比例,用于刻画服务效率。
由差分方程可知Pn=ρnP0
◎可计算出排队论主要的结论如下:
队长:
队列长:
逗留时间:Ws=1/(μ-λ)
等候时间=逗留时间-被服务时间,即Wq=Ws-1/μ=ρ/(μ-λ)
◎LINGO代码为:
Model:
S=2;R=3;T=2/5;load=R*T; (S,R,T数值根据具体情况设定)
Pwait=@peb(load,S);
W_Q=Pwait*T/(S-load);
L_Q=R*W_Q;
W_S=W_Q+T;
L_S=W_S*R;
End
二、灵敏度分析和稳健性检验
灵敏度分析是研究与分析一个系统(或模型)的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此,灵敏度分析几乎在所有的运筹学方法中以及在对各种方案进行评价时都是很重要的。
灵敏度分析用途:
主要用于模型检验和推广。简单来说就是改变模型原有的假设条件之后灵敏度计算,所得到的结果会发生多大的变化。
灵敏度分析举例:
数据是由测量,观察有时甚至完全猜测得到的,因此,我们要考虑数据不准确的可能性。
案例分析:
猪的重量w(磅),从现在到出售猪期间经历的时间t(天),t天内饲养猪的花费C(美元),猪的市场价格p(美元/磅),出售生猪所获得的收益R(美元),我们最终要获得的净收益P(美元)。还有一些其他量,如猪的初始重量200磅。
(建议先写显而易见的部分)
猪从200磅按每天5磅增加
(w磅)=(200磅)+(5磅/天)*(t天)
饲养每天花费45美分
(C美元)=(0.45美元/天)*(t天)
价格65美分按每天1美分下降
(p美元/磅)=(0.65美元/磅)-(0.01美元/磅)*(t天)
生猪收益
(R美元)=(p美元/磅)*(w磅)
净利润
(P美元)=(R美元)-(C美元)
用数学语言总结和表达如下:
参数设定:
t=时间(天)
w=猪的重量(磅)
p=猪的价格(美元/磅)
C=饲养t天的花费(美元)
R=出售猪的收益(美元)
P=净收益(美元)
假设:
w=200+5t
C=0.45t
p=0.65-0.01t
R=p*w
P=R-C
t>=0
目标:求P的最大值
第二步:选择建模方法
本例采用单变量最优化问题或极大—极小化问题
第三步:推导模型的数学表达式子
P=R-C (1)
R=p*w (2)
C=0.45t (3)
得到R=p*w-0.45t
p=0.65-0.01t (4)
w=200+5t (5)
得到P=(0.65-0.01t)(200+5t)-0.45t
令y=P是需最大化的目标变量,x=t是自变量,现在我们将问题转化为集合S={x:x>=0}上求函数的最大值:
y=f(x)=(0.65-0.01x)(200+5x)-0.45x
通过以上分析,得到,生猪现在的重量,现在的价格,每天饲养花费都很容易测量,而且有相当大的确定性。但是猪的生长率则不那么确定,而价格的下降率则确定性更低,记r为价格的下降率,现在假设r的实际值不同,对几个不同的r值重复前面的求解过程,我们会对问题的解关于r的敏感程度有所了解。下表给出了几个不同r值求出的计算结果。根据表格绘制图形,我们可以看到售猪的最优时间对参数r很敏感。
对灵敏度的更系统的分析是将r视为未知参数,按前面的步骤求解,写出p=0.65-rt。得到y=f(x)=(0.65-rx)(200+5x)-0.45x。使得导数为0,得到x=(7-500r)/25r,当x>=0时,只要0
对于猪的生长率g同样不确定,我们有w=200+gt,得到y=f(x)=(0.65-rx)(200+gx)-0.45x。使得导数为0,得到x=5*(13g-49)/2g。当x>=0时,得到g>=3.769。
我们将灵敏度数据用相对改变量表示,例如:r下降10%导致了x增加了39%,而g下降了10%导致了x下降了34%。
如果x的改变量Δx,则Δx/x表示相对改变量。如果r改变了Δr,导致了x有Δx的改变量,则相对改变量的比值为(Δx/x)/(Δr/r),令Δr→0,我们有(Δx/x)/(Δr/r)→(dx/dr)*(r/x)。我们称这个极限值为x对r的灵敏度,即为S(x,r)。
在售猪问题中,r=0.01和x=8得到dx/dr=-7/25r2=-2800,因此S(x,r)=(dx/dr)*(r/x)=-2800*(0.01/8)=-7/2,即若r增加2%,则x下降7%。由于
dx/dg=245/2g2=4.9,我们有S(x,g)=(dx/dg)*(g/x)=4.9*(5/8)=3.0625。于是猪的生长率增加1%,会导致大约等待3%的时间再将猪售出。
灵敏度分析的成功应用要有较好的判断力,通常即不可能对模型中的每个参数都计算灵敏度分析,也没有特别的要求。我们需要选择那些有较大不确定性的参数进行灵敏度分析。对灵敏度系数的解释还要依赖与参数的不确定程度,主要问题是数据的不确定程度影响答案的置信度。在这个问题中,我们通常认为猪的生长率g比价格下降率r更可靠。如果我们观察了猪或者其他类似动物在过去的生长情况,则g有25%的误差会是很不寻常的,但对r的估计有25%的误差则不足为奇。
数学模型的稳健性
一个数学模型称为稳健的,是指即使这个模型不完全精确,由其导出的结果也是正确的。在实际问题中,我们不会有绝对准确的信息,即使能够建立一个完美的精确模型,我们也可能采取较为简单和易于处理的方法。出于数学处理的方便和简化的目的,常常要做一些假设,建模者有责任要考察这些假设是否太特殊,以致使模型的结果无效。
上例中我们主要是假设猪的重量和每磅的价格都是时间线性函数。假设一年后,猪的重量为200+5*365=2025磅,卖出收益为0.65-0.01*365=-3美元/磅。一个更为实际的模型应该考虑到这些函数的非线性性,又考虑到随着时间的推移不确定性的增加。
考察售猪问题中的线性假设。基本方程为P=pw-0.45t。如果模型初始数据和假设没有与实际相差太远,则售猪的最佳时间应该有令P求导为0得到。计算后有p"w+pw"=0.45,得到只要猪价比饲养的费用增长快,就应暂时不卖出。其中,p"w为价格下降带来的损失,pw"为猪增重而增加的价值。考虑更一般的模型的情况,猪的未来增长和价格的未来变化并不确定。
假设如下情况,一个农民有一头重量大约是200磅的猪,上一周猪每天增重约5磅,五天前猪价为70美分/磅,但现在是65美分/磅,根据现有数据我们可以得出何时出售,问题是p"和w"在未来几周内不会保持常数,因此,两者不会是时间的线性函数。但是只要在这段时间内,两者变化不太大,假设他们保持为常数而导致的误差就不会太大。