运筹学重修复习大纲.doc

复习提纲 绪论 一、运筹学的基本特征（3个） 二、运筹学的工作步骤（6步） 线性规划部分 一、最优化问题、数学规划、线性规划之间的关系 二、将一般LP转化为SLP。注：先满足 ，再看目标与约束 三、线性规划单纯形法的理论基础和技术路线 凸集、顶点、（凸集的顶点）、凸组合 基本定理：1若LP存在可行解，则可行域为凸集 2 LP的基可行解对应可行域的顶点 3 LP有最优解，一定存在最优基解（最优解可在某顶点找到） 技术路线：从某初始基可行解开始、判别是否最优。否则转到相邻顶点（基可行解）。如此往复，直至找到最优解。 四、LP可能出现的四种求解结果的判别条件 无界解判别（Max问题）：非基变量的检验数 无穷多最优（Max问题）：非基变量的检验数。 唯一最优解（Max问题）：非基变量的检验数且基解不退化。 （注：基解退化时，非基变量检验数不满足非正，该解也可能是最优的，这时该解对应另一个基是最优基可行解）。 无可行解：当大M法中构造的LPM或二阶段法中构造的LP0问题的最优解中人工变量不全为零，则原问题无可行解 五、计算题 1．线性规划的建模应用题（人员配备）以及指派问题（见下面的思考题） 2．由互松驰定理求对偶问题的最优解（影子价格） 七、人工变量与附加变量的区别。 八、对偶问题的五个基本性质与推论（每个性质的具体内容） 对称性、弱对偶性、最优性、强对偶性（对偶理论）、互松驰性 弱对偶性的推论：无界性（LP无界解，则DLP无可行） 九、影子价格的概念以及影子价格与市场价格的联系与区别 （1）影子价格是特定企业在现有的最优生产方式下，该资源单位增量对企业利润的增加量；而市场价格是由市场供需关系决定的； （2）影子价格随生产方式和企业的不同而不同，市场价格在短期内相对稳定。 （3）影子价格是一种机会成本。当影子价格大于市场价格应考虑购入，反之则出售。长期看，资源的影子价格与市场价格会趋向一致。 运输问题部分 一、将供销不匹配的运输问题转化为供销平衡的模型。 二、供销平衡的运输问题模型的特点（有m+n-1个基变量；一定有最优解） 三、表上作业法的技术路线 通过划线法（如最小元素法、伏格尔法）找初始可行解； 运用闭回路法或位势法（对偶变量法）判别是否最优； 若不是最优，则运用闭回路调整法改善运输方案（转换基），如此往复直至最优。 四、需求可变的运输问题建模 注：运输问题首先一定是计算总供给和总需求，判断供需关系的类型；若不平衡，少的一方增加虚拟的节点转化为供销平衡的模型。 图论部分 一、基本概念 简单图、简单链、初等链、树、最小支撑树（最小生成树）、截集、截量、增广链； 生成树存在的充要条件，最小生成树的唯一性； 二、基本定理 定理1所有点的次之和为边数的两倍。 定理2图中奇点的个数是偶数 最小截量最大流定理 三、计算题 1、最短路问题； 决策论部分 一、了解决策过程与决策模型构成的要素，决策的分类及主要方法； 二、掌握不确定性决策模型的五个决策准则尤其是掌握后悔准则； 三、掌握风险型决策模型的最大期望收益准则和最大期望效用准则及其应用； 最大期望效用准则的主要步骤： （1）建立决策问题的收益矩阵； （2）用对比提问法得到决策者对于各个收益的效用值,画出效用曲线。 对比一个确定方案和一个风险组合方案U(x)=p U(y)+(1-p)U(z)其中x在y,z之间。 （3）建立效用矩阵 （4）计算各行动方案的期望效用值，选择值最大的行动方案 四、阿莱斯悖论 （1）有两个投资机会Ａ与Ｂ：Ａ会稳赢3000元；Ｂ会以80％概率获4000元，20％概率得零；大多数人会选Ａ。这说明； （2）再考虑投资机会Ｃ与Ｄ，Ｃ会以20％的概率获4000元，80％的概率得零，Ｄ会以25％的概率得3000元，75％的概率得零，这时，上述在Ａ与Ｂ中偏好Ａ的大多数人又会选Ｃ，这又说明： 在期望效用理论体系下，会产生无法解释的矛盾。 五、了解前景理论的主要内容；（3个基本内容和2个推论） 对策论部分 一、基本概念 1、纳什均衡，2对策模型构成的三要素，3、了解对策模型的分类和基本研究方法； 二、了解博弈论在企业管理中的作用。 计算题 线性规划建模（人员配备） 指派问题建模 互松弛（影子价格） 需求可变的运输问题（注意首先求总供给和总需求，判断供需关系） 最短路 期望收益准则（风险型决策）/后悔准则（不确定型决策） 简答题 \运筹学的工作步骤 \线性规划基本定理 \单纯形法的技术路线 \影子价格与市场价格的关系 \最大期望效用准则 \表上作业法 \阿莱斯悖论和前景理论 \对策模型的分类和基本研究方法 思考题 1、有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使得总的消耗时间最少？只要建立模型，