优化设计第四节ppt课件.ppt

第四章线性规划 本章教学内容线性规划的特点 性质线性规划的应用及在包装领域中的应用 写出数学模型用现有软件 公用软件或专用软件 求解 第一节线性规划问题及其数学模型第二节线性规划的图解法第三节线性规划应用专题 第一节线性规划问题及其数学模型 线性规划的定义 目标函数和约束函数都是线性函数的约束问题 线性规划主要解决两类问题1 用最少的人力 物力 财力资源去完成给定的任务 2 用给定的人力 物力 财力资源去完成尽可能多的任务 线性规划能成功地解决以下问题 1 合理利用材料问题 2 配料问题 3 投资问题 4 产品生产计划 5 劳动力安排 6 运输问题 例某公司用资源A B C生产两种产品甲和乙 生产每单位产品甲和乙分别需要用各种资源的数量以及在一个计划期内各种资源的现有数量及产品获利见下表 问应如何安排生产才能获得最大利润 第一节线性规划问题和数学模型 1 生产决策问题 试决定应生产这两种产品各多少吨 才能使创造的总利润最高 如何确定决策变量 第一步 决策变量可选择以下哪几种 1 利用A资源的数量2 利用B资源的数量3 利用C资源的数量4 生产产品甲的产量5 生产产品乙的产量6 产品获利 建立问题的线性规划模型 常有以下几个步骤 确定决策变量x1 生产产品甲的数量 吨 x2 生产产品乙的数量 吨 以上变量是由决策者决定的未知变量 代表决策者可能采取的行动 称为决策变量 目标函数是什么 第二步 目标函数以 表示生产甲 乙两种产品各为x1 x2 吨 时产生的经济价值 则Min 7x1 5x2 约束条件 第三步 约束条件约束条件 对各个限制条件逐一加以分析 写出反映其限制关系的表达式 等式或不等式 资源 限制 3x1 2x2 90资源B限制 4x1 6x2 200资源C限制 7x2 210非负条件 x1 0 x2 0 综上分析 MaxZ 7x1 5x2约束条件3x1 2x2 904x1 6x2 2007x2 210 x1 0 x2 0 2 运输问题 产销平衡 设有两个电器厂A1 A2 电器厂的产量 销售地点B1 B2 B3的需求量及运价如下表所示 问怎样调运这些电器产品才能使总运费最小 如何确定决策变量 第一步 1 电器厂A1的产量2 电器厂A2的产量3 销售地点B1的需求量4 销售地点B2的需求量5 销售地点B3的需求量6 电器产品总运费 7 电器厂A1运往销售地点B1的数量8电器厂A1运往销售地点B2的数量9电器厂A1运往销售地点B3的数量10电器厂A2运往销售地点B1的数量11电器厂A2运往销售地点B2的数量12电器厂A3运往销售地点B3的数量 决策变量可选择以下哪几种 解 确定决策变量设xij为由产地 i运往销地Bj的物品数量 其中i 1 2 j 1 3 X11电器厂A1运往销售地点B1的数量X12电器厂A1运往销售地点B2的数量X13电器厂A1运往销售地点B3的数量X21电器厂A2运往销售地点B1的数量X22电器厂A2运往销售地点B2的数量X23电器厂A3运往销售地点B3的数量 以上变量是由决策者决定的未知变量 代表决策者可能采取的调运方案 目标函数 第二步 分析目标MinZ 50 x11 60 x12 70 x13 60 x21 110 x22 160 x23 总的运输费用最少 运价 约束条件 第三步 约束条件 A1电器厂运往B1 B2 B3的总量应等于A1电器厂的产量x11 x12 x13 23A2电器厂运往B1 B2 B3的总量应等于A2电器厂的产量x21 x22 x23 27 A1电器厂的产量 分析并表达约束条件 A2电器厂的产量 A1 A2电器厂运往销售地B1的数量应等于销售地B1的销量x11 x21 17A1 A2电器厂运往销售地B2的数量应等于销售地B2的销量x12 x22 18A1 A2电器厂运往销售地B3的数量应等于销售地B3的销量x13 x23 15xij 0 i 1 2 j 1 3 综上分析 MinZ 50 x11 60 x12 70 x13 60 x21 110 x22 160 x23约束条件x11 x12 x13 23x21 x22 x23 27x11 x21 17x12 x22 18x13 x23 15xij 0 i 1 2 j 1 3 最优调运问题的线性规划数学模型 以上实例具有以下的特征 1 用未知自变量表示某种重要的可变因素 变量的一组数据代表一种解决方案 2 存在一定的限制条件 如材料 人力 设备 时间 费用等 它们可以用自变量的线性方程 等式 或线性不等式来表达 这些条件称为约束条件 3 都有一个要达到的目标 它也是自变量的线性函数 称为目标函数 根据需要 要求目标函数极大化或极小化 定义 由于目标函数和约束条件都是自变量的线性函数 故称这类问题是线性规划问题 建立线性规划的数学模型的步骤 首先选取一组适当的变量xi 或xij 作为这个问题的主要 物理量 这组变量要能切实表达所要解决的问题 都有一个明确的目标 这些目标正是各个问题所要求解答的主要数量指标 同时这些目标都可以表示为变量xi 或xij 的线性函数 称为线性目标函数 对各个变量xi 或xij 存在一定的限制条件 称它们为约束条件 这些条件又都可以用一组线性不等式或线性等式来表示 所要解决的问题都可以表达为一组约束条件下 求目标函数的最大值或最小值问题 Max min S c1x1 c2x2 cnxn并满足约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn cj 价值系数bi 限制常数 1 某木器厂生产圆桌和衣柜两种产品 现有两种材料 第一种为72m3 第二种为52m3 生产每张圆桌和衣柜所需两种材料见下表 已知每生产一张圆桌可获利润20元 生产一个衣柜可获利润50元 木器厂在现有木料条件下 圆桌和衣柜各生产多少方能获得最大利润 作业 2 某车间用三台机床A1 A2 A3加工两种零件B1 B2分别需要50个和70个 各机床必须加工出零件数A1为40个 A2为35个 A3为45个 各个机床加工各种零件的加工费见下表 应如何安排加工任务 方能使总的加工费最少 3 某公司用原料A B C D生产两种包装产品甲和乙 生产每单位产品甲和乙分别需要用各种原料的数量以及在一个计划期内各种原料的现有数量见下表 生产包装产品甲可获利2千元 生产包装产品乙可获利3千元问应如何安排生产才能获得最大利润 4 设有某种包装原材料 从m个产地A1 A2 A3 Am运往n个销售地B1 B2 Bn 产地Ai的月产量为ai吨 销售地Bj的月需求量为bj吨 由Ai运往Bj的单位运费价格为下表 问应如何调运可使总的运输费用最省 第二节线性规划的图解法 求解一个线性规划问题就是找出一组满足约束条件的变量 使得目标函数达到最大值 或最小值 对于只有两个变量的线性规划问题是容易办到的 求解过程可以用图形表示出来 例 MaxS 2x1 3x2约束条件 2x1 2x2 142x1 x2 104x1 16X1 2x2 12X1 x2 0 解 在以x1 x2为坐标轴的直角坐标系中X1 x2 0表示第一象限满足约束2x1 2x2 142x1 x2 104x1 16X1 2x2 12X1 x2 0的图形如下 X1 x2 0 2x1 2x2 14X1 0 x2 7X2 0 x1 7 2x1 x2 10X1 0 x2 10X2 0 x1 5 2x1 2x2 14 4x1 16X1 4 X1 2x2 12X1 0 x2 6x2 0 X1 12 通过以上图形 定义以下概念可行解 区域0A1A2A3A4A5O中的每一个点 包括边界点 都是线性规划问题的一个解最优解 在可行域0A1A2A3A4A5O上找出使目标函数S达到最大值的点 如何找最优解 用目标函数等值线的方法 目标函数S 2X1 3X2等值线2X1 3X2 C令 C 62X1 3X2 6 2X1 3X2 6X1 0 X2 2X2 0 X1 3 目标函数S 2X1 3X2等值线2X1 3X2 C 当C由0不断增大时 目标函数的值也由0沿着直线2X1 3X2 C的法线方向不断增大 直到直线2X1 3X2 C与区域0A1A2A3A4A5O只交于一点A4 这时如果C再继续增大 直线2X1 3X2 C与区域0A1A2A3A4A5O就不再相交了 最后交点A4就是所要求的目标函数S在约束条件下的最大值点 即最优解A4点 如何找最优解 用目标函数等值线的方法 2X1 3X2 C A4点x1 2x2 122x1 2x2 14解得 x1 2x2 5 最大利润MAXS 2 2 3 5 19千元生产产品 2件生产产品 5件 X1 2x2 12 2X1 2x2 14 的交点 无限多个最优解 如果目标函数MAXS x1 x2约束条件2x1 2x2 142x1 x2 104x1 16X1 2x2 12X1 x2 0 MAXS x1 x2目标函数的等值线X1 X2 C当C增大时 等值线x1 x2 C沿它的法线方向平行移动最终必与线段A3A4重合 这时线段A3A4上的每一点都使目标函数S达到相同的最大值 线段A3A4上有无数个点 上面线性规划问题就是有无限多个最优解 2x1 2x2 14 X1 X2 C 无界解MAXS x1 x2 约束条件 2x1 x2 4x1 x2 2x1 x2 0 2x1 x2 4 X1 x2 2 由约束条件构成的可区域是一个无界域 当等值线沿箭头方向无限远移时 始终与可行域相交 这种情况下问题的最优解无界 原因 建模时遗漏了某些必要的资源约束条件 x2 x1 MAXS 3x1 x2 约束条件 2x1 x2 4x1 x2 2x1 x2 0X1 0 x2 4是最优解MAXS 4 2x1 x2 4 X1 x2 2 可行域无界不等于问题无界 这要看目标函数的情况 无可行解MAXS 2x1 x2约束条件x1 x2 22x1 2x2 6x1 x2 0 x1 x2 用图解法求解时看出不存在满足所有约束的公共区域 说明问题无解原因 模型的约束条件之间存在矛盾 建模时有错误 从图解法可得出重要结论 求解线性规划问题时 解的情况有 唯一最优解 无限多个最优解 无界解 无可行解 如果线性规划的所有约束条件构成的可行域存在 则可行域是凸多边形 对于给定的线性规划 如果存在最优解 最优解之一 则一定在可行域的某个顶点上取得 作业 用图解法解下列线性规划问题MAXZ x1 3x25x1 10 x2 50 x1 x2 1x2 4x1 x2 0指出问题是具有唯一最优解无穷多最优解无界解无可行解 第三节线性规划应用专题 应用线性规划解决经济 管理 生产领域的实际问题 最重要的一步是建立实际问题的线性规划模型 这是一项技巧性很强的创造性工作 即要求对研究问题有深入了解 又要求很好掌握线性规划模型的结构特点 并具有对实际问题进行数学描述的较强的能力 因此在研究建立一些较复杂的数学模型时 需要各方面专业人员的通力协作配合 一般来讲 一个经济管理 生产实际问题要满足下列条件才能归结为线性规划的模型 1 要求解的问题的目标能用某种效益指标度量大小程度 并能用线性函数描述目标的要求 2 为达到这个目标存在多种方案3 要达到的目标是在一定约束条件下实现 这些条件可用线性等式或不等式描述 实际问题 数学模型 解决问题 创造性工作 例1 要做100套运输包装中的特殊托盘钢架 每套由长2 9米 2 1米和1 5米的圆钢各一根组成 已知原料长7 4米 应如何下料 才能使用的原料最省 合理下料问题 现有几种经验套裁方案 如何确定设计变量 1 设计变量设按第一种方案下料的原料根数为x1 设按第二种方案下料的原料根数为x2设按第三种方案下料的原料根数为x3设按第四种方案下料的原料根数为x4设按第五种方案下料的原料根数为x5设按第六种方案下料的原料根数为x6 在省料的条件下 得到100套钢架 需要混合使用表中各种下料方案 目标函数是什么 2 目标函数所剩料头的总数 MinZ 0X1 0 1X2 0 2X3 0 3X4 0 8X5 0 9X6 约束条件 3 约束函数2 9m长圆钢总数x1 2x2 0 x3 x4 0 x5 x6 1002 1m长圆钢总数0 x1 0 x2 2x3 2x4 x5 x6 1001 5m长圆钢总数3x1 2x2 2x3 0 x4 3x5 x6 100非负变量x1 x2 x3 x4 x5 x6 0 MinZ 0X1 0 1X2 0 2X3 0 3X4 0 8X5 0 9X6约束函数x1 2x2 0 x3 x4 0 x5 x6 1000 x1 0 x2 2x3 2x4 x5 x6 1003x1 2x2 2x3 0 x4 3x5 x6 100非负变量x1 x2 x3 x4 x5 x6 0 优化数学模型 例二设要在某种型号的纸板上 裁下m种不同型号的包装纸盒A1 A2 A3 AM 根据经验 在一块纸板共有n个不同的下料方式B1 B2 Bn 对每个下料方式Bj j 1 2 3 n 可得包装纸盒Ai I 1 2 m Cij个 已知包装纸盒Ai的需求量为ai个 问应如何下料才能满足需要 又使所用的纸板最少 包装纸盒的印刷 该数学模型可以应用到包装纸盒印刷和包装标签印刷的企业中 包装标签的印刷 某种包装纸盒 两种不同的排版方式 某种包装纸盒 该纸盒的排版 为了节省纸板 一般将不同型号 大小不同的 的包装纸盒混合排在一张纸板上 根据经验可有多种排法 俗称套裁 如何理解 我们用简单几何图形来分析 设有4种不同包装纸盒Ai i 4 A1i 1 A2i 2 A3i 3 A4i 4 根据经验有3种下料 混排 方式Bj j 3 B1j 1 B3j 3 B2j 2 A1i 1 A2i 2 A3i 3 A4i 4 包装纸盒 下料方式 解 1 设计变量设xj表示按方式Bj下料所需用的纸板数j 1 2 n 2 目标函数按各种不同方式下料所需用的纸板总数MinS x1 x2 xn 3 约束函数按各种不同下料方式Bj生产包装纸盒盒坯Ai的总数应等于盒坯Ai的需要量aiC11X1 C12X2 C1nXn a1C21X1 C22X2 C2nXn a2 Cm1X1 Cm2X2 CmnXn amx1 x2 xn 0 m个方程 下料方式 包装盒型 MinS x1 x2 xn约束函数Ci1X1 Ci2X2 CinXn ai i 1 2 m x1 x2 xn 0 优化数学模型 某油墨厂用原料A B C加工成三种不同牌号的油墨甲 乙 丙 已知各种牌号油墨中A B C含量 原料成本 各种原料的每月限制用量 三种牌号油墨的单位加工费及售价如下表 问该厂每月生产这三种牌号油墨各多少公斤 使该厂获利最大 试建立该问题的线性规划的数学模型 混合配料问题 解 确定设计变量用i 1 2 3分别代表原料A B C用j 1 2 3分别代表不同牌号的油墨甲 乙 丙 Xij 为生产第j种油墨耗用的第i种原料的kg 公斤 数 分析目标该油墨厂的获利为三种牌号的油墨的售价减去相应的加工费和原料成本 三种油墨的生产量分别为 X甲 x11 x21 x31 x甲 X11 生产甲种油墨耗用的原料A的kg数X21 生产甲种油墨耗用的原料B的kg数X31 生产甲种油墨耗用的原料C的kg数 X乙 X丙 X11 生产乙种油墨耗用的原料A的kg数X21 生产乙种油墨耗用的原料B的kg数X31 生产乙种油墨耗用的原料C的kg数 X11 生产丙种油墨耗用的原料A的kg数X21 生产丙种油墨耗用的原料B的kg数X31 生产丙种油墨耗用的原料C的kg数 X乙 x12 x22 x32 X丙 x13 x23 x33 MAXZ 3 4 0 5 X11 X21 X31 2 85 0 4 X12 X22 X32 2 25 0 3 X13 X23 X33 2 X11 X12 X13 1 5 X21 X22 X23 1 0 X31 X32 X33 X乙 x甲 X丙 原料A的成本 原料B的成本 原料C的成本 目标函数为三种牌号的油墨售价减去相应的加工费和原料成本 MAXZ 0 9X11 1 4X21 1 9X31 0 45X12 0 95X22 1 45X32 0 05X13 0 45X23 0 95X33 约束条件 三种油墨的生产数量受到原材料月供应量和原料含量成份的限制 原料Ax11 x12 x13 2000原料Bx21 x22 x23 2500原料Cx31 x32 x33 1200 1 原料月供应量限制 2 含量成份的限制 甲种油墨含原料Ax11 0 6 x11 x21 x31 甲种油墨含原料Cx31 0 2 x11 x21 x31 乙种油墨含原料Ax12 0 3 x12 x22 x32 乙种油墨含原料Cx32 0 5 x12 x22 x32 丙种油墨含原料Cx33 0 6 x13 x23 x33 xij 0 i 1 2 3j 1 2 3 x甲 x甲 X乙 X乙 X丙 约束条件化简为 0 4x11 0 6x21 0 6x31 00 2x11 0 2x21 0 8x31 00 7x12 0 3x22 0 3x32 00 5x12 0 5x22 0 5x32 00 6x13 0 6x23 0 4x33 0 xij 0 i 1 2 3j 1 2 3 MINZ 0 9X11 1 4X21 1 9X31 0 45X12 0 95X22 1 45X32 0 05X13 0 45X23 0 95X33约束条件 x11 x12 x13 2000 x21 x22 x23 2500 x31 x32 x33 12000 4x11 0 6x21 0 6x31 00 2x11 0 2x21 0 8x31 00 7x12 0 3x22 0 3x32 00 5x12 0 5x22 0 5x32 00 6x13 0 6x23 0 4x33 0 xij 0 i 1 2 3j 1 2 3 成功了 2 配料问题某养鸡专业户 养鸡1000只 用大豆和谷物饲料混合喂养 每天每只鸡平均吃混合饲料0 5公斤 其中应至少含有0 1公斤蛋白质和0 002公斤钙 已知每公斤大豆含有50 的蛋白质和0 5 的钙 价格是每公斤1元 每公斤谷物含有10 的蛋白质和0 4 的钙 价格是每公斤0 3元 粮食部门每周只保证供应谷物2500公斤 大豆供应量不限 问如何搭配这两种饲料 才能使喂养成本最低 解 确定决策变量设 一周1000只鸡用大豆x1公斤一周1000只鸡用谷物x2公斤 分析目标一周1000只鸡使用大豆和谷物的成本费用为ZMinZ x1 0 3x2 大豆费用 谷物费用 约束条件 1 一周1000只鸡使用混合饲料的数量x1 x2 3500 1000 0 5 7 2 一周1000只鸡需要蛋白质不少于 0 1 1000 7 7000 5x1 0 1x2 700 大豆中的蛋白质 谷物中的蛋白质 3 一周1000只鸡需要钙不少于 0 002 1000 7 140 005x1 0 004x2 14 4 谷物的限量x2 2500 x1 0 x2 0 大豆中的钙 谷物中的钙 综上分析 MinZ x1 0 3x2x1 x2 35005x1 x2 7000 x1 x2 14000 x2 2500 x1 0 x2 0 哇塞 好简单 三 广告媒体选择问题例 白云洗涤剂厂试制出一种新型高效洗衣粉 该厂希望在较短的时间内将这种新产品推向市场 其中要采取的一个重要的营销手段就是广告 该厂可使用电视 报刊 收音机等媒体做广告 也可将洗衣粉样品与广告小册子同时发放给消费者进行宣传 上述各种广告途径的可达人数 成本 可提供的广告数 单位广告的影响力如表所示 此外 该厂希望通过各种广告 使得至少500000人看到广告 并且由于电视的影响力较大 厂方要求电视广告数不得少于10个 其中黄金档电视广告数不得少于2个 广告的总预算为30000元 其中电视广告预算为18000元 该厂应如何合理地选择媒体 在满足上述要求的前提下使得广告的影响力最大 表 白云洗涤剂厂广告媒体选择数据 解 1 决策变量决策变量是各媒体投入的广告数设 x1为电视1 x2为电视2 x3为报刊 x4为收音机 x5为赠送样品 这五种不同的广告媒体或途径上投入的广告数 2 目标函数广告影响力函数Z为最大MAXZ 65xl 90 x2十60 x3 40 x4 20 x5 3 约束函数 可达消费者数应大于500000人10000 xl 20000 x2十15000 x3 25000 x4 3000 x5 500000 广告总费用应小于30000元1500 xl 3000 x2十450 x3 800 x4 100 x5 30000 电视广告费用应小于18000元1500 xl 3000 x2 18000 电视广告数不得大于10个xl x2 10 黄金档电视广告数大于2个x2 2 媒体可提