第1章
优化算法概述
1.1优化算法简介
优化算法，即优计算方法，也是运筹学，主要介绍优化问题的算法及其应用，在第二次世界大战及战后经济恢复期间，一些由多学科专家组成的运筹组织在军事决策、资源合理利用和提高生产效率等领域做出了很大贡献，他们的工作促使运筹学逐步形成一门新兴的学科，并迅速得到普及和发展。
优化同运筹学一样，是利用现代数学、系统科学、计算机科学及其他学科的新成果，来研究人类从事的各种活动中处理事务的数量化规律，使有限的人、物、财、时空、信息等资源得到充分和合理的利用，以期获得尽可能满意的经济和社会效果。
优化算法早研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着客观实际的发展，它在生产生活中也得到了广泛的应用，经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。优化算法本身也在不断发展，涵盖线性规划、非线性规划、整数规划、组合规划、图论、网络流、决策分析、排队论、可靠性数学理论、仓储库存论、物流论、博弈论、搜索论和模拟等分支。
当前优化算法的应用领域如下。
（1）市场销售：多应用在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的编制等方面。如美国杜邦公司在20世纪50年代起就非常重视对广告、产品定价和新产品引入的算法研究。
（2）生产计划：从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划，主要采用线性规划和仿真方法等。此外，还可用于日程表的编排，以及合理下料、配料、物料管理等方面。
（3）库存管理：存货模型将库存理论与物料管理信息系统相结合，主要应用于多种物料库存量的管理，确定某些设备的能力或容量，如工厂库存量、仓库容量、新增发电装机容量、计算机的主存储器容量、合理的水库容量等。
（4）运输问题：涉及空运、水运、陆路运输，以及铁路运输、管道运输和厂内运输等，包括班次调度计划及人员服务时间安排等问题。
（5）财政和会计：涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等，采用的方法包括统计分析、数学规划、决策分析，以及盈亏点分析和价值分析等。
（6）人事管理：主要涉及以下6个方面。
①人员的获得和需求估计。
②人才的开发，即进行教育和培训。
③人员的分配，主要是各种指派问题。
④各类人员的合理利用问题。
⑤人才的评价，主要是测定一个人对组织及社会的贡献。
⑥人员的薪资和津贴的确定。
（7）设备维修、更新、可靠度及项目选择和评价：如电力系统的可靠度分析、核能电厂的可靠度及风险评估等。
（8）工程的佳化设计：在土木、水利、信息、电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。
（9）计算机信息系统：可将作业研究的优化算法应用于计算机的主存储器配置，如等候理论在不同排队规则下对磁盘、磁鼓和光盘工作性能的影响。利用整数规划寻找满足一组需求档案的寻找次序，并通过图论、数学规划等方法研究计算机信息系统的自动设计。
（10）城市管理：包括各种紧急服务救难系统的设计和运用，如消防车、救护车、警车等分布点的设立。美国采用等候理论方法来确定纽约市紧急电话站的值班人数，加拿大采用该方法研究城市警车的配置和负责范围，以及事故发生后警车应走的路线等。此外，还涉及城市垃圾的清扫、搬运和处理，以及城市供水和污水处理系统的规划等相关问题。
1.2优化算法的内容
优化算法的内容包括：规划论（线性规划、非线性规划、整数规划和动态规划）、库存论、图论、排队论、可靠性理论、对策论、决策论、搜索论等，下面将具体介绍这些内容。
1.2.1 规划论
规划论（数学规划）是运筹学的一个重要分支，早在1939年苏联的康托罗维奇（Leonid V.Kantorovich）和美国的希奇柯克（F.L.Hitchcock）等人就在生产组织管理和编制交通运输方案时研究和应用了线性规划方法。
1947年美国的旦茨格（G.B. Dantzig）等人提出了求解线性规划问题的单纯形法，为线性规划的理论与计算奠定了基础，特别是计算机的出现和日益完善，更使规划论得到迅速的发展，它采用计算机处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的优化，到工业、农业、商业、交通运输业和决策分析部门都可以发挥作用。
从应用范围来看，小到一个班组的计划安排，大至整个部门乃至国民经济计划的优化方案分析都有用武之地，因此，它具有适应性强、应用面广、计算技术比较简便的特点。非线性规划的基础性工作是在1951年由库恩（H.W.Kuhn）和塔克（A.W.Tucker）等人完成的，到了20世纪70年代，数学规划无论是在理论和方法上，还是在应用的深度和广度上都得到了进一步的发展。
数学规划的研究对象是计划管理工作中有关安排和估值的问题，即在给定条件下，按某个衡量指标来寻找安排的优方案。它可以表示为求函数在满足约束条件下的极大值或极小值问题。
现代的数学规划和古典的求极值的问题有本质的不同。古典的求极值方法只能处理具有简单表达式和简单约束条件的情况，而现代的数学规划中的问题目标函数和约束条件都很复杂，而且要求给出某种度的数字解答，因此算法的研究受到了特别的重视。
数学规划中简单的一类问题就是线性规划。如果约束条件和目标函数都属于线性关系就叫线性规划。要解决线性规划问题，从理论上讲要解线性方程组，因此解线性方程组的方法，以及关于行列式、矩阵的知识，在线性规划中非常重要。
线性规划及其解法（单纯形法）的出现，对优化算法的发展起了很大的推动作用。许多实际问题都可以转化成线性规划来解决，而单纯形法又是一个行之有效的算法，加上计算机的出现，能够使一些大型复杂的实际问题得以解决。
非线性规划是线性规划的进一步发展和延伸。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本的理论问题，使数学中的如凸分析、数值分析等也得到了发展。还有一种规划问题和时间有关，即“动态规划”，它已经成为在工程控制、技术物理和通信中佳控制问题的重要工具。
1.2.2 库存论
库存论（存贮论）是运筹学中发展较早的分支。早在1915年，哈里斯（F.Harris）就针对银行货币的储备问题进行了详细的研究，建立了一个确定性的存贮费用模型，并求得了佳批量公式。1934年威尔逊（R.H.Wilson）重新得出经济订购批量公式（EOQ公式）。
库存论真正作为一门理论发展起来是在20世纪50年代。1958年威汀（T.M.Whitin）发表了《存贮管理的理论》，随后阿罗（K.J.Arrow）等发表了《存贮和生产的数学理论研究》，莫兰（P.A.Moran）在1959年编写了《存贮理论》。此后，库存论成了运筹学中的一个独立的分支，有关学者相继对随机或非平稳需求的存贮模型进行了广泛深入的研究。
现代化的生产和经营活动都离不开存贮，为了使生产和经营活动能有条不紊地进行，工商企业都需要进行一定数量的物资贮备。例如，工厂为了进行连续生产，就需要贮备一定数量的原材料或半成品；商店为了满足顾客的需求，就必须有足够的商品库存；农业部门为了确保正常生产，就需要贮备一定数量的种子、化肥、农药；军事部门为了战备的需要，就要存贮各种武器弹药等军用物品；银行为了进行正常的业务，就需要有一定的资金贮备；在如今的信息社会，人们又建立了各种数据库和信息库，用以存贮大量的信息。
因此，存贮问题是人类社会活动，特别是生产活动中一个普遍存在的问题。物资的存贮，除了用来支持日常生产经营活动，库存调节还可以满足高于平均水平的需求，同时也可以防止低于平均水平的供给。此外，大批量物资的订货或利用物资季节性价格的波动，也可以得到价格上的优惠。
但是，存贮物资需要占用大量的资金、人力和物力，有时甚至造成资源的严重浪费。大量的库存物资所占用的资金，无论从相对数值还是数值上来看都是十分惊人的。此外，大量的库存物资还会引起货物的劣化变质而造成巨大损失，如药品、水果、蔬菜等，长期存放就会引起变质。特别是在市场经济条件下，过多地存贮物资还要承受市场价格波动的风险。
那么，一个企业究竟应存放多少物资为适宜呢？对于这个问题，很难笼统地给出准确回答，必须根据企业自身的实际情况和外部的经营环境来决定，若能通过科学的存贮管理，建立一套控制库存的有效方法，从而降低物资的库存水平，减少资金的占用量，提高资源的利用率，这对企业来讲，所带来的经济效益无疑是十分可观的。这正是现代存贮论所要研究的问题。
物资的存贮按其目的的不同可分为以下3种。
（1）生产存贮。它是企业为了维持正常生产而储备的原材料或半成品。
（2）产品存贮。它是企业为了满足其他部门的需要而存贮的半成品或成品。
（3）供销存贮。它是指存贮在供销部门的各种物资，可直接满足顾客的需要。
但不论哪种类型的存贮系统，一般都可以使用如图1.1所示的形式来表示。
图1.1 库存模型
库存论可以用“供、存、销”3个字来描述，即一个存贮系统，通过订货和进货后的存贮与销售来满足顾客的需求。或者说，由于生产或销售的需求，从存贮系统中取出一定数量的库存货物，这就是存贮系统的输出；存贮的货物由于不断地输出而减少，必须及时地补充，补充就是存贮系统的输入，补充可以通过外部订货、采购等活动来进行，也可以通过内部的生产活动来进行。在这个系统中，决策者可以通过控制订货时间的间隔和订货量的多少来调节系统的运行，使得在某种准则下系统运行能够达到优。
因此，库存论中研究的主要问题可以概括为何时订货（补充存贮）和每次订多少货（补充多少库存）这两个问题。
1.2.3 图论
自然界和人类社会中的很多事物，以及事物之间的联系，都可以用点和线联系起来的图形来描述，如用点表示城市，用点与点之间的连线表示城市之间的道路，这样就可以描述城市之间的交通。如果在连线旁标明城市间的距离（在网络图中称为权），则形成加权图，就可以进一步研究从一个城市到另一个城市的短路径；或者在连线旁边标上运输单价，就可以分析运费少的运输方案。用图来描述事物间的联系，不仅直观清晰，而且网络的画法简单，不必拘泥于比例与曲直。图论既是拓扑学的一个分支，也是运筹学的重要分支，它是建立和处理离散数学模型的有用工具。
早在1736年，瑞士数学家欧拉（E.Euler）在求解的哥尼斯堡七桥难题时，就使用了图来进行分析论证。19世纪以来，英国数学家哈密顿提出了哈密顿（William Rowan Hamilton）回路和旅行商问题；电路定律创始人德国物理学家基尔霍夫（Gustav Robert Kirchhoff）和英国数学家凯莱（Arthur Cayley）提出了树的概念，分别用于求解和研究电力线网与化学分析结构，进一步发展了图论。1736年欧拉发表了关于图论的篇论文《依据几何位置的解题方法》，同年匈牙利数学家柯尼格（D. Konig）出版了图论的本专著《有限图与无限图的理论》。
近年来，随着计算机科学技术和优化算法的发展，网络图论得到了更进一步的发展，其应用日益广泛。网络图论的分析方法被广泛应用于电力线网和煤气管道网的分析、印刷电路与集成电路的布线和测试、通信网络分析、交通运输网络的分析、经济和管理领域中流行的网络分析等。
1.2.4 排队论
排队论（随机服务系统理论）是在20世纪初由丹麦工程师爱尔朗（A. K. Erlang）对电话交换机的效率研究开始的，在第二次世界大战中为了对飞机场跑道的容纳量进行估算，该理论得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展了起来。
丹麦的电话工程师爱尔朗于1930年以后，开始了关于排队问题的研究，取得了一些重要成果。1949年前后，他开始了对机器管理、陆空交通等方面的研究，1951年以后，他的理论工作有了新的进展，逐渐奠定了现代随机服务系统的理论基础。排队论主要研究各种系统的排队长度、排队的等待时间及所提供的服务等各种参数，以便求得更好的服务，它是研究系统随机聚散现象的理论。
排队论的研究目的是要回答如何改进服务机构或组织所服务的对象，使某种指标达到优的问题。如一个港口应该有多少个码头、一个工厂应该有多少名维修人员等。
因为排队现象是一个随机现象，因此在研究排队现象时，主要采用将研究随机现象的概率论作为主要工具。此外，还涉及微分和微分方程的相关内容。排队论把它所要研究的对象形象地描述为顾客来到服务台前要求接待。如果服务台已被其他顾客占用，那么就要排队。或者服务台时而空闲、时而忙碌，那就需要通过数学方法求得顾客的等待时间、排队长度等的概率分布。
排队论在日常生活中的应用非常广泛，如水库水量的调节、生产流水线的安排、铁路运输的调度、电网的设计等。
