运筹学复习大纲2015-06.pdf

2015年运筹学复习提纲 绪论 一、运筹学的基本特征（3个） 二、运筹学的工作步骤 （6步）提出形成问题；建立模型；求解；解的检验；解的控制；解 的实施。 线性规划部分 一、线性规划问题的标准形式SLP的3要素 （目标最大，等式约束，右边项和决策变量非负） 二、将一般LP转化为SLP。注：先满足x0,b0 ，再看目标与约束 三、线性规划单纯形法的理论基础和技术路线 基本概念：可行解、凸集、凸组合、顶点（凸集的顶点）、基、基可行解 基本定理：1）若LP存在可行解，则可行域为凸集 2）LP 的基可行解对应可行域的顶点 3）LP有最优解，一定存在最优基解（最优解可在某顶点找到） 技术路线：从某初始基可行解开始、判别是否最优。否则转到相邻顶点（基可行解）。如此 往复，直至找到最优解。 四、LP可能出现的四种求解结果的判别条件    1k   (1) 无界解判别（Max 问题）：非基变量的检验数 0,kR且P   0. k K      mk   (2) 无穷多最优（Max 问题）：非基变量的检验数 0,且至少一个 0,kRj k 。 (3) 唯一最优解（Max 问题）：非基变量的检验数 0，j R.j 且基解不退化。 其中，R为非基变量下标集。 （注：基解退化时，非基变量检验数不满足非正，该解也可能是最优的，这时该解对应另一 个基是最优基可行解）。 M (4) 无可行解：当大M法中构造的LP 或两阶段法中构造的LP 问题的最优解中人工变量0 不全为零，则原问题无可行解。 注：当LP是最小化问题时，判别条件中非基变量的检验数不等式方向与最大化问题相反。 五、计算题 1．单纯形法的计算（熟练掌握大M法和两阶段法） 2．线性规划的建模应用题（人员配备、LP在市场营销中的应用、转运问题、投资问题） 六、人工变量与附加变量的区别。（作用的不同；目标函数中系数的不同） 对偶问题理论和灵敏度分析 一、正确写出DLP LP （DLP） DLP （LP） max min 目标函数系数/右边项 右边项/目标函数系数 行约束 列约束 Ax≤b约束式 y≥0变量取值 等式约束 变量无约束 x≥0变量取值 yA≥c约束式 变量无约束