首页 > 其他分享 >排队论——随机服务系统仿真精解

排队论——随机服务系统仿真精解

时间:2024-09-20 22:24:49浏览次数:8  
标签:仿真 self 系统 mu 随机 env time 精解

排队论作为研究随机服务系统的重要工具,专门研究系统中客户到达、排队、服务和离开的过程。排队论的核心目的是通过数学建模和分析,研究系统的性能指标,如平均等待时间、队列长度、系统的吞吐量等。虽然排队论提供了强大的数学工具来分析随机服务系统,但在许多复杂的实际问题中,精确的数学模型可能难以建立。这时候,模拟与仿真技术便成为了研究和优化系统的重要方法。
模拟是通过计算机程序对一个真实系统进行近似模拟的过程。通过在仿真中引入随机变量,可以对系统的随机行为进行研究,从而评估系统在不同条件下的性能表现。仿真不仅可以用于验证理论模型,还能用于探索无法通过解析方法解决的复杂系统。与排队论的解析模型不同,模拟与仿真更灵活,可以处理非标准的、复杂的排队系统。一个典型的应用场景是机场的安检系统。乘客到达安检口的时间、安检速度、安检通道数量等因素都具有随机性。通过仿真技术,可以对不同配置方案下的乘客等待时间、系统吞吐量等性能指标进行估计,从而为决策者提供优化方案。

单服务台 多服务台

一、Python仿真库概述

仿真库名 用途 概述 功能特点
SimPy 离散事件仿真 简单易用的离散事件仿真库,适合模拟排队系统、生产线、交通系统等。 支持并发进程,简单易用,适用于大多数离散事件仿真需求。
DEAP 蒙特卡洛仿真、遗传算法仿真 用于演化计算的库,适合用于遗传算法、遗传规划、模拟进化过程、解决优化问题等。 支持遗传算法、演化策略等,支持分布式计算,适合优化问题、复杂的决策系统。
PyDSTool 动力学系统仿真 适用于连续和混合动力系统仿真的工具库。 支持符号数学和自动微分,适合科学研究和复杂系统的仿真。
SALib 敏感性分析、蒙特卡洛仿真 用于敏感性分析的库,常与蒙特卡洛仿真结合使用。 支持全局和局部敏感性分析,可以用于评估输入参数对模型输出的影响,常与其他仿真库结合使用。
PySim 系统建模与仿真 通用的仿真框架,适合模拟各种物理系统。 支持多学科系统仿真,支持FMI标准,适用于复杂的工程仿真需求。
AnyLogic 系统动力学、离散事件、Agent-Based仿真 商业化的仿真平台,提供Python接口来进行定制化仿真。 提供Python接口来扩展仿真能力,适合大规模工业仿真,可用于供应链管理、物流、生产制造等领域。
Gym 强化学习仿真 用于强化学习的仿真环境库。 预设了多种仿真环境,适合强化学习和动态系统仿真,灵活的接口,可以自定义仿真环境。
Mesa 基于Agent的仿真 基于Agent的仿真框架,适合用于模拟复杂系统中的个体行为和交互。 易于使用的API,快速构建多智能体模型,提供图形化界面和可视化工具,适合社会学、经济学、生态学等领域。

二、M/M/1排队系统模型仿真

2.1 M/M/1排队系统的绩效指标

在M/M/1排队模型中,系统只有一个服务机构,顾客到达的时间间隔和服务时间都服从指数分布。通过M/M/1模型,可以计算系统的各项性能指标。下面我们先给出6个常见的性能指标的计算公式,然后提供一个Python程序来计算这些指标。

常用符号

  • λ: 到达率(每单位时间内的平均顾客到达数量)
  • μ: 服务率(每单位时间内的平均服务数量)
  • ρ: 系统的利用率(利用率 = λ/μ)

