《线性规划问题》PPT课件.ppt

线性规划问题 一 线性规划问题二 Excel求解线性规划问题三 实例讲解 一 线性规划问题 线性规划是运筹学的一个重要分支 是运筹学的最基本的部分 线性规划的应用及其广泛 从解决技术问题的最优化设计到工业 农业 商业 交通运输业 军事和经济计划管理决策领域都可以发挥作用 它是现代科学管理的一种重要手段 引言 在经济生活中 人们经常遇到这样两类实际问题 1 资源给定 如何对给定资源予以充分地 合理地运用 使之完成的任务尽可能地多 2 任务给定 如何以尽可能少的资源消耗来完成给定的任务 可见 上述两类问题都是寻求利润最大 第一类 是以最大收益扣除定量成本 第二类 是以定量收益扣除最小成本 在满足一定条件时 这类优化问题都可以用线性规划的方法来予以解决 线性规划的概念当收益和消耗均与计划指标呈正比时 一个规划问题所列出的数学表达式都是关于计划指标的线性关系式 称此类型规划问题为线性规划问题 线性规划问题是 在一组线性约束条件下 求一组非负变量的值 使一个线性目标函数达到最大或最小 线性规划问题 例1 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 问题 如何安排生产计划 使得获利最多 分析 这是一个生产计划问题 设生产A产品X1kg B产品X2kg 则该问题可以用如下模型来描述 MaxZ 70X1 120X29X1 4X2 360s t 4X1 5X2 2003X1 10X2 300X1 0X2 0该模型的解为生产计划 线性规划问题 例2 某运输问题 已知资料如下表所示 问如何调运 使产销平衡且总运费最小 单位运费 产地 销地 单位 百万 吨 这是一个产销平衡运输问题 即 Ai地产量ai Bj地销量bj i 1 2 3 j 1 2 3 4 设从生产地Ai到销售地Bj的调运量为 Xij i 1 2 3 j 1 2 3 4 该问题的数学模型为 MinZ 5X11 6X12 10X13 3X14 4X33 8X34X11 X12 X13 X14 60X21 X22 X23 X24 40 s t X11 X21 X31 30 X14 X24 X34 40Xij 0 i 1 2 3 j 1 2 3 4 产量约束 销量约束 从数学上来讲 它们的共同特征是 每个问题都用一组决策变量 x1 x2 xn 表示某一方案 这组未知数的值就代表一个具体的方案 通常要求这些未知数取值是非负的 2 存在一定的限制条件 称为约束条件 这些条件都可以用关于决策变量的一组线性等式或不等式来表示 3 都有一个目标要求 并且这个目标可表示为这组决策变量的线性函数 称为目标函数 按研究问题的不同 要求目标函数实现最大化或最小化 线性规划问题是 在一组线性约束条件下 求一组非负变量的值 使一个线性目标函数达到最大或最小 线性规划的三要素决策变量 根据影响所要达到目的的因素找到决策变量 生产产品量 运输分配量等目标函数 由决策变量和所要达到目的之间的函数关系确定目标函数 最大利润 最小运费等约束条件 由决策变量所受的限制条件确定决策变量所要满足的约束条件 原材料限制 工时限制等 求解线性规划问题的方法 1 数学方法 单纯形法 图解法等 2 计算机方法 各种软件 lingo matlab excel等 二 利用ExcelSolver求解线性规划问题 如何加载Excel的 规划求解 安装office的时候 系统默认的安装方式不会安装宏程序 需要用户根据自己的需求选择安装 下面是加载 规划求解 宏的步骤 1 在 工具 菜单上 单击 加载宏 2 在弹出的对话框中的 可用加载宏 列表框中 选定待添加的加载宏 规划求解 选项旁的复选框 然后单击 确定 单击 确定 以后 工具 菜单下酒会出现一项 规划求解 实例1 生产计划问题 某公司最畅销的3种商品单位利润不一 A为10元 B为8元 C为9元 不论哪一种商品 其生产过程都需要经过 制造 测试 品管 和 封装 四个部门 而每种商品在各个部门所耗费的工时也不一样 如下表 每个部门的可用工时也是有限制的 如下表 问 如何安排生产 才能使总利润最大 excel求解结果 规划求解 各参数解释和设置单击 规划求解 按钮 将会出现以下的规划求解参数的对话框 1 目标单元格 存放目标函数的计算值的位置 2 最大值 最小值 在此指定是否希望目标单元格为最大值 最小值或某一特定数值 如果需要指定书 请在右侧编辑框中键入该值 3 可变单元格 在此指定可变单元格 求解时其中的数值不断调整 直到满足约束条件并且 设置目标单元格 框中指定的单元格达到目标值 4 约束 在此列出了规划求解的所有约束条件 5 最长运算时间 在此设定求解过程的时间 默认值100 秒 一般可以满足大多数小型规划求解要求 6 迭代次数 在此设定求解过程中迭代运算的次数 限制求解过程的时间 默认值100次 基本可以满足大多数小型规划求解要求 7 精度 在此输入用于控制求解精度的数字 以确定约束条件单元格中的数值是否满足目标值或上下限 8 允许误差 在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差 这个选项只用于具有整数约束条件的问题 设置的允许误差值越大 求解过程就越快 9 采用线性模型 当模型中的所有关系都是线性的 并且希望解决线性优化问题时 选中此复选框可加速求解过程 10 显示迭代结果 如果选中此复选框 每进行一次迭代都将中断 规划求解 并显示当前的迭代结果 11 假定非负 如果选中此复选框 则对于在 添加约束 对话框的 约束值 框中没有设置下限的所有可变单元格 假定其下限为0 Excel求解线性规划问题的步骤 1 在电子表格中确定目标单元格 活动单元格 输入所有参数 2 利用数据组相乘公式 常用函数里SUMPRODUCT 确定好约束条件的左边对应单元格 3 打开工具栏里的规划求解 1 给定目标单元格 活动单元格 求最大或最小 2 添加约束条件 3 选项栏里 线性 非负 确定 4 确定求解 某自动售货机制造商的仓储中心坐落于济南 杭州 厦门3地区 而往来的客户主要位于北京 上海 广州 天津 香港与西安6大城市 由于各仓储中心地利环境 人力资源及区域性成本的不同 自动售货机的运送成本或多或少会有所差异 如下表1 当前各仓储中心的自动售货机的库存量如下表2 各地的需求量如下表3 问 为了能够有效降低运送成本 应如何安排运输 才能支付最低的运费又同时能够满足所有地区的运送需求 实例2 运费问题 表3各地需求量 单位 台 表2仓储中心库存总量 单位 台 实例2 运费问题 表1运输成本 单位 元 实例2 运费问题 假设各仓储中心运往各地区的数量如下表 实例2 运费问题 目标函数 MinZ 58X11 47X12 108X13 87X21 28X62 38X63 约束条件 SubjecttoX11 X12 X13 150X21 X22 X23 225X31 X32 X33 100X4