《运筹学ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学ppt课件.ppt（66页珍藏版）》请在三一文库上搜索。
1、1,运筹学,1 运筹学的释义和发展简史 2 运筹学的特征和方法 3 运筹学的分支 4 运筹学应用与管理科学,2,名称的由来 Operation Research 运筹帷幄 “史记” 运作研究 发展历程,运筹学的由来与发展,3,引入数学方法解决实际问题 -定性与定量方法结合 系统与整体性 -从全局考察问题 应用性 -源于实践、为了实践、服务于实践 交叉学科 -涉及经济、管理、数学、工程和系统等 多学科 开放性 -不断产生新的问题和学科分支 多分支 -问题的复杂和多样性,运筹学的性质与特点,4,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,学 科 内 容,多目标规划,双层规划,组 合
2、优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,5,成熟的学科分支向纵深发展 新的研究领域产生 与新的技术结合 与其他学科的结合加强 传统优化观念不断变化,运筹学的发展趋势,6,运筹数学,系统工程,管理与运筹学,问题与方法,方法与应用,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,7,模型要素 变量可控因素 目标优化的动力和依据 约束内部条件和外部约束 研究内容,建模,概念,最优性条件,算法,灵敏度分析,最优化模型,实例,8,运筹学（Operations Research)释义 运筹学是
3、应用数学方法对经济、民政、国防等部门在内外环境的约束条件下合理分配安排人力、物力、财力等资源,使实际系统有效运行的技术科学。它可以用来预测发展趋势,制定行动规划或优选可行方案。 运筹学的产生和发展 运筹学产生于第二次世界大战，主要用于解决如何在与德军的对抗中最大限度地杀伤敌人，减少损失。 二战以后，运筹学得到了快速的发展，成立了国际运筹学联合会（IFORS），形成了许多分支. 运筹学有广泛应用 运筹学在军事，生产、决策、运输、存储、排队等经济管理领域有着广泛的应用。,9,运筹学的特征 （1）系统的整体观念， （2）多学科交叉， （3）模型方法应用 决策步骤： 1）分析、表述问题； 2）建立模型
4、； 3）求解和优化方案； 4）测试模型，修正模型； 5）解的检验、灵敏性分析等； 6）实施方案；,2 运筹学的特征和步骤,10,线性规划 非线性规划 动态规划 整数线性规划 图与网络分析 存储论 排队论 对策论 决策分析,3 运筹学的分支,11,合伙 原则 催化原则 渗透原则 独立原则 宽容原则 平衡原则,12,生产计划：生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等，追求利润最大化和成 本最小化 库存管理：多种物资库存量的管理，库存方式、库存量等 运输问题：确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等 人事管理：对人员的需求和使用的预测，确定人员编
5、制、 人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等 财务和会计：预测、贷款、成本分析、定价、证券管理、 现金管理等,4 运筹学的应用和管理科学,13,由国际运筹与管理科学协会（INFORMS）和它的管理科学实践学会（College for the Practice of the Management Sciences）主持评奖的负有盛名的弗兰茨厄德曼（Frany Edlman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入闱者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二
6、年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。,14,15,16,17,第二章 线性规划基本概念,1 线性规划问题及模型 2 图解法 3 单纯形方法 4 线性规划应用举例分析,18,1 问题的提出,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位、产品才能使工厂获利最多？ 线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1
7、, x2 0,19,线性规划的组成要素： 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素 建模步骤 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,20,一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 +
8、+ a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0,21,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法。 例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E),2 图 解 法,22,（1）画出线性规划问题
9、的可行域，如图所示。,23,（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。得到最优解： x1 = 50， x2 = 250， 最优目标值 z = 27500,24,重要结论： 如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2，则线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约
10、束条件； 无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,25,线性规划的标准化引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =5
11、0 s3 = 0 说明：生产50单位产品和250单位产品将消耗完所有 可能的设备台时数及原料B，但对原料A则还剩余50千克。,26,线性规划的标准化 线性规划标准形式 目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0,27,可以看出，线性规划的标准形式有如下四个特 点： 目标最大化； 约束为等式； 决策变量均非负； 右
12、端项非负。 对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:,28,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f - Max z,29,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右
13、边与左 边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,30,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约 束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,31,为了使约束由不等式成为等式而引进的变量s,当 不等式为“小于等于”时称为“松弛变量”；当不等式 为“大于等于”时称为“剩余变
14、量”。如果原问题中有 若干个非等式约束，则将其转化为标准形式时，必须 对各个约束引进不同的松弛变量。,3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。,32,例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0 解：首先,将目标函数转换成极大化： 令 z= -f =
15、-2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。,33,通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的
16、符号 取决于xj和xj”的大小。,34,3 单纯形方法及大M法,单纯形法的基本思路和原理 单纯形法的表格形式 求目标函数值最小的线性规划的问题的 单纯形表解法 几种特殊情况,35,1 单纯形法的基本思路和原理,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优 解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此 点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的 解，或者能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 在加上松弛变量之后我们可得到标准型如下： 目标函数： max 50x1+100x2 约束条件：
17、x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250. xj0 （j=1，2）,sj0 （j=1，2,3）,36,它的系数矩阵 , 其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变 量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的 基本概念。 基： 已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非 奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，
18、基变量有m个。,37,非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有nm个。 由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个 基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一 的解了，这个解我们称之为线性规划的基本解。 在此例中我们不妨找到了 为A的一个基，令这个基的 非基变量x，s2为零。这时约束方程就变为基变量的约束方程：,38,x2+s1300， x2=400， x2+s3=250. 求解得到此线性规划的一个基本解： x1=0，x2=400，s1=100，s2=0，s3=150 由于在这个基本解中s1=100，s3=150，不满足该线性规划s1
19、0， s30的约束条件，显然不是此线性规划的可行解，一个基本解可以是 可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行 解，并把这样的基叫做可行基。,39,一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解 所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行 基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个 基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中 要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位 矩阵的各
20、列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向 量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等 于零。,40,在本例题中我们就找到了一个基是单位矩阵。 在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各 列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行 解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行 基，我们将构造初始可行基，具体做法在以后详细讲述。,41,4 线性规划应用举例分析,例1某昼夜服务的公交线路每天各时间段内所需司机 和乘务人员
21、数如下： 设司机和乘务人员分别在各时间段一开始时上班，并 连续工作八小时，问该公交线路怎样安排司机和乘务人员， 既能满足工作需要，又配备最少司机和乘务人员?,42,解：设 xi 表示第i班次时开始上班的司机和乘务人员数, 这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,43,例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售
22、货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,44,解：设 xi ( i = 1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 +
23、x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0,45,例3某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表,设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x
24、3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0,46,第三章 整数规划,1 整数规划的数学模型及其解的特点 2 整数规划的应用 3 指派问题,47,1 整数规划的数学模型及其解的特点,例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： 195 x1 + 273 x2 1365 4 x1
25、 + 40 x2 140 x1 4 x1，x2 0 为整数。,48,如果去掉最后一个约束，就是一个线性规划问题。利用图解法，如果 去掉最后一个约束，就是一个线性规划问题。“解”得线性规划的最优 解为x1=2.44, x2=3.26,目标函数值为14.66。由图表可看出，整数规划 的最优解为x1=4, x2=2,目标函数值为14。 一般求整数解的线性规划问题，不可用四舍五入法或去尾法对线性 规划的非整数解加以处理来解决整数规划。在整数规划中，如果所有的 变量都为非负整数，则称为纯整数规划问题； 如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规 划中，如果变量的取值只限于0和1，这样的
26、变量我们称之为0-1变量。在 纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称 之为0-1规划。,49,性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。,50,2 整数规划的应用,一、投资场所的选择 例1、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点
27、至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,51,解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x
28、2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 且xj 为0-1变量，i = 1,2,3,10,52,有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由 于每人特长不同，完成各项任务的效率等情况也不同。现假设必须 指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使 得完成 n 项任务的总的效率最高，这就是指派问题。 例1有四个工人，要分别指派他们完成四项不同的工作，每 人做各项工作所消耗的时间如下表所示，问
29、应如何指派工作，才能 使总的消耗时间为最少。,3 指派问题,53,解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33 +19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x
30、33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4,54,1 基本概念 2 一维搜索 3 无约束极值问题 4 约束极值问题,第四章 非线性规划,55,1 基本概念,非线性规划问题 非线性规划方法概述,56,例1 曲线的最优拟合问题,1 基本概念,57,数学规划,58,向量化表示,59,最优解和极小点,60,非线性规划方法概述,61,非线性规划基本迭代格式,62,凸函数和凸规划,凸函数及其性质 凸规划及其性质,63,凸函数及其性质,64,65,凸规划及其性质,66,