第一章线性规划与单纯形法(运筹学)讲述.ppt

运筹学 Operational research 绪论 运筹帷幄，决胜千里 运筹=谋划（规划） 第一节 运筹学释义和发展简史 运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决生产和管理过程中提出的专门问题，为决策者选择最优方案提供定量依据。 1914，F.W.Lanchester战斗方程 一方有x个战斗单位，另一方有y个战斗单位， dy/dt=-ax, dx/dt=-ay ax2=by2 1935，Bawdsey雷达站的研究 1942，大西洋反潜作战 P.W.Morse协助英国打破德国对英吉利海峡的封锁： 将反潜攻击由潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米改为25米。 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模，减少批次，这样损失率将减少 第二节 运筹学研究的基本特征和基本方法 基本特征： 系统的整体观念 多学科的综合 模型方法的应用 研究的基本步骤 分析和表述问题 建立模型 求解模型和优化方案 测试模型及对模型进行必要的修正 建立对解的有效控制 方案的实施 第三节 运筹学的主要分支 线性规划 非线性规划 动态规划 图论与网络分析 存储论 排队论 对策论 决策论 运筹学的主要内容 第一章 线性规划与单纯形法 第二章 对偶理论与灵敏度分析 第三章 运输问题 第四章 目标规划 第五章 整数规划 第十章 图与网络分析 第十二章 排队论 运筹学学习方法 1、课前预习 2、认真听课，适当笔记 3、认真作业 运筹学有一定难度，该课程有一定的研究性特征；以线性代数和概率论为基础 运筹学 解决问题的主要程序 第一章 线性规划与单纯形法 §1 线性规划问题及其数学模型 §2 线性规划问题的几何意义 §3 单纯形法 §4 单纯形法的计算步骤与表格单纯形法 §5 单纯形法的进一步讨论 §6 应用举例 线性规划(运筹学)主要解决两类问题 企业利润=收入-成本 收入由提供产品或服务获得 成本由消耗的资源承担 1、资源有限（获成本），要求生产的产品获得的收入（或利润）最多。1 2、任务（或产品收入）一定，要求消耗的资源（或成本）最少。2 线性规划中的两类数学模型1 1、max 总收入或总利润 总成本≤b 返回 线性规划中的两类数学模型2 2、min 总成本 总收入≥b 返回 2）表格单纯形法 §1 线性规划问题 及其数学模型 1.1 问题的提出 线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。 1、线性规划问题的提出 将生产经营和管理过程中的决策问题 ——转化成数学模型 例1: 生产计划问题(步骤) 第3步 --表示约束条件 该计划的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x1、 x2 ? 0 决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 符号约束 可行域（Feasible region) 最优解（Optimal solution) 建立线性规划数学模型的步骤 1、选择适当的决策变量 设决策变量的原则 2、用决策变量表达目标函数 收入或利润极大化 成本或支出极小化 3、用决策变量表达所有的约束条件 4、注意变量的符号约束返回 例 2 环境保护问题 工厂1（工业污水2万m3 ）治污成本 1000元/万m3 500万m3 20%自然净化 200万m3 工厂2