绩效指标及公式

  • 系统利用率 \(ρ (ρ = λ/μ)\):系统中服务器被占用的比例。
  • 系统中平均客户数 \(L (L = ρ / (1 - ρ))\):系统中的平均客户数,包括排队和正在接受服务的客户。
  • 队列中的平均客户数 \(L_q (L_q = ρ^2 / (1 - ρ))\):系统中正在排队的平均客户数,不包括正在服务的客户。
  • 系统中客户的平均逗留时间 \(W (W = 1 / (μ - λ))\):系统中每个客户的平均停留时间,包括等待和服务时间。
  • 客户在队列中的平均等待时间 \(W_q (W_q = ρ / (μ - λ))\):每个客户在排队中等待的平均时间,不包括服务时间。
  • 空闲概率 $P_0 (P_0 = 1 - ρ):系统处于空闲状态(即无客户到达或正在服务)的概率。
# 定义计算性能指标的函数
def mm1_performance(lmbda, mu):
    # 系统利用率 rho
    rho = lmbda / mu

    if rho >= 1:
        raise ValueError("系统利用率不能大于或等于1,说明到达率必须小于服务率。")

    # 系统中平均客户数 L
    L = rho / (1 - rho)

    # 队列中的平均客户数 Lq
    Lq = rho**2 / (1 - rho)

    # 系统中客户的平均逗留时间 W
    W = 1 / (mu - lmbda)

    # 客户在队列中的平均等待时间 Wq
    Wq = rho / (mu - lmbda)

    # 空闲概率 P0
    P0 = 1 - rho

    # 返回结果
    return {
        "系统利用率 (rho)": rho,
        "系统中平均客户数 (L)": L,
        "队列中的平均客户数 (Lq)": Lq,
        "系统中客户的平均逗留时间 (W)": W,
        "客户在队列中的平均等待时间 (Wq)": Wq,
        "空闲概率 (P0)": P0
    }

# 固定的到达率和服务率
lmbda = 3  # 到达率 λ
mu = 5     # 服务率 μ

# 计算并输出各个性能指标,保留两位小数
try:
    performance = mm1_performance(lmbda, mu)
    for key, value in performance.items():
        print(f"{key}: {value:.2f}")
except ValueError as e:
    print(e)
系统利用率 (rho): 0.60
系统中平均客户数 (L): 1.50
队列中的平均客户数 (Lq): 0.90
系统中客户的平均逗留时间 (W): 0.50
客户在队列中的平均等待时间 (Wq): 0.30
空闲概率 (P0): 0.40

2.2 M/M/1排队系统仿真分析

import simpy
import random
import matplotlib.pyplot as plt
from matplotlib import rcParams

# 设置中文字体
rcParams['font.sans-serif'] = ['SimHei']  # 使用黑体
rcParams['axes.unicode_minus'] = False    # 正常显示负号

# 设置种子以确保仿真结果的可重复性
RANDOM_SEED = 42
random.seed(RANDOM_SEED)

# 定义全局变量
lmbda = 3  # 到达率 λ (每单位时间的顾客到达数)
mu = 5     # 服务率 μ (每单位时间的服务能力)
SIM_TIME = 1000  # 仿真运行时间

