IEORCH绪论andCH线性规划及单纯形法.ppt

ORIE §0.3 运筹学的主要分支及本课程的讲授内容 运筹学是一门应用性学科，它主要是应用定性分析和定量分析相结合的方法，通过建立实际问题的数学模型，应用合适的优化算法对模型进行求解，从而解决实际问题。 运筹学的内容很多，一般认为有以下分支：线性规划、整数规划、非线性规划、动态规划、图与网络分析、网络计划、存储论、排队论、目标规划、决策分析、对策（博弈论）等。 线性规划 数 学 规 划 非线性规划 整数规划 动态规划 学 科 内 容 多目标规划 双层规划 组 合 优 化 最优计数问题 网络优化 排序问题 统筹图 随 机 优 化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要内容 讲授内容 教学内容 CH0 绪论 CH1 线性规划及单纯形法 CH2 线性规划的对偶理论与灵敏度分析 CH3 运输问题 CH4 整数规划 CH5 动态规划 CH6 图与网络方法 CH7 网络计划 CH8 目标规划 CH9 排队论 CH10 对策论 CH11 决策分析 CH12 存贮论（库存模型） § 0.4 运筹学研究的基本特征与基本方法 1、运筹学研究的基本特点： 系统的整体优化 多学科的配合 模型方法的应用 1）系统的整体观念 系统是由相互关联、相互制约、相互作用的一些部分组成的具有某种功能的有机整体。 2）多学科的综合 系统常常涉及到很多领域,运筹学研究中需吸收来自不同领域、具有不同经验和技能的专家。 3）模型方法的应用 运筹学研究的系统往往不能搬到实验室来,代替的方法是建立这个问题的模型。 ２、运筹学解决问题的步骤 1）问题的分析；2）模型的建立 3）模型的求解；4）解的检验 5）解的有效控制；6）方案的实施。 真实系统 系统分析 问题描述 模型建立与修改 模型求解与检验 结果分析与实施 数据准备 ? ? ? ? ? ? ? ? CH1 线性规划及单纯形法 §1.1 线性规划问题及其数学模型 §1.2 线性规划问题的解 §1.3 线性规划的单纯形法 §1.4 单纯形表 §1.5 单纯形法应用的几个问题 §1.6 线性规划建模举例 §1.1 线性规划问题及其数学模型 一、线性规划问题 在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源（人力、物力、财力等 ），以得到最大的效益。 生产计划问题 如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。 如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。 §1.1 线性规划问题及其数学模型 例1-1 某工厂生产A,B两种产品,若生产A产品每吨需煤9吨,木材4立方米,人力3个劳动日,生产B产品每吨需煤4吨,木材5立方米,人力10个劳动日。已知A,B两种产品每吨的价格分别为700元和1200元,并知该厂现有的资源为：煤360吨,木材200立方米,可提供人力300个劳动日,试问应生产A,B产品各多少吨,能使该厂的产值最高？ 解 先将题中有关数据列为下表 产品 原材料 A B 资源 煤 9 4 360 木材 4 5 200 人力 3 10 300 单价 700 1200 设计划生产A,B产品分别为 吨,产值为Z元,该问题的数学模型如下： 称（1-1）为目标函数,（1-2）～（1-5）为约束条件（其中s.t是subject to的缩写,可译为受约束于）。 ? 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。 因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。 例1-2:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？ ? 产品甲 产品乙 设备能力（h） 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润（元/件） 1500