排队论在运筹学中的运用
【摘要】本文阐述了运筹学的起源、发展及其在我国的教学和实际运用，并着重对排队论的应用展开分析和讨论。 【关键词】运筹 排队论 应用
一、运筹学的起源和发展
运筹学（Operations Research ），顾名思义，即“运用研究”或“作业研究”简称为OR。溯及运筹学的发展历史，当从第一次世界大战开始。渊源第一次世界大战期间，1914～1915 年间，兰彻斯特为研究战争的胜负与兵力多寡、火力强弱之间的关系发表了若干军事论文；爱迪生在研究反潜战的项目中，汇编各项典型统计数据，用于选择回避或击毁潜艇的最佳方法，使用“战术对策演示盘”解决了免受潜艇攻击的问题。第二次时世界大战期间，鲍德西（Bawdsey）雷达站的负责人罗伊（A.P.Kowe）提出立即进行整个防空作战系统运行的研究。1942 年美国大西洋舰队反潜艇指挥官Baker 组织并领导了反潜艇战运筹组，即后来隶属于美国海军总司令部的运筹组的前身，这个运筹组集中了一批著名的科学家。战争结束时，海军运筹组的科学家人数已达到70 多位，美国陆军空战部队在Leach 的领导下建立的作战分析小组也超过了20 多个。
现代运筹学的起源可以追溯到在某些组织的管理中最先试用科学手段的时候。可是，现在普遍认为，运筹学的活动是从二次世界大战初期的军事任务开始的。第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。当战后的工业恢复繁荣时，由于组织内与日俱增的复杂性和专门化所产生的问题，使人们认识到这些问题基本上与战争中所曾面临的问题类似，只是具有不同的现实环境而已，运筹学就这样潜入工商企业和其它部门，在1950年代以后得到了广泛的应用。对于系统配置、聚散、竞争的运用机理深入的研究和应用，形成了比较完备的一套理论，如规划论、排队论、存贮论、决策论等等，由于其理论上的成熟，电子计算机的问世，又大大促进了运筹学的发展。
上世纪50年代初期到50年代末期,被认为是运筹学的成长时期。此阶段的一个特点是电子计算机技术的迅速发展,这样,使得运筹学中的一些方法(如单纯形法、动态规划方法等)得以用来解决实际管理系统中的一些优化问题,促进了运筹学的推广和应用。最初几年,工业运筹学发展较为谨慎,绝大多数队伍规模尚未壮大起来。50年代末,在美国大约有半数的大型公司在自己的经营管理中应用运筹学。
二、运筹学在中国的产生于发展
中国的第一个运筹学研究小组是在钱学森、许国志先生的推动下于1956年在中国科学院力学研究所成立的[8](P162-63)。其“应用是在1957年始于建筑业和纺织业,从1958年开始在交通运输、工业、农业、水利建设、邮电等方面皆有使用。尤其是在运输方面,从物资调运、装卸到调度等。”[9](P140-42)。1958年,建立了专门的运筹学研究室,但由于在应用单纯形法解决粮食合理运输问题时遇到了困难,我国运筹学工作者于是创立了运输问题的“图上作业法”;而管梅谷教授则提出了“中国邮路问题”模型的解法。可想而知,运筹学从一开始就被理解为与工程有着密切联系的学科。1959年,第二个运筹学部门在中国科学院数学研究所成立,这是大跃进中数学家们投身于国家建设的一个产物。力学所小组与数学所小组于1960年合并成为数学研究所的一个研究室,当时,其主要研究方向为:排队论、非线形规划和图论,还有人专门研究运输理论、动态规划和经济分析。50年代后期,运筹学在中国的应用主要是集中在运输问题上,一个典型的例子是“打麦场的选址问题”,在使用运筹学的基础上,其结果大大节省了人力资源[8](P162-63)。自60年代以来,被认为是运筹学迅速发展和开始普及的时期。此阶段的特点是运筹学进一步细分为各个分支,专业学术团体的迅速增多,更多期刊的创办,运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中。第三代电子数字计算机的出现,促使运筹学得以用来研究一些大型复杂系统,如城市交通、环境污染、国民经济计划等。运筹学被广泛应用于政府机构、国有部门、企业界。“至1963年,应用运筹学的行业已有飞机和导弹制造、玻璃、金属、矿业、包装、造纸、炼油、照相器材、印刷和出版、造鞋、纺织、烟草业、运输、木材加工、餐饮业和民意调查等。很多大型企业都设有自己的专业运筹队伍和小组,例如ICI、NCB、UnitedStell、EnglishElectric、BISRA、Unilever等。至1970年,运筹学几乎已经渗透到所有的政府部门和机构。”1976年后,我国国防科学技术大学为湖南常德地区研制了社会经济10年规划,所用的主要工具就是运筹学。中国运筹学学会还负责组织及管理亚太地区运筹学研究中心的日常学术活动,已组织过四次国际学术会议并出版了四本论文集,受到了国内外学术界的青睐。近年来,中国运筹学工作者继续坚持把运筹学研究与经济建设等重大问题紧密结合起来。例如,山东省与大连市经济发展计划的制定,兰州铁路局铁路运输的优化安排,中外合资经营项目经济评价,若干国家重大工程中的综合风险分析等方面,我国运筹学者都发挥了极大的作用。
21世纪已经到来,这是一个伟大的时代,机遇与挑战并存,中国运筹学会将在中国科协的指导下,团结广大运筹学工作者,继续创造宽松、和谐和团结的学术气氛,群策群力,为我国社会经济的发展做出应有的贡献。
三、排队论的发展和应用
排队论又叫随机服务系统理论。最初是在二十世纪初由丹麦工程师艾尔郎关于电话交换机的效率研究开始的，在第二次世界大战中为了对飞机场跑道的容纳量进行估算，它得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展起来。因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外，还有微分和微分方程。排队论把它所要研究的对象形象的描述为顾客来到服务台前要求接待。如果服务台以被其它顾客占用，那么就要排队。另一方面，服务台也时而空闲、时而忙碌。就需要通过数学方法求得顾客的等待时间、排队长度等的概率分布。排队论在日常生活中的应用是相当广泛的，比如水库水量的调节、生产流水线的安排，铁路分成场的调度、电网的设计等等。
1.排队论的基本特征
实际的排队系统各有不同，但是都由3个基本部分组成：输入过程、排队及排队规则和服务机制。 2.排队系统常用的几个理论分布 A．负指数分布
T0=0, Tn表示第n个顾客到达的时刻，则有
T0≤T1≤„≤Tn≤„，记Xn＝Tn- Tn-1，则Xn是第n个顾客与第n-1个顾客到达的时间间隔。一般假定{Xn}独立同分布，并记其分布函数为A(t)。定长分布(D)：顾客相继到达时间间隔为确定常数。
B．泊松分布
C.Poion流（Poion过程）
1、平稳性：在时间区间[t, t+t)内有一个顾客到达的概率为t+o(t）。
2、独立性(无后效性)：不相交的时间区间内到达的顾客数互相独立。
3、普通性：设在[t,t+t）内到达多于一个顾客的概率为q(t），则 q(t)=o(t)
实际中更容易得到和进行分析的往往是顾客相继到达的系统的时刻，或相继到达的时间间隔。设N(t)为时间[0,t]内到达系统的顾客数，则{N(t)，t≥0)}为参数为的Poion过程的充要条件是——相继到达时间间隔服从相互独立的参数为的负指数分布。
3.排队论的运用
A．排队论在收费站设计与管理中的应用
在高速公路上，车辆在收费站前等待服务的排队现象可以有三种形式：
图一为单队单服务台系统，排队等待服务的通道只有一条．图二为多队多服务台系统，有m个通道，每个通道各排一个队，且每个通道只为自己通道上的车辆服务，车辆不能任意插队．图三为单队多服务台系统，即车辆排成一个队，队列中第一辆车视哪个通道有空就去哪一个通道排队接服务．其中图一是图
二、图三的一种特殊情况．
为建立模型，首先给出如下假设：
(1)车辆到达整个收费站按泊松到达，到达每一个收费窗口也是泊松到达，在
图二中收费站的总到达率为nA，到达每一个收费窗口的车辆平均到达率为A，在图
三中整个收费站的车辆平均到达率为A；
(2)把整个收费站当作服务台，服务方式是先到先服务； (3)对每辆车的服务是独立的，服务时间服从相同的负指数分布，设平均服务率为p；从而图
一、图
二、图三就分别表示M／M／1系统，m个并联的M／M／1系统，及M／M／m系统．
我们选取M／M／1／oo模型．当服务通道不止一个时，应选取M／M／m／oo服务系统．在这个系统
中，主要涉及的参数有三个： A，肛，m．参数A是车辆的到达率，这是收费站工作人员所无法控制的，工作人员能控制的只有参数p和1\"n．工作人员可以通过对通道的开放个数m的控制来调节服务水平，也可以通过控制每个通道的服务率p来调节服务水平，使排队等待通过的车辆数量在合理的范围内． B．基于排队理论的汽车租赁运营策略
将汽车租赁问题转化为即时排队系统M／M／n／n／模型。解决了在租赁模型中顾客需求与租期都是随机参数的难题。在租赁商独立经营的情况下，以利润最大化为目标建立模型，得到租赁商的最优车辆购置数；比较两家租赁商合作经营与独立经营情况下的利润，得出合作经营后总利润增加值与两租赁商均可以接受的转租价格，为租赁商选择有利的运营策略提供了理论依据。若是建立DVD租赁供应链独立决策、一体化决策和收益共享的3种决策模型，其结果表明收益共享对双方都有利，可以实现供应链完美协调。 C．基于排队论的生产物流系统的仿真优化
为研究生产过程中物流运输资源配置的问题，为了有效提高企业生产过程中物流效率并控制投资，依据排队理论，建立等待费用和配置资源费用的综合比较模型，从而选择最佳资源配置方案。通过对仓储物流系统的详细调研和数据采集，建立生产系统物流模型，从而选择一个较好的策略。随着计算机模拟技术的快速发展，通过仿真较为方便地表达现实问题的物理性、逻辑性、静态特征、动态特征，能够全面地描述问题的各种关联因素，因而成为解决此
类多因素复杂问题的首选方法H，。通过计算机仿真来模拟顾客的来到、排队、服务及离开，统计得到整个系统的运行参数，从而分析排队系统的性能，根据可接受的等待时间和服务台效率求解最佳服务台开启数，一艘隋况下，不考虑投资成本的问题，不进行等待成本和投资成本综合比较。
D．基于排队论的电动汽车电池回收建模与仿真研究
从仿真的角度,对电池回收系统中的主要对象电动汽车、电池以及电动汽车和电池匹配进行模拟,应用Anylogic仿真平台,搭建电动汽车电池回收的排队论模型,进而分析电动汽车和电池生产速率、电动汽车和电池寿命、电池更新次数以及电池翻新率等因素对报废车比例、报废电池比例以及汽车重复使用电池比例的影响程度.研究获得以下主要结论:电池生产速率在区间[1,2]变化对结果影响最大,报废车比例迅速下降约10％,其它指标则平均增加5％；电动汽车和电池按照1∶4的比例进行生产,系统处于最优状态；电池寿命在区间[12,24]之间变化对结果影响最明显,报废电池比例降12％左右,其它指标则平均增加4％左右；电池更新次数在区间[1,2]变化,报废电池比例会迅速下降15％,随着电池更新次数的继续增加,报废电池比例会缓慢下降,直到更新次数为4的时候,系统处于最优；当翻新率从0.5增加到0.9时候,报废电池比例会从70％迅速下降到16％左右,二/三/四手电池使用比例,则从43％、17％、6％分别提高到78％、31％、11％左右,几乎都是提高了一倍.因素对对仿真结果的影响程度,会受到电池和汽车的相对寿命RL的约束.最后文章提出,根据RL合理安排电动汽车和电池的生产速率以及科学计算电池翻新次数,重视技术的投入产出分析和提高电池翻新率等政策建议.，运用工业工程的有关理论和方法解决物流运输资源配置的问题。
在排队理论的基础上，建立等待费用和配置资源费用的比较模型，选择最佳资源配置方案，用Arena 7．0仿真软件模拟物流过程和运输工具的配置过程。该方法与传统仿真方法相比，有效地快速求解排队系统中费用最小的最佳资源配置方案。
四、总结 排队论在运筹学中应用十分广泛，凡是人类活动中, 存在大量服务的过程, 均可应用排队论。在工业生产上, 原材料供应, 产品销售属于大量服务性质。在生产过程中, 多机床看管问题, 流水线各道工序的在制品的储备量的选择, 产保, 检验问题,成品, 包装问题, 工具收发保管, 以及仓库管理问题都可应用排队论。池伙的电力用户供电; 需建查多大容量的发电厂; 保证用户通话需要敷设多少条线路; 复杂自动控制系统的元件参数选择和可靠性估计量。应用排队论可以从许多可行方案中选出技术上先进, 经济上合算的最优方案。在城市服务性行业中, 亦可应用排队论确定食堂、理发店、商场、剧院的设置方案;确定各类公用事业( 市内交通, 煤气、自来水等) 的规模。这对于有计划发展的新城市尤其重要。在军事上应用排队论是一个重点, 它可用来正确组织武器系统和修理基地, 确保军事系统的作战能力。在新武器的研制过程中, 存在大量排队论问题。每类武器的目的是配合总的作战力量最有效地消灭敌人。可以在研制阶段就查明这些武器的使用效果, 选择效果最优的作为发展方向。由此可见, 排队论的应用范围十分广泛, 几乎遍及人类活动的各个领域,在许多尖端科学技术部门, 例如自动控制系统的可靠性问题, 核子物理学等应用排队论亦有广阔的前景。
参考文献：1.基于排队理论的汽车租赁运营策略（王娟，杨爱峰）
2.基于排队论的生产物流系统的仿真优化（马旭耀） 3.基于排队论的电动汽车电池回收建模与仿真研究 （宫大庆 刘世峰 ） 4.排队论及其应用（严智渊） 5.运筹学的历史与现状 （ 雷晓军）
6.基于物流运筹学的运输优化决策问题解决方案 （唐永洪）
7.排队论在收费站设计与管理中的应用木（潘全如） 8.运筹学在食品生产优化中的应用（叶保平） 9.游戏教学法在“运筹学\"课程实验教学中的应用 （覃频频， 钱峙元， 黄大明）