class MM1Queue:
    def __init__(self, env, mu):
        self.env = env
        self.server = simpy.Resource(env, capacity=1)  # 1表示单个服务器
        self.mu = mu
        self.total_waiting_time = 0.0
        self.total_system_time = 0.0
        self.total_customers = 0
        self.system_size = 0  # 系统中顾客人数
        self.time_data = []  # 时间点
        self.size_data = []  # 系统中顾客人数

    def serve(self, customer):
        """顾客服务时间"""
        yield self.env.timeout(random.expovariate(self.mu))
        
    def arrival(self, customer):
        """顾客到达"""
        arrival_time = self.env.now
        self.system_size += 1  # 系统中顾客人数 +1
        self.record_data()  # 记录当前时刻的顾客人数

        with self.server.request() as request:
            yield request  # 等待服务
            waiting_time = self.env.now - arrival_time  # 计算等待时间
            self.total_waiting_time += waiting_time
            self.total_customers += 1

            yield self.env.process(self.serve(customer))  # 开始服务

            self.system_size -= 1  # 系统中顾客人数 -1
            self.record_data()  # 记录当前时刻的顾客人数

            # 计算系统内停留时间
            system_time = self.env.now - arrival_time
            self.total_system_time += system_time

    def record_data(self):
        """记录当前仿真时间和系统中顾客人数"""
        self.time_data.append(self.env.now)
        self.size_data.append(self.system_size)

    def run(self):
        """顾客不断到达"""
        customer_id = 0
        while True:
            yield self.env.timeout(random.expovariate(lmbda))  # 顾客到达时间间隔
            customer_id += 1
            self.env.process(self.arrival(customer_id))

def simulate_mm1():
    # 初始化环境
    env = simpy.Environment()
    mm1_queue = MM1Queue(env, mu)
    
    # 运行仿真
    env.process(mm1_queue.run())
    env.run(until=SIM_TIME)
    
    # 计算系统性能指标
    L = mm1_queue.total_system_time / SIM_TIME  # 系统中平均客户数
    Lq = mm1_queue.total_waiting_time / SIM_TIME  # 队列中的平均客户数
    W = mm1_queue.total_system_time / mm1_queue.total_customers  # 系统中客户的平均逗留时间
    Wq = mm1_queue.total_waiting_time / mm1_queue.total_customers  # 客户在队列中的平均等待时间

    # 输出结果
    print(f"系统中平均客户数 (L): {L:.2f}")
    print(f"队列中的平均客户数 (Lq): {Lq:.2f}")
    print(f"系统中客户的平均逗留时间 (W): {W:.2f}")
    print(f"客户在队列中的平均等待时间 (Wq): {Wq:.2f}")
    
    # 绘制时间-顾客人数曲线图
    plt.plot(mm1_queue.time_data, mm1_queue.size_data)
    plt.xlabel('仿真时间')
    plt.ylabel('系统中顾客人数')
    plt.title('M/M/1 排队系统仿真')
    plt.grid(True)
    plt.show()

# 运行仿真并输出结果
simulate_mm1()
系统中平均客户数 (L): 1.59
队列中的平均客户数 (Lq): 1.00
系统中客户的平均逗留时间 (W): 0.54
客户在队列中的平均等待时间 (Wq): 0.34

三、M/M/c排队系统仿真分析

3.1 M/M/c排队系统的绩效指标

对于 M/M/c 系统,常见的6个性能指标及其计算公式如下:
常用符号

  • λ: 到达率(每单位时间内的平均顾客到达数量)
  • μ: 服务率(每单位时间内的平均服务数量)
  • c: 为服务台的数量

绩效指标及公式

  • 系统利用率 $ \rho(\rho = \frac{\lambda}{c\mu} $):表示系统的平均工作负荷,或是所有服务台的平均占用率。
  • 队列中的平均顾客数 \(L_q(L_q = \frac{P_0 (\lambda/\mu)^c \rho}{c! (1 - \rho)^2})\):表示在队列中等待服务的平均顾客数量。这里,\(P_0\) 是系统空闲时的概率。
  • 系统中平均顾客数 $L(L = L_q + \frac{\lambda}{\mu} $):表示在整个系统(包括正在接受服务的顾客)中的平均顾客数量。
  • 顾客在队列中的平均等待时间 $ W_q (W_q = \frac{L_q}{\lambda} $):表示顾客在队列中等待服务的平均时间。
  • 顾客在系统中的平均逗留时间 $ W ( W = W_q + \frac{1}{\mu} $):表示顾客在整个系统中(包括服务时间)的平均逗留时间。
  • 系统空闲的概率 $ P_0( P_0 = \left[ \sum_{n=0}^{c-1} \frac{(\lambda/\mu)^n}{n!} + \frac{(\lambda/\mu)^c}{c!(1 - \rho)} \right]^{-1} $):表示系统中没有顾客时的概率,即所有服务台均空闲的概率。
