运筹学基础 课件 第1章

第1章运筹学概述1.1

运筹学的起源1.2运筹学的定义1.3运筹学的模型1.4运筹学的优化范式1.5运筹学应用的过程

1.1

运筹学的起源

运筹学起源于军事问题的研究。第二次世界大战初期,英国人为了将最新的雷达技术整合进英国空军战术,开始了相关研究,并称之为OperationalResearch。最初,OperationalResearch的主要工作就是收集经验数据并进行基础的统计分析,也有一些工作应用了较为复杂的数学方法,如搜索理论。

1941年,OperationalResearch这个词被泛指所有为了辅助

军官筹划作战策略和作战行动而进行的研究,目标是通过量化分析技术最有效地利用有限的军事资源。第二次世界大战之后,OperationalResearch变成一种专业,并且更加关注和聚焦于复杂的数学方法。

早在1936年,英国空军在东海岸(位于Felixstowe,Suffolk附近)建立了Bawdsey研究站,在这里对空军和陆军的雷达开展实验活动。

1937年,Bawdsey研究站的第一部实验雷达部署完毕。

1938年,Bawdsey研究站又增加部署了四部雷达,并进行了第二次实验。

1939年,Bawdsey研究站进行了第三次实验,有33000人、1300架飞机、110套高射机枪、700套探照灯和100个阻塞气球参与了实验过程。第三次实验的结果表明,作战应用研究团队的有效工作使防空预警和控制系统在作战效能方面有巨大提升。

1940年5月14日,德国军队在法国快速推进,法国此时的兵力消耗速度为每两天三个中队。法国请求英国再增加10个中队力量的支援(每个中队12架飞机,总共120架飞机),而英国首相很可能因为联盟关系而向法国增援。

1941年,OperationalResearchSection(ORS)在英国海岸司令部成立,并进行了许多著名的运筹学工作。当时海岸司令部的主要工作是利用飞机发现并攻击德国的U型潜艇(当时U型潜艇经常浮出水面,因为只有浮出水面才能给电池充电、排出潜艇上的烟、给气罐充气,并且在水面上U型潜艇航行得更快,也可以降低被声呐发现的概率)。

从1942年开始,Blackett带领的运筹学团队为海军海岸司令部作战研究处提供了许多有益的分析。在研究深水炸弹的触发深度问题时,Blackett团队的研究指出,如果将空投深水炸弹的触发深度从100英尺改为25英尺,那么杀伤率就会上升。

运筹学在它起源于英国的几年后就传到了美国。

第二次世界大战刚结束时,许多科学家认识到他们用于解决军事问题的原则同样适用于民用部门,于是运筹学在民用领域迅速发展起来,同时运筹学在军事领域的发展也在持

续。

直至今天,美国空军的军事运筹组织还存在并发挥作用。

1.2运筹学的定义

1951年,莫尔斯和金博尔出版的《运筹学方法》一书中将运筹学定义为:运筹学是在实行管理的领域,运用数学方法,对需要进行管理的问题统筹规划,做出决策的一门应用科学。美国运筹学会给出的定义为:运筹学关注的是,在需要考虑稀缺资源分配的条件下,研究最优设计的决策问题,研究人机系统的运用问题。

英国运筹学会给出的定义为:运筹学应用科学的方法解决工业、商业、政府和国防等领域大系统的指导与管理方面的问题,指导和管理的对象包括人员、机器、材料、资金等。

在顾基昌等人提出的物理事理人理方法论(简称WSR方法论)中,运筹学被归属为研究事理的科学。在WSR方法论中,“物理”指涉及物质运动的机理,既包括狭义的物理,也包括化学、生物、地理、天文等,通常要用自然科学知识回答“物”是什么。

“事理”指做事的道理,主要解决如何去安排所有的设备、材料、人员等,通常要回答“怎样去做”的问题,也就是需要决策。“人理”指做人的道理,通常要用人文和社会科学的知识回答“应当怎样做”的问题。人理的作用可以反映在世界观、文化、信仰、宗教和情感等方面,特别表现在人们处理一些“事”和“物”中的利益观和价值观上。

与军事相关的运筹学称作军事运筹学。张最良给出的军事运筹学的定义是:应用数学和计算机等科学技术方法研究各类军事活动,为决策优化提供理论和方法的一门军事学科。OODA环模型是描述军事活动的常用模型,它将交战双方的交战过程描述为由观察、判断、决策、行动四个基本活动构成的环,如图1-1所示。

图1-1-OODA环模型

维基百科上给出了运筹学最为简洁的定义:运筹学(OperationsResearch,OR)研究怎样使用高级的分析技术做更好的决策。所谓的“高级分析技术”是一个相对的概念,是相对问题本身来讲的,取决于是否更适合实际问题以及能否做出更好的决策,并不是复杂程度的代名词。因此,分析技术本身没有普适性,一切要视实际问题而定。

1.3运筹学的模型

