运筹学基础及应用.ppt
《运筹学基础及应用.ppt》由会员分享,可在线阅读,更多相关《运筹学基础及应用.ppt(122页珍藏版)》请在三一办公上搜索。
1、运 筹 学,(Operations Research),夫运筹策帷幄之中,决胜于千里之外 史记 高祖本纪,绪 论,(1)运筹学简述(2)运筹学的主要内容(3)本课程的主要学习内容(4)运筹学的应用(5)本课程的教材及参考书(6)本课程授课方式与考核,本章主要内容:,一、古代朴素的运筹学思想,国外英文原名 Operations Research 简称“O.R.”直译为:运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中,中国古代运筹学案例,二、运筹学的起源,(一)运筹学简述,运作研究(Operational Research)小组”:二战期间解决复杂的战略和战术问
2、题。例如:如何合理运用雷达有效地对付德军空袭对商船如何进行编队护航,使船队遭受德国潜艇攻击时损失最少;在各种情况下如何调整反潜深水炸弹的爆炸深度,才能增加对德国潜艇的杀伤力等。二战后运筹学的发展经历了三个阶段(1)1945年到20世纪50年代初创建时期(2)20 世纪50年代初到20世纪50年代末成长时期(3)20 世纪60年代以来迅速发展和普及的时期,国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中,决胜于千里之外”中摘取“运筹”二字,将O.R.正式翻译为“运筹学”,三、运筹学的定义,研究工具:数学,计算机科学及其他相关科学,研究目的:对有限资源进行合理规划、使用,并提供 优
3、化决策方案。,研究对象:复杂系统的组织和管理,参考大英百科全书、辞海、中国企业管理百科全书等。,四、运筹学研究的基本特点,系统的整体优化 多学科的配合 模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题 建立数学模型 对问题求解 对模型和模型导出的解进行检验 建立对解的有效控制 方案的实施,(二)运筹学的主要内容,数学规划(线性规划、整数规划、目标规划、动态规划等)图论存贮论排队论对策论(博弈论)决策论,(三)运筹学的应用,运筹学方法 应用例 线性规划 生产结构优化 非线性规划 投资组合优化 整数规划 选址问题 动态规划 资源分配问题 网络分析 工程计划优化 排队论 服务系统优化 存贮论
4、 订货库存管理 决策分析 机会选择,运筹学的广泛实际背景促使其不断发展并 在经济管理和系统工程等多领域中发挥着令 人瞩目的重要作用。诺贝尔经济学奖从1969年首发至今的57 位获奖者中就有多位是运筹学家。1975年诺贝尔经济学奖授给了库普曼和康脱罗维 奇,以表彰首先将线性规划与经济问题相联系而 做出的贡献;1994年诺贝尔经济学奖授给了三位博弈论专家:纳什、泽尔腾、海萨尼。博弈论已经成为当代经 济学的基石。2005年以色列经济学家罗伯特-奥曼和美国经济 学家托马斯-斯切林,因“通过博弈论分析加强了 我们对冲突和合作的理解”所作出的贡献而获奖。,发表的部分获奖项目,(四)本课程的教材及参考书,选
5、用教材 运筹学基础及应用胡运权主编(第五版)高等教育出版社参考教材运筹学教程胡运权主编(第4版)清华出版社管理运筹学韩伯棠主编(第2版)高等教育出版社运筹学(修订版)钱颂迪主编 清华出版社,(五)本课程的主要学习内容,第一章 线性规划及单纯形法 第二章 线性规划的对偶理论 第三章 运输问题 第四章 整数规划与分配问题,(六)本课程授课方式与考核,讲授为主,结合讨论、习题作业,第一章 线性规划及单纯形法,Linear Programming and Simplex Method,线性规划-发展简史,法国数学家 J.-B.-J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想
6、法,但未引起注意。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题,也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法,为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。,50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪
7、等人解决了线性规划的灵敏度分析和参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题。,1979年苏联数学家.哈奇扬提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法-内点算法。用这种方法求解线性规划问题在变量个数为5000时只要单
8、纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。,1.1939年,前苏联科学家康托洛维奇-生产组织与管理中的数学方法是线性规划应用于工业生产问题的开山之作;(LEONID VITALIYEVICH KANTOROV(1912-1986),2.1947年,美国数学家乔治伯纳德丹齐格-单纯形法,被称为线性规划之父。George Bernard Dantzig(19142005),丹齐格在1946年获伯克利大学的博士学位。1947年,33岁提出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础,使得经济学、环境科学、统计学应用等学科获得了迅速发
9、展。Dantzig也因而被誉为“线性规划之父”。1952年他在兰德公司任研究数学家,在公司电脑上实行线性规划。1960年他被母校聘任教授计算机科学,终于当上运筹学中心主任。1966年他在史丹福大学当类似职位,留在那里直到1990年代退休。Dantzig在运筹学建树极高,获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linear programming andextensions一书中研究了线性编程模型,为计算机语言的发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰出工作,还推进很多领域的发展,有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划。SIAM Journa
10、l on Optimization1991年创刊号是献给他的。Mathematical Programming Society为表彰丹齐格,设立丹齐格奖,1982年起每三年颁给一至两位在数学规划有突出贡献的人。,x,a,此为无约束的极值问题,1.1 一般线性规划问题的数学模型,1-1 问题的提出,例1 用一块边长为a的正方形铁皮做一个无盖长方体容器,应如何裁剪可使做成的容器的容积最大?,解:如图设四个角上减去的小正方形边长为x,则容器体积为:,时,容积最大,例2 常山机器厂生产 I、II 两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定,生产每件产品的单位利润、消耗三种设
11、备的工时以及各种设备工时的限额如下表:,如何安排生产才能使总的利润最大?,解:设计划期内两种产品的数量分别为x1,x2,则总利润为:,maxz=2 x1+3 x2,2 x1+2 x2 12,4x1 16,5 x2 15,x10,x2 0,简记为:,s.t.(约束于:),z=2 x1+3 x2,在满足限制条件下求z的最大值。,此为有约束极值问题,1-2 线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1、原型:现实世界中人们关心、研究的实际对象。模型:将某一部分信息简缩、提炼而构造的原型替代物。数学模型:对现实世界的一个特定对象,为达到一定目的,根据内在规律做出必要的简化假设,并运
12、用适当数学工具得到的一个数学结构。,3、规划问题数学模型的三要素,(2)目标函数:问题要达到的目标要求,表示为决策变量的函数。用 z=f(x1,x2,xn)表示。,(1)决策变量:决策者为实现规划目标采取的方案、措施,是问题中要确定的未知量。用x1,x2,xn表示。,(3)约束条件:决策变量取值时受到的各种可用资源的限制,表示为含决策变量的等式或不等式。,2、规划问题,即求目标函数在若干约束条件下的最值。,4、线性规划问题(Linear Programming)的数学模型,(2)一般形式:,(1)条件:决策变量为可控的连续变量,目标函数和约束条件都是线性的。简记为“L.P.”,max(或 mi
13、n)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、条件,目标函数求极大值,约束条件全是等式(线性方程组),决策变量全非负,右端常数全非负,3、标准化方法,(1)若目标函数求极小值,即,则令,转化为,(2)若约束
14、条件为不等式,,则依次引入松弛变量或剩余变量(统称为松弛变量),转化为等式约束条件。,注意:松弛变量在目标函数中系数全为0。,约束为不等式,减去松弛变量,化为等式约束条件;约束为不等式,加上松弛变量,化为等式约束条件。,多退少补,例:max z=2 x1+3 x2,2 x1+2 x2 12,4x1 16,5 x2 15,x10,x2 0,s.t.,标准化,(3)若决策变量xj0,则令,(4)若决策变量xj取值无限制,则令,(5)若约束等式的右端常数bi 0,则等式两边同时乘以“-1”。,其中,(“一分为二”),例:将下列线性规划模型化为标准形式。,则问题化为标准形式:,并引入松弛变量x4,x5
15、,课堂练习:将下列线性规划问题化为标准形式,线性规划问题的数学模型,标准形式如下:,1-4 线性规划问题的解,已知线性规划的标准形式:,或,1、求解线性规划问题:,从满足(2)、(3)的方程组中找出一个解使目标函数(1)达到最大值。,2、可行解:,所有可行解的集合。,可行域:,满足约束条件(2)、(3)的解。记做,最优解:,使目标函数达到最大值的可行解。,(1)基:设A为线性规划问题约束条件的 m n 系数矩阵(mn),且 B 为其 mm 子矩阵,若|B|0(即 B 可逆),则称 B 为该线性规划问题的一个基。,(3)基变量:每个基向量所对应的决策变量,即x1,x2,xm 记为XB=(x1,x
16、2,xm)T,(4)非基变量:除去基变量之外的其他决策变量,即xm+1,xm+2,xn,记为XN=(xm+1,xm+2,xn)T,3、基,不妨假设 A 中前 m 行 m 列对应的子矩阵为一个基,即,(2)基向量:基B中每个列向量,即P1,P2,Pm,(5)基解(基本解):在约束方程组中,令所有非基变量xm+1=xm+2=xn=0 后,解出基变量的唯一解,得到的解,(6)基可行解(基本可行解):满足决策变量非负要求的基解。,(7)可行基:与基可行解对应的基。,(8)基最优解:使目标函数达到最大值的基可行解。,注意:基解最多 个。,(9)最优基:与基最优解对应的基。,4、线性规划问题各种解之间的关
17、系,约束方程的解空间,基解,可行解,非可行解,基可行解,例:在下述线性规划问题中,列出全部基、基解、基可行解,并指出最优解。,解:系数矩阵为,若取基为 B=(P1,P2,P3),则基变量为x1,x2,x3,非基变量为x4,x5,令x4=x5=0,代入约束方程组,解得x1=4,x2=3,x3=-2,从而得到一个基解 X=(4,3,-2,0,0)T,这个基解不是基可行解!,该 L.P.共有8个基解。,若取基为 B=(P3,P4,P5)=I3,则基变量为x3,x4,x5,非基变量为x1,x2,令x1=x2=0,代入约束方程组,从而得到一个基解 X=(0,0,12,16,15)T,这个基解是基可行解!
18、,(注意:选择单位矩阵为基可以较方便的求出一个基可行解。),同理可得其他基解.,(最优基),(最优解),(最优目标函数值),1.2 图解法,1、适用范围:仅含两个决策变量的 L.P.,2、步骤:(1)作平面直角坐标系,标上刻度;(2)作出约束方程所在直线,确定可行域;(3)作出一组目标函数的等值线,判定优化方向;(4)沿优化方向移动,确定与可行域相切的点,确定最优解,并计算最优目标函数值。,例:用图解法求解下列线性规划问题。(1)max z=2x1+3x2 s.t.2x1+2x212-4x1 16-5x2 15-x10,x20,x1,x2,2,2,4,6,8,4,6,0,2x1+2x2=12,
19、5x2=15,4x1=16,Z=6,Z=0,A(3,3),Zmax,有唯一最优解,当 x1=x2=3 时,Zmax=15,C(4,0),D(0,3),(0,0),B(4,2),一一对应,x1,x2,o,4x1=16(),5x2=15(),2x1+2x2=12(),红色线段上的所有点都是最优解这种情形为有无穷多最优解,但是最优目标函数值max Z=18是唯一的。,D可行域,(4,2),(3,3),x1,x2,o,4x1=16(),无界解(无最优解),x1,x2,无可行解(即无最优解),x1+2x2=14(),2x1+2x2=12(),3、线性规划问题解的类型,(1)唯一最优解:只有一个解为最优解
20、(2)无穷多最优解:有无穷多个解为最优解(3)无界解:目标函数的取值无界(4)无可行解:可行域为空集,即存在互相矛盾的约束条件。,4、可行域的特征,(1)若L.P.的可行域不是空集,则可行域为凸集。(2)若L.P.有最优解,则一定可以在可行域的顶点上找到最优解。(3)L.P.的顶点与基可行解一一对应。,1.3 单纯形法(Simplex Method)原理,3-1 预备知识:凸集与顶点,(1)凸集:对于集合C中任意两点连线段上的点,若全在C内,则称集合C为凸集。或对任何X1C,X2C,有a X1+(1-a)X2 C,则称C为凸集.,直观特征:图形从内部向外部凸出。,凸集,非凸集,(2)顶点:凸集
21、中不在任意两点的连线段内部的点。,X1,X4,X3,X5,X2,3-2 几个基本结论,(1)若线性规划问题存在可行解,则可行域为凸集。(2)线性规划问题的可行解 X=(x1,x2,xn)T 为基可行解的充要条件是 X 的正分量所对应的系数列向量线性无关。(3)线性规划问题的基可行解1-1对应可行域的顶点。例如:比较表1-1和图1-3(4)若线性规划问题有最优解,则一定存在一个基可行解为最优解。,注意:若线性规划问题有最优解,不一定所有的最优解都是基可行解。,单纯形法的计算步骤:,初始基可行解,使目标函数值增大的新的基可行解,是否最优解?,结束,是,否,3-3 确定初始基可行解,已知线性规划问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 应用

链接地址:https://www.31ppt.com/p-5392623.html