运筹学教程复习

运筹学教程复习

线性规划部分

一、最优化问题、数学规划、线性规划

二、将一般LP转化为SLP。先满足x0,b0，再看目标与约束 三、LP的可行解及可能出现的求解结果（四种）

建模失败的求解结果：无可行解或无界解。

大M法，两阶段法step1人工变量在新LP最优基解中不为零无可行解条件矛盾对偶单纯形法中bL0对应Lj0j1n.无界解maxmin(漏条件)一个有可行解有最优解无穷多1k无界解判别（Max问题）：k0,kR且PK0. mk无穷多最优（Max问题）：0,且k0,kR。

唯一最优解（Max问题）：0且j0，jR.且基解不退化。

（注：基解退化时，非基变量检验数不满足非正，该解也可能是最优的，这时该解对应另一

个基是最优基可行解）。

四、LP 可行解、基、基解、基可行解、最优解的概念与关系

基AP中mRank(A)个线性无关列向量组成的方阵（满秩子矩阵） 1,Pn五、线性规划单纯形法的理论基础和技术路线 凸集、顶点、（凸集的顶点）、凸组合

基本定理：1若LP存在可行解，则可行域为凸集

2 LP的基可行解对应可行域的顶点

3 LP有最优解，一定存在最优基解（最优解可在某顶点找到）

技术路线：从某初始基可行解开始、判别是否最优。否则转到相邻顶点（转换基）直至最优 最优性判别、无穷多解、无界解、唯一最优解的判别 最小化问题的最优性如何判别？0

ZCBXBCNXNCNCBB1NXNCBB1bZ0NXNBXBNXNbXBBbBNXN六、计算题

11

1．图解法

先xK入，再xL出2．单纯形法

miniik0ikjminLj0jRLj

先xL出，再xK入3．对偶单纯形法

4．求LP所有基解、可行基解 5．列对偶问题

6．由互松驰定理求对偶问题的最优解（影子价格） 7．灵敏度分析（ b , c变化……） 七、人工变量与附加变量的区别。

八、退化（基变量中有零分量）及Bland法则避免死循环 九、对偶问题的五个基本性质与推论 对称、弱对偶、最优性判别、强对偶（对偶理论）、、互松驰性和弱对偶性的推论：无界性（DLP无可行）

LP最优x DLP也有最优且cxyb

十、影子价格的概念以及影子价格与市场价格的联系

yi是该企业在现有生产工艺、生产方式最优方案下的资源i的估价

z资源i在最优利用条件下的对利润目标函数的边际贡献 ybii单位增加对目标值产生的增量有调节市场价格的作用

运输问题部分

将供销不匹配的运输问题划为供销平衡的模型。 供销平衡的模型的特点（一定有最优解） 表上作业法

掌握最小元素法、Vogel法并能运用位势法进行最优性检验。 需求可变的运输问题建模

图论部分

基本概念：简单图、图的次序列、简单链、初等链、树、最小支撑树、截集、截量 掌握求解最小生成树问题，最短路问题，最大流问题

决策论部分

了解决策过程与决策模型构成的要素，决策的分类及主要方法； 掌握不确定性决策模型的五个决策准则；

掌握风险型决策模型的最大期望收益和最大期望效用理论及其应用； 层次分析法的主要思想

层次分析法是美国Thomas Saaty于20世纪70年代初提出的一种定性与定量相结合的多目标决策分析方法，可以用来分析相互关联, 相互制约的复杂决策问题.

通过分析复杂系统的有关要素及其相互关系，简化为有序的递阶层次结构，使这些要素归并为不同的层次，形成一个多层次的分析结构模型. 最终把系统分析归结为最低层(供决策的方案,措施等)相对于最高层(总目标)的相对重要性权值的确定问题。 主要包括四个步骤： 建立层次结构模型 构造判断矩阵

层次单排序及一致性检验 层次总排序以及一致性检验

对策论部分

理解对策问题的基本概念：纳什均衡，对策模型构成的三要素，了解对策模型的分类和基本研究方法；了解博弈论在企业管理中的作用。

计算题

线性规划图解法或大M法，建模 互松弛（影子价格），灵敏度分析 运筹问题需求可变表上作业法 最大流、最短路

期望收益准则和后悔准则 简答题

线性规划基本定理 \\单纯形法

\\对偶理论\\对偶单纯形法\\影子价格 \\最大期望效用 \\表上作业法 \\层次分析法 \\纳什均衡