1.3.1-线性规划模型数学规划模型包含决策变量、目标函数、约束条件等三类必要元素。决策变量是决策要素的变量化定义;利用决策变量表达问题目标的函数就是目标函数;利用决策变量表达问题约束的等式或者不等式就是约束条件。

1.3.2网络模型

网络模型包含点和边两类必要元素。点代表问题中的对象,边代表问题中对象之间的关系。以网络模型为基础,可以研究很多网路优化问题,如最小支撑树问题、最短路问题、最大流问题、最小费用流问题等。1956年福特和福克逊提出了网络最大流问题的标号法,建立了网络流理论。

1.3.3动态规划模型

动态规划是一种算法设计技术,也是一种解决优化问题的模型及算法构造方法。它以递归的方式将一个复杂的问题分解成一系列简单的子问题,并通过子问题序列化的求解得

到问题的最优方案。动态规划模型包含状态、状态转移等两类基本要素,可以看作是一种具有阶段性的特殊的网络模型。

1.3.4生灭过程模型

生灭过程模型的基本要素包括状态和状态转移,状态代表排队系统中的顾客的数量,状态转移代表排队系统中顾客数量的变化,也就是系统状态的变化。生灭过程模型以计算

系统处于各个状态的概率为中介,结合排队系统的Little公式,可以得到排队系统的平均队长、期望等待时间等各项参数,进而为排队系统的优化提供支持。

1.3.5神经网络模型

神经网络模型是一种基于网络模型的计算模型,计算的数据从输入层开始往后流动,主要通过模拟生物的神经网络进行模式识别,相当于OODA环中的“判断”。

。传统上,优化决策的步骤可分为问题定义、建立模型、设计算法、求解并检验验证等环节,人工参与是全程和深入的,对人的建模求解能力和技术要求高。基于人工智能的优化决策技术,让机器可以在有监督或者无监督的情况下学习,无须人类的参与,甚至无须人类经验的加入,就能做出优化的决策。

1.3.6启发式模型

启发式模型将问题的求解方案编码为生物基因、粒子、鸟类等对象,并模拟这些对象的进化优化过程进行进化。1975年,Holland教授借鉴生物界的进化规律提出了遗传算法,

从而开启了进化计算的时代。

1.3.7仿真模型

基于解析分析的方法和基于仿真的方法,是两种不同的研究客观世界的方法。基于解析分析的方法能够迅速抓住客观问题的主要矛盾和关键的变量关系,因此适合解决条件比较理想化、变量个数和关系不是太过复杂的问题。而运筹学要面对大量复杂的现实问题,借助基于仿真的方法,是必由之路。仿真本质上是计算,是对客观问题数量关系在时间轴上演进的模拟,它可以将不确定性、结构复杂、计算量巨大等困难交给计算机,使人员的精力集中到仿真模型的建立和仿真数据的分析上。

仿真模型非常强大,并且它有一个非常可取的特性:将其用于非常复杂的系统建模时,不需要做太多的简化假设,也不需要牺牲过多细节。然而,使用仿真模型时必须非常小心,避免误用仿真。首先,在使用模型之前,必须对其进行适当的验证。验证对于任何模型来说都是必要的,对于仿真尤为重要。其次,分析人员必须熟悉如何正确使用仿真模型,包括复制、运行时间等。再次,为了有意义地分析仿真输出,分析人员必须熟悉各种统计技术。最后,在计算机上构建复杂的仿真模型是一项具有挑战性和相对耗时的任务,分析人员必须具有耐心。这里强调这些问题的原因是,现代仿真模型种类繁多,其真正的价值在于它能够洞察非常复杂的问题。

值得指出的一点是,仿真只是利用计算机的仿真模型进行了大量时间轴上的计算,它不能提供最佳策略的指示。从某种意义上说,这是一个反复实验的过程,因为我们用各种似乎有意义的策略进行实验,并查看仿真模型提供的客观结果,以评估每种策略的优点。

1.4运筹学的优化范式

自运筹学诞生以来,运筹学所利用的模型和分析技术众多。在面对一个新问题或者尚未很好解决的问题时,需要选择相应的模型和分析技术。通过对运筹学解决问题方法的聚类分析,可以得到运筹学的五大优化范式,即朴素优化范式、机械优化范式、仿真优化范式、智能优化范式和数据驱动优化范式(见图1-2)。

图1-2运筹学的五大优化范式

1.4.1-朴素优化范式

朴素优化范式是源于智能体直觉本能的规则式优化范式,是出现较早的一种优化决策范式,目前,对许多问题仍然具有生命力,同时,也会作为其他优化决策范式的子算法或者启发思路。贪婪算法、穷举法、深度优先搜索、广度优先搜索、生成测试范例等都可划分到此类。这类方法不需要复杂的数学推导,基本是一种规则式的算法,可以单独使用,也可以作为一种规则融入其他更复杂的算法中去。这些朴素优化的思想,为运筹学的许多高级算法持续提供支撑。

