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

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