高等运筹学(总)课程内容特点主要内容第1章概论1.1运筹学概述英国：1948年成立运筹学俱乐部，1950年创办第一份运筹学刊物“OperationalResearchQuarterly”，该俱乐部于1953年改名为运筹学会，刊物也更名为“JournaloftheOperationalResearchSociety”。美国：1952年成立运筹学会，并创刊“OperationsResearch”。中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”、“JournaloftheOperationsResearchSocietyofChina”。相关的学术刊物还有很多。“运筹帷幄之中，决胜千里之外”与“运筹学”。OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。大家学习辛苦了，还是要坚持3.运筹学的性质核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。研究对象：人类对各种资源的运用及筹划活动。研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。研究目的：了解和发现这些运用及活动的基本规律，发挥有限资源的最大效益。OR：TheScienceofBetterDecisions.ORusesmathematics,butitisnotabranchofmathematics.4.运筹学的特点强调研究过程的完整性：问题的提出→建立模型→提出解案→付诸实施。强调理论与实践的结合。5.运筹学的应用领域其影响继续扩大：国际运筹学联合会已有50个成员国。应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上。1.2最优化问题及其分类组合优化问题可用数学模型描述为：minf(x)s.t.g(x)≤0,x∈S,其中，f(x)为目标函数，g(x)为约束函数，x为决策变量，S表示有限个点组成的集合。一个组合优化问题也可用三个参数（S,F,f）来描述：S：决策变量的定义域，即解空间；F={x|x∈S,g(x)≤0}：可行解区域；f：目标函数值，满足f(x*)=min{f(x)|x∈F}的可行解x*称为该问题的最优解。组合优化的特点：可行解集合为有限点集。(3)装箱问题（binpackingproblem）如何以个数最少的尺寸为1单位的箱子装入n个尺寸不超过1单位的物品。(4)机器排序问题（machineschedulingproblem）。有n个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序。以Aj和Bj分别表示工件j（j=1,2,…,n）在A和B上的加工时间。问应如何安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？在组合优化问题中，有些可以用整数规划模型表示，有些则用文字叙述更易理解。上述问题描述均非常简单，但求其最优解确很困难。1.3计算复杂性概述算法复杂性：算法对时间和空间的需要量分别称为算法的时间复杂性和空间复杂性。算法执行基本操作的次数定义为算法的时间复杂性，记为T(n)；算法执行期间占用的计算机存储单元定义为算法的空间复杂性，记为S(n)。对于占用存储空间不是太多的问题，一般只讨论算法的时间复杂性。算法的复杂性的表示：一般表示为问题规模n（如TSP中的城市数）的函数。当一个算法A对于规模为n的问题进行求解计算时，若所需的基本操作次数的上界（指在最坏情况下）为f(n)，则称f(n)为算法A的时间复杂性函数。在分析复杂性时，可用其函数主要项的阶O(f(n))来表示。若算法A的时间复杂性为T(n)=O(f(n))，且f(n)为n的多项式函数，如O(n)、O(n3)等，则称算法A为多项式算法。时间复杂性函数不属于n的多项式函数的算法统称为指数算法，如f(n)为2n、n!、nn等形式。算法性能：多项式算法是有效算法；指数算法不是有效算法。另外，多项式算法有较好的“闭”性。问题的难易性：若一个问题找到了多项式算法，就可以认为这个问题基本解决了。若一个问题不存在多项式算法，则称这个问题是难解的。有少数复杂度为指数函数的算法，在实践中却被证明是有效的算法，如求解线性规划问题的单纯形法就是一个突出的例子。2.P,NP,NP完全和NP难P类和NP类问题若问题有求解它的多项式算法，则属于P类问题。若问题仍没有找到求其最优解的多项式算法，则称这类问题为非多项式确定问题，即NP类问题。N