线性规划(二一).ppt

简单的线性规划 二 内蒙古第二地质中学 冯彬 问题的提出 x 4y 3 0 3x 5y 25 0 x 1 x y O 求的最大值和最小值 2x y 0 A 5 2 B 1 1 线性规划的有关定义 1 对于变量x y的约束条件 都是关于x y的一次不等式 称为线性约束条件 z f x y 是欲达到最值所涉及的变量x y的解析式 叫做目标函数 当f x y 是关于x y的一次解析式时 z f x y 叫做线性目标函数 2 求线性目标函数在约束条件下的最值问题称为线性规划问题 满足线性约束条件的解 x y 称为可行解 由所有解组成的集合叫可行域 使目标函数取得最值的可行解叫最优解 返回 求Z的最大值和最小值 1 例1 设 式中变量满足下列条件 求的最大值 x O A 3 7 y 求的最大值 x y O A 3 7 1 x y O A 3 7 1 x O A 3 7 y 1 将 0 1 代入2y x 即2 1 0 2 0说明越向左上移动 z的值越大所以z的最大值在点A 3 7 处得到此时z 2 7 3 11 练习 变量x y满足线性约束条件 1 求z 2x 7y的最大值与最小值 2 求z 2x y的最大值与最小值 3 求z y 2x的最大值和最小值 x 2y 5 0 3x y 5 0 2x y 5 0 A 3 4 B 2 1 C 1 3 1 z 2x 7y在B点最大 在A点最小2 z 2x y在A点最大 在线段BC上的所有点最小 x y 2x 7y 0 2x y 0 O 3 z y 2x在C点最大 在B点最小 y 2x 0 注意 1 线性目标函数的最大值 最小值一般在可行域的顶点处取得 2 线性目标函数的最大值 最小值也可在可行域的边界上取得 即满足条件的最优解有无数多个 例2 要将两种大小不同规格的钢板截成A B C三种规格 每张钢板可同时截得三种规格的小钢板的块数如下表所示 解 设需截第一种钢板x张 第二种钢板y张 则 作出可行域 如图 目标函数为z x y 今需要A B C三种规格的成品分别为15 18 27块 问各截这两种钢板多少张可得所需三种规格成品 且使所用钢板张数最少 例题分析 2x y 15 x 3y 27 x 2y 18 x y 0 经过可行域内的整点B 3 9 和C 4 8 且和原点距离最近的直线是x y 12 它们是最优解 答 略 作出一组平行直线t x y 目标函数z x y 打网格线法 在可行域内打出网格线 当直线经过点A时t x y 11 4 但它不是最优整数解 将直线x y 11 4继续向上平移 7 5 15 18 27 9 经过可行域内的整点B 3 9 和C 4 8 且和原点距离最近的直线是x y 12 它们是最优解 例题分析 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 D的坐标B 3 9 和D 4 5 7 5 调整优值法 7 5 15 18 27 9 分析 将已知数据列成下表 设生产甲 乙两种产品 分别为x吨 y吨 利润总额为z元 那么 z 600 x 1000y 解 设生产甲 乙两种产品 分别为x吨 y吨 利润总额为z元 那么 作出以上不等式组所表示的可行域 作出一组平行直线600 x 1000y t 10 x 4y 300 5x 4y 200 4x 9y 360 600 x 1000y 0 M 答 略 12 4 34 4 经过可行域上的点M时 目标函数在y轴上截距最大 此时z 600 x 1000y取得最大值 平移找解法 90 40 30 40 50 75 x y x y 0 x y 4 x 1 1 1 2 2 1 3 练习 已知变量x y满足约束条件1 x y 4 2 x y 2 若目标函数z ax y 其中a 0 仅在点 3 1 处取得最大值 则a的取值范围为 3 1 x y O x y 2 x y 2 x y 1 x y 4 a 1 4a 2b 0 设函数f x ax2 bx满足 1 f 1 2 2 f 1 4 求f 2 的范围 解 由已知条件得 f 2 4a 2b 4 3 2 1 10 故 a A 3 1 b a b 2 a b 4 a b 1 a b 2 O 解线性规划问题的步骤 2 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且取得最大值或最小值的直线 3 求 通过解方程组求出最优解 4 答 作出答案 小结 1 画 画出线性约束条件所表示的可行域 解 设每天应配制甲种饮料x杯 乙种饮料y杯 咖啡