1.4.2机械优化范式

机械优化范式是可以程序化和结果重现的一些算法,比朴素优化范式更加需要智慧和直觉之上的智能。例如,单纯形法、内点法、表上作业法、动态规划、匈牙利算法、标号法、层次分析法、非线性规划中的梯度法等均属于此类。

1.4.3仿真优化范式

仿真优化范式是基于计算机仿真技术和平台的优化方法,可充分利用仿真对复杂系统的强大描述和承载能力,为优化提供动态、复杂结构的数据输入能力,并能够对随机性提供天然支持。

1.4.4智能优化范式

智能优化范式通过智能算法借鉴了智能体的进化优化过程,比较容易理解,能够解决的问题也是广谱的,但是针对具体的问题需要更多的专业知识,才能对算法的编码、解的进化、参数的调整等技术细节进行良好的控制和优化。

1.4.5数据驱动优化范式

数据驱动优化范式是优化决策与大数据技术相结合的产物,它将数据作为驱动优化决策的直接动力,解决了传统优化决策领域理论和实践脱节的问题。传统的优化决策方法都

是先对真实系统进行选择性的抽象,建立实际上失真的模型,然后对模型进行优化,将对模型进行优化的结果作为对真实系统优化决策的替代物。然而数据驱动优化范式的模型本

身始终与真实系统保持联系,真实系统的数据源源不断地输入模型中,使模型的失真度达到最小,从而保证了优化决策的准确度。

1.5运筹学应用的过程

运筹学不仅仅是数学工具的集合。运筹学也不仅仅是模型方法的集合,而更应该是一个完整的、系统的过程。运筹学研究的最终目的是对所分析的问题实施解决方案,因此保持问题驱动的焦点是至关重要的。运筹学实践者经常要面对的是对系统化解决方案的需求,要面对的是对问题全系统全寿命的考验。现实中的太多病态定义、非标准化结构的问题,往往需要运筹学实践者自己提炼和解决。

如图1-3所示,运筹学的应用过程包括以下七个步骤:定位、问题定义、数据收集、模型构建、模型求解、验证与分析、实施与监控。将这些步骤结合在一起构成了一种持续反馈的机制。

图1-3运筹学的应用过程

例1-1-考虑一个高度简化的军事作战计划问题。蓝军试图入侵由红军防御的领地。红军有三条防线和200个正规战斗单位,并且还能抽调出200个预备单位。蓝军计划进攻两条前线(南线和北线);红军设置三条东西防线(Ⅰ、Ⅱ、Ⅲ),防线Ⅰ和防线Ⅱ各自要至少阻止蓝军进攻4天以上,并尽可能延长总的战斗持续时间。蓝军的前进时间由下列经验公式估计得到:

其中,系数a和b如表1-1所示。

红军的预备单位能够且只能用在防线Ⅱ上。蓝军分配到三条防线的单位数由表1-2给出。

红军应如何在北线/南线和三条防线上部署他的军队?

1.5.1-定位

“定位”的主要目标是组成一个小组,并确保其所有成员对有关问题有一个清楚的了解。通常,团队由一个领导者和来自不同职能领域或部门的成员组成。

1.5.2问题定义

“问题定义”需要对问题的范围和期望的结果有一个明确定义。这一阶段不应与前一阶段相混淆,因为它更加集中和面向目标。

对问题的清晰定义包含三个主要部分。第一个是明确目标的陈述。虽然完整的系统级解决方案会更受青睐,但当系统非常大或复杂时,这通常是不现实的,在许多情况下,必须将重点放在系统中可以有效隔离和分析的部分。

第二个是对影响目标的因素的规范。

第三个也是最后一个组成部分是对行动过程的约束的规范,即为决策者可能采取的具体行动设定界限。

1.5.3数据收集

“数据收集”的目的是将第二阶段定义的问题转化为模型进行客观分析。数据通常有两个来源———观察和预测。一些数据可以通过“观察”得到,即通过观察系统的运行实际收集数据。

1.5.4模型构建

模型是对现实世界的选择性抽象,建模是捕获系统或流程的选定特征。分析一个简化的模型通常比分析原始系统要容易得多,并且只要模型合理、准确,由得出的结论就可以有效地推回原始系统。

给出的模型的正式定义中,关键字是“选择性”。有了清晰的问题定义,就可以更好地确定系统的关键方面。这些方面必须由模型来表示。最终的目的是得到一个模型,该模型捕获了系统的所有关键元素,同时又足够简单,可以进行分析。

例如,在建立例1-1的数学规划模型时,首先要定义决策变量xij和yij(i=1,2;j=1,2,3),xij表示各个防线上的正规兵力部署数量,yij表示部署在防线Ⅱ上的预备兵力数量。下面我们就可以依据经验公式计算各个防线上的战斗持续时间,即

如果我们的目标是使六个防线上的持续时间之和达到最大,则目标函数可以表示为以下形式: