线性规划习题精选精讲.pdf

习题精选精讲 1 线 性 规 划 常 见 题 型 及 解 法 线 性 规 划 是 新 教 材 中 新 增 的 内 容 之 一 由 已 知 条 件 写 出 约 束 条 件 并 作 出 可 行 域 进 而 通 过 平 移 直 线 在 可 行 域 内 求 线 性 目 标 函 数 的 最 优 解 是 最 常 见 的 题 型 除 此 之 外 还 有 以 下 六 类 常 见 题 型 线 性 规 划 是 新 教 材 中 新 增 的 内 容 之 一 由 已 知 条 件 写 出 约 束 条 件 并 作 出 可 行 域 进 而 通 过 平 移 直 线 在 可 行 域 内 求 线 性 目 标 函 数 的 最 优 解 是 最 常 见 的 题 型 除 此 之 外 还 有 以 下 六 类 常 见 题 型 一 求 线 性 目 标 函 数 的 取 值 范 围 例例 1 若 若 x y 满 足 约 束 条 件满 足 约 束 条 件 2 2 2 x y xy 则 则 z x 2y 的 取 值 范 围 是 的 取 值 范 围 是 A 2 6 B 2 5 C 3 6 D 3 5 解 如 图 作 出 可 行 域 作 直 线解 如 图 作 出 可 行 域 作 直 线 l x 2y 0 将 将 l 向 右 上 方 平 移 过 点向 右 上 方 平 移 过 点 A 2 0 时 有 最 小 值 时 有 最 小 值 2 过 点 过 点 B 2 2 时 有 最 大 值 时 有 最 大 值 6 故 选 故 选 A 二 求 可 行 域 的 面 积 例例2 不 等 式 组 不 等 式 组 260 30 2 xy xy y 表 示 的 平 面 区 域 的 面 积 为 表 示 的 平 面 区 域 的 面 积 为 A 4B 1C 5D 无 穷 大 解 如 图 作 出 可 行 域 无 穷 大 解 如 图 作 出 可 行 域 ABC 的 面 积 即 为 所 求 由 梯 形的 面 积 即 为 所 求 由 梯 形 OMBC 的 面 积的 面 积 减 去 梯 形减 去 梯 形 OMAC 的 面 积 即 可 选的 面 积 即 可 选 B 三 求 可 行 域 中 整 点 个 数 例例 3 满 足 满 足 x y 2 的 点 2 的 点 x y 中 整 点 横 纵 坐 标 都 是 整 数 有 中 整 点 横 纵 坐 标 都 是 整 数 有 A 9 个个B 10 个个C 13 个个D 14 个 解 个 解 x y 2 等 价 于 2 等 价 于 2 0 0 2 0 0 2 0 0 2 0 0 xyxy xyxy xyxy xyxy 作 出 可 行 域 如 右 图 是 正 方 形 内 部 包 括 边 界 容 易 得 到 整 点 个 数作 出 可 行 域 如 右 图 是 正 方 形 内 部 包 括 边 界 容 易 得 到 整 点 个 数 为为 13 个 选个 选 D 四 求 线 性 目 标 函 数 中 参 数 的 取 值 范 围 例例 4 已 知 已 知 x y 满 足 以 下 约 束 条 件满 足 以 下 约 束 条 件 5 50 3 xy xy x 使 使 z x ay a 0 取 得取 得 最 小 值 的 最 优 解 有 无 数 个 则最 小 值 的 最 优 解 有 无 数 个 则 a 的 值 为 的 值 为 A 3B 3C 1D 1 解 如 图 作 出 可 行 域 作 直 线解 如 图 作 出 可 行 域 作 直 线 l x ay 0 要 使 目 标 函 数 要 使 目 标 函 数 z x ay a 0 取 得 最 小 值 的 最 优 解 有 无 数 个 则 将取 得 最 小 值 的 最 优 解 有 无 数 个 则 将 l 向 右 上 方 平 移 后 与 直 线向 右 上 方 平 移 后 与 直 线 x y 5 重 合 故重 合 故 a 1 选 选 D 五 求 非 线 性 目 标 函 数 的 最 值 x y O x y 5 x y 5 0 O y xx 3 x y O2 2 x 2 y 2 x y 2 B A 2x y 6 0 x y 3 0 O y x A B C M y 2 Generated by Foxit PDF Creator Foxit Software For evaluation only 习题精选精讲 2 例例 5 已 知 已 知 x y 满 足 以 下 约 束 条 件满 足 以 下 约 束 条 件 220 240 330 xy xy xy 则 则 z x2 y2的 最 大 值 和 最 小 值 分 别 是 的 最 大 值 和 最 小 值 分 别 是 A 13 1B 13 2 C 13 4 5 D 13 2 5 5 解 如 图 作 出 可 行 域解 如 图 作 出 可 行 域 x2 y 2 是 点 是 点 x y 到 原 点 的 距到 原 点 的 距离 的 平 方 故 最 大 值 为 点 离 的 平 方 故 最 大 值 为 点 A 2 3 到 原 点 的 距 离 的 平 方 即 到 原 点 的 距 离 的 平 方 即 AO 2 13 最 小 值 为 原 点 到 直 线 最 小 值 为 原 点 到 直 线 2x y 2 0 的 距 离 的 平 方 即 为的 距 离 的 平 方 即 为 4 5 选 选 C 六 求 约 束 条 件 中 参 数 的 取 值 范 围 例例 6 已 知 已 知 2x y m 3 表 示 的 平 面 区 域 包 含 点 表 示 的 平 面 区 域 包 含 点 0 0 和 和 1 1 则 则 m 的 取 值 范 围 是 的 取 值 范 围 是 A 3 6 B 0 6 C 0 3 D 3 3 解 解 2x y m 3 等 价 于等 价 于 230 230 xym xym 由 右 图 可 知由 右 图 可 知 33 30 m m 故故 0 m 3 选 选 C 线性规划的实际应用 在科学研究 工程设计 经济管理等方面 我们都会碰到最优化决策的实际问题 而解 决这类问题的理论基础是线性规划 利用线性规划研究的问题 大致可归纳为两种类型 第一种类型是给定一定数量的人力 物力资源 问怎样安排运用这些资源 能使完成的任务量最大 的效益最大 第二种类型是给定一项任务 问怎样统筹安排 能使完成这项任务的 人力 物力资源量最小 例 1 某木器厂生产圆桌和衣柜两种产品 现有两种木料 第一种有 72m3 第二种有 56m3 假设生产每种产品都需要用两种木料 生产一只圆桌和一个衣柜分别所需木料如下表所示 每生产一只圆桌可获利 6 元 生产一个衣柜可获利 10 元 木器厂在现有木料条件下 圆 桌和衣柜各生产多少 才使获得利润最多 产 品 木料 单位 m3 第 一 种第 二 种 圆 桌0 180 08 衣 柜0 090 28 解 设生产圆桌 x 只 生产衣柜 y 个 利润总额为 z 元 那么 0 0 5628 0 08 0 7209 0 18 0 y x yx yx 而 z 6x 10y 如上图所示 作出以上不等式组所表示的平面区域 即可行域 O 2x y 0 y 2x y 3 0 2x y 2 0 x 2y 4 0 3x y 3 0 O y x A Generated by Foxit PDF Creator Foxit Software For evaluation only 习题精选精讲 3 作直线 l 6x 10y 0 即 l 3x 5y 0 把直线 l 向右上方平移至 l1的位置时 直线经过可行域上点 M 且与原点距离最大 此时 z 6x 10y 取最大值 解方程组 5628 0 08 0 7209 0 18 0 yx yx 得 M 点坐标 350 100 答 应生产圆桌 350 只 生产衣柜 100 个 能使利润总额达到最大 指出 资源数量一定 如何安排使用它们 使得效益最好 这是线性规划中常见的问题之一 例 2 某养鸡场有 1 万只鸡 用动物饲料和谷物饲料混合喂养 每天每只鸡平均吃混合饲料 0 5kg 其中动物饲料不能少于谷物饲料的 5 1 动物饲料每千克 0 9 元 谷物饲料每千克 0 28 元 饲料公司每周仅保证供应谷物饲料 50000kg 问饲料怎样混合 才使成本最低 解 设每周需用谷物饲料 x kg 动物饲料 y kg 每周总的饲料费用为 z 元 那么 0 500000 5 1 35000 y x xy yx 而 z 0 28x 0 9y 如下图所示 作出以上不等式组所表示的平面区域 即可行域 作一组平行直线 0 28x 0 9y t 其中经过可行域内的点且和原点最近的直线 经过直线 x y 35000 和直线xy 5 1 的交点 3 17500 3 87500 A 即 3 87500 x 3 17500 y时 饲料费用最低 所以 谷物饲料和动物饲料应按 5 1 的比例混合 此时成本最低 指出 要完成一项确定的任务 如何统筹安排 尽量做到用最少的资源去完成它 这是线性规划中最常见的问题之一 例 3 图 例 4 图 例 3 下表给出甲 乙 丙三种食物的维生素 A B 的含量及成本 甲乙丙 维生素 A 单位 千克 维生素 B 单位 千克 成本 元 千克 400 800 7 600 200 6 400 400 5 营养师想购这三种食物共 10 千克 使之所含维生素 A不少于 4400单位 维生素 B不少于 4800 单位 问三种食物各购多少时 成本最低 最低成本是多少 解 设所购甲 乙两种食物分别为 x 千克 y 千克 则丙种食物为 10 x y 千克 x y 应满足线性条件为 4800 10 400200800 4400 10 400600400 yxyx yxyx 化简得 42 2 yx y 作出可行域如上图中阴影部分 目标函数为 z 7x 6y 5 10 x y 2x y 50 令 m 2x y 作直线 l 2x y 0 则直线2x y m经过可行域中 A 3 2 时 m最小 即 mmin 2 3 2 8 zmin mmin 50 58 答 甲 乙 丙三种食物各购 3 千克 2 千克 5 千克时成本最低 最低成本为 58 元 指出 本题可以不用图解法来解 比如 由 42 2 yx y 得 Generated by Foxit PDF Creator Foxit Software For evaluation only 习题精选精讲 4 z 2x y 50 2x y 2y 50 4 2 2 50 58 当且仅当 y 2 x 3 时取等号 总结 1 设出决策变量 找出线性规划的约束条件和线性目标函数 2 利用图象 在线性约束条件下找出决策变量 使线性目标函数达到最大 或最小 2 线性规划问题的一般数学模型是 已知 nmnmnn mm mm bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 这n个式子中的 也可以是 或 号 其中 aij i 1 2 n j 1 2 m bi i 1 2 n 都是常量 xj j 1 2 m 是非负变量 求 z c1x1 c2x2 cmxm的最大值或最小值 这里 cj j 1 2 m 是常量 3 线性规划的理论和方法主要在以下两类问题中得到应用 一是在人力 物力资金等资源一定的条件下 如何使用它们来完成最多的 任务 二是给一项任务 如何合理安排和规划 能以最少的人力 物力 资金等资源来完成该项任务 线性规划中整点最优解的求解策略线性规划中整点最优解的求解策略 在工程设计 经营管理等活动中 经常会碰到最优化决策的实际问题 而解决此类问题一般以线性规划为其重要的理论基础 然而 在实际问题中 最优解 x y 通常要满足 x y N 这种最优解称为整点最优解 下面通过具体例子谈谈如何求整点最优解 1 平移找解法 平移找解法 作出可行域后 先打网格 描出整点 然后平移直线 l 直线 l 最先经过或最后经过的那个整点便是整点最优解 例 1 某木器厂生产圆桌和衣柜两种产品 现有两种木料 第一种有 72m3 第二种有 56m3 假设生产每种产品都需要用两种木料 生产一只圆桌和一个衣柜分别所需木料如下表所示 每生产一只圆桌可获利 6 元 生产一个衣柜可获利 10 元 木器厂在现有木料条件下 圆 桌和衣柜各生产多少 才使获得利润最多 产 品 木料 单位 m3 第 一 种第 二 种 圆 桌0 180 08 衣 柜0 090 28 解 设 生 产 圆 桌 x 只 生 产 衣 柜 y 个 利 润 总 额 为 z 元 那 么 0 0 5628 0 08 0 7209 0 18 0 y x yx yx 而 z 6x 10y 如图所示 作出以上不等式组所表示的平面区域 即可行域 作直线 l 6x 10y 0 即 l 3x 5y 0 把直线 l 向右上方平移至 l1的位置时 直线经过可行域上点 M 且与原点距离最大 此时 z 6x 10y 取最 大值 解方程组 5628 0 08 0 7209 0 18 0 yx yx 得 M 点坐标 350 100 答 应生产圆桌 350 只 生产衣柜 100 个 能使利润总额达到最 大 点评 点评 本题的最优点恰为直线 0 18x 0 09y 72 和 0 08x 0 28y 56 的交点 M 例 2 有一批钢管 长度都是 4000mm 要截成 500mm 和 600mm 两种毛坯 且这两种毛坯按数量比不小于 3 1 配套 怎样截最合理 解 解 设截 500mm 的钢管 x 根 600mm 的 y 根 总数 为 z 根 根据题意 得 目标函数 为 作出如图所示的可行域内的整点 Generated by Foxit PDF Creator Foxit Software For evaluation only 习题精选精讲 5 作一组平行直线 x y t 经过可行域内的点且和原点距离最远的直线为过 B 8 0 的直线 这时 x y 8 由于 x y 为正整数 知 8 0 不是最优解 显然要往下平移该直线 在可行域内找整点 使 x y 7 可知点 2 5 3 4 4 3 5 2 6 1 均为最 优解 答 略 点评 点评 本题与上题的不同之处在于 直线 x y t 经过可行域内且和原点距离最远的点 B 8 0 并不符合题意 此时必须往下平移 该直线 在可行域内找整点 比如使 x y 7 从而求得最优解 从这两例也可看到 平移找解法一般适用于其可行域是有限区域且整点个数又较少 但作图要求较高 二 整点调整法二 整点调整法 先按 平移找解法 求出非整点最优解及最优值 再借助不定方程的知识调整最优值 最后筛选出整点最优解 例 3 已知 x y满足不等式组 230 2360 35150 xy xy xy 求使xy 取最大值的整数 x y 解 不等式组的解集为三直线 1 l 230 xy 2 l 2360 xy 3 l 35150 xy 所围成的三角形内部 不含边界 设 1 l与 2 l 1 l与 3 l 2 l与 3 l交点分别为 A B C 则 A B C坐标分别为 15 3 84 A 0 3 B 7512 1919 C 作一组平行线l xyt 平行于 0 l 0 xy 当l往 0 l右上方移动时 t随之增大 当l过C点时xy 最大为 63 19 但不是整数解 又由 75 0 19 x 知x可取1 2 3 当1x 时 代入原不等式组得2y 1xy 当2x 时 得0y 或1 2xy 或1 当3x 时 1y 2xy 故xy 的最大整数解为 2 0 x y 或 3 1 x y 3 逐一检验法逐一检验法 由于作图有时有误差 有时仅有图象不一定就能准确而迅速地找到最优解 此时可将若干个可能解逐一校验即可见分晓 例 4 一批长 4000mm 的条形钢材 需要将其截成长分别为 518mm 与 698mm 的甲 乙两种毛坯 求钢材的最大利用率 解 设甲种毛坯截 x 根 乙种毛坯截 y 根 钢材的利用率为 P 则 目标函数为 线性约束条件 表示的可行域是图中 阴影部分的整点 表示与直线 518x 698y 4000 平行的直线系 所以 使 P 取得最大值的最优解是阴影内最靠近直线 518x 698y 4000 的整点 坐标 如图看到 0 5 1 4 2 4 3 3 4 2 5 2 6 1 7 0 都有可能是最优解 将它们的坐标逐一代入 进行校验 可知当 x 5 y 2 时 答 当甲种毛坯截 5 根 乙种毛坯截 2 根 钢材的利用率最大 为 99 65 解线性规划问题的关键步骤是在图 可行域 上完成的 所以作图时 应尽可能精确 图上操作尽可能规范 但考虑到作图时必然会有误差 假如图上的最优点并不十分明显易辨时 不妨将几个有可能是最 优点的坐标都求出来 然后逐一进行校验 以确定整点最优解 A B C x y O 1 l 3 l 2 l Generated by Foxit PDF Creator Foxit Software For evaluation only 习题精选精讲 6 线性规划的实际应用 习题精选线性规划的实际应用 习题精选 1 某家俱公司生产甲 乙两种型号的组合柜 每种柜的制造白坯时间 油漆时间及有关数据如下 问该公司如何安排这两种产品的生产 才能获得最大的利润 最大利润是多少 2 要将两种大小不同的钢板截成 A B C 三种规格 每张钢板可同时截得三种规格小钢板的块数如下 每张钢板的面积 第一种为 1m 2 第二种为 2m2 今需要 A B C 三种规格的成品各 12 15 17 块 问各截这两种钢板多少张 可 得所需三种规格成品 且使所用钢板面积最小 3 某人承揽一项业务 需做文字标牌 2 个 绘画标牌 3 个 现有两种规格的原料 甲种规格每张 3m 2 可做文字标牌 1 个 绘画 标牌 2 个 乙种规格每张 2m 2 可做文字标牌 2 个 绘画标牌 1 个 求两种规格的原料各用多少张 才能使总的用料面积最小 4 某蔬菜收购点租用车辆 将 100 吨新鲜黄瓜运往某市销售 可供租用的大卡车和农用车分别为 10 辆和 20 辆 若每辆卡车载重 8 吨 运费 960 元 每辆农用车载重 2 5 吨 运费 360 元 问两种车各租多少辆时 可全部运完黄瓜 且动费最低 并求出最低运费 5 某木器厂生产圆桌和衣柜两种产品 现有两种木料 第一种有 72 立方米 第二种有 56 立方米 假设生产每种产品都需要两种 木料 生产一只圆桌需用第一种木料 0 18 立方米 第二种木料 0 08 立方米 可获利润 60 元 生产一个衣柜需用第一种木料 0 09 立方 米 第二种 0 28 立方米 可获利润 100 元 木器厂在现有木料情况下 圆桌和衣柜应各生产多少 才能使所获利润最多 解答提示 解答提示 1 设 x y 分别为甲 乙两种柜的日产量 目标函数 z 200 x 240y 线性约束条件 Generated by Foxit PDF Creator Foxit So