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