运筹学基础 课件 第1章.pptx

第1章运筹学概述;

1.1运筹学的起源;

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运筹学的定义;

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

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

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

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

;

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

1.3运筹学的模型;

1.3.2网络模型

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

1.3.3动态规划模型

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

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

1.3.4生灭过程模型

生灭过程模型的基本要素包括状态和状态转移,状态代