【数学建模】排队论（最优化）

古城微笑少年丶 2023-03-04 09:23 3阅读 0赞

### 文章目录 ###

*  一、算法介绍
 *   *  1.算法介绍
     *  2.模型介绍
 *  二、适用问题
 *  三、算法总结
 *   *  1.M/M/1排队系统
     *  2.M/M/S排队系统
 *  四、应用场景举例
 *   *  1.M/M/1排队系统
     *  2.M/M/S排队系统1
     *  2.M/M/S排队系统2
 *  五、MATLAB代码
 *   *  1.M/M/1
     *  2.M/M/S
 *  六、实际案例
 *  七、论文案例片段（待完善）

> 排队论主要针对数学建模问题中的一些小的子问题进行求解，如果想直接使用请跳转至——**四**、**五**  
> [视频回顾][Link 1]

# 一、算法介绍 #

## 1.算法介绍 ##

排队论发源于上世纪初。当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。这个新发明带来了一个新问题，即通话线路与电话用户呼叫的数量关系应如何妥善解决，这个问题久久未能解决。  
 1909年，丹麦的哥本哈根电话公司A. K.埃尔浪(Er lang)在热力学统计平衡概念的启发下解决了这个问题。  
 (1)由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免;  
 (2)排队过程，通常是一个随机过程，排队论又称“随机服务系统理论”  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]

## 2.模型介绍 ##

*  排队系统的要素

(1)顾客输入过程;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]  
 (2)排队结构与排队规则;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]  
 (3)服务机构与服务规则;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3]

*  服务台(员)为顾客服务的顺序:  
    a)先到先服务(FCFS);  
    b)后到先服务(LCFS);  
    c)随机服务;  
    d)优先服务;
 *  到达间隔和服务时间典型分布  
    （1）泊松分布M ；  
    （2）负指数分布M ；  
    （3）k阶爱尔朗分布Ek；  
    （4）确定型分布D；  
    （5）一般服务时间分布G；
 *  排队模型示例  
    ——M/M/1，M/D/1，M/ Ek /1；  
    ——M/M/c，M/M/c/∞/m，  
    ——M/M/c/N/∞，。。。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 4]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][20200803110239381.png]
 *  评价参数⭐⭐⭐  
    ⭐1、队长与排队长  
     (1)队长: 系统中的顾客数（n）期望值记为Ls ；  
     (2)排队长: 系统中排队等待服务的顾客数;期望值记为Lq  
    ⭐2、逗留时间与等待时间  
     (1)逗留时间:指一个顾客在系统中的全部停留时间；期望值，记为Ws  
     (2)等待时间:指一个顾客在系统中的排队等待时间；期望值，记为Wq  
    Ws = Wq + E\[服务时间\]  
    3、其他相关指标  
     (1)忙期: 指从顾客到达空闲服务机构起到服务  
    机构再次空闲的时间长度；  
     (2)忙期服务量：指一个忙期内系统平均完成  
    服务的顾客数；  
     (3)损失率: 指顾客到达排队系统，未接受服务  
    而离去的概率；  
    ⭐ (4)服务强度：ρ= λ/sμ；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 7]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 8]

# 二、适用问题 #

*  **排队问题**
 *  **例如：**

1.  ![排队][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 9]

# 三、算法总结 #

## 1.M/M/1排队系统 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 11]

## 2.M/M/S排队系统 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 14]

# 四、应用场景举例 #

## 1.M/M/1排队系统 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 17]

## 2.M/M/S排队系统1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 19]

## 2.M/M/S排队系统2 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 20]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 21]

# 五、MATLAB代码 #

## 1.M/M/1 ##

clear 
    clc 
    %***************************************** 
    %初始化顾客源 
    %***************************************** 
    %总仿真时间 
    Total_time = 10; 
    %队列最大长度 
    N = 10000000000; 
    %到达率与服务率 
    lambda = 10; 
    mu = 6; 
    %平均到达时间与平均服务时间 
    arr_mean = 1/lambda; 
    ser_mean = 1/mu; 
    arr_num = round(Total_time*lambda*2); 
    events = []; 
    %按负指数分布产生各顾客达到时间间隔 
    events(1,:) = exprnd(arr_mean,1,arr_num); 
    %各顾客的到达时刻等于时间间隔的累积和 
    events(1,:) = cumsum(events(1,:)); 
    %按负指数分布产生各顾客服务时间 
    events(2,:) = exprnd(ser_mean,1,arr_num); 
    %计算仿真顾客个数，即到达时刻在仿真时间内的顾客数 
    len_sim = sum(events(1,:)<= Total_time); 
    %***************************************** 
    %计算第 1个顾客的信息 
    %***************************************** 
    %第 1个顾客进入系统后直接接受服务，无需等待 
    events(3,1) = 0; 
    %其离开时刻等于其到达时刻与服务时间之和 
    events(4,1) = events(1,1)+events(2,1); 
    %其肯定被系统接纳，此时系统内共有 
    %1个顾客，故标志位置1 
    events(5,1) = 1; 
    %其进入系统后，系统内已有成员序号为 1 
    member = [1]; 
    for i = 2:arr_num 
    %如果第 i个顾客的到达时间超过了仿真时间，则跳出循环 
    
    if events(1,i)>Total_time 
    
    break; 
    
    else 
    number = sum(events(4,member) > events(1,i)); 
    %如果系统已满，则系统拒绝第 i个顾客，其标志位置 0 
    if number >= N+1 
    events(5,i) = 0; 
    %如果系统为空，则第 i个顾客直接接受服务 
    else 
    if number == 0 
    %其等待时间为 0
    
    2009.1516
    
    %PROGRAMLANGUAGEPROGRAMLANGUAGE
    events(3,i) = 0; 
    %其离开时刻等于到达时刻与服务时间之和 
    events(4,i) = events(1,i)+events(2,i); 
    %其标志位置 1 
    events(5,i) = 1; 
    member = [member,i]; 
    %如果系统有顾客正在接受服务，且系统等待队列未满，则 第 i个顾客进入系统 
    
    else len_mem = length(member); 
    %其等待时间等于队列中前一个顾客的离开时刻减去其到 达时刻 
    events(3,i)=events(4,member(len_mem))-events(1,i); 
    %其离开时刻等于队列中前一个顾客的离开时刻加上其服 
    %务时间 
    events(4,i)=events(4,member(len_mem))+events(2,i); 
    %标识位表示其进入系统后，系统内共有的顾客数 
    events(5,i) = number+1; 
    member = [member,i]; 
    end 
    end 
    
    end 
    end 
    %仿真结束时，进入系统的总顾客数 
    len_mem = length(member); 
    %***************************************** 
    %输出结果 
    %***************************************** 
    %绘制在仿真时间内，进入系统的所有顾客的到达时刻和离 
    %开时刻曲线图（stairs：绘制二维阶梯图） 
    stairs([0 events(1,member)],0:len_mem); 
    hold on; 
    stairs([0 events(4,member)],0:len_mem,'.-r'); 
    legend('到达时间 ','离开时间 '); 
    hold off; 
    grid on; 
    %绘制在仿真时间内，进入系统的所有顾客的停留时间和等 
    %待时间曲线图（plot：绘制二维线性图） 
    figure; 
    plot(1:len_mem,events(3,member),'r-*',1: len_mem,events(2,member)+events(3,member),'k-'); 
    legend('等待时间 ','停留时间 '); 
    grid on;

## 2.M/M/S ##

s=2;
    mu=4;
    lambda=3;
    ro=lambda/mu;
    ros=ro/s;
    sum1=0;
    
    for i=0:(s-1)
        sum1=sum1+ro.^i/factorial(i);
    end
    
    sum2=ro.^s/factorial(s)/(1-ros);
    
    p0=1/(sum1+sum2);
    p=ro.^s.*p0/factorial(s)/(1-ros);
    Lq=p.*ros/(1-ros);
    L=Lq+ro;
    W=L/lambda;
    Wq=Lq/lambda;
    fprintf('排队等待的平均人数为%5.2f人\n',Lq)
    fprintf('系统内的平均人数为%5.2f人\n',L)
    fprintf('平均逗留时间为%5.2f分钟\n',W*60)
    fprintf('平均等待时间为%5.2f分种\n',Wq*60)

# 六、实际案例 #

# 七、论文案例片段（待完善） #

[Link 1]: https://www.bilibili.com/video/BV12W411X7aE?p=9
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]: /images/20230208/2d9da686c20d475986857c6b9212dc7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]: /images/20230208/0dc11c54e1dc4d1a862c2930be09de63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]: /images/20230208/e488583c68614046ae00fe130fdb0f32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3]: /images/20230208/2bff33b6f67b44a5ba4f6a9752384ccf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 4]: /images/20230208/b17398eb0a0d455fab04f4f629bd453b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 5]: /images/20230208/a1a0d31baff9452a9b295031a90f0d58.png
[20200803110239381.png]: /images/20230208/634864d73ce4458ba69d51f0fb152c57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 6]: /images/20230208/a0201310da774906a7d6dfb8471bf6c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 7]: /images/20230208/9192248ea9894b86b03b1d7e7b498899.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 8]: /images/20230208/6a23f8681107411685295fba9ffe04b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 9]: /images/20230208/1d7443e3e1014bb4aaf3509474a1e076.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 10]: /images/20230208/0ac87126d82b4f5a9da7b775a4ee2eda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 11]: /images/20230208/3aeb761b3bb9431f8262b56d9908bda0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 12]: /images/20230208/ba727c292ca74ab59ea5413ae54de5d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 13]: /images/20230208/e6f414e5e138488b94295f827513e5d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 14]: /images/20230208/085c163227284af7b3c299f080df535a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 15]: /images/20230208/d845bdb826f242d7932dfbf2f7fdc24d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 16]: /images/20230208/c491f4abe36346aebcd05cbfa5531034.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 17]: /images/20230208/4e5441532fd74e11a942a638e6a293b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 18]: /images/20230208/c99afec9ca0c4477b104d735734a5315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 19]: /images/20230208/4079ed33a4094e478ed1475cf4172bad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 20]: /images/20230208/717f1d92673d4f69bceecf04e8991d44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 21]: /images/20230208/1b32802b111c4fe280f61cf3203f5d0d.png