下载文档原格式
运筹学讲稿一、运筹学的简史运筹学的早期工作及其历史可追溯到1914年，当时兰彻斯特（Lanchester）提出了军事运筹学的战斗方程；1917年，丹麦工程师埃尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排对论的一些著名公式；20世纪20年代初提出了存储论的最优批量公式.1947年美国数学家丹西格（G..B.Danting）在解决美国空军军事规划问题时，提出了线性规划及单纯形法.早在1939年，前苏联学者康托洛维奇（JT.B.KaHTopobny）在解决工业生产组织和计划问题时，已提出了类似线性规划模型，并给出了“解乘数法”的求解法.可惜当时未被重视.运筹学作为一门科学诞生于20世纪30年代末期，通常认为运筹学的活动是第二次世界大战早期从军事部门开始的.当时，英国为了研究“如何最好的运用空军及新发明的雷达保卫国家”，成立了一个由各方面的专家组成的交叉学科小组，即最早的运筹小组.进行“作战研究”（Operational,research），后来中文译名为“运筹学”.（我国在1956年用过运用学的名词，到1957年正式定名为运筹学）.第二次世界大战期间，英、美军队中的运筹学小组研究诸如护航舰队保护商对的编队问题；当船队遭受德国潜艇的攻击时，如何使船队损失最小的问题，反潜深水炸弹的合理起爆深度问题；稀有资源在军队中的分配问题等.第二次世界大战后，特别是运筹学在军事上的显著成功，引起了人们的广泛的关注，运筹学很快深入到工业、商业、政府部门等，并得到了迅速发展.在20世纪50年代中期，钱学森、许国志等老教授全面介绍运筹学，并结合我国特点在国内推广应用.1957年，我国在建筑业和纺织业中首先应用运筹学；从1958年开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用.在解决邮递员合理投递线路时，管梅谷教授提出了国外称之为“中国邮路问题”的解法；从20世纪60年代起，运筹学在钢铁和石油部门开始得到了比较全面、深入的应用.从1965年起，统筹学法在建筑业和大型设备维修计划等方面的应用取得了可喜的进展；1970年在全国大部分省、市和部门推广优选法；70年代中期，最优化方法在工程设计界受到了广泛的重视，并在许多方面取得成果；排队论开始应用于矿山、港口、电信及计算机等方面；图论用于线路布置、计算机设计、化学物品的存放等；70年代后期,存储论在应用汽车工业等方面获得成功.在此期间，以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平.运筹学是一门应用科学，至今还没有统一且确切的定义. 参见：程理民《运筹学模型与方法教程》 钱颂迪主编《运筹学》，清华大学出版二、引例例1 某工厂生产甲、乙两种产品，生产每件产品需要原材料、能源消耗、劳动力及所获利如下表所示：现有库存原材料1400千克；能源消耗总额不超过2400百元；全厂劳动满员为2000人，试安排生产任务（生产甲、乙产品各多少件），使获得利润最大，并求出最大利润. [模型建立]设安排生产甲产品x 件，乙产品y 件，相应的利润为S ,则此问题的数学模型为：maxS=5x+6y s.t. 2x+3y ≦1400x+6y ≦2400 (1) 4x+2y ≦2000 x ≥0,y ≥0,x,y ∈Z这是一个整数线性规划问题.例2 某工厂有100台机器，拟分四期使用，在每一期中有生产任务1A ，2A 两种.设第k 个周期初有完好的机器k x 台，根据经验，若周期初把k u 、k x -k u 台机器分别投入任务1A ，2A ，则周期末分别有k u /3、k x -k u /10台机器作废（k=1，2，3，4），如果在一个生产周期中每一台机器执行任务1A 可收益10千元，执行任务2A 可收益7千元，问怎样分配机器使收益最大？试建立数学模型.[数学模型的建立] 按题设，k x ，k u （k=1、2、3、4）受约束于(subject to 简记为 s.t.）1+k x =32k u +109(k x -k u ),0≤k u ≤k x 且1x =100 第K 个周期收益10k u +7（k x -k u ），因此四个周期的总收益为 V=∑=41k （10k u +7（k x -k u ）），于是问题的数学模型为：Max V=∑=41k （10k u +7(k x -k u ））s.t. 1+k x =32k u +109(k x -k u ) (2) 0≤k u ≤k x 且1x =100 ， k=1,2,3,4 这是一个分步决策，且为线性规划问题.例3 某投资者有5亿元，想取其中的一部分对项目1A ，2A 进行投资，设投资i x 亿元项目i A ,从历史资料来分析，投资于项目1A 和2A 分别有预期的年收益20%和16%.同时，与项目1A 和2A 有关的总的风险损失为2212221)(2x x x x +++ (记为Q) .试设计使预期的总收益R 最大而风险损失Q 尽可能的小的投资方案. [数学模型]此问题的数学模型为： Max R=0.21x +0.162x Min Q=2212221)(2x x x x +++ (3)s.t 21x x +≦5, 21,x x ≧0注意到：Min Q=Max(-Q),若投资者根据总收益与风险损失对自己的重要程度确定权系数，希望f=0.8R+0.2(-Q)最大，则数学模型为Max f=0.8(0.21x +0.162x )-0.2[2212221)(2x x x x +++] s.t 21x x +≦5, 21,x x ≧0 (4)三、数学模型的基本概念及解法1、概念① 在上面的数学模型（1）--（4）中，都是求函数的极值问题，象这样的在等式或不等式约束条件下求一元或多元函数的极值问题，称为数学规划问题.这个需要求极值的函数称为目标函数.数学规划问题中的自变量称为决策变量.② 在数学规划中，目标函数和约束条件中的函数式都是线性的，就称它为线性规划问题.否则就称非线性规划问题（至少有一个非线性的）. 如（1）（2）是线性规划；（4）是非线性规划.③ 早在1939年前苏联数学家康托洛维奇（JT.B.KaHTopobny ）和美国的希奇柯克（F.Litchcock ）等人就在生产组织管理和制定交通运输方案方面首先研究了和运用了线性规划方法.1947年，美国数学家丹西格（G..B.Danting ）提出了单纯行法，给出了求线性规划的上实用方法.④ 对于例3，数学规划（3）：在此数学规划问题中目标函数有多个，就称它为多目标规划问题.例如，全国大学生数学建模竞赛题96年A 题、98年A 题、98年B 题、03年B 题等都是多目标函数规划问题.⑤ 另外，目标函数，约束条件，出现“最多约能”；“约不能超过”.这种模糊概念、若至少出现一个，则就称相应的规划为模糊（数学）规划问题.⑥ 又如在(4)中，数学规划问题中，目标函数为二次函数，且约束条件中的函数式子是线性的，则称它为二次规划. ⑦线性规划的一般形式为∑==nj j j x c Z 1mins.t.()()()n j x b a x a b x a x a j m mn m n n,2,1.01111111=≥≥≤+≥≤++其中j i ij c b a ,,均为已知常数.矩阵表示:()0..min ≥≥≤=X b b AX t s CX Z 或⑧标准形式(矩阵)为..min ≥≤=X b AX t s CX Z (松弛度量,剩余度量)⑨线性规划问题中满足约束条件的解称为可行解,其全体称为可行域,使目标函数达到最小值(最大值)的可行解称为最优解,最优解对应的目标函数值勤称为最优值. 最优解为0X ,最优值为0CX . 2.重要结论 ① 若线性规划问题⑸存在可行域,则可行域为凸集.②若线性规划问题可行域有界，则最优解在可行域的顶点达到.3．数学规划的解法； ①． 解线性规划的单纯形法，（解法一）. ②．解法二 lindo 数学软件.Lindo ()()⎪⎪⎩⎪⎪⎨⎧.2.30,,50,100,200,,解线性非线性整数规划解线性整数规划个约束个变量解非线性规划个约束个变量二次规划线性规划Lingo lingo Gind lindo安装 A ：>install ↓ C: > . ；(表示进入状态) 例如 求 y x Z 32max +=s.t. 0.12531034≥≤+≤+y x y x y x.32max y x +? S T (或S.T 或Subject to) ? 1034<+y x ? 1253<+y x ? END : 运行 Go③． 图解法（线性规划）求例的数学模型.可行域为由；y x y x l by x l y x l 组成的凸五边形区域及.0,0.200024:,2400:,140032:321===+=+=+ 直线。
运筹学Operations ResearchPRESENTED BY Xingzi Xie参考学时：48学时（24次课）3 平时成绩课堂表现与考勤占50%；作业占50%2 课程总成绩 平时成绩占30%，期末考试成绩占70%。
考试为闭卷。
学习内容1 绪论（4）；线性规划（10）；整数规划（10）图与网络（8）；网络计划（8）；决策分析/对策论（4）CONTENT基本概念INTRODUCTION01起源和发展 HISTORY02性质和特点 PROPERTIES03模型构建 BUILDING MODELS04计算步骤 COMPUTATION STEPS05名称由来高祖曰：“公知其一，未知其二。
夫运筹策帷帐之中，决胜于千里之外，吾不如子房。
镇国家，抚百姓，给馈饷，不绝粮道，吾不如萧何。
连百万之军，战必胜，攻必取，吾不如韩信。
——刘邦《史记•高祖本记》运筹学定义“运筹学是在实行管理的领域运用数学方法对需要进行管理的问题统筹规划、做出决策的一门应用科学。
”Morse 和 Kimball运筹学定义“由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。
”钱学森运筹学定义“运用科学方法来解决工业、商业、政府和国防等部门里有关人力、机器、物资、金钱等大型系统的指挥或管理中所出现的复杂问题的一门学科，其目的是帮助管理者确定其方针和行动。
”英国运筹学学会定义的核心数以百计的定义之核心都是科学方法来处理自然环境和社会环境中有关人和物的运行体系2、环境自然环境、社会环境、心理环境、信息环境3、体系1、方法科学定量、定性、建模、求解、验证由“人-物”扩展为“人-财-物”萌芽成长发展成熟1、运筹学的发展历程二战以前二战期间五六十年代七八十年代一战古代中国《孙子兵法》、田忌赛马、围魏救赵军事古代欧洲阿基米德、达芬奇、伽利略都研究过作战中的运筹问题二战Lanchester 战斗方程鲍德西雷达站与 大西洋反潜战运筹学的三个起源：军事、管理、经济2.1 军事——第一次世界大战期间1）1914-1915年兰彻斯特（ Lanchester）的若干军事论文用微分方程研究军事行为中双方兵力多寡、火力强弱与战争结果关系，提出Lanchester战斗方程；2）爱迪生的海军作战程序分析商船在海战中走Z形路线的优缺点；2.1 军事——第二次世界大战期间鲍德西雷达站的研究——“布莱克特马戏团”1）整个运筹小组由3位心理学家，2位数学家，2位数学物理学家，1位天文物理学家，1位普通物理学家，1位陆军军官与1位测量员组成。
《运筹学》教学大纲1.课程中文名称（英文名称）：运筹学（Operations Research）2,课程类别：□公共课程□学科基础课程因专业课程□其他3,课程性质：因必修课口选修课,课程总学时：51总学分：34 .适用专业：工商管理专业6•先修课程：《微积分》、《线性代数》、《计算机软件应用》等一、课程简介《运筹学》是工商管理等经济管理类各专业的学位课程，是学生学习专业课和从事本专业的科研与工作的必备理论基础和技术方法。
通过本实验能理解运筹学领域中常用数学模型的建立、算法求解和结果分析，为该专业学生学习其它相关专业课程提供有关系统决策和最优化的基础知识，同时也为学生今后从事工程实践和科学研究打下良好基础。
二、课程教学目标本课程内容及具体要求（一）实验之前熟悉各种数学模型的建立；（二）会使用excel软件的规划求解功能进行求解。
（三）对学生能力培养的要求：1 .掌握各种运筹学模型的共性和特性，掌握不同运筹学模型的求解步骤和计算方法，在实践中正确地运用运筹学的理论和方法解决实际问题；2 .掌握教excel软件的操作试验方法，同时培养学生一定的科学研究能力和严谨的科学态度。
课程学时分配、教学内容与教学基本要求第一章线性规划（6学时）教学内容：第一节线性规划的基本概念和数学模型第二节线性规划的图解法第三节使用Excel 2010 “规划求解”工具求解线性规划问题第四节线性规划问题求解的几种可能结果第五节建立规划模型的流程教学基本要求：使学生基本了解线性规划的基本概念和数学模型，掌握线性规划的图解法，熟练掌握使用Excel2010 “规划求解”工具求解线性规划问题，理解线性规划问题求解的几种可能结果, 知道建立规划模型的流程。
第二章线性规划的灵敏度分析（9学时）教学内容：第一节线性规划的灵敏度分析第二节单个目标函数系数变化的灵敏度分析第三节多个目标函数系数同时变化的灵敏度分析第四节单个约束右端值变化的灵敏度分析第五节多个约束右端值同时变化的灵敏度分析第六节约束条件系数变化的灵敏度分析第七节增加一个新变量第八节增加一个约束条件第九节灵敏度分析的应用举例教学基本要求：使学生基本了解线性规划的灵敏度分析，掌握单个目标函数系数变化的灵敏度分析、多个目标函数系数同时变化的灵敏度分析，理解单个约束右端值变化的灵敏度分析、多个约束右端值同时变化的灵敏度分析、约束条件系数变化的灵敏度分析。
《运筹学》课程简介06191340 运筹学 3Operational Research 3-0预修要求：线性代数面向对象：三、四年级本科生内容简介：《运筹学》这本教材主要内容包括线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论以外；还包括目标规划和多目标规划。
本书着重介绍运筹学的基本原理和方法，注重结合经济管理专业实际和其它实际问题，具有一定的深度和广度。
书中每章后附有习题，便于自学。
有些部分增补了“注记”，便于读者了解运筹学的各分支的发展趋势，便于读者对运筹学进一步研究。
推荐教材或参考书：《运筹学》《运筹学》教材编写组编清华大学出版社出版日期：2005.6 《运筹学》徐渝胡奇英主编陕西人民出版社出版日期：2001.8 《运筹学习题集》胡运权主编清华大学出版社出版日期：2005.12《运筹学》教学大纲06191340 运筹学 3Operational Research 3-0预修要求：线性代数面向对象：三、四年级本科生一、课程的教学目的和基本要求《运筹学》是应用数学的重要分支和管理类本科重要的学科基础课之一。
目的是通过讲授、作业、上机、讨论等教学环节，学习理解与经济管理领域密切相关的运筹学基本模型与方法，掌握运筹学整体优化的思想和若干定量分析的优化技术，能正确应用各类模型分析、解决不十分复杂的实际问题。
学生学完本课程后，应达到如下要求：正确理解运筹学的方法论，掌握运筹学整体优化思想；掌握线性规划、整数规划、运输问题、动态规划等基本模型的功能和特点，熟悉其建模条件、步骤和相应的技巧，能根据实际背景抽象出适当的运筹学模型，熟练掌握各种模型特别是确定性模型的求解方法，并能对求解结果作简单分析；掌握与基本模型相关的基本概念及基本原理，做到思路清晰、概念明确；具有初步运用《运筹学》思想和方法分析、解决实际问题的能力。
二、课程主要内容及学时数的分配（打★的为重点讲授部分）每周3学时，共3×16=48学时（一）绪论3学时1．运筹学的简史、运筹学的性质和特点1学时2．运筹学的工作步骤、运筹学的模型1学时3．运筹学的应用、运筹学的展望1学时（二）线性规划及单纯形法9学时1．线性规划问题及其数学模型2学时2．线性规划的几何意义1学时3．单纯形法★2学时4．单纯形法的计算步骤★2学时5．单纯形法的进一步讨论1学时6．应用举例1学时（三）对偶理论与灵敏度分析5学时1．单纯形法的矩阵描述、改进单纯形法1学时2．对偶问题的提出1学时3．线性规划的对偶理论★2学时4．对偶问题的经济解释、对偶单纯形法★1学时(四)运输问题4学时1．运输问题的数学模型1学时2．表上作业法★1学时3．产销不平衡的运输问题1学时4．应用举例1学时（五）整数规划6学时1．整数规划的提出1学时2．分枝定界法1学时3．割平面法★2学时4．0-1整数规划1学时5．指派问题1学时（六）无约束问题6学时1．基本概念1学时2．一维搜索★2学时3．无约束极值问题的解法★3学时（七）约束极值问题6学时1．最优性条件★2学时2．二次规划1学时3．可行方向法1学时4．制约函数法★1学时（八）动态规划的基本方法6学时1．多阶段决策过程及实例1学时2．动态规划的基本概念和基本方程★2学时3．动态规划的最优性原理和最优定理1学时4．动态规划的静态规划的关系★2学时（九）动态规划应用举例3学时1．资源分配问题1学时2．生产与贮存问题1学时3．背包问题1学时三、教学方式：课堂讲授四、相关教学环节安排：1．安排教辅同学负责作业分发与答疑；2．采用多媒体教学；3．课件、课程作业采用FTP服务器上传下载。
