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

《线性规划习题精选精讲.pdf》由会员分享，可在线阅读，更多相关《线性规划习题精选精讲.pdf（9页珍藏版）》请在三一文库上搜索。

1、习题精选精讲 1 线性 规划 常 见题 型 及解 法 线 性 规 划 是 新 教 材 中 新 增 的 内 容 之 一 ， 由 已 知 条 件 写 出 约 束 条 件 ， 并 作 出 可 行 域 ， 进 而 通 过 平 移 直 线 在 可 行 域 内 求 线 性 目 标 函 数 的 最 优 解 是 最 常 见 的 题 型 ， 除 此 之 外 ， 还 有 以 下 六 类 常 见 题 型 。 一 、 求 线 性 目 标 函 数 的 取 值 范 围 例 1、若x、 y 满 足 约 束 条 件 2 2 2 x y xy ， 则z=x +2 y 的 取 值 范 围 是（） A 、 2, 6 B、 2, 5

2、 C、 3, 6D 、 （ 3, 5 解 ： 如 图 ， 作 出 可 行 域 ， 作 直 线l： x+2 y 0， 将 l 向 右 上 方 平 移 ， 过 点 A（ 2,0 ） 时 ， 有 最 小 值 2， 过 点B（ 2, 2） 时 ， 有 最 大 值6， 故 选 A 二 、 求 可 行 域 的 面 积 例2、 不 等 式 组 260 30 2 xy xy y 表 示 的 平 面 区 域 的 面 积 为（） A、 4B、 1C、 5D 、 无 穷 大 解 ： 如 图 ， 作 出 可 行 域 ， ABC的 面 积 即 为 所 求 ， 由 梯 形O MBC的 面 积 减 去 梯 形O M AC

3、的 面 积 即 可 ， 选B 三 、 求 可 行 域 中 整 点 个 数 例3、满 足 |x| |y| 2 的 点（ x，y）中 整 点（ 横 纵 坐 标 都 是 整 数 ）有（） A、 9 个B、 10 个C 、 13 个D 、 14 个 解 ： |x| |y| 2 等 价 于 2(0,0) 2(0,0) 2(0,0) 2(0,0) xyxy xyxy xyxy xyxy 作 出 可 行 域 如 右 图 ， 是 正 方 形 内 部 （ 包 括 边 界 ） ，容 易 得 到 整 点 个 数 为 1 3 个 ， 选D 四 、 求 线 性 目 标 函 数 中 参 数 的 取 值 范 围 例4、 已

4、 知x、 y 满 足 以 下 约 束 条 件 5 50 3 xy xy x ， 使z=x +a y( a0 ) 取 得 最 小 值 的 最 优 解 有 无 数 个 ， 则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 x x=3 x y O 2 2 x

5、=2 y =2 x + y =2 B A 2x + y 6= 0 = 5 xy 3 = 0 O y x A B C M y =2 习题精选精讲 2 五 、 求 非 线 性 目 标 函 数 的 最 值 例5、 已 知x、 y 满 足 以 下 约 束 条 件 220 240 330 xy xy xy ， 则 z=x 2 +y 2 的 最 大 值 和 最 小 值 分 别 是（） A、 13， 1B、 13， 2 C、 13， 4 5 D 、13， 25 5 解 ： 如 图 ， 作 出 可 行 域 ,x 2 +y 2 是 点 （ x， y） 到 原 点 的 距离 的 平 方 ，故 最 大 值 为 点A

6、 （ 2, 3） 到 原 点 的 距 离 的 平 方 ， 即 |AO | 2 =1 3，最 小值 为 原 点 到 直 线 2x y 2= 0 的 距 离 的 平 方 ， 即 为 4 5 ， 选 C 六 、 求 约 束 条 件 中 参 数 的 取 值 范 围 例6、 已 知 |2 x 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 由 右 图 可 知

7、33 30 m m ,故0 m 3， 选C 线性规划的实际应用 在科学研究、工程设计、经济管理等方面，我们都会碰到最优化决策的实际问题，而解 决这类问题的理论基础是线性规划。利用线性规划研究的问题，大致可归纳为两种类型：第一种类型是给定一定数量的人力、物力资源， 问怎样安排运用这些资源，能使完成的任务量最大，的效益最大，第二种类型是给定一项任务，问怎样统筹安排，能使完成这项任务的 人力、物力资源量最小。 例 1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有 56m3，假设生产每种产品都需要用两种木料， 生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获

8、利6 元,生产一个衣柜可获利10 元.木器厂在现有木料条件下,圆 桌和衣柜各生产多少,才使获得利润最多? 产 品 木料 (单位 m3) 第 一 种第 二 种 圆 桌0.18 0.08 衣 柜0.09 0.28 解：设生产圆桌x 只,生产衣柜 y 个,利润总额为z 元,那么 0 0 5628.008.0 7209.018.0 y x yx yx 而 z=6x+10y. O 2x y = 0 y 2x y + 3 = 0 2x + y - 2= 0 = 5 x 2y + 4 = 0 3x y 3 = 0 O y x A 习题精选精讲 3 如上图所示 ,作出以上不等式组所表示的平面区域,即可行域 .

9、 作直线 l:6x+10y=0,即 l:3x+5y=0,把直线 l 向右上方平移至l1的位置时 ,直线经过可行域上点M, 且与原点距离最大,此时 z=6x+10y 取最大值 解方程组 5628.008.0 7209.018.0 yx yx ,得 M 点坐标 (350,100).答:应生产圆桌350 只,生产衣柜 100 个,能使利润总额达到最大. 指出 :资源数量一定 ,如何安排使用它们,使得效益最好 ,这是线性规划中常见的问题之一 例 2、 某养鸡场有 1 万只鸡 ,用动物饲料和谷物饲料混合喂养.每天每只鸡平均吃混合饲料0.5kg,其中动物饲料不能少于谷物饲料的 5 1 . 动物饲料每千克0

10、.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时,饲料费

11、用最低 . 所以 ,谷物饲料和动物饲料应按5:1 的比例混合 ,此时成本最低 . 指出 :要完成一项确定的任务,如何统筹安排 ,尽量做到用最少的资源去完成它,这是线性规划中最常见的问题之一. (例 3 图) (例 4 图) 例 3、下表给出甲、乙、丙三种食物的维生素A、B 的含量及成本 : 甲乙丙 维生素 A(单位 /千克 ) 维生素 B(单位 /千克 ) 成本 (元/千克 ) 400 800 7 600 200 6 400 400 5 营养师想购这三种食物共10千克 ,使之所含维生素A 不少于 4400 单位 ,维生素 B 不少于 4800单位 ,问三种食物各购多少时,成本最低 ? 最低成本

12、是多少? 解:设所购甲、乙两种食物分别为x 千克、 y 千克 ,则丙种食物为 (10 x y)千克 .x、y 应满足线性条件为 习题精选精讲 4 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 千克时成本最低

13、,最低成本为58 元. 指出 :本题可以不用图解法来解,比如 ,由 42 2 yx y 得 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,

14、,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)线性规划的理论和方法主要在以下两类问题中得到应用:一是在人力、 物力资金等资源一定的条件下,如何使用它们来完成最多的 任务；二是给一项任务,如何合理安排和规划,能以最少的人力、物力、资金等资源来完成该项任务. 线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中，经常会碰到最优化决策的实际问题，而解决此类问题一般以线性规划为其重要的理论基础。然而 在实际问题中，最优解

15、(x,y) 通常要满足x,yN ，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解. 1平移找解法 作出可行域后，先打网格，描出整点，然后平移直线l，直线 l 最先经过或最后经过的那个整点便是整点最优解. 例 1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有 56m3，假设生产每种产品都需要用两种木料， 生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6 元,生产一个衣柜可获利10 元.木器厂在现有木料条件下,圆 桌和衣柜各生产多少,才使获得利润最多? 产 品 木料(单位 m3) 第 一 种第 二 种 圆 桌0.18 0.08 衣 柜

16、 0.09 0.28 解 ： 设 生 产 圆 桌x只 , 生 产 衣 柜y个 , 利 润 总 额 为z元 ,那 么 0 0 5628.008.0 7209.018.0 y x yx yx 而 z=6x+10y.如图所示 ,作出以上不等式组所表示的平面区域,即可行域 . 作直线 l:6x+10y=0,即 l:3x+5y=0,把直线 l 向右上方平移至l1的位置时 ,直线经过可行域上点M, 且与原点距离最大,此时 z=6x+10y 取最 大值。解方程组 5628.008.0 7209.018.0 yx yx ,得 M 点坐标 (350,100).答：应生产圆桌350 只,生产衣柜100 个,能使利

17、润总额达到最 大.点评： 本题的最优点恰为直线0.18x+0.09y=72 和 0.08x+0.28y=56 的交点 M。 习题精选精讲 5 例 2 有一批钢管，长度都是4000mm ，要截成 500mm 和 600mm 两种毛坯，且这两种毛坯按数量比不小于 3 1 配套，怎样截最合理？ 解： 设截 500mm 的钢管 x 根， 600mm 的 y 根，总数 为 z 根。根据题意， 得，目标函数 为， 作出如图所示的可行域内的整点， 作一组平行直线x+y=t ，经过可行域内的点且和原点距离最远的直线为过B（8，0）的直线，这时x+y=8. 由于 x,y 为正整数，知（ 8， 0）不是最优解。显

18、然要往下平移该直线，在可行域内找整点，使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

