算法集 matlab程序.doc

§1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问 题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有 单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都 有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本 概念。 2 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过 程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程 优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这 是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习 时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的 技巧去求解。 3 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问 题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说， 到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中 出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机 待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机 性。可以说排队现象几乎是不可避免的。 4 排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分： （i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待 时间分布和忙期分布等，包括了瞬态和稳态两种情形。 （ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队 系统的最优运营。 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便 根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识，分析几个常见的排队模型 5 对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。 一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展 的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常 生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。 在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并 力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 §2 对策问题 对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的 努力而是各方所采取的策略的综合结果。 6§1 层次分析法的基本原理与步骤 人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临