运筹写总复习.pdf

运筹学 总 复 习 1 第1章 线性规划与单纯形法 第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例 第1章 线性规划与单纯形法 第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例 单纯形法求解线性规划 （1）确定初始基可行解 1)直接观察 2)加松弛变量 3)加非负的人工变量（大M法；两阶段法） （2） 最优性检验 （3）基变换 （4）迭代运算 （2） 最优性检验 (i). 最优解的判别定理 对一切j=m+ 1, …, n ，有σ ≤0 j (ii).无穷多最优解判别定理 对一切j =m+ 1, …, n ，有σ ≤0 ，又存 j 在某个非基变量的检验数σm+k=0 (iii)．无界解判别定理 有一个σm+k ＞0，并且对i=1, 2, … , m ，有 ai,mk  0 成立。 m  c c a , j m 1, m  2, , n j j i ij i 1 （3）基变换 若初始基可行解x(0) 不是最优解或不能判别其无解时，需要找一个 新的基可行解。 一个非基变量换入成为基变量。一个基变量换出成为非基变量。 对目标函数求 Max 的线性规划 问题，用单纯形 法计算步骤的框 图如右图。 第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 第2节 改进单纯形法 第3节 对偶问题的提出 第4节 线性规划的对偶理论 第5节 对偶问题的经济解释——影子价格 第6节 对偶单纯形法 第7节 灵敏度分析 第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述 第2节 改进单纯形法 第3节 对偶问题的提出 第4节 线性规划的对偶理论 第5节 对偶问题的经济解释——影子价格 第6节 对偶单纯形法 第7节 灵敏度分析 原问题与对偶问题的关系 (1) 标准型原问题与对偶问题的关系（对称形式）  原问题（LP）： max z c x c x  c x 1 1 2 2 n n x   a a a 1 b      11 12 1n 1