简单的线性规划3

《简单的线性规划3》由会员分享，可在线阅读，更多相关《简单的线性规划3（20页珍藏版）》请在金锄头文库上搜索。

1、xyo线性规划的简单应用 使z=2x+y取得最大值的可行解为 ，且最大值为 ；复习引入1.已知二元一次不等式组x-y0 x+y-10 y-1（1）画出不等式组所表示的平面区域；满足 的解(x,y)都叫做可行解；z=2x+y 叫做 ；（2）设z=2x+y，则式中变量x,y满足的二元一次不等式组叫做x,y的 ；y=-1x-y=0x+y=12x+y=0返回(-1,-1)(2,-1)使z=2x+y取得最小值的可行解 ，且最小值为 ；这两个最值都叫做问题的 。线性约束条件线性目标函数线性约束条件(2,-1)(-1,-1)3-3最优解xy011例题分析1:某工厂生产甲、乙两种产品.已知生产甲种产品1t需消

2、耗 A种矿石10t、B种矿石5t、煤4t；生产乙种产品1吨需消耗A 种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是600元, 每1t乙种产品的利润是1000元.工厂在生产这两种产品的计 划中要求消耗A种矿石不超过300t、消耗B种矿石不超过 200t、消耗煤不超过360t.甲、乙两种产品应各生产多少(精 确到0.1t),能使利润总额达到最大?甲产产品（1t）乙产产品（1t）资资源限额额（t） A种矿矿石（t） B种矿矿石（t） 煤（t） 利润润（元） 产品消耗量 资源列表：5104 6004 4 9 1000300 200 360设生产甲、乙两种产品.分别为x t、yt,利润总额为z

3、元例题分析甲产产品（1t）乙产产品（1t）资资源限额额（t） A种矿矿石（t） B种矿矿石（t） 煤（t） 利润润（元） 产品消耗量资源列表：51046004 4 9 1000300200 360把题中限制条件进行转化：约束条件10x+4y300 5x+4y200 4x+9y360 x0 y 0z=600x+1000y. 目标函数：设生产甲、乙两种产品.分别为x t、yt,利润总额为z元xtyt例题分析解:设生产甲、乙两种产品.分别为x t、yt,利润总额为z=600x+1000y. 元, 那么10x+4y300 5x+4y200 4x+9y360 x0 y 0 z=600x+1000y. 作

4、出以上不等式组所表示的可行域作出一组平行直线 600x+1000y=t，解得交点M的坐标为(12.4,34.4)5x+4y=2004x+9y=360由10x+4y=3005x+4y=2004x+9y=360600x+1000y=0M答:应生产甲产品约12.4吨，乙产品34.4吨，能使利润总额达到最大 。(12.4,34.4)经过可行域上的点M时,目标函数 在y轴上截距最大. 90300 xy10 2010754050 40此时z=600x+1000y取得最大值.例题分析2 要将两种大小不同规格的钢板截成A、B、C三种规格，每 张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：设需截第一

5、种钢板x张，第一种钢板y张，则 规格类型 钢板类型第一种钢板第二种钢板A规格B规格C规格2121312x+y15,x+2y18, x+3y27, x0 y0 作出可行域（如图）目标函数为 z=x+y今需要A,B,C三种规格的成品分别为15，18，27块，问 各截这两种钢板多少张可得所需三种规格成品，且使所 用钢板张数最少。X张y张例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18, x+3y27, x0, xN y0 yN直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解. 作出一组平行直线z=x+y ，目标函数z= x+yB(3,

6、9) C(4,8) A(18/5,39/5)当直线经过点A时z=x+y=11.4,x+y=12解得交点B,C的坐标B(3,9)和C(4,8)调整优值法2 4 6181282724681015但它不是最优整数解.作直线x+y=12答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18, x+3y27, x0, xN* y0 yN*经过可行域内的整点B(3,9)和C(4,8)时，t=x+y=12是最优解.答:(略)作出一组平行直线t = x+y，目标函数t = x+yB(3,9) C(4,8) A(18/5,39/5)打网格线法在可行域内打出网格线，

7、当直线经过点A时t=x+y=11.4,但它不是最优整数解 ， 将直线x+y=11.4继续向上平移，1212 182715978不等式组 表示的平面区域内的整数点共有（ ）个巩固练习1:1 2 3 4 xy432104x+3y=12在可行域内找出最优解、线性规划整数 解问题的一般方法是：1.若区域“顶点”处恰好为整点，那么它就是最优解；（ 在包括边界的情况下） 2.若区域“顶点”不是整点或不包括边界时，应先求出该 点坐标，并计算目标函数值Z，然后在可行域内适当放 缩目标函数值，使它为整数，且与Z最接近，在这条对 应的直线中，取可行域内整点，如果没有整点，继续放 缩，直至取到整点为止。 3.在可行

