简单线性规划.ppt

复习 1 直线的截距 注意 截距不是距离 有正负 横截距 直线与X轴交点横坐标 纵截距 直线与Y轴交点纵坐标 复习 2 在同一坐标系上作出下列直线 2x y 0 2x y 1 2x y 3 2x y 4 2x y 7 x Y o 观察图像 形如2x y t t 0 的直线有什么特点 复习 二元一次不等式 组 表示平面区域的方法 x y 1 0 x y 1 0 3 二元一次不等式组表示的平面区域是各个不等式表示的平面区域的交集 即各个不等式表示的平面区域的公共部分 1 直线定界 Ax By C 0 注意实线和虚线的区别 2 特殊点定域 一般的 选取原点 0 0 问题1 某工厂用A B两种配件生产甲 乙两种产品 每生产一件甲种产品使用4个A配件耗时1h 每生产一件乙种产品使用4个B配件耗时2h 该厂每天最多可从配件厂获得16个A配件和12个B配件 按每天工作8小时计算 该厂所有可能的日生产安排是什么 分析 把问题1的有关数据列表表示如下 设甲 乙两种产品分别生产x y件 将上面不等式组表示成平面上的区域 设甲 乙两种产品分别生产x y件 由己知条件可得 y 4 8 4 3 o 区域内所有坐标为整数的点P x y 安排生产任务x y都是有意义的 思考 若生产1件甲种产品获利2万元 生产1件乙种产品获利3万元 采用哪种生产安排利润最大 若设利润为z 则z 2x 3y 这样上述问题转化为 当x y在满足上述约束条件时 z的最大值为多少 分析 设甲 乙两种产品分别生产x y件 则利润可以表示为 2x 3y z 2x 3y表示与2x 3y 0平行的一组直线 问题 求利润z 2x 3y的最大值 转化为求直线的截距的最大值 M 4 2 象这样关于x y一次不等式组的约束条件称为线性约束条件 Z 2x 3y称为目标函数 因这里目标函数为关于x y的一次式 又称为线性目标函数 在线性约束下求线性目标函数的最值问题 统称为线性规划 满足线性约束的解 x y 叫做可行解 所有可行解组成的集合叫做可行域 使目标函数取得最值的可行解叫做这个问题的最优解 变式 若生产一件甲产品获利1万元 生产一件乙产品获利3万元 采用哪种生产安排利润最大 N 2 3 变式 求利润z x 3y的最大值 解线性规划问题的步骤 2 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 3 求 通过解方程组求出最优解 4 答 作出答案 1 画 画出线性约束条件所表示的可行域 练习 解下列线性规划问题 1 求z 2x y的最值 使式中的x y满足约束条件 Zmin 3 Zmax 3 线性规划 问题 设z 2x 3y 式中变量满足下列条件 求z的最大值与最小值 目标函数 线性目标函数 线性约束条件 任何一个满足不等式组的 x y 可行解 可行域 所有的 最优解 线性规划问题 解决线性规划问题的步骤 画 画出线性约束条件所表示的可行域 答 做出答案 求 根据观察的结论 先求交点的坐标 再求出最优解 移 在目标函数所表示的一组平行线 与目标函数中z 0平行 中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 小结 小结 本节主要学习了线性约束下如何求目标函数的最值问题正确列出变量的不等关系式 准确作出可行域是解决目标函数最值的关健线性目标函数的最值一般都是在可行域的顶点或边界取得 把目标函数转化为某一直线 其斜率与可行域边界所在直线斜率的大小关系一定要弄清楚 体验 二 最优解一般在可行域的顶点处取得 三 在哪个顶点取得不仅与B的符号有关 而且还与直线Z Ax By的斜率有关 一 先定可行域和平移方向 再找最优解 把问题1的有关数据列表表示如下 设甲 乙两种产品分别生产x y件 y 4 8 4 3 o M M 4 2 y 4 8 4 3 o M 简单的线性规划问题 二 一 复习概念 y x 4 8 4 3 o 把求最大值或求最小值的的函数称为目标函数 因为它是关于变量x y的一次解析式 又称线性目标函数 满足线性约束的解 x y 叫做可行解 在线性约束条件下求线性目标函数的最大值或最小值问题 统称为线性规划问题 一组关于变量x y的一次不等式 称为线性约束条件 由所有可行解组成的集合叫做可行域 使目标函数取得最大值或最小值的可行解叫做这个问题的最优解 可行域 可行解 最优解 二 回顾解线性规划问题的步骤 2 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 3 求 通过解方程组求出最优解 4 答 作出答案 1 画 画出线性约束条件所表示的可行域 练习 解下列线性规划问题 1 求z 2x y的最大值 使式中的x y满足约束条件 Zmin 3 Zmax 3 例2 一个化肥厂生产甲 乙两种混合肥料 生产1车皮甲种肥料的主要原料是磷酸盐4t 硝酸盐18t 生产1车皮乙种肥料需要的主要原料是磷酸盐1t 硝酸盐15t 现库存磷酸盐10t 硝酸盐66t 在此基础上生产这两种混合肥料 列出满足生产条件的数学关系式 并画出相应的平面区域 并计算生产甲 乙两种肥料各多少车皮 能够产生最大的利润 解 设x y分别为计划生产甲 乙两种混合肥料的车皮数 于是满足以下条件 x y o 解 设生产甲种肥料x车皮 乙种肥料y车皮 能够产生利润Z万元 目标函数为Z x 0 5y 可行域如图 把Z x 0 5y变形为y 2x 2z 它表示斜率为 2 在y轴上的截距为2z的一组直线系 x y o 由图可以看出 当直线经过可行域上的点M时 截距2z最大 即z最大 答 生产甲种 乙种肥料各2车皮 能够产生最大利润 最大利润为3万元 M 容易求得M点的坐标为 2 2 则Zmax 3 3 制定投资计划时 不仅要考虑可能获得的盈利 而且要考虑可能出现的亏损 某投资人打算投资甲 乙两个项目 根据预测 甲 乙项目可能的最大盈利率分别为100 和50 可能的最大亏损率分别为30 和10 投资人计划投资金额不超过10万元 要求确保可能的资金亏损不超过1 8万元 问投资人对甲 乙两个项目各投资多少万元 才能使可能的盈利最大 解题回顾 要能从实际问题中 建构有关线性规划问题的数学模型 关键求出约束条件和目标函数 解 设投资方对甲 乙两个项目各投资x y万元 依题意线性约束条件为 目标函数为 作出可行域 可知直线Z x 0 5y通过点A时利润最大 由 万元 答 练习题 1 某厂拟生产甲 乙两种适销产品 每件销售收入分别为3000元 2000元 甲 乙产品都需要在A B两种设备上加工 在每台A B上加工1件甲所需工时分别为1h 2h 加工1件乙所需工时分别为2h 1h A B两种设备每月有效使用台时数分别为400h和500h 如何安排生产可使收入最大 解 设每月生产甲产品x件 生产乙产品y件 每月收入为Z千元 目标函数为Z 3x 2y 满足的条件是 Z 3x 2y变形为它表示斜率为的直线系 Z与这条直线的截距有关 X Y O 400 200 250 500 当直线经过点M时 截距最大 Z最大 M 解方程组 可得M 200 100 Z的最大值Zmax 3x 2y 800 千元 故生产甲产品200件 乙产品100件 收入最大 为80万元 小结 二元一次不等式表示平面区域 直线定界 特殊点定域 简单的线性规划 约束条件 目标函数 可行解 可行域 最优解 求解方法 画 移 求 答 作业 课本P1064 简单的线性规划问题 三 复习回顾 二元一次不等式表示平面区域 直线定界 特殊点定域 简单的线性规划 约束条件 目标函数 可行解 可行域 最优解 求解方法 画 移 求 答 例 要将两种大小不同规格的钢板截成A B C三种规格 每张钢板可同时截得三种规格的小钢板的块数如下表所示 今需要A B C三种规格的成品分别为15 18 27块 问各截这两种钢板多少张可得所需三种规格成品 且使所用钢板张数最少 解 设需截第一种钢板x张 第二种钢板y张 可得 2x y 15 x 3y 27 x 2y 18 x y 0 经过可行域内的整点B 3 9 和C 4 8 且和原点距离最近的直线是x y 12 它们是最优解 答 略 作出一组平行直线z x y 目标函数z x y 打网格线法 在可行域内打出网格线 当直线经过点A时z x y 11 4 但它不是最优整数解 将直线x y 11 4继续向上平移 2x y 15 x 3y 27 x 2y 18 x y 0 直线x y 12经过的整点是B 3 9 和C 4 8 它们是最优解 作出一组平行直线z x y 目标函数z x y 当直线经过点A时z x y 11 4 但它不是最优整数解 作直线x y 12 x y 12 解得交点B C的坐标B 3 9 和C