韩伯棠教授管理运筹学第三习总复习

1、一、管理运筹学的定义运筹学（Operational Research，简称OR) ，英文直译为“运作研究”。 管理运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 中国企业管理百科全书绪论二、管理运筹学的主要分支线性规划(Linear Programming，简称LP)整数规划(Integral Programming，简称IP)目标规划(Objective Programming，简称OP)动态规划(Dynamic Programming，简称DP)图与网络(Graph and Network)三、管

2、理运筹学的工作步骤 提出问题、分析问题 建立模型 求解 解的检验、控制、实施四、运筹学方法的特点1. 最优化方法 2. 定量的方法 线性规划(LP)一、问题的提出1.生产计划安排问题： 合理利用人力、物力、财力等，在资源有限的约束条件下,寻求使得获利最大的最优生产计划方案。2.人力资源分配的问题： 在满足工作的需要的条件下，寻求使用最少的劳动力的最优分配方案。3.套裁下料问题： 在保证正常生产，完成生产任务的条件下，寻求使用原料最省的最优下料方案。4.投资问题：在投资额限制的条件下，从多个投资项目中选取使得投资回报最大的最优投资方案。5.运输问题：寻求使得总运费最小的最优调运方案。二、建模1.

3、一般步骤:分析问题，设出决策变量 根据所提问题列出目标函数根据已知条件列出所有约束条件2.LP数学模型的一般形式矩阵形式：假设有n个决策变量，m个约束条件。目标函数：Max （Min） z = CX约束条件： AX （ =, ）b s.t. X 0其中，C=(c1 , c2 , , cn )(价值向量) X= (x1 , x2 , , xn )T(决策变量向量) b=(b1 , b2 , , bm )T (限定向量) a11 a12 a1n a21 a22 a2n (约束条件系数矩阵) Am×n = am1 am2 amn 3.LP数学模型的特点（1）由目标函数和约束条件构成；（2）

4、目标函数只有两种情况：求极小或求极大。（3）双线性 目标函数是关于决策变量的线性函数; 所有约束条件是关于决策变量的线性函数。三、求解1.方法一：图解法（1）适用条件 有且仅有两个决策变量X1，X2。（2）基本概念 可行解；可行域；最优解（3）基本思路：先求出可行解（即找出可行域），再在可行解的基础上（即在可行域内）求出最优解。（4） 基本步骤 作图找出可行域 作出目标函数等值线，判断其平移的方向平移目标函数等值线，在可行域内找出最优点，计算最优解。（5）图解法解的情况唯一最优解 无穷多最优解 无可行解 无界解注意：能够区分无可行解和无界解的情况。（6）图解法的灵敏度分析灵敏度分析的含义；目标

5、函数中的系数 ci 的灵敏度分析；约束条件右端常数项 bj 的灵敏度分析； 对偶价格：约束条件右端常数b增加一个单位而使目标函数最优值得到改进的数量，称之为该约束条件的对偶价格。 对偶价格=z/b2.方法二：单纯型法(1)基本概念 基；基向量,非基向量；基变量,非基变量；基本解,基本可行解,基本最优解；可行基，最优基(2)重要定理及性质若LP的可行域存在，则可行域为凸多边形。若LP存在最优解，则最优解一定可在可行域凸多边形的顶点上取得。LP问题的一个基本可行解对应于可行域的一个顶点。 可行域的一个顶点 一个基本可行解 以单位矩阵Im×m做基，其基本解的特点是：所有非基变量xj =0，

6、所有基变量xi =bi（标准型中规定b 0 ），故单位矩阵可做可行基。规定:LP数学模型的标准型 : 目标函数：MaxZ = CX约束条件： AX =b s.t. X 0要求:能够将任意模型标准化。3.方法三：对偶单纯型法（1）原问题与对偶问题的数学模型 对称形式的对偶(对偶定义) 设有原问题：LP:则对偶问题为：DP: 要求：掌握二者模型之间的对应关系。非对称形式的对偶 方法：先将原问题化为对称形式(注:无需处理等式约束及自由变量)，再由对偶定义直接写出对偶问题即可。 等式约束 自由变量要求：能够根据任意模型（原问题）写出其对偶问题模型。（2）对偶规划的基本性质 对称性 弱对偶性 最优性 强

7、对偶性（3）对偶单纯型法适用条件（极大化问题）：a.初始单纯形表中，检验数行所有 j 0 ；b.初始单纯形表中，常数列中至少存在一个负值(bk<0)基本步骤： 从与单纯型法的比较中掌握此方法。4. 求解运输问题的表上作业法（1）适用条件：产销平衡的运输问题。（2）基本步骤注意：假设有m个产地，n个销地，则运输问题有m+n-1个基变量。 （3）解的情况唯一最优解；有限多最优解整数规划（IP）一、问题的提出1.投资场所的选择2.指派问题3.分布系统设计4.投资问题二、建模1.纯整数规划问题Max(min)Z=CX AX(,=)b X 0 X1, X2 ,Xn 均为整数2.混合整数规划问题Ma

8、x(min)Z=CXAX(,=)bX 0X1, X2 ,Xk 均为整数(k<n)求解方法：分枝定界法，割平面法3.0-1整数规划问题 Max(min)Z=CXAX(,=)bX =0或1求解方法：隐枚举法，匈牙利法三、模型求解 1.分枝定界法 2.求解指派问题的匈牙利法。目标规划（OP）一、问题的提出 多目标决策问题 二、建模1. 基本概念 决策变量 偏差变量 ； 绝对约束，目标约束； 优先因子，权系数2.基本步骤设出决策变量根据各个目标列出绝对约束 将绝对约束转化为目标约束和目标函数,并根据实际问题对各个目标赋予优先因子或权系数3.OP数学模型一般形式minZ=f(P,w,d+,d-)F

9、i(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: 图解法、单纯形法； 根据原问题写出对偶问题； 运输