import math

# 输入数据
lmbda = 0.9  # 到达率 λ (人/分钟)
mu = 0.4     # 服务率 μ (人/分钟)
c = 3        # 售票窗口数

# 系统利用率 ρ
rho = lmbda / (c * mu)

# 计算 P0 (系统空闲的概率)
def calculate_P0(lmbda, mu, c):
    sum_terms = sum((lmbda / mu) ** n / math.factorial(n) for n in range(c))
    last_term = ((lmbda / mu) ** c) / (math.factorial(c) * (1 - rho))
    P0 = 1 / (sum_terms + last_term)
    return P0

# 计算 Lq (队列中的平均顾客数)
def calculate_Lq(lmbda, mu, c, rho, P0):
    numerator = P0 * (lmbda / mu) ** c * rho
    denominator = math.factorial(c) * (1 - rho) ** 2
    Lq = numerator / denominator
    return Lq

# 计算各项指标
P0 = calculate_P0(lmbda, mu, c)  # 系统空闲的概率
Lq = calculate_Lq(lmbda, mu, c, rho, P0)  # 队列中的平均顾客数
L = Lq + lmbda / mu  # 系统中平均顾客数
Wq = Lq / lmbda  # 顾客在队列中的平均等待时间
W = Wq + 1 / mu  # 顾客在系统中的平均逗留时间

# 输出结果
print(f"系统利用率 (ρ): {rho:.2f}")
print(f"系统空闲的概率 (P0): {P0:.4f}")
print(f"队列中的平均顾客数 (Lq): {Lq:.2f}")
print(f"系统中平均顾客数 (L): {L:.2f}")
print(f"顾客在队列中的平均等待时间 (Wq): {Wq:.2f} 分钟")
print(f"顾客在系统中的平均逗留时间 (W): {W:.2f} 分钟")

3.2 M/M/c排队系统仿真分析

import simpy
import random
import matplotlib.pyplot as plt
from matplotlib import rcParams

# 设置中文字体支持
rcParams['font.sans-serif'] = ['SimHei']  # 使用黑体显示中文
rcParams['axes.unicode_minus'] = False    # 解决负号显示问题

# 输入数据
RANDOM_SEED = 42
lmbda = 0.9  # 到达率 λ (人/分钟)
mu = 0.4     # 服务率 μ (人/分钟)
c = 3        # 售票窗口数
SIM_TIME = 1000  # 仿真时间(分钟)

random.seed(RANDOM_SEED)

class MMcQueue:
    def __init__(self, env, num_servers, mu):
        self.env = env
        self.server = simpy.Resource(env, capacity=num_servers)
        self.mu = mu
        self.total_waiting_time = 0.0
        self.total_system_time = 0.0
        self.total_customers = 0
        self.customers_in_queue = 0
        self.queue_time = 0.0
        self.system_customers = []
        
        # 记录仿真过程中各时刻的系统内顾客人数
        self.time_data = []
        self.num_customers_data = []

    def serve(self, customer):
        """服务过程,顾客服务时间"""
        service_time = random.expovariate(self.mu)
        yield self.env.timeout(service_time)

    def arrival(self, customer):
        """顾客到达"""
        arrival_time = self.env.now
        self.system_customers.append(len(self.server.queue) + len(self.server.users))
        
        # 记录当前时刻的顾客人数
        self.record_customers_count()

        # 顾客加入队列
        with self.server.request() as request:
            yield request
            waiting_time = self.env.now - arrival_time  # 计算顾客等待时间
            self.total_waiting_time += waiting_time
            self.queue_time += len(self.server.queue)
            self.total_customers += 1
            
            # 开始服务
            yield self.env.process(self.serve(customer))
            
            # 系统内停留时间 = 当前时间 - 到达时间
            system_time = self.env.now - arrival_time
            self.total_system_time += system_time

            # 记录当前时刻的顾客人数
            self.record_customers_count()

    def record_customers_count(self):
        """记录当前仿真时刻的系统内顾客人数"""
        current_time = self.env.now
        num_customers = len(self.server.queue) + len(self.server.users)
        self.time_data.append(current_time)
        self.num_customers_data.append(num_customers)

