《运筹学基础及应用PPT课件》由会员分享，可在线阅读，更多相关《运筹学基础及应用PPT课件（119页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学( Operations Research )夫运筹策帷幄之中，决胜于千里之外 史记 高祖本纪绪 论（1）运筹学简述（2）运筹学的主要内容（3）本课程的主要学习内容（4）运筹学的应用（5）本课程的教材及参考书（6）本课程授课方式与考核 本章主要内容：一、古代朴素的运筹学思想国外英文原名 Operations Research 简称“O.R.”直译为：运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中中国古代运筹学案例二、运筹学的起源（一）运筹学简述运作研究(Operational Research)小组”:二战期间解决复杂的战略和战术问题。例如：1.如
2、何合理运用雷达有效地对付德军空袭2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。-二战后运筹学的发展经历了三个阶段 （1）1945年到20世纪50年代初创建时期 （2）20 世纪50年代初到20世纪50年代末成长时期 （3） 20 世纪60年代以来迅速发展和普及的时期 国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供 优
3、化决策方案。研究对象：复杂系统的组织和管理参考大英百科全书、辞海、中国企业管理百科全书等。四、运筹学研究的基本特点 系统的整体优化 多学科的配合 模型方法的应用五、运筹学研究的基本步骤 分析与表述问题 建立数学模型 对问题求解 对模型和模型导出的解进行检验 建立对解的有效控制 方案的实施（二）运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论存贮论排队论对策论（博弈论）决策论（三）运筹学的应用 运筹学方法 应用例 线性规划 生产结构优化 非线性规划 投资组合优化 整数规划 选址问题 动态规划 资源分配问题 网络分析 工程计划优化 排队论 服务系统优化 存贮论 订货库存管理
4、 决策分析 机会选择 运筹学的广泛实际背景促使其不断发展并 在经济管理和系统工程等多领域中发挥着令 人瞩目的重要作用。 诺贝尔经济学奖从1969年首发至今的57 位获奖者中就有多位是运筹学家。 1975年诺贝尔经济学奖授给了库普曼和康脱罗维 奇，以表彰首先将线性规划与经济问题相联系而 做出的贡献； 1994年诺贝尔经济学奖授给了三位博弈论专家： 纳什、泽尔腾、海萨尼。博弈论已经成为当代经 济学的基石。 2005年以色列经济学家罗伯特-奥曼和美国经济 学家托马斯-斯切林，因“通过博弈论分析加强了 我们对冲突和合作的理解”所作出的贡献而获奖。 发表的部分获奖项目组织应用效果联合航空公司在满足乘客需
5、求的前提下，以最低成本进行订票及机场工作班次安排每年节约成本600万美元Citgo石油公司优化炼油程序及产品供应、配送和营销每年节约成本7000万AT&T优化商业用户的电话销售中心选址每年节约成本4.06亿美元，销售额大幅增加标准品牌公司控制成本库存（制定最优再定购点和定购量确保安全库存）每年节约成本380万美元法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量每年节约成本1500万美元，年收入大幅增加。Taco Bell优化员工安排，以最低成本服务客户每年节约成本1300万美元Delta航空公司优化配置上千个国内航线航班来实现利润最大化每年节约成本1亿美元（四）本课程的教材及参考书选用教材
6、 运筹学基础及应用胡运权主编 （第五版）高等教育出版社参考教材运筹学教程胡运权主编 （第4版）清华出版社管理运筹学韩伯棠主编 （第2版）高等教育出版社运筹学(修订版) 钱颂迪主编 清华出版社 （五）本课程的主要学习内容 第一章 线性规划及单纯形法 第二章 线性规划的对偶理论 第三章 运输问题 第四章 整数规划与分配问题 （六）本课程授课方式与考核学科总成绩平时成绩（30）课堂考勤（12）平时作业（18）期末成绩（70）讲授为主，结合讨论、习题作业第一章 线性规划及单纯形法Linear Programming and Simplex Method线性规划-发展简史法国数学家J.-B.-J.傅里叶
7、和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，195
8、4年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家.哈奇扬提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法-内点算
9、法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。1.1939年，前苏联科学家康托洛维奇-生产组织与管理中的数学方法是线性规划应用于工业生产问题的开山之作；(LEONIDVITALIYEVICHKANTOROV(1912-1986) 2. 1947年，美国数学家乔治伯纳德丹齐格-单纯形法，被称为线性规划之父。GeorgeBernardDantzig(19142005) 丹齐格在1946年获伯克利大学的博士学位。1947年，33岁提出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础，
10、使得经济学、环境科学、统计学应用等学科获得了迅速发展。Dantzig也因而被誉为“线性规划之父”。 1952年他在兰德公司任研究数学家，在公司电脑上实行线性规划。1960年他被母校聘任教授计算机科学，终于当上运筹学中心主任。1966年他在史丹福大学当类似职位，留在那里直到1990年代退休。Dantzig在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linear programming andextensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最
11、优化、非线性规划和不确定规划。SIAM Journal on Optimization1991年创刊号是献给他的。Mathematical Programming Society为表彰丹齐格，设立丹齐格奖，1982年起每三年颁给一至两位在数学规划有突出贡献的人。xa此为无约束的极值问题1.1 一般线性规划问题的数学模型1-1 问题的提出例1 用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？解：如图设四个角上减去的小正方形边长为x，则容器体积为：时，容积最大 例2 常山机器厂生产 I、II 两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定
12、，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表： 单位产品消耗设备工时III设备工时限量（小时） 设备A设备B设备C240205121615单位利润（元）23如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？解：设计划期内两种产品的数量分别为x1，x2，则总利润为：maxz=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10， x2 0简记为： s.t.（约束于：）z=2 x1+3 x2在满足限制条件下求z的最大值。此为有约束极值问题1-2 线性规划问题的数学模型原型模型数学模型提炼数学工具1、原型：现实世界中人们关心、研究的
13、实际对象。 模型：将某一部分信息简缩、提炼而构造的原型替代物。 数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。3、规划问题数学模型的三要素（2）目标函数：问题要达到的目标要求，表示为决策变量的函数。用 z=f(x1，x2，xn)表示。（1）决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，xn表示。（3）约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。2、规划问题即求目标函数在若干约束条件下的最值。4、线性规划问题（Linear Programmin
14、g）的数学模型（2）一般形式：（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.” max (或 min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn （=，）b1 a21x1+a22x2+a2nxn （=，） b2 am1x1+am2x2+amnxn（=，） bm x1 , x2, , xn0（3）其他形式：连加形式向量形式其中 称为价值行向量；决策列向量系数列向量右端列向量矩阵形式其中 称为价值行向量；决策列向量右端列向量约束矩阵或系数矩阵1-3 线性规划问题的标准形式1、标准形式或2、条件目标函数求极大值约束条件全是等
15、式（线性方程组）决策变量全非负右端常数全非负3、标准化方法（1）若目标函数求极小值，即则令 转化为（2）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。注意：松弛变量在目标函数中系数全为0。约束为不等式，减去松弛变量，化为等式约束条件；约束为不等式，加上松弛变量，化为等式约束条件。多退少补例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10， x2 0 s.t.标准化（3）若决策变量xj0，则令（4）若决策变量xj取值无限制，则令（5）若约束等式的右端常数bi 0，则等式两边同时乘以“-1”。其中（“一分为二”）
16、例：将下列线性规划模型化为标准形式。则问题化为标准形式：并引入松弛变量x4, x5,课堂练习：将下列线性规划问题化为标准形式线性规划问题的数学模型标准形式如下：1-4 线性规划问题的解已知线性规划的标准形式：或1、求解线性规划问题：从满足（2）、（3）的方程组中找出一个解使目标函数（1）达到最大值。2、可行解：所有可行解的集合。可行域：满足约束条件（2）、（3）的解。记做最优解： 使目标函数达到最大值的可行解。（1）基：设A为线性规划问题约束条件的 m n 系数矩阵（m0，有如下结论：(1) 若对所有jm+1，有j 0 ，则z（1） z （0） ，即z （0）为最优函数值，X（0）为唯一最优解；(2) 若对所有j m+1 ，有j 0，且存在某个非基变量的检验数k=0，则将Pk作为新的基向量得出新的基可行解X（1） ，满足z（1） = z （0） ，故z（1） 也为最优函数值，从而 X（1）也为最优解， X（0） 、X（1） 连线上所有点均为最优解，因此该线性规划模型具有无穷多最优解；(3) 若存在某个j 0，但对应的第j列系数全非正，即aij0，则当 +时，有z（1） +， 该线性规划
