运筹学基础.ppt
《运筹学基础.ppt》由会员分享,可在线阅读,更多相关《运筹学基础.ppt(137页珍藏版)》请在三一文库上搜索。
1、运筹学基础,第一讲,运筹学的产生和发展 运筹学的定义与特点 运筹学解决问题的过程 运筹学的主要研究内容 参考文献,绪 论,运筹学在英国被称为,运筹学的产生和发展,运筹学在美国被称为,1957年我国,operational research,operations research,缩写为O.R.,“夫运筹帷幄之中,决胜于千里之外”汉书,1957年我国将O.R.译为“运筹学”,运筹学思想的出现可以追溯到很早以前“田忌齐王赛马”(对策论)、“丁谓修宫 ” (网络计划 )等都体现了优化的思想。,运筹学的产生和发展,田忌赛马 齐王要与大臣田忌赛马,双方各出上、中、下马各一匹,对局三次,每次胜负1000金
2、。田忌在好友、著名的军事谋略家孙膑的指导下,以以下安排: 齐王 上 中 下 田忌 下 上 中 最终净胜一局,赢得1000金。,运筹学思想的出现可以追溯到很早以前“田忌齐王赛马”(对策论)、“丁谓修宫 ” (网络计划 )等都体现了优化的思想。 “运筹学”作为科学概念最早出现在第二次世界大战期间 美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的,如水雷的布置、对深水潜艇的袭击、商船护航的规模等等。,运筹学的产生和发展,战后这些研究成果被应用到生产、经济领域,其发展可以分为三个阶段: 1945至50年代初期创建时期,运筹学的产生和发展,1948年英国成立“运筹学俱
3、乐部”在煤力、电力等部门推广应用运筹学 相继一些大学开设运筹学课程 1948年美国麻省理工学院 1950年英国伯明翰大学 1950年第一本运筹学杂志运筹学季刊在英国创刊 1952年第一个运筹学学会在美国成立 1947年丹齐克在研究美国空军资源优化配置时提出线性规划及其通用解法单纯形法,战后这些研究成果被应用到生产、经济领域,其发展可以分为三个阶段: 1945至50年代初期创建时期 50年代初期至50年代末期成长时期,运筹学的产生和发展,战后这些研究成果被应用到生产、经济领域,其发展可以分为三个阶段: 1945至50年代初期创建时期 50年代初期至50年代末期成长时期,运筹学的产生和发展,此阶段
4、的一个特点是电子计算机技术的迅速发展,使得运筹学中一些方法如单纯形法、动态规划方法等,得以用来解决实际管理统中的优化问题,促进了运筹学的推广应用。 50年代未,美国大约有半数的公司在自己的经营管理中应用运筹学,如用于制订生产计划、资源分配、设备更新等方面的决策。 另一个特点是有更多刊物、学会出现。,战后这些研究成果被应用到生产、经济领域,其发展可以分为三个阶段: 1945至50年代初期创建时期 50年代初期至50年代末期成长时期 自60年代来,运筹学迅速普及和迅速发展时期。,运筹学的产生和发展,此阶段的特点是运筹学进一步细分为各个分支,专业学术团体的迅速增多,更多期刊的创办,运筹学书籍的大量出
5、版以及更多学校将运筹学课程纳入教学计划之中。第三代电子数字计算机的出现,促使运筹学得以用来研究一些大的复杂的系统如城市交通、环境污染、回民经济计划等。,战后这些研究成果被应用到生产、经济领域,其发展可以分为三个阶段: 1945至50年代初期创建时期 50年代初期至50年代末期成长时期 自60年代来,运筹学迅速普及和迅速发展时期。 运筹学在我国的发展,运筹学的产生和发展,运筹学的定义与特点,运筹学(Operations Research)直译 为“运作研究”。 美国运筹学会认为:运筹学所研究的问题,通常是在要求有限资源的条件下科学地决定如何最好地设计和运营人机系统。 中国大百科全书释义:它用数学
6、方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源,使实际系统有效运行的技术科学,它可以用来预测发展趋势,制定行动规划或优选可行方案。,运筹学的定义与特点,还有人:运筹学是一门应用科学,它广泛应用现有的科学技术知识和数学方法,解决实际问题中提出的专门问题,为决策者选择最优决策提供定量依据。,特点: 系统寻优、多学科综合、辅助决策,运筹学解决问题的过程,运筹学解决问题的过程主要包括以 下几个步骤: 分析和表述问题,这是对问题的定性分析过程。 建立模型。运筹学模型大都包括两个部分:目标和约束,建立模型的过程就是用参数、决策变量表达目标函数、约束条件。,运筹学解决问题
7、的过程,模型求解。用各种手段求解模型,解的精度要求可由决策者提出。 模型的测试:首先检查解的求解步骤和程序有无错误,然后检查解是否反映现实问题。 建立对解的有效控制。 方案实施:将方案应用的实践 中,并检验方案的可行性,若不可行重新进行上述过程。,运筹学解决问题的过程,例1.某工厂生产和两种型号计 算机,生产型和型计算机所需 要原料分别为2和3个单位,需要的 工时分别是4和2个单位。在计划期 内可以使用的原料的100个单位,工 时为120个单位。已知生产每台、 型计算机可获利润分别为6个单位 和4个单位,试确定获得最大利润的 生产方案。,运筹学解决问题的过程,目标函数:,约束条件:,设z为获得
8、的利润, 和 分别为生产型和型计算机台数,线性规划,运筹学的主要研究内容,运筹学的主要研究内容,运输问题,运输问题,线性规划 非线性规划 动态规划,运筹学的主要研究内容,某厂新购某种机床125台。据估计,这种设备5年后将被其它设备所取代。此机床如在高负荷状态下工作,年损坏率为1/2,年利润为10万元;如在低负荷状态下工作,年损坏率为1/5,年利润为6万元。问应如何安排这些机床的生产负荷,才能使5年内获得最大利润。,线性规划 非线性规划 动态规划,图与网络分析,运筹学的主要研究内容,运筹学基础,第二讲,主讲教师:郑黎黎 学时:48,线性规划 非线性规划 动态规划,图与网络分析 存贮论 排队论 决
9、策论 对策论,运筹学的主要研究内容,参 考 文献,胡运权.运筹学教程M.北京,清华大学出 版社,2002年。 钱颂迪.运筹学M.北京,清华大学出版社,1990年。 郭立夫.运筹学M.长春,吉林大学出版社,2002年。 胡运权.运筹学习题集M.北京,清华大学出 版社,1985年。 刘满凤、付波、聂高飞.运筹学模型与方法教程例题分析与题解M.北京,清华大学出版社,2001年。,线性规划与单纯形法,线性规划(Linear programming) 是运筹学的重要分支,是研究在一组 线性等式或者不等式约束下,使得某 一线性目标函数取得最大(最小)的 极值问题。 1947年美国人丹齐克提出了用于 求解线
10、性规划的单纯形法。,例1.美佳公司计划制造、两种家 电产品。各制造一件时分别占用的设 备A、B的台时、调试时间及每天这 两种家电可用能力、各售出一件时获 利情况如表所示:,问公司应制造两种家电各多少台,使获取的利润最大。,线性规划问题及其 数学模型,线性规划问题及其 数学模型,(1.1c),目标函数,约束条件,(1.1a),(1.1b),(1.1d),max: maximize的缩写, “最大化”, s.t. subject to的缩写, “受限制于”,运筹学基础,第三讲,主讲教师:郑黎黎 学时:48,线性规划问题及其 数学模型,例2 捷运公司在下一年度的14月的4个月内拟 租用仓库堆放物资。
11、已知各月份所需仓库面积 列于表1-2。仓库租借费用随合同期而定,期限 越长,折扣越大,具体数字见表1-3。租借仓库 的合同每月初都可办理,每份合同具体规定租 用面积和期限。因此该厂可根据需要,在任何 一个月初办理租借合同。每次办理时可签一份 合同,也可签若干份租用面积和租借期限不同 的合同,试确定该公司签订租借合同的最优决 策,目的是使所付租借费用最小。,表1-2,单位:100m2,表1-3,单位:元/100m2,月,份,1,2,3,4,所需仓库面积,15,10,20,12,线性规划问题及其 数学模型,用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面
12、积的合同。因5月份起该公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零。该公司希望总的租借费用为最小,故有如下数学模型:,min:minimize , “最小化”,线性规划问题的特征: 每个问题都用一组未知变量 表示目标函数和约束条件,并且这些变量都是非负的。 有一个目标函数,并且这个目标可表示为一组未知量 的线性函数,目标函数可以是求最大也可以求最小。 存在一组约束条件,这些约束条件都可以用一组未知量线性等式或不等式表示。,线性规划问题及其 数学模型,目标函数:,约束条件:,线性规划问题数学模型的一般形式:,其中: 为价值系数; 为资源系数; 为技术系数,或约束 系
13、数 ;,线性规划问题及其 数学模型,若设: ,,,1. 矩阵式,线性规划问题及其 数学模型,,,2.向量式 3.和式,在后面的公式推导中矩阵式和向 量式用的比较多。,线性规划问题及其 数学模型,线性规划问题数学模型的标准型:,目标函数:,约束条件:,其中: 为价值系数; 为资源系数; 为技术系数,或约束 系数 ;,线性规划问题及其 数学模型,运筹学基础,第四讲,主讲教师:郑黎黎 学时:48,线性规划的标准形式有四个特点 : 目标最大化、约束为等式、右端项 非负、决策变量均非负。 对于各种非标准形式的线性规划问 题,我们总可以通过以下变换,将 其转化为标准形式。,线性规划问题及其 数学模型,1.
14、极小化目标函数的问题 设目标函数为: 则可以令: ,该极小化问题 与下面的极大化问题有相同的最 优解:,线性规划问题及其 数学模型,2.约束条件不是等式的问题 设约束条件为: 则可在约束的左端加上一个非负 变量 使上面的约束这个不等式 约束变为等式约束:,松弛变量,线性规划问题及其 数学模型,同理,对于不等式约束: 则可在约束的左端减去一个非负变 量 ,则这个不等式约束变为: 这个非负变量称为松弛变量或剩余 变量。,线性规划问题及其 数学模型,线性规划问题的标准型,3.变量无符号限制的问题 在标准形式中,必须每一个变量均 有非负约束。当某一个变量 没有 非负约束时,可以令: 其中, 即用两个非
15、负变量之差来表示一个 无符号限制的变量,当然 的符号取决于 和 的大小。,4.对于 可以令: 显然,5.右端项有负值的问题 在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如 ,则把该等式约束两端同时乘以-1,得到:,线性规划问题及其 数学模型,线性规划问题的数学模型和图解法,图解法求解线性规划问题的步骤: 分别取决策变量x1 ,x2 为坐标向量建立直角坐标系。 确定可行域: 对每个不等式约束(包括非负约束)条件,先画出其等式在直角坐标系中的直线,然后确定约束不等式所决定的半平面,各约束半平面交出来的区域即为可行域。 图示目标函数。 最优解的确定。,线性规划问题的标准型
16、和解的概念,例1的可行域表示,利用图解法求解例1的最优解:,线性规划问题的标准型 和解的概念,例1的可行域表示,利用图解法求解例1的最优解:,线性规划问题的标准型 和解的概念,图示目标函数和最优解的确定,(1.1d),查看目标函数和可行域的关系,寻找线性规划问题的最优解。,先将目标函数变为:,求解Q2,得到问题最优值,线性规划问题的标准型 和解的概念,因此,美佳公司每天制造家电 3.5件,家电1.5件,能获得的最 大利润是8.5元。,线性规划问题的标准型 和解的概念, 无穷多个最优解情况,将例1的目标函数变为 :,(1.1d),线性规划问题的标准型 和解的概念,无界解,例1只包含约束1.1a,
17、(1.1d),线性规划问题的标准型 和解的概念, 无可行解情况 如果约束条件中存在相互矛盾的约束 时,可行域为空,问题无可行解。,线性规划问题的标准型 和解的概念,从图解法可以看到: 当线性规划问题的可行域非空时,它的可行域是有界或无界凸多边形。 若线性规划存在最优解,它一定是在可行域的某个顶点得到;若在两个顶点同时得到,则它们连线上的任意一点都是最优解,即无穷多最优解。,线性规划问题的标准型 和解的概念,从图解法可以看到: 解题思路: 先找出凸集的任一顶点,计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大,如果为否,则该顶点就是最优解的点或最优解的点之一,否则转到比这个点
18、的目标函数值更大的另一顶点,重复上述过程,一直到找出使目标函数值达到最大的顶点为止。,复习线性代数内容: 列向量 x=(x1,x2,xn)T为n维列向量。xRn 行向量 x=(x1,x2,xn)为n维列向量。xRn 矩阵(向量)运算规则 加减乘、求逆运算 线性相关 一组向量v1,vn,如果有一组不全为零的 系数1, ,n,使得: 1 v1+nvn=0 则称v1,vn 是线性相关的. 线性无关 一组向量v1,vn,如果对于任何数1,n, 若要满足: 1 v1+nvn=0 ,则必有系数 1=n=0,(全为零)则称v1,vn线性无关. 矩阵A的秩 设A为一个mn阶矩阵(mn)若矩阵中最大线性 无关列
19、向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k.,线性规划解的概念,线性规划数学模型标准型矩阵式: (1.6) (1.7) (1.8),,,可行解:满足约束条件(1.7)和非负条 件(1.8)的解称为可行解。 可行域:可行解的集合。 最优解:满足条件(1.6)的可行解。,(L),运筹学基础,第五讲,主讲教师:郑黎黎 学时:48,线性规划解的概念,基:设A是 阶系数矩阵( ), 秩A=m,则A中一定存在m个线性无关的列向量,称由m个线性无关的列向量构成的可逆矩阵 为问题L的一个基,L最多有 个基。 基变量:称与基B中的列向量对应的变量为基变量,记为 其余变量为非基变量,记为 。,,,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础
链接地址:https://www.31doc.com/p-3981511.html