运筹学讲稿(2007年6月)1-4章.ppt

教学日历 课程名称： 运筹学 主讲教师： 王平安 年级： 专业： 建筑科技大学 教学计划学时： 80 其中课内72学时 实验8学时 第一章 绪 论 运筹学概况简述 运筹学（Operations Research ） 直译为“运作研究” 运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。 运筹学解决问题的过程 1）提出问题：认清问题 2）寻求可行方案：建模、求解 3）确定评估目标及方案的标准或方法、途径 4）评估各个方案：解的检验、灵敏性分析等 2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。做题要有信心，要独立完成，不要怕出错。 以下各章节的重点、难点及注意事项 第二章 线性规划建模及单纯形法 1、线性规划的概念 例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 1、线性规划的概念 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3 x2 ≤ 75 ；另外，产品数不可能为负，即 x1 ，x2 ≥ 0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数Z为相应的生产计划可以获得的总利润：Z = 1500 x1 + 2500 x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型： 1、线性规划的概念 目标函数 Max Z =1500x1+2500x2? 约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1,x2≥0? 1、线性规划的概念 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数Z达到最大的x1，x2 的取值。 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 2、线性规划的图解法 线性规划的图解法(解的几何表示) 对于只有两个变量的线性规划问题，可 以在二维直角坐标平面上作图表示线性 规划问题的有关概念，并求解。图解法 求解线性规划问题的步骤如下： (1）分别取决策变量x1 ，x2 为坐标向 量建立直角坐标系； 2、线性规划的图解法 （2）对每个约束（包括非负约束） 条件，先取其等式在坐标系中作出直 线，通过判断确定不等式所决定的半 平面。各约束半平面交出来的区域 (存在或不存在），若存在，其中的 点表示的解称为此线性规划的可行解。 这些符合约束限制的点集合，称为可 行集或可行域。进行（3）；否则该 线性规划问题无可行解。 2、线性规划的图解法 （3）任意给定目标函数一个值作一 条目标函数的等值线，并确定该等值 线平移后值增加的方向，平移此目标 函数的等值线，使其达到既与可行域 有交点又不可能使值再增加的位置 (有时交于无穷远处，此时称无有限 最优解）。若有交点时，此目标函数 等值线与可行域的交点即最优解（一 个或多个），此目标函数的值即最优 值。 2、线性规划的图解法 例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 2、线性规划的图解法 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。 解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据前面分析，可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2 ≤ 65 (A) 2x1+x2 ≤ 40 (B) 3 x2 ≤ 75 (C) x1 ,x2 ≥ 0 (D, E