排队论_系统仿真.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本文档使用了Python的离散事件仿真库对于排队论模型进行了仿真  \n",
    "仿真的主要目的是提供个性化定制，如对分布的设定，对排队规则的设定等。  \n",
    "本文档提供了： \n",
    "基础排队模型仿真  \n",
    "Erlang分布实现  \n",
    "通用分布函数适配器  \n",
    "如有额外需求，可以前往SimPy官网进行查阅\n",
    "Copy Right：@MCM 2019 SJTU 61组 朱文杰"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SimPy 核心概念\n",
    "https://zhuanlan.zhihu.com/p/31526894<br/>\n",
    "SimPy 是离散事件驱动的仿真库。<br/>\n",
    "所有活动部件，例如车辆、顾客,、即便是信息，都可以用 process (进程) 来模拟。<br/>\n",
    "这些 process 存放在 environment (环境) 。所有 process 之间，以及与environment 之间的互动，通过 event (事件) 来进行.<br/>\n",
    "\n",
    "process 表达为 generators (生成器)， 构建event(事件)并通过 yield 语句抛出事件。<br/>\n",
    "\n",
    "当一个进程抛出事件，进程会被暂停，直到事件被激活(triggered)。多个进程可以等待同一个事件。 SimPy 会按照这些进程抛出的事件激活的先后， 来恢复进程。<br/>\n",
    "\n",
    "其实中最重要的一类事件是 Timeout， 这类事件允许一段时间后再被激活， 用来表达一个进程休眠或者保持当前的状态持续指定的一段时间。这类事件通过 Environment.timeout来调用。<br/>\n",
    "\n",
    "Environment<br/>\n",
    "\n",
    "Environment 决定仿真的起点/终点， 管理仿真元素之间的关联, 主要 API 有<br/>\n",
    "\n",
    "simpy.Environment.process - 添加仿真进程<br/>\n",
    "simpy.Environment.event - 创建事件<br/>\n",
    "simpy.Environment.timeout - 提供延时(timeout)事件<br/>\n",
    "simpy.Environment.until - 仿真结束的条件（时间或事件）<br/>\n",
    "simpy.Environment.run - 仿真启动<br/>\n",
    "\n",
    "Resource 和 Store\n",
    "\n",
    "Resource/Store 也是另外一类重要的核心概念, 但凡仿真中涉及的人力资源以及工艺上的物料消耗都会抽象用 Resource 来表达, 主要的 method 是 request. Store 处理各种优先级的队列问题, 表现跟 queue 一致, 通过 method get / put 存放 item<br/>\n",
    "\n",
    "Store - 抽象队列<br/>\n",
    "\n",
    "simpy.Store - 存取 item 遵循仿真时间上的先到后到<br/>\n",
    "simpy.PriorityStore - 存取 item 遵循仿真时间上的先到后到同时考虑人为添加的优先级<br/>\n",
    "simpy.FilterStore - 存取 item 遵循仿真时间上的先到后到, 同时队列中存在分类, 按照不同类别进行存取<br/>\n",
    "simpy.Container - 表达连续/不可分的物质, 包括液体/气体的存放, 存取的是一个 float 数值<br/>\n",
    "Resource - 抽象资源<br/>\n",
    "\n",
    "simpy.Resource - 表达人力资源或某种限制条件, 例如某个工序可调用的工人数, 可以调用的机器数<br/>\n",
    "simpy.PriorityResource - 兼容Resource的功能, 添加可以插队的功能, 高优先级的进程可以优先调用资源, 但只能是在前一个被服务的进程结束以后进行插队<br/>\n",
    "simpy.PreemptiveResource - 兼容Resource的功能, 添加可以插队的功能, 高优先级的进程可以打断正在被服务的进程进行插队<br/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy.random import *\n",
    "from simpy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "高阶函数随机数生成器  \n",
    "\n",
    "输入：分布函数，单一参数(多参数请柯里化)  \n",
    "输出：随机数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rng(dis,param):\n",
    "    \"\"\"random number generator\"\"\"\n",
    "    def generate():\n",
    "        return dis(lam=param,size=1)[0]\n",
    "    return generate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Erlang分布函数：  \n",
    "输入：结束  \n",
    "输出：k阶erlang分布函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def erlang(k):\n",
    "    \"\"\"由k个指数分布拟合\"\"\"\n",
    "    def exp2erlang(lam,size):\n",
    "        res=[]\n",
    "        for n in range(size):\n",
    "            k_poisson= exponential(lam/k,size=k)\n",
    "            sum=0\n",
    "            for x in k_poisson:\n",
    "                sum = sum + x\n",
    "            res.append(sum)\n",
    "        return res\n",
    "    return exp2erlang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.99565983119657\n"
     ]
    }
   ],
   "source": [
    "#测试，计算分布期望\n",
    "x=rng(erlang(10),10)\n",
    "sum=0\n",
    "for i in range(10000):\n",
    "    sum= sum+x()\n",
    "print(sum/10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#典型银行模型：FIFO\n",
    "def bankSample(X,Y,Z,A,B,EX):\n",
    "    \"\"\"\n",
    "银行排队服务例子\n",
    "\n",
    "情景:\n",
    "  一个柜台对客户进行服务, 服务耗时, 客户等候过长会离开柜台\n",
    "    %X 表示时间间隔分布\n",
    "    %Y 表示服务时间的分布\n",
    "    %Z 表示服务台的个数\n",
    "    %A 表示系统的容量,此处特殊化为客户的耐心时间分布\n",
    "    %B 表示顾客数\n",
    "    %以上参数必须有界，受到计算机精度限制，可以使用大常数近似无穷\n",
    "    %C 表示服务规则,请修改函数\n",
    "    %EX 传递了银行储蓄额的分布\n",
    "  \"\"\"\n",
    "    #加入随机种子是为了对比模型的变化\n",
    "    seed(2)\n",
    "    def source(env, number, interval,counter):\n",
    "        \"\"\"生成客户\"\"\"\n",
    "        for i in range(number):\n",
    "            c = customer(env, '客户%04d' % i, counter, time_in_bank=Y(),account=EX())\n",
    "            env.process(c)\n",
    "            yield env.timeout(interval)\n",
    "    #成功服务的客户\n",
    "    SUCC=0\n",
    "    #成功客户等待时间\n",
    "    WAIT=0\n",
    "    #成功客户逗留时间\n",
    "    STAY=0\n",
    "    #业务额\n",
    "    AMT=0\n",
    "    def customer(env, name, counter, time_in_bank,account):\n",
    "        nonlocal WAIT\n",
    "        nonlocal SUCC\n",
    "        nonlocal STAY\n",
    "        nonlocal AMT\n",
    "        \"\"\"顾客服务与离开仿真\"\"\"\n",
    "        arrive = env.now\n",
    "        #print('%7.4f  %s: 到达' % (arrive, name))\n",
    "        with counter.request() as req:\n",
    "            patience = A()\n",
    "            # 直到到达或者失去耐心\n",
    "            results = yield req | env.timeout(patience)\n",
    "            wait = env.now - arrive\n",
    "        \n",
    "            if req in results:\n",
    "                # 到达\n",
    "                WAIT=WAIT+wait\n",
    "                STAY=STAY+time_in_bank\n",
    "                AMT= AMT + account\n",
    "                #print('%7.4f %s:等待%6.3f' % (env.now, name, wait))\n",
    "                yield env.timeout(time_in_bank)\n",
    "                SUCC=SUCC+1\n",
    "                #print('%7.4f %s:服务完成' % (env.now, name))\n",
    "            else:\n",
    "                # We reneged\n",
    "                pass\n",
    "                #print('%7.4f %s:等待%6.3f后离开' % (env.now, name, wait))\n",
    "    # 初始化环境\n",
    "    print('排队问题仿真')\n",
    "    env = Environment()\n",
    "\n",
    "    # 开始协程\n",
    "    counter = Resource(env, capacity=Z)\n",
    "    env.process(source(env, B, X(), counter))\n",
    "    env.run()\n",
    "    print(\"总服务人数：{0:n}人\".format(SUCC))\n",
    "    print(\"总营业额：{0:n}元\".format(AMT))\n",
    "    print(\"总计失去： {0:n}名客户\".format(B-SUCC))\n",
    "    print(\"损失率为： {0:n}%\".format((B-SUCC)/B*100))\n",
    "    print(\"平均等待时间：{0:n}\".format(WAIT/SUCC) )\n",
    "    print(\"平均耗费时间：{0:n}\".format(STAY/SUCC) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#间隔分布\n",
    "X=rng(erlang(3),3)\n",
    "#服务时间分布\n",
    "Y=rng(erlang(3),10)\n",
    "#耐心时间分布\n",
    "A=rng(erlang(3),3)\n",
    "#业务额分布\n",
    "def normaltocurry(s):\n",
    "    def normalcurry(lam,size):\n",
    "        return normal(lam,s,size=size)\n",
    "    return normalcurry\n",
    "EX=rng(normaltocurry(200),1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排队问题仿真\n",
      "总服务人数：417人\n",
      "总营业额：409903元\n",
      "总计失去： 583名客户\n",
      "损失率为： 58.3%\n",
      "平均等待时间：1.8828\n",
      "平均耗费时间：10.0787\n"
     ]
    }
   ],
   "source": [
    "bankSample(X,Y,3,A,1000,EX)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#银行模型·ELite：优先队列\n",
    "def eliteBankSample(X,Y,Z,A,B,EX):\n",
    "    \"\"\"\n",
    "银行排队服务例子\n",
    "\n",
    "情景:\n",
    "  一个柜台对客户进行服务, 服务耗时, 客户等候过长会离开柜台\n",
    "    %X 表示时间间隔分布\n",
    "    %Y 表示服务时间的分布\n",
    "    %Z 表示服务台的个数\n",
    "    %A 表示系统的容量,此处特殊化为客户的耐心时间分布\n",
    "    %B 表示顾客数\n",
    "    %以上参数必须有界，受到计算机精度限制，可以使用大常数近似无穷\n",
    "    %C 表示服务规则,请修改函数\n",
    "    %EX 传递了银行储蓄额的分布\n",
    "  \"\"\"\n",
    "    #加入随机种子是为了对比模型的变化\n",
    "    seed(2)\n",
    "    def source(env, number, interval,counter):\n",
    "        \"\"\"生成客户\"\"\"\n",
    "        for i in range(number):\n",
    "            c = customer(env, '客户%04d' % i, counter, time_in_bank=Y(),account=EX())\n",
    "            env.process(c)\n",
    "            yield env.timeout(interval)\n",
    "    #成功服务的客户\n",
    "    SUCC=0\n",
    "    #成功客户等待时间\n",
    "    WAIT=0\n",
    "    #成功客户逗留时间\n",
    "    STAY=0\n",
    "    #业务额\n",
    "    AMT=0\n",
    "    def customer(env, name, counter, time_in_bank,account):\n",
    "        nonlocal WAIT\n",
    "        nonlocal SUCC\n",
    "        nonlocal STAY\n",
    "        nonlocal AMT\n",
    "        \"\"\"顾客服务与离开仿真\"\"\"\n",
    "        arrive = env.now\n",
    "        #print('%7.4f  %s: 到达' % (arrive, name))\n",
    "        #以业绩作为优先级，priority越小，优先级越大，\n",
    "        with counter.request(priority = 1/account) as req:\n",
    "            patience = A()\n",
    "            # 直到到达或者失去耐心\n",
    "            results = yield req | env.timeout(patience)\n",
    "            wait = env.now - arrive\n",
    "        \n",
    "            if req in results:\n",
    "                # 到达\n",
    "                WAIT=WAIT+wait\n",
    "                STAY=STAY+time_in_bank\n",
    "                AMT= AMT + account\n",
    "                #print('%7.4f %s:等待%6.3f' % (env.now, name, wait))\n",
    "                yield env.timeout(time_in_bank)\n",
    "                SUCC=SUCC+1\n",
    "                #print('%7.4f %s:服务完成' % (env.now, name))\n",
    "            else:\n",
    "                # We reneged\n",
    "                pass\n",
    "                #print('%7.4f %s:等待%6.3f后离开' % (env.now, name, wait))\n",
    "    # 初始化环境\n",
    "    print('排队问题仿真')\n",
    "    env = Environment()\n",
    "\n",
    "    # 开始协程\n",
    "    counter = PriorityResource(env, capacity=Z)\n",
    "    env.process(source(env, B, X(), counter))\n",
    "    env.run()\n",
    "    print(\"总服务人数：{0:n}人\".format(SUCC))\n",
    "    print(\"总营业额：{0:n}元\".format(AMT))\n",
    "    print(\"总计失去： {0:n}名客户\".format(B-SUCC))\n",
    "    print(\"损失率为： {0:n}%\".format((B-SUCC)/B*100))\n",
    "    print(\"平均等待时间：{0:n}\".format(WAIT/SUCC) )\n",
    "    print(\"平均耗费时间：{0:n}\".format(STAY/SUCC) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#间隔分布\n",
    "X=rng(erlang(3),3)\n",
    "#服务时间分布\n",
    "Y=rng(erlang(3),10)\n",
    "#耐心时间分布\n",
    "A=rng(erlang(3),3)\n",
    "#业务额分布\n",
    "def normaltocurry(s):\n",
    "    def normalcurry(lam,size):\n",
    "        return normal(lam,s,size=size)\n",
    "    return normalcurry\n",
    "EX=rng(normaltocurry(200),1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排队问题仿真\n",
      "总服务人数：432人\n",
      "总营业额：450145元\n",
      "总计失去： 568名客户\n",
      "损失率为： 56.8%\n",
      "平均等待时间：1.28862\n",
      "平均耗费时间：9.69799\n"
     ]
    }
   ],
   "source": [
    "eliteBankSample(X,Y,3,A,1000,EX)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "可以看出，在加入了上述充满着歧视与不公平的规则之后，  \n",
    "人均营业额上升，并且等待时间和耗费时间都有所下降  \n",
    "即：富人和银行获得了利益，富人节约了自己的时间，银行增加了业绩"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}