《管理运筹学》第三版习总复习

一、管理运筹学的定义运筹学( Operational Research ，简称 OR) ，英文直译为“运作研究” 。管理运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。中国企业管理百科全书绪论二、管理运筹学I的主要分支线性规划 （Linear Programming ，简称 LP）整数规划 （Integral Programming ，简称 IP）目标规划 （Objective Programming ，简称 OP）动态规划（Dynamic Programming ，简称 DP）图与网络（Graph and Network）三、管理运筹学的工作步骤提出问题、分析问题建立模型求解解的检验、控制、实施四、运筹学方法的特点1. 最优化方法2. 定量的方法线性规划 (LP)一、问题的提出1. 生产计划安排问题：合理利用人力、物力、财力等，在资源有限的约束条件下 , 寻求使得获利最大的最优生产计划方案。2. 人力资源分配的问题：在满足工作的需要的条件下，寻求使用最少的劳动力的最优分配方案。3. 套裁下料问题：在保证正常生产，完成生产任务的条件下，寻求使用原料最省的最优下料方案。4. 投资问题： 在投资额限制的条件下， 从多个投资项目中选取使得投资回报最大的最优投资、 . 1-4_方案。5. 运输问题：寻求使得总运费最小的最优调运方案。二、建模1.一般步骤 :分析问题，设出决策变量根据所提问题列出目标函数根据已知条件列出所有约束条件 数学模型的一般形式矩阵形式：假设有 n个决策变量，m个约束条件。目标函数： Max （ Min） z = CX约束条件：AXw （ =, ） b其中， C=(c1 , c2 , cn ）（ 价值向量 ）X= (x1 , x2 ,，xn )T(决策变量向量)b=(b1 , b2 ,，bm )T (限定向量)all a12a1n约束条件系数矩阵）a21 a22a2n(Am x n =ami am2amn数学模型的特点（ 1 ）由目标函数和约束条件构成；（ 2 ）目标函数只有两种情况：求极小或求极大。（ 3 ）双线性目标函数是关于决策变量的线性函数 ;所有约束条件是关于决策变量的线性函数。三、求解1.方法一：图解法（ 1 ）适用条件有且仅有两个决策变量X1， X2。（ 2 ）基本概念可行解；可行域；最优解（ 3 ）基本思路：先求出可行解（即找出可行域） ，再在可行解的基础上（即在可行域内）求出最优解。（ 4 ） 基本步骤 作图找出可行域作出目标函数等值线，判断其平移的方向平移目标函数等值线，在可行域内找出最优点，计算最优解。（ 5 ）图解法解的情况唯一最优解无穷多最优解无可行解无界解注意：能够区分无可行解和无界解的情况。（ 6 ）图解法的灵敏度分析灵敏度分析的含义；目标函数中的系数ci 的灵敏度分析；约束条件右端常数项bj 的灵敏度分析；对偶价格：约束条件右端常数b 增加一个单位而使目标函数最优值得到改进的数量，称之为该约束条件的对偶价格。对偶价格=Az/ Ab2. 方法二：单纯型法（1） 基本概念基；基向量, 非基向量； 基变量 , 非基变量； 基本解 , 基本可行解, 基本最优解；可行基，最优基（2） 重要定理及性质若LP 的可行域存在，则可行域为凸多边形。若LP 存在最优解，则最优解一定可在可行域凸多边形的顶点上取得。（3） LP 问题的一个基本可行解对应于可行域的一个顶点。可行域的一个顶点 一个基本可行解以单位矩阵Im xm做基，其基本解的特点是：所有非基变量xj =0 ,所有基变量 xi =bi（标准型中规定 b 0 ）,故单位矩阵可做可行基。规定 :LP 数学模型的标准型目标函数： MaxZ = CX约束条件：AX =b要求 : 能够将任意模型标准化。3. 方法三：对偶单纯型法（ 1 ）原问题与对偶问题的数学模型对称形式的对偶（ 对偶定义 ） 设有原问题： LP:则对偶问题为： DP:要求：掌握二者模型之间的对应关系。非对称形式的对偶方法：先将原问题化为对称形式（注: 无需处理等式约束及自由变量） ，再由对偶定义直接写出对偶问题即可。等式约束 自由变量要求：能够根据任意模型（原问题）写出其对偶问题模型。（ 2 ）对偶规划的基本性质对称性弱对偶性最优性强对偶性（ 3 ）对偶单纯型法适用条件（极大化问题）：a.初始单纯形表中，检验数行所有 山 w 0 ；b. 初始单纯形表中，常数列中至少存在一个负值 （bk（0XI , X2 ,Xn均为整数2. 混合整数规划问题Max（min）Z=CXAX （& ,=）bX 0XI , X2 ,Xk均为整数（k (& ,=)bX =0 或 1求解方法：隐枚举法，匈牙利法三、模型求解1. 分枝定界法2. 求解指派问题的匈牙利法。目标规划(OP)一、问题的提出多目标决策问题二、建模1. 基本概念决策变量 偏差变量 ； 绝对约束，目标约束； 优先因子，权系数2. 基本步骤设出决策变量根据各个目标列出绝对约束将绝对约束转化为目标约束和目标函数,并根据实际问题对各个目标赋予优先因子或权系数数学模型一般形式minZ=f(P,w,d+,d-)Fi(x)+ - =biX, d+,d- 0注：OP数学模型中可能存在绝对约束。三、模型求解1 .图解法( 1 )适用条件有且仅有两个决策变量。( 2 )基本步骤注意：准确判断各偏差变量增加的方向。从优先权最高的目标开始求解，清楚写出每一优先级目标的满意解。动态规划 (DP)一、问题的提出多阶段决策问题： 1. 最短路问题 2. 资源分配问题3. 背包问题 4. 生产与存贮问题 5. 系统可靠性问题二、建模注意：动态规划没有统一确定的数学模型。1.基本概念阶段；状态；决策；策略；指标函数（包括阶段指标函数和最优指标函数） 方程；基本方程（递推公式）三、模型求解逆序算法（根据最优化原理）1. 求解最短路问题的逆推法； 2. 求解最短路问题的顺推法。图与网络一、基本概念1. 图 ; 无向图 ; 有向图 ; 简单图 ; 多重图 ; 连通图 ; 顶点的次2. 网络3. 树 ; 生成子图 ; 生成树 ; 最小生成树二、问题的提出 1. 最短路问题 2. 最小生成树问题3. 最大流问题4. 最小费用最大流问题三、求解方法 1. 求解最短路问题的双标号法； 2. 求解最小生成树问题的破圈法和避圈法；3. 求解最大流问题的线性规划法和图论解法；4. 求解最小费用最大流问题的线性规划法和图论解法。考试形式：闭卷考试考试时间： 120 分钟考试题型 ：填空题，判断题，计算题，应用题计算题、应用题：LP: 图解法、单纯形法；根据原问题写出对偶问题；运输问题的建模及求解（表上作业法）OP:建模及求解（图解法）DP: 建模及求解（逆序算法）最短路问题：顺推法与逆推法；资源分配问题Graph and network:最小生成树问题：破圈法与避圈法；最短路问题：双标号法、，、.一、一注意：计算题、应用题：按步骤给分，做题应写清楚每一步骤计算过程和计算结果。自带尺子