19、35150 xy xy xy ，求使xy取最大值的整数,x y 解：不等式组的解 集为三直线 1 l：230xy， 2 l：2360xy， 3 l： 35150xy所围成的三角形内部（不含边界），设 1 l与 2 l， 1 l与 3 l， 2 l与 3 l交点分别为 ,A B C ，则 ,A B C 坐标分别为 153 (,) 84 A， (0,3)B ， 7512 (,) 1919 C， 作一组平行线l：xyt平行于 0 l：0xy，当l往 0 l右上方移动时，t随之增大， 当l过C点时xy最大为 63 19 ，但不是整数解，又由 75 0 19 x 知x可取1, 2, 3， 当1x时，代入

20、原不等式组得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 ，则 ，目标函数为 A B Cx y O 1 l 3 l 2 l 习题精选精讲 6 ，线性约束条件 表示的可行域是图中阴影部分的整点

21、表示与直线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% 解线性规划问题的关键步骤是在图（可行域）上完成的，所以作图时应尽可能精确，图上操作尽可能规范，但考虑到作图时必然会 有误差，假如图上的最优点并不十分明显易辨时，不妨将几个有可能是最优点的坐标都求出来，

22、然后逐一进行校验，以确定整点最优解. 线性规划的实际应用习题精选 1 某家俱公司生产甲、乙两种型号的组合柜，每种柜的制造白坯时间、油漆时间及有关数据如下： 问该公司如何安排这两种产品的生产，才能获得最大的利润最大利润是多少？ 2 要将两种大小不同的钢板截成A、B 、C三种规格，每张钢板可同时截得三种规格小钢板的块数如下： 每张钢板的面积，第一种为1m 2，第二种为 2m 2，今需要 A、B、C 三种规格的成品各 12，15，17 块，问各截这两种钢板多少张，可 得所需三种规格成品，且使所用钢板面积最小 3 某人承揽一项业务，需做文字标牌2 个，绘画标牌3 个，现有两种规格的原料，甲种规格每张3

23、m 2，可做文字标牌 1 个，绘画 标牌 2 个，乙种规格每张2m 2，可做文字标牌 2 个，绘画标牌1 个，求两种规格的原料各用多少张，才能使总的用料面积最小 4 某蔬菜收购点租用车辆，将100 吨新鲜黄瓜运往某市销售，可供租用的大卡车和农用车分别为10 辆和 20 辆，若每辆卡车载重 8 吨，运费 960 元，每辆农用车载重2.5 吨，运费 360 元，问两种车各租多少辆时，可全部运完黄瓜，且动费最低并求出最低运费 5 某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72 立方米，第二种有56立方米，假设生产每种产品都需要两种 木料生产一只圆桌需用第一种木料0.18 立方米，第二种木

24、料0.08 立方米，可获利润60 元，生产一个衣柜需用第一种木料0.09 立方 米，第二种0.28 立方米，可获利润100 元，木器厂在现有木料情况下，圆桌和衣柜应各生产多少，才能使所获利润最多 解答提示： 1设 x，y 分别为甲、乙两种柜的日产量， 习题精选精讲 7 目标函数 z=200x240y，线性约束条件： 作出可行域 z最大=20042408=2720 答：该公司安排甲、乙两种柜的日产量分别为4 台和 8 台，可获最大利润2720 元 2 设需截第一种钢板x 张，第二种钢板y 张，所用钢板面积zm 2 目标函数 z=x2y，线性约束条件： 作出可行域作一组平行直线x2y=t 的整点中

25、，点 (4 ，8) 使 z 取得最小值 答：应截第一种钢板4 张，第二种钢板8 张，能得所需三种规格的钢板，且使所用钢板的面积最小 3 设用甲种规格原料x 张，乙种规格原料y 张，所用原料的总面积是zm 2，目标函数 z=3x2y， 习题精选精讲 8 线性约束条件， 作出可行域作一组平等直线3x2y=t A 不是整点， A不是最优解在可行域内的整点中，点B(1，1)使 z 取得最小值 z最小=3121=5， 答：用甲种规格的原料1 张，乙种原料的原料1 张，可使所用原料的总面积最小为5m 2 4 设租用大卡车x 辆，农用车y 辆，最低运费为z 元 z=960x360y 线性约束条件是： 作出可行域 作直线 960x360y=0即 8x3y=0，向上平移至过点B(10，8)时， z=960x360y 取到最小值 z最小=960103608=12480 答：大卡车租10辆，农用车租8 辆时运费最低，最低运费为12480 元 5 设圆桌和衣柜的生产件数分别为x、y，所获利润为z，则 z=6x10y 习题精选精讲 9 作出可行域 即 M(350，100) 当直线 6x10y=0 即 3x5y=0 平移到经过点M(350，100) 时， z=6x 10y 最大