运筹学大纲.doc

运筹学大学纲课程名称（中文/英文名称）：运筹学/Operations Research课程代码：0921016005学分/总学时：3/54开课单位：数学与信息科学学院面向专业：数学与应用数学专业、信息与计算科学专业和统计学专业一、课程的性质、目的和任务 本课程是数学与应用数学专业和统计学专业的一门专业选修课及信息与计算科学专业的模块选修课。它以数学为主要工具，寻求由生产、管理和生活中提出的若干问题的最优方案，是一门研究优化决策的科学。开设本课程是让学生熟悉一些运筹学的基本模型及其求解原理、方法技巧、主要算法和实际应用，并掌握简单问题的建模方法；同时能够运用常用数学软件（如LINDO，LINGO，MATLAB等）求解运筹学的一些实际应用案例,从而培养学生建立数学模型，选择优化方法，利用计算机去处理、分析数据和解决实际问题的能力。因此，本课程所学知识既能作为工作后指导生产实践、提高经济效益的有利工具，又能为学生攻读相关专业（包括运筹学、信息类、计算机专业、经济类、管理类等）的硕士研究生，设计系统软件和应用软件等，打下坚实的基础。二、学习本课程学生应掌握的前设课程知识数学分析, 高等代数, 概率论, 计算机语言等三、学时分配章节学 时理论实验合计第一章 线性规划1.1线性规划问题221.2可行区域与基本可行解441.3单纯形方法441.4对偶性与对偶单纯形法661.5灵敏度分析22第二章 整数线性规划2.1整数线性规划问题112.2 Gomory割平面法222.3分枝定界法22第三章 动态规划3.1最优化原理223.2确定性的定期多阶段决策问题44第四章 图与网络分析4.1图与子图224.2图的连通性114.3树与支撑树224.4最小树114.5最短有向路问题224.6最大流问题22第五章 排队论5.1随机服务系统概论225.2无限源的排队系统66第六章 决策分析6.1决策分析的基本概念0.50.56.2风险型决策分析1.51.56.3不确定型决策分析11第七章 对策论7.1对策的基本概念117.2矩阵对策的平衡局势33合计5454四、课程内容和基本要求1线性规划 （18学时）1 线性规划问题 (2学时)1.线性规划问题举例2.线性规划模型：可行解，最优解，标准型2 可行区域与基本可行解 （4学时）1. 图解法2.可行区域的几何结构：凸集及性质，顶点3. 基本可行解及线性规划的基本定理：基，基向量，基变量，非基变量，基本解，基本可行解，可行基3 单纯形方法 （4学时）1. 单纯形方法：初始基本可行解2. 单纯形表3. 两阶段法4 对偶性与对偶单纯形法 （6学时）1. 对偶线性规划：原始问题与对偶问题的关系2. 对偶理论：互补松紧条件3. 原始和对偶问题的解及经济意义4.对偶单纯形法5 灵敏度分析 （2学时） 1.改变价值向量 2.改变右端向量 基本要求：使学生掌握线性规划的基本概念、基本理论和求解线性规划图解法、单纯形法和两阶段法；掌握对偶线性规划基本理论和求解法及其经济解释；能够对线性规划问题进行灵敏度分析；能够利用优化软件求解和分析实际案例。2整数线性规划（5学时）1 整数线性规划问题（1学时）1.整数线性规划问题举例2.解整数线性规划问题的困难性.2 Gomory割平面法 （2学时）1. Gomory割平面法的基本思想2. Gomory割平面法计算步骤3 分枝定界法 （2学时）1. 分枝定界法的基本思想 2. 分枝定界法计算步骤基本要求：使学生了解整数线性规划的一些实际背景, 求解的困难性及常用算法；掌握求解整数线性规划的Gomory割平面法和分枝定界法；能够利用优化软件求解和分析实际案例。3动态规划 （6学时）1 最优化原理（2学时）1.多阶段决策问题2.用递推法解最短路线问题，阶段，决策变量，状态变量，策略，状态转移方程，最优指标函数3.最优化原理2 确定性的定期多阶段决策问题 （4学时）1. 旅行售货员问题2. 多阶段资源分配问题3. 用最优化原理解某些非线性规划问题：背包问题，可靠性理论问题基本要求：使学生掌握多阶段决策问题的最优化原理和求解方法；理解多阶段决策问题的特点和最优化原理；掌握几种典型的确定性的定期多阶段决策问题的求解方法：如最短路线问题，旅行售货员问题，多阶段资源分配问题，背包问题，可靠性理论问题等；能够利用优化软件求解和分析实际案例。4网络分析（10学时）1 图与子图 （2学时）1.图与网络，简单图，多重图，空图，平凡图，完全图，二部图，完全二部图，补图，有向图2.关联矩阵和邻接矩阵3. 子图，点的导出子图，边的导出子图，支撑子图，子图的交与并2 图的连通性 （1学时）1. 图的连通，（有向）路，简单（有向）路，初级（有向）路，（有向）回路，简单（有 向）回路，初级（有向）回路，（强）连通分支，强连通的充分必要条件 2. 图的割集，割边，边割，割集，弧割，有向割集。3 树与支撑树 （2学时）1. 树及其基本性质，树的等价定义2. 支撑树及基本性质4 最小树问题 （1学时）1. 最小树及其性质2. 求最小树Kruskal算法3.Dijkstra算法5 最短有向路问题 （2学时）1. 最短有向路方程2.求最短有向路的Dijkstra算法6 最大流问题 （2学时）1. 最大流最小割定理，可行流，增广路2. 最大流算法基本要求：使学生掌握图和网络的基本概念；掌握几种典型网络模型的特征及其求解方法；掌握图的连通与割集及其树的概念；掌握支撑树、最小树、最短有向路和最大流问题的求解方法。能够利用优化软件求解和分析实际案例。5排队论 （8学时）1 随机服务系统概论 （2学时）1.随机服务系统的基本组成部分，输入过程，排队规则，服务机构，2.几个常用的概率分布和最简单流，负指数分布，泊松分布 ，生灭过程2 无限源的排队系统 （6学时）1. M/M/1/系统,2. M/M/1/k系统 基本要求：了解排队论的基本理论和方法；掌握随机服务系统的基本概念和负指数分布，泊松分布 ，生灭过程；掌握几种典型的无限源的排队系统。6决策分析（3学时）1 决策分析的基本概念 （0.5学时）1.决策分析的基本概念，决策问题分类，状态集，决策集，报酬函数，决策准则2.决策的数学模型和例子2 风险型决策分析 （1.5学时）1. 进行风险型决策分析的基本条件和方法，最大可能法，期望值法2. 决策树3 不确定型决策分析 （1学时）1.不确定型决策分析的条件和例子2. 不确定型决策分析基本方法，乐观法，悲观法 ，乐观系数法，后悔值法，等可能法基本要求：使学生了解决策分析的基本概念和方法；掌握风险型和不确定型决策分析的基本条件和求解方法。7对策论 （4学时）1 对策的基本概念（1学时）1.对策论发展简史2.对策模型2 矩阵对策的平衡局势 （3学时）1.矩阵对策及其平衡局势2. 矩阵对策的混合扩充3. 矩阵对策的简化4. 线性规划求解方法基本要求：使学生了解各种决策问题及其求解方法；掌握矩阵对策解的概念及解的存在性和求解方法；掌握矩阵对策的线性规划解法。五、教材及学生参考书教 材：运筹学（第三版），刁在筠、刘桂真、宿洁、马建华编著，高等教育出版社，2007年1月参考书：1、运筹学教程(第二版) ，胡运权主编,郭耀辉副主编，清华大学出版社，2003年2、运筹学习题集(第三版) ，胡运权主编，清华大学出版社，2002年3、运筹学(修订版)，运筹学教材编写组，清华大学出版社，1990年4、现代应用数学手册(运筹学与最优化卷) ，马振华主编，清华大学出版社，1998年5、优化建模与LINGO/LINDO软件，谢金星， 薛毅编著，清华大学出版社，2006年6、Introduction to Operations Research，Sixth ed. Hiller S Frederick ,Gerald J Leberman, McGraw Hi