1、运筹学概述和主要内容数学规划 线性规划 非线性规划 整数规划 目标规划 动态规划 参数规划 随机规划 组合最优化 图论 排队论 存贮论 对策论（博弈论）决策论 搜索论 统筹论 最优化 启发式演算法 计算机仿真 数据挖掘 预测学 软系统方法 认知映射 运筹学教学内容：运筹学教学内容：线性规划（LP）；*整数规划（IP）；*非线性规划(NP)；*多目标规划（MP）；动态规划（DP）；对策论（GT）；决策分析（DA）；存贮论（IC）；排队论（QT）；图论（Graph Theory）（统筹方法）计算机仿真（随机模拟）运筹学是近代应用数学的一个分支，主要是研究如何将运筹学是近代应用数学的一个分支，主要是
2、研究如何将生产生产、管理管理等事件中等事件中出现的运筹问题加以提炼，然后利用数学方法进行解决的学科。运筹学是出现的运筹问题加以提炼，然后利用数学方法进行解决的学科。运筹学是应应用数学用数学和和形式科学形式科学的跨领域研究，利用像是的跨领域研究，利用像是统计学统计学、数学模型数学模型和算法等方法，和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的中的复杂问题，特别是改善或优化现有系统的效率效率。运筹学的思想在古代就已经产生了。但是作运筹学的思想在古代就已经产生了
3、。但是作为一门数学学科，用纯数学的方法来解决最优方为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是在二十世纪四十年代才开始法的选择安排，却是在二十世纪四十年代才开始兴起的一门分支。兴起的一门分支。随着科学技术和生产的发展，运筹学已渗入随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是包括好几个分支本身也在不断发展，现在已经是包括好几个分支的数学部门了。的数学部门了。运筹学在英国称为运筹学在英国称为operational researchoperational research，在美国
4、称为在美国称为operations researchoperations research，英文缩写是，英文缩写是OROR。中国科学工作者取。中国科学工作者取“运筹运筹”一词作为一词作为OROR的意的意译，包含运用筹划、以策略取胜等意义。译，包含运用筹划、以策略取胜等意义。一、运筹学的定义一、运筹学的定义 运筹学（运筹学（Operational Research)Operational Research)直译为直译为“运作研究运作研究”应用运筹学处理问题时分为应用运筹学处理问题时分为5 5个阶段。个阶段。规定目标和明确问题：包括把整个问题分解成若干子问题，确定问题规定目标和明确问题：包括把整个
5、问题分解成若干子问题，确定问题的尺度、有效性度量、可控变量和不可控变量，以及用来表示变量界限和变的尺度、有效性度量、可控变量和不可控变量，以及用来表示变量界限和变量间关系的常数和参数。量间关系的常数和参数。收集数据和建立模型：包括定义关系、经验关系和规范关系。收集数据和建立模型：包括定义关系、经验关系和规范关系。求解模型和优化方案：包括确定求解模型的数学方法求解模型和优化方案：包括确定求解模型的数学方法,程序设计和调试程序设计和调试,仿真运行和方案选优。仿真运行和方案选优。检验模型和评价解答：包括检验模型的一致性、灵敏度、似然性和检验模型和评价解答：包括检验模型的一致性、灵敏度、似然性和工作工
6、作能力能力，并用试验数据来评价模型的解。一致性是指主要参数变动时（尤其是，并用试验数据来评价模型的解。一致性是指主要参数变动时（尤其是变到极值时）模型得出的结果是否合理；灵敏度是指输入发生微小变化时输变到极值时）模型得出的结果是否合理；灵敏度是指输入发生微小变化时输出变化的相对大小是否合适；似然性是指对于真实数据的案例，模型是否适出变化的相对大小是否合适；似然性是指对于真实数据的案例，模型是否适应；工作能力则是指模型是否容易解出，即在规定时间内算出所需的结果。应；工作能力则是指模型是否容易解出，即在规定时间内算出所需的结果。方案实施和不断优化：包括应用所得的解解决实际问题，并在方案实施方案实施
7、和不断优化：包括应用所得的解解决实际问题，并在方案实施过程中发现新的问题和不断进行优化。上述过程中发现新的问题和不断进行优化。上述5 5个阶段往往需要交叉进行，不断个阶段往往需要交叉进行，不断反复。反复。现代运筹学方法强调现代运筹学方法强调黑箱方法黑箱方法、数学模型数学模型和和仿真运行仿真运行。它重视系统的输入输。它重视系统的输入输出关系，即问题所处的环境条件和问题中主要因素与环境间的关系，而不追出关系，即问题所处的环境条件和问题中主要因素与环境间的关系，而不追求系统内部机理，因而易于达到从系统整体出发来研究问题的目的。常用的求系统内部机理，因而易于达到从系统整体出发来研究问题的目的。常用的数
8、学模型有：数学模型有：分配模型分配模型、运输模型运输模型、选址模型选址模型、网络模型网络模型、计划排序模型计划排序模型、存储模型存储模型、排队模型排队模型、概率决策模型概率决策模型、马尔可夫模型马尔可夫模型等。模型求解往往成为等。模型求解往往成为应用计算机程序进行仿真运行。现在已有各种运筹学软件包供应，使运筹学应用计算机程序进行仿真运行。现在已有各种运筹学软件包供应，使运筹学可以处理相当复杂的大型问题。可以处理相当复杂的大型问题。随着运筹学应用于社会大系统，仅靠随着运筹学应用于社会大系统，仅靠定量分析定量分析已难以找到合理的优化方案，已难以找到合理的优化方案，人们常采用定量与定性相结合、在人们
9、常采用定量与定性相结合、在定量分析定量分析的基础上进行的基础上进行定性分析定性分析的方法。的方法。因此，在许多情况下已很难划分运筹学、系统分析与政策分析的界限。因此，在许多情况下已很难划分运筹学、系统分析与政策分析的界限。1、Mathematical programming(数学规划数学规划)：Linear programming(线性规划线性规划),Nonlinear programming（非线性规划）（非线性规划）,Integer programming（整数规划）（整数规划）,Objective programming（目标规划）（目标规划）Dynamic programming（动态
10、规划）（动态规划）,2、Graph theory（图论）（图论）3、Network analysis（网络分析）（网络分析）4、Queueing theory（排队论）（排队论）5、Game theory（博弈论，对策论）（博弈论，对策论）6、Decision theory（决策论）（决策论）7、Storage theory（存储论）（存储论）马马马马马马赢马马马马马马赢bxtyaytxddddba 202022yxyx0 x0yy2020yxxx=100人=80人=0人=60人当当F.W.Lanchester的模型十分简单，只考虑：双方兵力多少和战斗力强弱；兵力因战斗减员和非战斗减员而减少，
11、由后备力量的增援而增加；杀伤对方的能力，与射击率、命中率以及战争类型有关。一般战争模型 假设：x0、x(t)-甲方的初始兵力及时刻 t 的兵力y0、y(t)-乙方的初始兵力及时刻 t 的兵力每一方战斗减员取决于双方的兵力，分别用f(x,y)与g(x,y)来表示甲、乙双方的战斗减员率；每一方的非战斗减员与本方兵力成正比；每一方的增援力是给定的函数，分别用u(t)与v(t)表示甲、乙双方的增援率。模型为：00()(,)()0()(,)()0(0)(0)x tf x yxu ty tg x yyv txxyy，正规战争模型 假设:甲乙两方都是正规部队，双方士兵公开活动，每个士兵处在对方的杀伤范围内；
12、甲方战斗减员率与乙方兵力成正比：f(x,y)=ay,a称为乙方战斗有效系数(a0)；乙方战斗减员率与甲方兵力成正比：g(x,y)=bx,b称为甲方战斗有效系数(b0).建模 00()()(0),(0)xayxu tybxyv txxyy 0)()(,0tvtu0000y)(y,x)(xbxyayx若则轨线方程 aybxaybxdt/dxdt/dydxdybxdxaydy 222200aybxkkaybx战争结局分析 情形一,k=0，轨线方程为xaby 00yx时，情形二,k0,轨线方程为2()akxyba双方兵力同时为0.战争结局应为平局.0aky时0 x甲方输,乙方胜。00bkx y时，情形
13、三,k0,轨线方程为乙方输，甲方胜2bkyxaa战争结局分析kakbxyOk0,乙胜k=0,平局初始兵力分析 双方战平的条件(平衡条件):2000ybkxa 可见若甲方初始兵力x0不变，乙方战斗有效系数a也不变，而乙方初始兵力y0增到原来的2倍,则甲方的战斗有效系数b就要增加到原来的4倍才能与之抗衡.同理可分析其余情况.也称为平方律模型。游击战争模型 假设假设 设甲乙双方都是游击部队，隐蔽在对方看不见的区域内活动，此时每方的战斗减员率不仅与对方兵力有关，而且与本方的密度有关；f(x,y)=cxy,c为乙方战斗有效系数；g(x,y)=hxy,h为甲方战斗有效系数。模型 只考虑 的情况，0,()(
14、)0u tv t0000y)(y,x)(xhxyycxyx轨线方程hdxcdy ,chcxyhxyxydxdy mhxcy00hxcym一族平行直线战争结局分析/mc/mhxyOm=0,平局m0,乙胜m0乙胜n=0,平局n0,即 02002)(cxbxy 实际上,由于正规军在明处,游击队在暗处,而且活动区域较大,从而使c很小而b较大.从而y0/x0较大.越南战争分析 美国军方曾用此模型分析越南战争(1961年1975年).甲方代表越南游击队,乙方代表美军，得出美军获胜的条件是:64)(200 xy 美军必须投入8倍于越南游击队的兵力才可能获胜，而美国当时最多只能派出6倍于越南游击队的兵力，故不
15、能取胜。最终美军不得不接受和谈并撤军，越南人民胜利了。硫磺岛战役 JHEngel用二次大战美日硫磺岛战役中的美军战地记录验证了正规战争模型。美军于1945年2月19日开始进攻硫磺岛，战斗进行了36天，日军21500人全部阵亡或被俘。美军投入了兵力73000人，伤亡20265人。美军战地记录有按天统计战斗减员与增援情况，日军没有增援，战地记录全部遗失。模型 设A(t)和J(t)表示美军和日军在第t天的兵力。在正规战争模型中取=0，则：已知美军的增援率为：并可由战地记录算出A(t),t=1,2,36.其它065130003260001054000)(ttttuA(t)-J(t)u(t)J(t)-A
16、(t)A(0)0,J(0)21500ab求近似解d)(bAd)(Jd)(u)(aJd)(Atttt000010()lim()()()ibxiiiiixiiiaf x dxfxfxf 在定积分的近似计算中，可用积分和作近似计算求近似解tttAbJtJuJaAtA111)9.3.4()()0()()8.3.4()()()0()(3612037000)(,0)36(,21500)0(ttAJJ01060203700021500360361.)t(A)(J)(Jbt从(4.3.9)令t=36解出 求近似解 把b代回(4.3.9)式便可求出J(t),t=1,2,336.又在(4.3.8)中令t=36解出
17、36136136tt)t(J)(A)t(ua近似解 其中分子表示美军总伤亡人人数，为20265人，分母可由已经算出的J(t)求出为372500，故11()0.0544()()1,2,36ttA tJut 0544.037250020265a从而得A(t)的理论值：效果J.H.ENGEL用美军战地记录数据对正规战争模型进行的验证：与实际情况吻合得很好第二次世界大战后，在这些军事运筹学小组中工作过的科学家转向研究在民第二次世界大战后，在这些军事运筹学小组中工作过的科学家转向研究在民用部门应用用部门应用运筹学方法运筹学方法的可能性的可能性,从而促进了在民用部门应用运筹学的发展。从而促进了在民用部门应
18、用运筹学的发展。19471947年年G.B.G.B.丹齐克在研究美国空军丹齐克在研究美国空军资源配置资源配置问题时提出问题时提出线性规划线性规划及其通用解及其通用解法法单纯形法单纯形法。5050年代初用电子计算机求解线性规划问题获得成功。年代初用电子计算机求解线性规划问题获得成功。19511951年年P.M.P.M.莫尔斯和莫尔斯和G.E.G.E.金布尔合著运筹学方法一书正式出版，标志着运筹金布尔合著运筹学方法一书正式出版，标志着运筹学这一学科已基本形成。学这一学科已基本形成。到到5050年代末，美国大企业在年代末，美国大企业在经营管理经营管理中大量应用运筹学。开始时主要用于制中大量应用运筹学
19、。开始时主要用于制订订生产计划生产计划，后来在，后来在物资储备物资储备、资源分配资源分配、设备更新设备更新、任务分派任务分派等方面应用等方面应用和发展了许多新的方法和模型。和发展了许多新的方法和模型。60 60年代中期，运筹学开始用于服务性行业和年代中期，运筹学开始用于服务性行业和公用事业。一些发达国家的企业、政府、军事等部门都拥有相当规模的运筹公用事业。一些发达国家的企业、政府、军事等部门都拥有相当规模的运筹学研究机构，专门从事有关方法和建模的研究，为决策提供科学的依据。学研究机构，专门从事有关方法和建模的研究，为决策提供科学的依据。英国在英国在19481948年成立了运筹学俱乐部，年成立了
20、运筹学俱乐部，19541954年改名为英国运筹学会，出版运年改名为英国运筹学会，出版运筹学季刊。美国在筹学季刊。美国在19521952年成立了美国运筹学会，出版运筹学杂志。年成立了美国运筹学会，出版运筹学杂志。19571957年在年在英国牛津大学英国牛津大学召开第一届国际运筹学会议，以后每隔召开第一届国际运筹学会议，以后每隔3 3年举行一次。年举行一次。19591959年成立年成立国际运筹学联合会国际运筹学联合会(IFORSIFORS)。中国在中国在19561956年曾用过年曾用过“运用学运用学”的名字，于的名字，于19571957年正式定名为年正式定名为“运筹学运筹学”，于于19801980
21、年成立中国运筹学会（年成立中国运筹学会（ORSCORSC），并于），并于19821982年加入国际运筹学联合会年加入国际运筹学联合会（IFORSIFORS）。）。七、七、展望展望 美国前运筹学会主席邦特（美国前运筹学会主席邦特（S.BonderS.Bonder）认为，运筹学应在三个领域发展：运筹学应认为，运筹学应在三个领域发展：运筹学应用、运筹科学和运筹数学。并强调发展前二用、运筹科学和运筹数学。并强调发展前二者，从整体讲应协调发展。者，从整体讲应协调发展。现代运筹学面临的新对象是经济、现代运筹学面临的新对象是经济、技术技术、社会、生态和政治等因素交叉在一起的复杂社会、生态和政治等因素交叉在一
22、起的复杂系统，因此必须注意大系统、注意与系统分系统，因此必须注意大系统、注意与系统分析相结合，与未来学相结合，引入一些非数析相结合，与未来学相结合，引入一些非数学的方法和理论，采用软系统的思考方法。学的方法和理论，采用软系统的思考方法。总之，运筹学还在不断发展中，新的思想、总之，运筹学还在不断发展中，新的思想、观点和方法不断出现。观点和方法不断出现。切克兰特（切克兰特（P.B.ChecklandP.B.Checkland）把传统的数）把传统的数学方法称为硬系统思考，它适用于解决那种学方法称为硬系统思考，它适用于解决那种结构明确的系统以及战术和技术性问题，而结构明确的系统以及战术和技术性问题，而
23、对于结构不明确的，有人参于的活动就不太对于结构不明确的，有人参于的活动就不太胜任了。在这种情况下，就应采取软系统思胜任了。在这种情况下，就应采取软系统思考的方法，如将过份理想化的考的方法，如将过份理想化的“最优解最优解”换换成成“满意解满意解”。过去把求得的。过去把求得的“解解”看成是看成是精确的、不能变的凝固的东西，而现在要以精确的、不能变的凝固的东西，而现在要以“易变性易变性”的概念来看待所求得的的概念来看待所求得的“解解”，以适应系统的不断变化。解决问题的过程是以适应系统的不断变化。解决问题的过程是决策者和分析者发挥其创造性的过程，这就决策者和分析者发挥其创造性的过程，这就是进入是进入7
24、070年代以来人们愈来愈对人机对话的年代以来人们愈来愈对人机对话的算法感兴趣的原因。大多数人认为决策支持算法感兴趣的原因。大多数人认为决策支持系统是运筹学的发展方向。系统是运筹学的发展方向。1.线性规划。线性规划。线性规划是目前在经济管理中应用最广泛的一种优化法，它的理论已经十分成熟，可以应用于生产计划、物资调用、资源优化配置等问题。它主要研究的是经济管理活动中经常遇到的两类问题：一类是在有限的劳动力、设备、资金等资源条件下，研究如何合理安排，取得最大的经济效果（如生产经营利润）；另一类是为了达到一定的目标（生产指标或其它指标），研究如何组织生产，或合理安排工艺流程，或调整产品的成份等等，以使
25、消耗资料（人力、设备台数、资金原材料等）为最少去实现目标。这类统筹规划的问题用数学语言表达（即数学模型），先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示(称为目标函数)，对问题的限制条件用有关变量的等式或不等式表达(称为约束条件)。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的数学模型。【例1】生产计划问题(资源配置)。某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量及所占设备时间见表1。该厂每周所能得到的维生素量为160kg、每周设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？本题的最优解X*=(2,5),最优值即该厂每周安排生产甲种药品生产量为2t，乙种产量为5t，每周可获得最大利润为20万元。解：设该厂每周安排生产甲种药品的产量为x1(t)，乙种产量为x2(t)，则每周所能获得的利润总额为Z=5x1+2x2数学模型为 maxZ=5x1+2x2（目标函数）