8、域内找整数解，一般采用平移找解法，即打网 络、找整点、平移直线、找出整数最优解解线性规划应用问题的一般步骤：2）设好变元并列出不等式组和目标函数3）由二元一次不等式表示的平面区域做出可行域；4）在可行域内求目标函数的最优解1）理清题意，列出表格：5)还原成实际问题 (准确作图，准确计算)咖啡馆配制两种饮料甲种饮料每杯含奶粉9g 、咖啡4g、 糖3g,乙种饮料每杯含奶粉4g 、咖啡5g、糖10g已知每天 原料的使用限额为奶粉3600g ，咖啡2000g 糖3000g,如果 甲种饮料每杯能获利0.7元，乙种饮料每杯能获利1.2元，每 天在原料的使用限额内饮料能全部售出，每天应配制两种 饮料各多少杯

9、能获利最大？ 解：将已知数据列为下表：消耗量 资源甲产品（ 1 杯）乙产品(1 杯)资源限额（g ）奶粉（g ）943600咖啡(g)452000糖(g)3103000利润（元 ）0.71.2 产品设每天应配制甲种饮料x杯，乙种饮料y杯，则作出可行域： 目标函数为：z =0.7x +1.2y 作直线l:0.7x+1.2y=0， 把直线l向右上方平移至l1的位置 时， 直线经过可行域上的点C，且与原 点距离最大， 此时z =0.7x +1.2y取最大值 解方程组 得点C的坐标为（200，240）_0_ 9 x + 4 y = 3600_ C (200,240)_ 4 x + 5 y = 2000

10、_ 3 x + 10 y = 3000_ 7 x + 12 y = 0_ 400_ 400_ 300_ 500_ 1000_ 900_ 0_ x_ y二元一次不等式 表示平面区域直线定界， 特殊点定域简单的线性规划约束条件目标函数可行解可行域最优解应用求解方法：画、 移、求、答练习巩固1.某家具厂有方木材90m3，木工板600m3，准备加工成 书桌和书橱出售，已知生产每张书桌需要方木料0.1m3 、木工板2m3；生产每个书橱需要方木料0.2m3，木工板 1m3，出售一张书桌可以获利80元，出售一张书橱可以 获利120元；（1）怎样安排生产可以获利最大？（2）若只生产书桌可以获利多少？（3）若只

11、生产书橱可以获利多少？由上表可知：（1）只生产书桌，用完木工板了，可生产书桌 6002=300张, 可获利润:80300=24000元,但木料没有用完 （2）只生产书橱，用完方木料，可生产书橱900.2=450 张,可 获利润120450=54000元,但木工板没有用完产品资源书桌（张） 书橱（张） 资源限额m 3方木料 m 3010290木工板m 321600利润 （元）80120分析：xy02x+y-600=0300600x+2y-900=0A(100,400)1.某家具厂有方木材90m3，木工板600m3，准备加工成书桌和书橱出售， 已知生产每张书桌需要方木料0.1m3、木工板2m3；生

12、产每个书橱需要方木 料0.2m3，木工板1m3，出售一张书桌可以获利80元，出售一张书橱可以获 利120元； （1）怎样安排生产可以获利最大？ （2）若只生产书桌可以获利多少？ （3）若只生产书橱可以获利多少？（1）设生产书桌x张，书橱y张，利 润为z元， 则约束条件为 0.1x+0.2y90 2x+y600 x，yN* Z=80x+120y 作出不等式表示的平面区域，当生产100张书桌，400张书橱时利润最大为 z=80100+120400=56000元（2）若只生产书桌可以生产300张，用完木工板，可获利 24000元；（3）若只生产书橱可以生产450张，用完方木料，可获利54000元。将

13、直线z=80x+120y平移可知：900450求解：Xy084x=8y=476543213 2 1x+y=104x+5y=30320x+504y=02.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资 的任务，该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨 的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车 4次，B型卡车3次，每辆卡车每天往返的成本费A型卡车为320元 ，B型卡车为504元，问如何安排车辆才能使该公司所花的成本费 最低，最低为多少元？(要求每型卡车至少安排一辆） 解：设每天调出的A型车x辆 ，B型车y辆，公司所花的费用 为z元，则x8y4 x+y10x,yN*4x+5y30Z=320x+504y作出可行域中的整点 ，可行域中的整点（5，2）使Z=320x+504y取得最 小值，且Zmin=2608元作出可行域2.附加练习深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥 制品1吨，需矿石4吨，煤3吨；生产乙种水泥制品1吨，需矿 石5吨，煤10吨，每1吨甲种水泥制品的利润为7万元，每1吨 乙种水泥制品的利润是12万元，工厂在生产这两种水泥制品 的计划中，要求消耗的矿石不超过200吨，煤不超过300吨， 甲乙两种水泥制品应生产多少，能使利润达到最大值？