def run_simulation(env, num_servers, mu):
    mmc_queue = MMcQueue(env, num_servers, mu)
    
    def customer_arrivals():
        customer_id = 0
        while True:
            # 顾客到达时间
            inter_arrival_time = random.expovariate(lmbda)
            yield env.timeout(inter_arrival_time)
            customer_id += 1
            env.process(mmc_queue.arrival(customer_id))
    
    # 启动顾客到达过程
    env.process(customer_arrivals())
    
    # 运行仿真
    env.run(until=SIM_TIME)
    
    # 计算系统性能指标
    Lq = mmc_queue.total_waiting_time / SIM_TIME  # 队列中的平均顾客数
    L = sum(mmc_queue.system_customers) / len(mmc_queue.system_customers)  # 系统中平均顾客数
    Wq = mmc_queue.total_waiting_time / mmc_queue.total_customers  # 顾客在队列中的平均等待时间
    W = mmc_queue.total_system_time / mmc_queue.total_customers  # 顾客在系统中的平均逗留时间

    # 输出结果
    print(f"队列中的平均顾客数 (Lq): {Lq:.2f}")
    print(f"系统中平均顾客数 (L): {L:.2f}")
    print(f"顾客在队列中的平均等待时间 (Wq): {Wq:.2f} 分钟")
    print(f"顾客在系统中的平均逗留时间 (W): {W:.2f} 分钟")
    
    # 绘制时间-顾客人数曲线图
    plt.figure(figsize=(10, 6))
    plt.plot(mmc_queue.time_data, mmc_queue.num_customers_data, label='系统内顾客人数', color='b')
    plt.xlabel('仿真时间(分钟)')
    plt.ylabel('系统内顾客人数')
    plt.title('M/M/3 排队系统中各时刻的顾客人数')
    plt.grid(True)
    plt.legend()
    plt.show()

# 运行仿真
env = simpy.Environment()
run_simulation(env, c, mu)

四、复杂排队系统仿真

复杂排队系统结构

这是一个多阶段、并行处理的排队模型,包含多个服务台多个服务节点。具体而言,系统包含多个队列和不同的服务率\(\mu\),包括:
\(\mu_r = 10\)\mu_b = 13 \mu_1 = 12 \mu_2 = 9 \mu_3 = 16

这是一个多通道、分层服务系统,常见于制造或物流场景。

仿真步骤:

  1. 顾客到达:顾客到达系统时可以进入不同的子系统。子系统包含两个阶段,分别通过 ( \mu_r ) 和 ( \mu_b ) 进行服务,之后可能进入下一个阶段。
  2. 各阶段的服务:根据不同的到达流,顾客在不同阶段接受服务,每个阶段有不同的服务率。
  3. 服务完毕:最终,顾客在系统中的最后一个节点完成所有服务。
#大模型编写的程序,没有验证,运行没有问题
import simpy
import random
import matplotlib.pyplot as plt

# 设置系统的服务率
mu_r = 10  # 红色队列服务率
mu_b = 13  # 蓝色队列服务率
mu1 = 12   # 第一个阶段服务率 (2个服务台)
mu2 = 9    # 第二个阶段服务率 (3个服务台)
mu3 = 16   # 第三个阶段服务率 (3个服务台)
SIM_TIME = 1000  # 仿真时间(分钟)

# 随机数种子
RANDOM_SEED = 42
random.seed(RANDOM_SEED)

