运筹学重点难点串讲课件.ppt

教学日历 课程名称： 运筹学 主讲教师： 王平安 年级： 专业： 建筑科技大学 教学计划学时： 80 其中课内72学时 实验8学时 第一章 绪 论 运筹学概况简述 运筹学（Operations Research ） 直译为“运作研究” 运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。 运筹学解决问题的过程 1）提出问题：认清问题 2）寻求可行方案：建模、求解 3）确定评估目标及方案的标准或方法、途径 4）评估各个方案：解的检验、灵敏性分析等 2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。做题要有信心，要独立完成，不要怕出错。 以下各章节的重点、难点及注意事项 第二章 线性规划建模及单纯形法 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 2、线性规划的图解法 线性规划的图解法(解的几何表示) 对于只有两个变量的线性规划问题，可 以在二维直角坐标平面上作图表示线性 规划问题的有关概念，并求解。图解法 求解线性规划问题的步骤如下： (1）分别取决策变量x1 ，x2 为坐标向 量建立直角坐标系； 2、线性规划的图解法 （2）对每个约束（包括非负约束） 条件，先取其等式在坐标系中作出直 线，通过判断确定不等式所决定的半 平面。各约束半平面交出来的区域 (存在或不存在），若存在，其中的 点表示的解称为此线性规划的可行解。 这些符合约束限制的点集合，称为可 行集或可行域。进行（3）；否则该 线性规划问题无可行解。 2、线性规划的图解法 （3）任意给定目标函数一个值作一 条目标函数的等值线，并确定该等值 线平移后值增加的方向，平移此目标 函数的等值线，使其达到既与可行域 有交点又不可能使值再增加的位置 (有时交于无穷远处，此时称无有限 最优解）。若有交点时，此目标函数 等值线与可行域的交点即最优解（一 个或多个），此目标函数的值即最优 值。 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1、可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2、可行域为封闭的无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3、可行域为空集 (f)没有可行解，原问题无最优解 可行解、可行解集（可行域） 最优解、最优值 基、基变量、非基变量 基本解、基本可行解 可行基、最优基 一般情况的处理及注意事项的强调： 主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。 考虑一般问题： bi 0 i = 1 , … , m Max z = c1x1 + c2x2 + … + cnxn s.t. a11x1+a12x2 +…+a1nxn = b1 a21x1+a22x2 +…+a2nxn = b2 …… …… am1x1+am2x2+…+amnxn = bm x1 ，x2 ，… ，xn ≥ 0 大M法： 引入人工变量 xn+i ≥ 0 （i = 1 , … , m）及充分大正数 M 。得到： 显然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解。 对应的基是单位矩阵。 结论：若得到的最优解满足 xn+i = 0 i = 1 , … , m 则是原问题的最优解；否则，原问题无可行解。 两阶段法： 引入人