陕西理工学院运筹学总复习课件

管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件1管理运筹学I总复习 总学时：总学时：48 学分：学分：3管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件2绪论一、管理运筹学的定义一、管理运筹学的定义 运筹学（运筹学（Operational ResearchOperational Research，简称，简称OR) OR) ，英文直译为，英文直译为“运作研究运作研究”。 管理运筹学是应用分析、试验、量化的管理运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。有依据的最优方案，以实现最有效的管理。 中国企业管理百科全书中国企业管理百科全书管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件3绪论二、管理运筹学二、管理运筹学的主要分支的主要分支 线性规划线性规划(Linear Programming，简称，简称LP) 整数规划整数规划(Integral Programming，简称，简称IP) 目标规划目标规划(Objective Programming，简称，简称OP) 动态规划动态规划(Dynamic Programming，简称，简称DP) 图与网络图与网络(Graph and Network)管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件4绪论三、管理运筹学的工作步骤三、管理运筹学的工作步骤 提出问题、分析问题提出问题、分析问题 建立模型建立模型 求解求解 解的检验、控制、实施解的检验、控制、实施管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件5绪论四、运筹学方法的特点四、运筹学方法的特点1. 最优化方法最优化方法 2. 定量的方法定量的方法 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件6 线性规划(LP)一、问题的提出一、问题的提出1.生产计划安排问题：生产计划安排问题： 合理利用人力、物力、财力等，在资源有限的约束条件下,寻求使得获利最大的最优生产计划方案。 2.人力资源分配的问题：人力资源分配的问题： 在满足工作的需要的条件下，寻求使用最少的劳动力的最优分配方案。3.3.套裁下料问题：套裁下料问题： 在保证正常生产，完成生产任务的条件下，寻求使用原料最省的最优下料方案。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件7 线性规划(LP)4.4.投资问题：投资问题：在投资额限制的条件下，从多个投资项目中选取使得投资回报最大的最优投资方案。5.5.运输问题：运输问题：寻求使得总运费最小的最优调运方案。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件8线性规划(LP)二、建模二、建模1.一般步骤一般步骤:分析问题，设出分析问题，设出决策变量决策变量 根据所提问题列出根据所提问题列出目标函数目标函数根据已知条件列出所有根据已知条件列出所有约束条件约束条件管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件9线性规划(LP)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 (约束条件系数矩阵约束条件系数矩阵) Amn = am1 am2 amn 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件10线性规划(LP)3.LP数学模型的特点数学模型的特点（1）由目标函数和约束条件构成；）由目标函数和约束条件构成；（2）目标函数只有两种情况：求极小或）目标函数只有两种情况：求极小或求极大。求极大。（3）双线性）双线性目标函数是关于决策变量的目标函数是关于决策变量的线性函数线性函数;所有约束条件是关于决策变量的所有约束条件是关于决策变量的线性线性函数。函数。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件11线性规划(LP)三、模型求解三、模型求解1.方法一：图解法方法一：图解法 （1）适用条件）适用条件 有且仅有两个决策变量有且仅有两个决策变量X1，X2。 （2）基本概念）基本概念 可行解；可行域；最优解可行解；可行域；最优解 （3）基本思路）基本思路 先求出可行解（即找出可行域），再在先求出可行解（即找出可行域），再在可行解的基础上（即在可行域内）求出最优可行解的基础上（即在可行域内）求出最优解。解。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件12线性规划(LP)（4） 基本步骤基本步骤作图找出可行域作图找出可行域作出目标函数等值线，判断其平移的方向作出目标函数等值线，判断其平移的方向平移目标函数等值线，平移目标函数等值线，在可行域内找出最优点，计算最优解。在可行域内找出最优点，计算最优解。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件13线性规划(LP)（5）图解法解的情况）图解法解的情况唯一最优解唯一最优解无穷多最优解无穷多最优解无可行解无可行解无界解无界解注意：能够区分无可行解和无界解的情况。注意：能够区分无可行解和无界解的情况。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件14线性规划(LP)2.方法二：单纯型法方法二：单纯型法(1)基本概念基本概念 基；基；基向量基向量, ,非基向量；基变量非基向量；基变量, ,非基变量；非基变量；基本解基本解,基本可行解基本可行解,基本最优解；可行基，基本最优解；可行基，最优基最优基(2)重要定理及性质重要定理及性质若若LP的可行域存在，则可行域为凸多边形。的可行域存在，则可行域为凸多边形。若若LP存在最优解，则最优解一定可在可行存在最优解，则最优解一定可在可行域凸多边形的顶点上取得。域凸多边形的顶点上取得。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件15线性规划(LP)LP问题的一个基本可行解对应于可行域的问题的一个基本可行解对应于可行域的一个顶点。一个顶点。 可行域的一个顶点可行域的一个顶点 一个基本可行解一个基本可行解 以单位矩阵以单位矩阵Imm做基，其基本解的特点是：做基，其基本解的特点是：所有非基变量所有非基变量x xj j =0，所有基变量，所有基变量x xi i =bi i（标（标准型中规定准型中规定b 0 ），故单位矩阵可做可行），故单位矩阵可做可行基。基。一一对应一一对应管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件16线性规划(LP)(3)基本思路基本思路寻找初始基本可行解寻找初始基本可行解方法：标准化并构造初始可方法：标准化并构造初始可行基行基I Im mm m最优性检验最优性检验stopstop是是否否迭代，寻找另一迭代，寻找另一组基本可行解组基本可行解管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件17线性规划(LP)(4)表上作业法基本步骤表上作业法基本步骤 标准化并构造初始可行基，列出初始单纯形表计算检验数所有基变换无界解STOPSTOPSTOP无可行解无穷多最优解唯一最优解是否存在非零人工变量是否存在非基变量检验数是否是否存在非基变量检验数 ，但Pk0且人工变量=0是是是否否否管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件18线性规划(LP)规定规定:LP数学模型的标准型数学模型的标准型 : 目标函数：目标函数：MaxZ = CX约束条件：约束条件： AX =b s.t. X 0要求要求: :能够将任意模型标准化。能够将任意模型标准化。( (考点考点) )管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件19线性规划(LP)(5)解的情况及判别定理解的情况及判别定理(以极大化问题为例以极大化问题为例)判别定理判别定理解的情况解的情况所有所有 0,且所有人工变量且所有人工变量=0唯一最优解唯一最优解对于某个基本最优解对于某个基本最优解,所有所有 0,又存在某个又存在某个非基变量检验数非基变量检验数 =0 无穷多最优解无穷多最优解所有所有 0,但人工变量但人工变量0无可行解无可行解在某次迭代表中在某次迭代表中,有一个非基变量的检验数有一个非基变量的检验数 0,但但Pk列中没有正元素列中没有正元素(aik0)无界解无界解jjjk k 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件20线性规划(LP)四、对偶规划四、对偶规划（1）原问题与对偶问题的数学模型）原问题与对偶问题的数学模型 对称形式的对偶对称形式的对偶(对偶定义对偶定义) 设有原问题：设有原问题：LP:则对偶问题为：则对偶问题为：DP: 要求：掌握二者模型之间的对应关系。要求：掌握二者模型之间的对应关系。=0,maxXbAXCXz=0.minYcYAYbfTTT管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件21线性规划线性规划(LP)原问题原问题LP对偶问题对偶问题DP决策变量个数决策变量个数nm约束条件个数约束条件个数mn价值向量价值向量CbT限定向量限定向量bCT约束条件系数矩约束条件系数矩阵阵AAT目标函数目标函数maxmin约束条件约束条件管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件22线性规划(LP)非对称形式的对偶非对称形式的对偶 方法：先将原问题化为对称形式方法：先将原问题化为对称形式(注注:无需无需处理等式约束及自由变量处理等式约束及自由变量)，再由对偶定义，再由对偶定义直接写出对偶问题即可。直接写出对偶问题即可。 等式约束等式约束 自由变量自由变量要求：要求：能够根据任意模型（原问题）写出其对能够根据任意模型（原问题）写出其对偶问题模型。偶问题模型。（考点）（考点）对应管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件23线性规划(LP)（2）对偶规划的基本性质对偶规划的基本性质 对称性对称性 互补松弛条件互补松弛条件 最优性最优性 强对偶性强对偶性 要求：要求：能够根据互补松弛条件计算原问题能够根据互补松弛条件计算原问题的最优解。的最优解。（考点）（考点） 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件24整数规划（IP）一、问题的提出一、问题的提出1.投资场所的选择投资场所的选择2.2.指派问题指派问题3.分布系统设计分布系统设计4.4.投资问题投资问题管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件25整数规划（IP）二、建模二、建模 IP问题的类型问题的类型 ：1.纯整数规划问题纯整数规划问题Max(min)Z=CX AX(,=)b X 0 X1, X2 ,Xn 均为整数均为整数2.混合整数规划问题混合整数规划问题Max(min)Z=CXAX(,=)bX 0X1, X2 ,Xk 均为整数均为整数(kn)求解方法：分枝定界法，割平面法求解方法：分枝定界法，割平面法管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件26整数规划（IP） 3.0-1整数规划问题整数规划问题 Max(min)Z=CXAX(,=)bX =0或或1求解方法：隐枚举法，匈牙利法求解方法：隐枚举法，匈牙利法管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件27整数规划（IP） 三、模型求解三、模型求解 1.分枝定界法分枝定界法 2.求解指派问题的匈牙利法求解指派问题的匈牙利法 。 3.求解求解0-1IP问题的隐枚举法。问题的隐枚举法。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件28目标规划（OP）一、问题的提出一、问题的提出 多目标决策问题多目标决策问题 二、建模二、建模1. 基本概念基本概念 决策变量，决策变量， 偏差变量偏差变量 ；绝对约束，目；绝对约束，目标约束标约束 ；目标函数；目标函数 ；优先因子，权系；优先因子，权系数数 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件29目标规划（OP）2.基本步骤基本步骤设出决策变量设出决策变量根据各个目标列出绝对约束根据各个目标列出绝对约束 将绝对约束转化为目标约束和目标函数将绝对约束转化为目标约束和目标函数,并根据实际问题对各个目标赋予优先因子或权系数并根据实际问题对各个目标赋予优先因子或权系数管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件30目标规划（OP）3.OP数学模型一般形式数学模型一般形式minZ=f(P,w,d+,d-)Fi(x)+ - =biX, d+,d-0注：注：OP数学模型中可能存在绝对约束。数学模型中可能存在绝对约束。idid管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件31目标规划（OP）三、模型求解三、模型求解1.图解法图解法（1）适用条件）适用条件 有且仅有两个决策变量。有且仅有两个决策变量。（2）基本步骤）基本步骤注意：注意：准确判断各偏差变量增加的方向。准确判断各偏差变量增加的方向。 从优先权最高的目标开始求解，清楚从优先权最高的目标开始求解，清楚写出每一优先级目标的满意解。写出每一优先级目标的满意解。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件32动态规划(DP)一、问题的提出一、问题的提出多阶段决策问题：多阶段决策问题： 1.最短路问题最短路问题 2.资源分配问题资源分配问题 3.背包问题背包问题 4.生产与存贮问题生产与存贮问题 5.系统可靠性问题系统可靠性问题管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件33动态规划(DP)二、建模二、建模注意：动态规划没有统一确定的数学模型。注意：动态规划没有统一确定的数学模型。1.基本概念基本概念 阶段；状态；决策；策略；指标函数（包阶段；状态；决策；策略；指标函数（包括阶段指标函数和最优指标函数）；状态转括阶段指标函数和最优指标函数）；状态转移方程；基本方程（递推公式）移方程；基本方程（递推公式）考点考点: 最短路问题动态规划模型的建立（包括最短路问题动态规划模型的建立（包括顺推法与逆推法）。顺推法与逆推法）。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件34动态规划(DP)2.基本步骤基本步骤 分析问题，划分阶段分析问题，划分阶段 确定阶段变量、决策变确定阶段变量、决策变量和状态变量、写出状态量和状态变量、写出状态转移方程、最优指标函数转移方程、最优指标函数及基本方程。及基本方程。 依据最优化原理，运用逆序算法，依据最优化原理，运用逆序算法，逆向寻优，列表计算每个阶段的最优逆向寻优，列表计算每个阶段的最优指标函数值及决策变量最优值，最后指标函数值及决策变量最优值，最后逆向查表求得整个过程上的最优策略。逆向查表求得整个过程上的最优策略。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件35动态规划(DP)三、模型求解三、模型求解求解方法：逆序算法（基于最优化原理）求解方法：逆序算法（基于最优化原理）1.求解最短路问题的逆推法；求解最短路问题的逆推法；2.求解最短路问题的顺推法。求解最短路问题的顺推法。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件36图与网络一、基本概念一、基本概念1.图图;无向图无向图;有向图有向图; 简单图简单图;多重图多重图; 连通图连通图;顶点的次顶点的次2. 网络网络3. 树树;生成子图生成子图;生成树生成树; 最小生成树最小生成树4. 弧容量；可行流；饱和弧、非饱和弧；前向弧容量；可行流；饱和弧、非饱和弧；前向弧、后向弧弧、后向弧；可扩充路（增广链）；可扩充路（增广链）管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件37图与网络二、问题的提出二、问题的提出 1.最短路问题最短路问题 2.最小生成树问题最小生成树问题 3.最大流问题最大流问题 4.最小费用最大流问题最小费用最大流问题管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件38图与网络三、求解方法三、求解方法 1.求解最短路问题的双标号法；求解最短路问题的双标号法； 2.求解最小生成树问题的破圈法和避圈法；求解最小生成树问题的破圈法和避圈法； 3. 求解最大流问题的线性规划法和图论解求解最大流问题的线性规划法和图论解法；法； 4.求解最小费用最大流问题的线性规划法和求解最小费用最大流问题的线性规划法和图论解法。图论解法。管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件39考试形式：闭卷考试考试形式：闭卷考试考试时间：考试时间：120分钟分钟考试题型考试题型 ：填空题，计算题，应用题：填空题，计算题，应用题 计算题、应用题考点：计算题、应用题考点：LP: 图解法、单纯形法；图解法、单纯形法； 根据原问题写出对偶问题（包括对称形根据原问题写出对偶问题（包括对称形式与非对称形式）；式与非对称形式）； 将任意模型标准化；将任意模型标准化； 互补松弛条件应用。互补松弛条件应用。 管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件40IP:求解求解0-1IP问题的隐枚举法；问题的隐枚举法； 求解指派问题的匈牙利法。求解指派问题的匈牙利法。OP：建模及求解（图解法）：建模及求解（图解法）管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件41DP: 建模及求解（逆序算法）建模及求解（逆序算法） 最短路问题：顺推法与逆推法；最短路问题：顺推法与逆推法； Graph and network: 最小生成树问题：破圈法与避圈法；最小生成树问题：破圈法与避圈法； 最短路问题：双标号法最短路问题：双标号法管管 理理 运运 筹筹 学学陕西理工学院运筹学总复习课件42注意：注意： 计算题、应用题：按步骤给分，做题应计算题、应用题：按步骤给分，做题应写清楚每一步骤计算过程和计算结果。写清楚每一步骤计算过程和计算结果。 自带尺子自带尺子