第一章 数学规划与线性规划.ppt

第一章 数学规划与线性规划 本 章 重 点 数学规划 线性规划 几何解法（图解法） 数学规划：一类用于求解最优方案的方法 应用 利润最大化 生产成本最小化 投资风险最小化 投资利润最大 邮递员最短投递路径 数 学 规 划 数学规划模型求解优化问题—实例 例１　求函数的 最大值 数学规划模型： 求解 数 学 规 划 例2　求函数的 最大值 数学规划模型： 求解： 数 学 规 划 例3　求函数的 最大值 数学规划模型： 求解：约束条件改写为： 那么，目标函数和约束函数的梯度（导数）分别为： 现在对　　和　　分别引入拉格朗日乘子　　和　　，则由Kuhn Tucker条件可得： 那么方程组(1)解的情况如下： 数学规划的一般模型 当目标函数和约束条件变复杂时，模型的求解变得困难，需要一种新的方法解决——这就是运筹学产生的原因 根据目标函数和约束条件的不同，数学规划被分为不同的分支，如：线性规划、非线性规划、目标规划等 　将以上几部分结合起来就得到反映家具厂经营活动的完整的数学模型： max z = 150x1 + 80x2 　　 s.t. 4x1 + 3x2 ? 180 　2x1 + x2 ? 90 (2.1) 　　　x1, x2 ? 0 例2.2某工厂可以生产甲乙两种产品，需消耗三种资源，有关数据见表，试拟定使总收入最大的生产方案 线性规划的建模 问题分析 决策变量：甲、乙两种产品的产量，分别为 和 目标：产品的总收入最大 受制条件：煤、电、油资源有限 煤： 电： 油： 蕴含的约束：产品产量不为负 数学模型 例2.3 某市今年要兴建大量住宅，已知有三种住宅体系可以大量兴建，各体系的资源用量及今年供应量见表，要求在充分利用各种资源的条件下使建造住宅的总面积为最大，求建造方案。 线性规划的建模 问题分析 决策变量：三种住宅砖混、壁板、大模为 m2 目标：住宅总面积最大 受约束条件：各种资源限制 造价： 钢材： 水泥： 砖： 人工： 隐含约束：各种住宅面积不为零 数学模型 目标函数 约束条件（subject to） 例2.4 一公司经营杂粮的批发业务。公司现有库存5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金2万元。估计第一季度杂粮价格如下表。如买进的杂粮当月到货，但需下个月才能卖出，且规定“货到付款”。本公司希望本季末库存为2000担，应采取的什么买进卖出的措施使得本季的净利润最大。 问题分析： 决策变量：每个月的买进、卖出量。设每个月的买进量为 担,卖出量为 担。 目标函数：净利润最大，出货价-进货价 约束条件：受存货、库容、资金约束 存货限制： 第一个月卖出的杂粮 第二个月卖出的杂粮(卖出小于等于买入） 第三个月卖出的杂粮 问题分析： 约束条件： 库容限制：不能超过最大库容，满足期末库存 第一个月的库容： 第二个月的库容： 第三个月的库容：为2000 问题分析： 约束条件： 资金限制： 第一个月使用的资金不能超过2万+卖出粮食获得的利润 第二个月使用的资金不能超过第一个月剩余资金+卖出的粮食获得的利润 第三个月使用的资金不能超过第二个月剩余的资金+卖出粮食获得的利润 隐含约束 数学模型 目标函数 ５　凸集：集中任意两点的连线仍属此集 注：线性规划的约束集（可行域）是一个凸多面体 。凸多面体是凸集的一种。 方法一 角点枚举法 最优解如果存在，都会在可行域的角点出现 计算每个角点的目标函数值，取最大 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 例１　设每日生产电视机A的数量为 台，电视机B的数量为 台 例２ 用图解法求解下面的线性规划问题： 例3 用图解法求解下面的线性规划问题： 例4 用图解法求解下面的线性规划问题： 例5 用图解法求解下面的线性规划问题： 例7 用图解法求解下面的线性规划问题： 几何解法的几种情况 唯一最优解 无穷多最优解 几 何 解 法 几何解法的几种情况 无界解 无解 总　结 １