第一节 运筹学概述
一、运筹学的形成及发展
纵观运筹学的发展史可以看到，朴素的运筹学思想自古有之：敌我双方交战，要克敌制胜就要在了解双方情况的基础上，找到对付敌人的最优方法。从阿基米德为战胜迦太基人设计的用于粉碎罗马海军攻占西那库斯城的设防方案，到《梦溪笔谈》所记录的军粮供应与用兵进退的关系等事例无不闪耀着运筹帷幄、整体优化的朴素思想。此外，在人类征服自然、改造自然的过程中，也大量运用了运筹的思想和方法。我国古代李冰父子主持修建的，由“鱼嘴”岷江分洪工程、“飞沙堰”分洪排沙工程和“宝瓶口”引水工程巧妙结合而成的都江堰水利工程；宋真宗皇宫失火，大臣丁渭提出的一举三得重建皇宫的方案都是很好的例子。
作为一门学科，运筹学直到20世纪才出现。第一次世界大战期间，以希尔为首的英国国防部防空试验小组，进行了高射炮系统利用研究，同时英国人莫尔斯利用数学模型，对美国海军横跨大西洋护航队损失情况进行了分析，这是最早关于运筹学的研究，其中包括著名的1914年提出的兰彻斯特战斗方程。1938年7月，英国波德塞雷达站的负责人罗伊提出立即进行整个防空作战系统运行的研究，并用“Operational Research”一词作为对这方面研究的描述，这就是O.R．这个名词的起源。对探测、信息传递、作战指挥、战斗机与防空火力协调等的研究获得的成功，大大提高了英国本土的防空能力，不久以后在对抗德国对英伦三岛的狂轰滥炸中，该研究发挥了极大的作用。1939至1940年，该项研究扩大到海军和陆军的作战中，并对未来的战斗进行预测，以供决策之用。鉴于其在战争中发挥的重要作用，1940年英国成立了由物理学家布莱克特领导的第一个运筹学小组，后来发展到每一个英军指挥部都成立运筹学小组。1942年美国和加拿大也相继成立了运筹学小组，研究并解决战争提出的运筹学课题。这些小组在确定扩大舰队规模、开展反潜艇战的侦察和组织有效的对敌轰炸等方面，作了大量研究，为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。其中最出色的工作之一是美国协助英国打破了德国对英吉利海峡的海上封锁。研究所提出的两条重要建议是：将反潜攻击由反潜艇投掷水雷改为飞机投掷深水炸弹，起爆深度由100米改为25米左右，即当德方潜艇刚下潜时进行攻击；运送物资的船队及护航舰艇的编队由小规模、多批次改为大规模、少批次，且在受敌机攻击时，采取大船急转向和小船慢转向的逃避方法。结果，德国潜艇被摧毁的数量增加到原来的400%，运输船只中弹的数量由47%下降到29%。从而打破了德国的封锁，并且重创了德国潜艇部队。第二次世界大战结束时，在英美及加拿大军队中工作的运筹学工作者已超过700人。
除上述军事领域的研究外，古典管理学派、经济学派特别是数理经济学派对运筹学的产生、发展也产生过巨大影响。古典管理学的主要思想是寻求一些方法，使人们自愿地联合与协作，保持个人的首创精神和创造能力，达到提高效率的目的。比如，动作研究与泰勒工作制；切削效率与车速、进刀量等因素的数学关系；管理的基本原则、机构设置、权限、工厂布局、计划等问题；举世闻名的刺激性工资制；用于生产活动分析和计划安排的甘特图（其进一步发展为统筹方法）等。
值得一提的是前苏联学者康托洛维奇的工作。1939年，康托洛维奇对生产中提出的大量组织与计划问题进行了研究，出版了著名的《生产组织与计划中的数学方法》一书，这是运筹学最早的在理论、方法上较为完整的著作。其研究的具体问题包括：生产配置问题，原材料的合理利用问题，运输计划，播种面积的分配等。其研究结果不仅给出了数学模型，而且可以确定最优方案。此贡献在于使运筹学的理论方法形成体系，其确定极值的方法超出了经典数学分析方法的范畴，遗憾的是这一研究成果直到第二次世界大战以后才受到重视。
数理经济学对运筹学产生与发展的影响主要表现为经济数学与运筹学互相影响、相互促进、共同发展的历程。1758年，魁奈在凡尔赛出版的《经济表》，对经济中各部门的平衡关系作了最早的研究；后来法国经济学家瓦尔拉对经济平衡问题的研究是对数理经济学的重大贡献，其数学形式在奥地利、德国被持续深入研究、发展和推广。特别要提到的是冯·诺依曼所做的开创性工作：1932年，冯·诺依曼提出第一个广义经济平衡模型；1939年他提出宏观经济优化的控制论模型，该模型成为数量经济学的一个典型模型；1944年他与摩根斯坦合作出版《对策论与经济行为》一书，将经济活动中的冲突、协调和平衡分析问题量化处理，解决了一些基本对策问题，理所当然成为近代对策论创始人之一。此外，他领导研究的电子计算机成为运筹学的技术实现支柱之一。尤为世人所称道的是，他最早肯定并扶持当时未满30岁的丹捷格从事以单纯形法为核心的线性规划研究。
二、运筹学的发展阶段
第二次世界大战以后，运筹学的应用由军事扩展到了工业、政府等部门，在理论上也逐步完善了其科学体系。具体地讲，它的发展大致可分为三个阶段。
1．20世纪40—50年代是运筹学的创建时期
英国一些战时从事运筹学研究的工作者积极探讨如何将运筹学方法应用于民用部门，于1948年成立了“运筹学俱乐部”，在煤炭、电力等部门推广应用运筹学方法并取得了一定进展。同年，美国麻省理工学院率先开设了运筹学课程，1950年，英国伯明翰大学正式开设运筹学课程，1952年，美国喀斯工业大学设立了运筹学的硕士和博士学位。1950年，第一本运筹学杂志《运筹学季刊》在英国创刊。1952年，第一个运筹学会——美国运筹学会成立，并于同年出版了《运筹学学报》。1951年，莫尔斯和金博尔合著的《运筹学方法》一书正式出版，这是第一本以运筹学为名的专著，书中总结了第二次世界大战中运筹学的军事应用，并且给出了运筹学一个著名的定义：运筹学是为执行部门对它们控制下的“业务”活动采取决策提供定量依据的科学方法。
2．20世纪50年代初期到50年代末期是运筹学的发展阶段
该阶段的突出特点是计算机技术的迅速发展使得运筹学中一些方法如单纯形法、动态规划方法等，得以用来解决实际管理系统中的优化问题，促进了运筹学的推广应用。20世纪50年代末，美国大约有半数的大公司在自己的经营管理中应用运筹学，如将运筹学应用于制订生产计划、物资储备、资源分配、设备更新等方面的决策。此外，在该阶段出现了更多的刊物和学会。1956年到1959年间就有法国、印度、日本、荷兰、比利时等10个国家成立运筹学会，又有6种运筹学刊物问世。1957年，在英国牛津大学召开了第一次国际运筹学会议，以后每三年举行一次。1959年，国际运筹学联合会（International Federation of Operations Research Societies，简称IFORS）成立。
3．20世纪60年代以来是运筹学迅速发展和开始普及的阶段
此阶段运筹学进一步细分为各个分支，专业学术团体迅速增多，运筹学方面的期刊和书籍大量出版，更多学校将运筹学课程纳入教学计划之中。计算机技术的迅速发展，促使运筹学得以用来研究一些大的复杂系统，如城市交通、环境污染、国民经济计划等。如今，运筹学已广泛应用于人类社会生活的各个方面，诸如军事问题、教育问题、污染问题、交通运输问题、人力资源管理问题等，还广泛应用于这样一些部门：能源、预测、会计金融、销售、存储、计算机与信息系统、设计、城市服务系统、保健与医疗、电气、加工工业、第三产业等。
在我国，运筹学的研究与应用起步较晚，20世纪50年代中期才由钱学森和许国志等科学家由西方引入。一开始将其直译为“运用研究”或“作业研究”。1957年，学者们从《史记·高祖本纪》中“运筹帷幄之中，决胜千里之外”这句古语中摘取“运筹”二字，将“O.R.”正式译作“运筹学”，包含运用筹划，以策略取胜等意义，比较恰当地反映了这门学科的性质和内涵。
50多年来，运筹学理论研究和应用在我国取得了较大的发展。1956年，我国第一个运筹学小组在中国科学院力学研究所成立。1958年建立了运筹学研究室。学者们结合我国的具体情况进行了运筹学的推广和应用，特别是投入产出表的研究和应用开展较早，质量控制的应用也很有特色，产生了具有独特风格的“图上作业法”。1958年，在纺织业中用排队论解决了细纱车间的劳动组织和最优折布长度等问题；1962年，管梅谷解决了中国邮路问题。在此期间，以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍中，在全国推广统筹法和优选法，并取得卓著成效，使运筹学的许多分支的研究及应用很快跟上了当时的国际步伐。
1960年，全国的运筹学研究者在山东济南召开了应用运筹学的经验交流和推广会议，1962年和1978年先后在北京和成都召开了全国运筹学专业学术会议，1980年4月，中国运筹学会正式成立，并于1982年加入了国际运筹联合会。运筹学的方法在农林、交通运输、建筑、机械、冶金、石油化工、水利、邮电、纺织等部门已开始得到广泛的应用和推广。除中国运筹学会外，中国系统工程学会以及与国民经济各部门有关的专业学会，也都把运筹学的应用作为重要的研究领域。我国各高等院校也已普遍把运筹学列入各专业的教学计划中。目前，国内运筹学的专门刊物或较多刊登运筹学理论和应用的刊物主要有：《运筹学学报》、《运筹与管理》、《系统工程学报》、《系统工程理论与实践》、《系统工程理论方法应用》、《数量经济》、《技术经济研究》、《预测》、《系统工程》和《系统科学与数学》等。
三、运筹学的特点及分析步骤
（一）运筹学的概念和特点
1．运筹学的概念
运筹学（Operations Research）是一门新兴的应用学科。由于它所研究的对象极其广泛，所以有着许多不同的定义。
英国《运筹学》杂志认为：“运筹学是运用科学方法（特别是数学方法）来解决那些在工业、商业、政府和国防部门中，有关人力、机器、物质、金钱等大型系统的指挥和管理方面出现的问题的科学，目的是帮助管理者科学地决定其策略和行动。”
美国运筹学会（1976年）的定义是：“运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人机系统，并使之最好地运行的一门学科。”这从侧面描写了运筹学的特点。
《联邦德国科学辞典》（1978年）上的定义是：“运筹学是从事决策模型的数学解法的一门科学。”
《辞海》（1979年）中有关运筹学条目的释义为：“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的取舍安排，以达到较经济、较有效地使用人力、物力。”
《中国大百科全书》（自动控制与系统工程卷，1991年）的释义为：“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下，合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制订行动规划或优选可行方案。”故有人将运筹学称作“管理数学”。
从这些定义中我们可以看出，虽然说法不一，但其基本含义大致相同，都包含了以下三方面的内容：
（1）既定的目标和条件；
（2）科学的方法和技术；
（3）最优的决策方案。
2．运筹学的特点
运筹学属于应用数学范畴，具体地说，它是一门管理数学，是一种通过对系统进行科学的定量分析，从而发现问题、解决问题的系统方法论。与其他的自然科学不同，运筹学研究的对象是“事”，而不是“物”，它揭示的是“事”的内在规律性，研究的是如何把“事”办得更好的方式方法。由此，我们可以看出运筹学主要有以下三个特点：
（1）系统的整体优化
所谓系统可以理解为是由相互关联、相互制约、相互作用的部分组成的具有某种特定功能的有机整体。例如物流系统由很多子系统组成，包括采购、运输、仓储、配送、流通加工、信息处理等，各子系统工作的好坏直接影响企业经营管理的好坏。但各子系统的目标往往不一致，生产部门为提高劳动生产效率希望尽可能增大批量；销售部门为满足更多用户的需要，要求增加花色品种；财务部门希望减少积压，加速流动资金周转，降低成本。
运筹学不是对每一个决策行为孤立地进行评价，而是把系统内所有子系统的相互作用综合起来作出评价，把相互影响的各方面作为一个统一体，从总体利益的观点出发，寻找出一个优化协调的方案。
（2）多学科的配合
一个企业的有效管理涉及很多方面，运筹学研究中吸收了来自不同领域、具有不同经验和技能的专家。由于专家们来自不同的学科领域，具有不同的经历经验，因此增强了集体提出问题和解决问题的能力。这种多学科的协调配合在研究的初期、在分析和确定问题的主要方面、在选定和探索解决问题的途径时，显得尤其重要。
（3）模型方法的应用
运筹学的研究不同于其他学科的实验室方法，其研究往往不能搬到实验室，而是建立这个问题的数学模型和模拟模型。如果说辅助决策是运筹学应用的核心，那么建立模型就是运筹学方法的精髓。
3．运筹学的工作步骤
经过长期的实践，运筹学已形成自己特有的方法论，具体工作步骤如下：
（1）系统分析和问题描述
应用运筹学的目的是要解决问题，解决问题首先必须提出问题和分析问题。因此要对研究的问题和系统进行观察分析，归纳出决策的目标及制定决策时在行动和时间等方面的限制条件。一旦明确地提出了需要解决的问题，就必须从以下三方面对问题进行分析，即技术可行性、经济可行性和操作可行性。
①技术可行性是指在既有的条件下有没有方法用于解决所提出的问题，如果不具备技术可行性，提出的问题就无法解决。
②经济可行性是指解决问题时需要投入多少，会不会受资金限制。进一步地，还需要分析解决问题之后的投入产出情况，要力争少投入、多产出。
③操作可行性是指解决问题时有没有合适的人员来操作，没有合适的人员从事具体工作，一切工作都将没有意义。
（2）模型的建立和修改
建立模型是运筹学分析的关键步骤。模型是对现实世界的抽象和简化，是用文字、图表、符号、关系式及实体模样描述所认识的客观对象。模型表达了问题中可控决策变量、不可控变量、各种条件及目标有效度量之间的相互关系。一个典型的运筹学模型应包括以下部分：
①一组需要通过求解模型确定的决策变量；
②一个反映决策目标的目标函数；
③一组反映系统复杂逻辑和约束关系的约束方程；
④模型要使用的各种参数。
模型的构造是一门基于经验的艺术，既要有坚实的理论做指导，又要靠不断的实践来积累经验。具体地讲，有以下几种方法：
①直接分析法，即按研究者对问题内在机理的认识直接构造出模型；
②类比法，即不同问题在构造模型时，如结构性质是类似的，就可以互相类比；
③数据分析法，即当对有些问题的机理尚未了解清楚时，若能搜集到与此问题密切相关的大量数据，或通过某些试验获得大量数据，就可采用统计分析的方法建模；
④试验分析法，即当有些问题的机理不清，又不能做大量的试验来获得数据时，只能通过做局部试验的数据加上分析来构造模型；
⑤构想法，即当有些问题的机理不清，又缺少数据，又不能做试验来获得数据时，只能在已有的知识、经验和某些研究的基础上，对将来可能发生的情况给出逻辑上合理的设想和描述。
（3）模型的求解和检验
对问题求解即用数学方法或其他工具对模型进行求解。根据问题的要求，可分别求出最优解、次优解或满意解；依据对解的精度的要求及算法上实现的可能性，又可区分为精确解和近似解等。模型和实际之间总是存在一定的差异，因此模型的最优解并不一定就是实际问题的最优解。所以，模型建成以后，它所依赖的理论和假设条件是否合理，模型结构是否正确，必须通过试验和求解进行检验。通过检验，可以发现模型的结构错误和逻辑错误，并了解模型求解结果与实际问题的差距。只有当模型在一定程度上能比较准确地反映实际问题时，运筹学分析才算达到了比较理想的效果。
（4）结果分析与实施
运筹学研究的最终目的是要提高被研究系统的效率，通过解的分析，控制解的变化来达到理想的结果。同时通过解的实施，才能最终实现。因此，实施是最重要的一步。这一步要求明确：方案由谁去实施，什么时间去实施，如何实施，要求估计实施过程可能遇到的阻力，并为此制订相应的克服困难的措施。此外，在实施过程中，最重要的是使管理人员与运筹学分析人员取得共识，并使管理人员了解分析的全过程，掌握分析的基本方法和理论，且能独立地完成日常分析工作。只有这样，才能确保研究和分析成果的真正实施。