class ComplexQueueSystem:
    def __init__(self, env):
        self.env = env
        # 定义各个服务资源,设置相应的服务台数量
        self.server_r = simpy.Resource(env, capacity=1)  # 红色队列1个服务台
        self.server_b = simpy.Resource(env, capacity=1)  # 蓝色队列1个服务台
        self.server1 = simpy.Resource(env, capacity=2)   # 阶段1有2个服务台
        self.server2 = simpy.Resource(env, capacity=3)   # 阶段2有3个服务台
        self.server3 = simpy.Resource(env, capacity=3)   # 阶段3有3个服务台
        
        # 统计数据
        self.total_waiting_time = 0
        self.total_system_time = 0
        self.total_customers = 0
        self.customers_in_queue = 0
        self.system_customers = []

    def serve(self, mu):
        """服务过程,服务时间服从负指数分布"""
        service_time = random.expovariate(mu)
        yield self.env.timeout(service_time)

    def process_customer(self, customer):
        arrival_time = self.env.now

        # 顾客进入红色或蓝色队列
        if random.choice(['red', 'blue']) == 'red':
            with self.server_r.request() as request:
                yield request
                yield self.env.process(self.serve(mu_r))
        else:
            with self.server_b.request() as request:
                yield request
                yield self.env.process(self.serve(mu_b))

        # 第一个服务阶段
        with self.server1.request() as request:
            yield request
            yield self.env.process(self.serve(mu1))
        
        # 第二个服务阶段
        with self.server2.request() as request:
            yield request
            yield self.env.process(self.serve(mu2))
        
        # 第三个服务阶段
        with self.server3.request() as request:
            yield request
            yield self.env.process(self.serve(mu3))

        # 计算总的系统停留时间
        system_time = self.env.now - arrival_time
        self.total_system_time += system_time

        # 统计顾客总数
        self.total_customers += 1

def customer_arrival(env, system, arrival_rate):
    """顾客到达过程,泊松到达"""
    while True:
        yield env.timeout(random.expovariate(arrival_rate))
        customer_id = system.total_customers + 1
        env.process(system.process_customer(customer_id))

def run_simulation():
    env = simpy.Environment()
    system = ComplexQueueSystem(env)
    
    # 顾客到达率
    arrival_rate = 5  # 每单位时间到达顾客数
    
    # 启动顾客到达过程
    env.process(customer_arrival(env, system, arrival_rate))
    
    # 运行仿真
    env.run(until=SIM_TIME)
    
    # 计算指标
    L = system.total_system_time / SIM_TIME  # 系统中的平均顾客数
    W = system.total_system_time / system.total_customers  # 顾客在系统中的平均逗留时间

    print(f"系统中平均顾客数 (L): {L:.2f}")
    print(f"顾客在系统中的平均逗留时间 (W): {W:.2f} 分钟")

# 运行仿真
run_simulation()

总结

随着大数据、人工智能、物联网等技术的发展,随机服务系统、排队论与仿真技术的应用前景将更加广阔。一方面,通过融合大数据分析和机器学习算法,可以更准确地预测系统中各类随机事件的发生规律,从而提高系统的效率;另一方面,云计算和高性能计算技术的发展,也使得复杂系统的仿真成为可能。模拟与仿真是解决随机服务系统实际问题的重要工具,通过理论分析和计算机仿真相结合的方式,研究人员和工程师可以优化系统的资源配置、提高服务效率,从而应对复杂系统中的随机性和不确定性。在未来,随着技术的进步,这些方法将会在更多领域得到广泛应用,并为各行各业带来更大的效益。

参考文献

  1. 排队模型和排队系统仿真
  2. 用R语言模拟随机服务排队系统
  3. 排队系统仿真python 排队系统建模仿真

标签:仿真,self,系统,mu,随机,env,time,精解
From: https://www.cnblogs.com/haohai9309/p/18423272

相关文章