[工学]1单纯形法.ppt

 运筹学基础及应用 胡运权等 编著 (第四版) 绪论 第 1章 线性规划及单纯形法 第 2章 线性规划的对偶理论 第 3章 运输问题 第 4章 整数规划与分配问题 第 5章 目标规划 第 6章 图与网络分析 第 7章 计划评审方法和关键路线法 第 8章 动态规划 第 9章 存贮论 第10章 排队论 第11章 决策分析 第12章 博弈论 绪 论 一、运筹学的起源与发展 二、运筹学的定义及应用 三、运筹学解决问题的方法步骤 一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科 与军事问题相关 如雷达的设置、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research 战后在经济、管理和科研单位继续研究 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 50年代中期由钱学森、许国志等同志从西方引入我国，并于1957年正式定名运筹学，取自于“运筹帷幄之中，决胜千里之外”之意。 1980年成立中国运筹学会 二、运筹学的定义及应用 运筹学的定义 为管理机构对所控制的业务活动作决策时，提供以数量为基础的科学方法。 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science 运筹学方法 应用实例 线性规划 生产结构优化 非线性规划 投资组合优化 0-1规划 选址问题 动态规划 资源分配 网络分析 工程计划优化 排队论 服务系统优化 存贮论 订货库存管理 决策分析 机会选择 对策论 军事作战模型 三、运筹学解决问题的方法步骤 明确问题 建立模型 求解模型 模型检验 解的控制 实施方案 §1 一般线性规划问题的数学模型 1-1 问题的提出 例2、常山机械厂生产Ⅰ、Ⅱ两种产品，分别要在A、B、C三种不同设备生产，每件产品占用各设备的工时、各设备的能力限制以及每件产品的利润如下表。求两种产品各生产多少件，使总利润最大。 线性规划模型三个特征 1、决策变量：需要决策的量，即待求的未知数。 2、目标函数：需要优化的量，即欲实现的目标，表示为 决策变量的线性函数。 3、约束条件：实现目标受到的限制，用决策变量的等式 或不等式表达。 1-2 线性规划问题的数学模型 非标准形如何化为标准形： min型化为max型 目标函数 为min型，令 min z =CX :——— max = -CX 例3 例： 5 基可行解 若基解 XB满足非负约束条件(1.6c) ，即它的各分量都 ? 0 时，称为基可行解 以例2为例，用图解法求解 以例2为例，用图解法求解 说明：图解法求解线性规划问题的几个特点： 图解法只适用于有两个变量的情况 线性规划问题可行解的集合是凸集 线性规划问题的基可行解一般都对应于凸集的顶点 最优解只可能在凸集的顶点上，而不可能发生在凸集的内部 注：线性规划问题解的几种情形： 无解 §3 单纯形法原理 §3 单纯形法的原理 线性规划的一些基本性质 线性规划的可行域是一个凸多面体 线性规划的最优解必能在可行域的顶点获得。 线性规划的可行域的顶点与基本可行解一一对应 单纯形法思路:先找一个初始基可行解,若不是最优解,设法转到另一基可行解,并使目标函数不断增大,一直找到最优解为止 。 约束方程的系数矩阵 3-4 从初始基可行解转换为另一个基可行解 将 换为 ， 称为基变换 （P1 ，P2 ，…… Pl , …，Pm，…, Pk , …….. Pn) 变换的方法 先决定进基的列，再决定出基的行 初始基可行解： 3-5 最优性检验和解的判别： §4 单纯形法的计算步骤 例：试列出下面线性规划问题的初始单纯型表 σ2最大，则P2 列进基 ? 4 =100/3=33.3 ? 5 =120/3=40 ?= ? 4 = min(33.3, 40) X4行出基 [3]表示进基列与出基行的交叉元素，又称主元素。下面将以它为主进行初等行变换。