西安建筑科技大学管理学院.ppt

运 筹 学 (Operations Research),西安建筑科技大学管理学院,运 筹 学 的 定 义,运筹学的主要特点,运筹学的工作步骤,运 筹 学 的 模 型,绪 论,运筹学的定义,运筹学(Operations Research)直译为“运作研究”。 运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。 运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开最劣的方案。,运筹学研究和解决问题的基础是最优化技术并强调系统最优 运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性 运筹学研究和解决问题的方法具有显著的系统性特征，建立模型和利用计算机求解 运筹学研究和解决问题的效果具有连续性 运筹学具用强烈的实践性和应用的广泛性,运筹学的特点,提出问题：弄清问题的目标、可能的约束、可控变量及其参数等 建立模型：将变量、参数、目标及约束关系用模型表示出来 求解：用各种手段对模型求解，解可以是最优解、次优解和满意解 解的检验：求解步骤和程序有无错误、解是否能反映实际 解的控制：根据要求可作改变 解的实施：主要是应用过程中需考虑的问题,运筹学的工作步骤,模型的 基本形式,形象模型,模拟模型,符号或数学模型,运筹学的模型,直接分析法,类比分析法,数据分析法,试验分析法,想定（构思）法,机理清楚,机理不清楚,方法和思路 构建模型的,运筹学的模型,模型的一般形式,目标评价准则：V = f （ xi , yj , k ）,约 束 条 件： g （xi , yj ,k ） 0,其中： xi 为可控变量； yj 为已知参数； k 为随机因素,运筹学的模型,或：max (或min ) Z = f ( x1 , x2 , . . . ,xn ),其中：xj ( i = 1.2n )为决策变量 Z 为目标函数 gi ( x1 . x2 . . . . . .xn ) 0 和 hj (x1 . x2 . . . . . .xn ) = 0 为约束条件,运筹学的模型,线性规划 整数规划 非线性规划 多目标规划 动态规划,运筹学的分支,对策论 决策论 存储论 排队论 图论,主要方面：,运筹学的应用,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。 库存管理：多种物资库存量管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。 人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。 财务会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其 他：设备维修、更新，项目选择、评价，工程优化设计与管理等。,线性规划问题及其数学模型,线性规划问题的基本原理,线性规划的图解法,线性规划的单纯形法,单纯形法的进一步讨论,线性规划模型的应用,线性规划,线性规划问题,待建模的线性规划问题需满足的条件： 所求问题的目标能表示为最大化或最小化问题 问题一定要具备有达到目标的不同方法，即必须要有选择的可能性 要达到的目标是有限制条件的 问题的目标和约束都能表示为线性式,资源利用问题,设某建筑公司的预制厂利用沙石灰三种原料 来生产两种产品和，已知该厂各种原料的现有数量，每单位产品对各种原料的消耗量及所获利润如下表所示。在这些现有的资源条件下，如何分配产品的生产，才使公司取得利润最大。,单,产,原 料,品,位,消,产,品,耗,资源利用问题,确定未知变量:设x1表示B1的生产数量, x2表示B2的生产数量 设立目标函数:要求公司取得最大利润，所以设利润函数为f(x) 则 f(x)=5 x1 +4 x2 (百元),归纳1，2，3式得出该问题为: 求满足约束函数并使f(x)=5 x1 +4 x2 最大的一组数 (x1， x2)T,建立约束函数:问题的约束资源限制为各种原料的现有数，则有关系式,投资计划问题,某企业拥有20万资金，拟在今后五年内对下列项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%； 项目B：第三年年初需要投资，到第五年末能回收本利125%，但规定最大投资不超过8万元； 项目C：第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过6万元； 项目D：五年内每年年初可购买公债或定期储蓄，于当年末归还，并加利息9%。 如何确定项目每年的投资额，可使第五年末投资本利总额最大。,投资计划问题,确定未知变量: 设xiA, xiB, xiC, xiD 分别表示第 i 年投资到项目 A, B, C, D的投资额,资金流转分析: 第一年投资 : x1A+ x1D = 20000 第一年回收 : 1.09 x1D 第二年投资 : x2A+ x2C + x2D = 1.09 x1D 第二年回收 : 1.15x1A + 1.09 x2D 第三年投资 : x3A+ x3B+ x3D = 1.15x1A + 1.09 x2D 第三年回收 : 1.15x2A + 1.09 x3D 第四年投资 : x4A+ x4D = 1.15x2A + 1.09 x3D 第四年回收 : 1.15x3A + 1.09 x4D 第五年投资 : x5D = 1.15x3A + 1.09 x4D 第五年回收 : 1.15x4A + 1.25x3B +1.4x2C + 1.09 x5D,投资计划问题,该投资问题的模型为: 求 xiA, xiB, xiC, xiD 并满足,并使 f =1.15x4A + 1.25x3B +1.4x2C + 1.09 x5D 最大,线性规划标准形式,模型转换,目标转换 求最小可以等价成求负的最大,约束转换,例 ：将下列线性规划问题化为标准形式,为无约束（无非负限制）,模型转换实例,解: 用 替换 ，且 ，,将第3个约束方程两边乘以（1）,将极小值问题反号，变为求极大值,标准形式如下：,引入变量,模型转换实例,可行解：满足约束条件、的解为可行解。所有解的集合为可行解的集或可行域。,最优解：目标函数达到最大值的可行解。, 基： B是矩阵A中mn阶非奇异子矩阵（B0），则B是一个基。,则称Pj ( j=1,2,m) 为线性规划的基向量。 与基向量对应的决策变量称为线性规划的基变量，否则为非基变量。,线性规划解的概念, 基本解：满足条件，但不满足条件的所有解，最多有Cnm个。,基本可行解：满足非负约束条件的基本解，称为基本可行解。,基本最优解：使目标函数极大的基本可行解，称为基本最优解。,非可行解,可 行 解,线性规划解的概念,基 本 解,基本可行解,定理1: 线性规划问题的可行域是凸集,凸集,凸集,不是凸集,顶 点,定理2: 最优解一定是在凸集的某一顶点实现（顶点数目不超过Cnm个）,线性规划解的基本定理,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6, 最 优 解：x1 = 4 x2 = 2 线性规划有唯一最优解，Z = 14,x2,x1,(4 2),线性规划的图解法,例 1, 线性规划有无穷多最优解,例 2,线性规划的图解法,线性规划的图解法,例 3, 线性规划有无界解,线性规划的图解法,例 4, 线性规划无可行解,线性规划的图解法,线性规划的可行域和最优解的情况 可行域为封闭的有界区域 有唯一的最优解 有无穷多个最优解 可行域为封闭的无界区域 有唯一的最优解 有无穷多个最优解 目标函数无界 可行域为空集 没有可行解，原问题无最优解,将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。,单纯形法基本思想,单纯形法,例 1,变成标准型,约束方程的系数矩阵,为基变量,为非基变量,I 为单位矩阵且线性独立,单纯形法,令：,则：, 基本可行解为（0 ,0 ,12, 8, 16 ,12） 此时，Z = 0,然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。,注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。,单纯形法,找出一个初始可行解,是否最优,转移到另一个目标函数 （找更大的基本可行解）,最优解,是,否,循 环,直到找出为止，核心是：变量迭代,结束,单纯形法,当 时， 为换入变量,确定换出变量,为换出变量,接下来有下式：,单纯形法,用高斯法，将 的系数列向量换为单位列向量，其步骤是：,结果是：,单纯形法,代入目标函数：,有正系数表明：还有潜力可挖，没有达到最大值；,有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。,此时：令 得到另一个基本可行解 （0，3，6，2，16，0）,如此循环进行，直到找到最优为止。,本例最优解为： (4，2，0，0，0，4）,单纯形法,单纯形表,单纯形表,例 2,2 3 0 0 0 0,12/2,8/2,12/4,3,x2,3,0,1,0,0,0,1/4,2,6,2,0,1,0,0,-1/2,1,0,0,1,0,-1/2,单纯形表,2 0 0 0 0 -3/4,6/2,2,16/4,单纯形表,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,单纯形表,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,单纯形表,（一）模型情况 变 量：xj0 xj0 xj 无约束 结 1、组成 约束条件： = b 目标函数： max min 果 2 、变量 xj0 令 xj= -xj ， xj0 xj0 不处理 xj 无约束 令xj = xj xj, xj0 , xj0,唯一最优 无穷最优 无界解 无可行解,单纯形法的进一步讨论,例 3,单纯形法的进一步讨论,4、目标函数：max , min 设规划模型约束条件为 ，需加入人工变量 ，而得到一个mm的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当 ，而还有人工变量（非零）时，则表示原问题无可行解。,加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。,单纯形法的进一步讨论,即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。,大M法,大M法,最优解为（4 , 1, 9, 0 , 0 , 0 , 0），Z = 2,大M法,用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错