运筹学复习提纲

南京工程学院运筹学复习提纲绪论一、 运筹学的基本特征（3个）⑴系统整体的观念⑵多学科的综合⑶模型方法的运用，尤其是数学模型的应用二、 运筹学的工作步骤（6步）⑴提出与形成问题⑵建立模型⑶求解⑷解的检验⑸解的控制⑹解的实施线性规划部分一、 最优化问题、数学规划、线性规划之间的关系二、 将一般LP转化为SLP。注：先满足x>0,b>0，再看目标与约束三、 线性规划单纯形法的理论基础和技术路线⑴凸集、顶点、（凸集的顶点）、凸组合⑵基本定理：1若LP存在可行解，则可行域为凸集LP的基可行解对应可行域的顶点LP有最优解，一定存在最优基解（最优解可在某顶点找到）⑶技术路线：从某初始基可行解开始、判别是否最优。否则转到相邻顶点（基可行解）。如此往复，直至找到最优解。四、 LP可能出现的四种求解结果的判别条件I"⑴无界解判别（Max问题）：非基变量的检验数5注0,kG人且4= <0.aLmk」⑵无穷多最优（Max问题）：非基变量的检验数5<0,且5女=0,kgR。⑶唯一最优解（Max问题）：非基变量的检验数5<0且七<0,jgR.且基解不退化。（注：基解退化时，非基变量检验数不满足非正，该解也可能是最优的，这时该解对应另一个基是最优基可行解）。⑷无可行解：当大M法中构造的LPM或二阶段法中构造的LP0问题的最优解中人工变量不全为零，则原问题无可行解五、计算题图解法（略）单纯形法（含大M法）对偶单纯形法（仅用于b参数变化时的灵敏度分析）单纯形法与对偶单纯形法的区别在于单纯形法是在满足基解可行性的条件下通过迭代逐步满足最优性;对偶单纯形法是在基解满足对偶可行性的条件下通过迭代逐步满足可行性。列对偶问题原问题（或对偶问题）对偶问题（或原问题）目标函数maxz目标函数minw(n个n个约变>=0>=［束量j<=0<=［条［无约束=J件，，f A~\约m个m个束<=>=0变条>=<=0量件［=无约束^约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项由互松驰定理求对偶问题的最优解（影子价格）灵敏度分析（b,c参数变化……）六、人工变量与附加变量的区别。七、对偶问题的五个基本性质与推论⑴对称性：对偶问题的对偶问题哦是原问题⑵弱对偶性：若x*、y*分别为原问题和对偶问题的最优解，则cx*<=y*b⑶弱对偶性的推论：无界性（LP无界解，则DLP无可行）LP和SLP分别给对方设定了界限若LP和SLP都有可行解，则存在最优解⑷最优性：若x*、y*分别为原问题和对偶问题的可行解，当cx*=y*b时，x*,y*为最优解⑸强对偶性（对偶理论）：若LP和SLP都存在可行解，则两者都存在最优解，且目标函数值相等⑸互松驰性：若x*、y*分别为原问题和对偶问题的最优解，则某一约束条件为严格不等式，则对偶变量为0；某一变量非0，则对偶问题的约束式为等式约束八、影子价格的概念以及影子价格与市场价格的联系与区别（1） 影子价格是特定企业在现有的最优生产方式下，该资源单位增量对企业利润的增加量;而市场价格是由市场供需关系决定的；（2） 影子价格随生产方式和企业的不同而不同，市场价格在短期内相对稳定。（3） 影子价格是一种机会成本。当影子价格大于市场价格应考虑购入，反之则出售。长期看，资源的影子价格与市场价格会趋向一致。运输问题部分一、 将供销不匹配的运输问题转化为供销平衡的模型。二、 供销平衡的运输问题模型的特点（有m+n-1个基变量；一定有最优解）三、 表上作业法的技术路线通过划线法（如最小元素法、伏格尔法）找初始可行解；运用闭回路法或位势法（对偶变量法）判别是否最优；若不是最优，则运用闭回路调整法改善运输方案（转换基），如此往复直至最优。四、 掌握最小元素法、Vogel法并能运用位势法进行最优性检验。五、 需求可变的运输问题建模注：运输问题首先一定是计算总供给和总需求，判断供需关系的类型;若不平衡，少的一方增加虚拟的节点转化为供销平衡的模型。图论部分一、 基本概念简单图、图的次序列、简单链、初等链、树、最小支撑树（最小生成树）、截集、截量；生成树存在的条件，最小生成树的唯一性；二、 基本定理定理1所有点的次之和为边数的两倍。定理2图中奇点的个数是偶数最小截量最大流定理三、 计算题1、 最短路问题；2、 最大流问题决策论部分一、 了解决策过程与决策模型构成的要素，决策的分类及主要方法；二、 掌握不确定性决策模型的五个决策准则尤其是掌握后悔准则；三、 掌握风险型决策模型的最大期望收益准则和最大期望效用准则及其应用;最大期望效用准则的主要步骤四、 阿莱斯悖论有两个投资机会A与B：A会稳赢3000元；B会以80%概率获4000元，20%概率得零；大多数人会选A。这说明〃(3000)>U(4000)x0.8；再考虑投资机会C与D,C会以20%的概率获4000元，80%的概率得零，D会以25%的概率得3000元，75%的概率得零，这时，上述在A与B中偏好A的大多数人又会选C,这又说明U(3000)x0.25vU(4000)x0.2nU(3000)vU(4000)x0.8:在期望效用理论体系下，会产生无法解释的矛盾。五、 了解前景理论的主要内容；(3个基本内容和2个推论)⑴三个基本定理：大多数人面对收益的的时候是风险规避的大多数人面对损失的的时候是风险偏好的获得和损失时相对参照点而言的⑵两个推论：如果改变人们在评价是我时的参照点，可以改变人们的风险偏好人们对损失比对获得更敏感，即对风险的规避程度大于对相同收益的追求程度对策论部分一、基本概念1、纳什均衡：是这样的一个策略的组合，在其中给定其他局中人策略不变的情况下，任何局中人都不会从改变自己的策略中获益2对策模型构成的三要素①局中人、②策略集、③赢得函数(支付函数)3、了解对策模型的分类和基本研究方法⑴通常的分类方式有：根据局中人的个数，分为二人对策和多人对策根据各局中人的赢得函数的代数和是否为零，分为零和对策和非零和对策根据各局中人之间时候允许合作，分为合作对策和非合作对策根据局中人策略集中的策略个数，分为有限对策和无限对策、了解博弈论在企业管理中的作用。计算题线性规划建模（最优生产计划、人员配备、指派问题）单纯形法（含大M法）互松弛（影子价格）/灵敏度分析（参数b，c变化）需求可变的运输问题/