(三)简单的线性规划问题

问题:设P=2x+y,式中变量x、y满足下列条件,求P的最大值和最小值。

首先,作出线性约束条件所表示的平面区域,这一区域称为可行区域;

其次,考虑目标P=2x+y的几何意义;

第三,设P=0,画出直线;观察、分析,平移直线,从而找到最优解;

最后,求得目标函数的最大值及最小值。

1. 基本概念:目标函数,线性目标函数线性规划问题,可行解,可行域,最优解:

诸如上述问题中,不等式组是一组对变量x、y的约束条件,由于这组约束条件都是关于x、y的一次不等式,所以又可称其为线性约束条件。P=2x+y是欲达到最大值或最小值所涉及的变量x、y的解析式,我们把它称为目标函数。由于P=2x+y又是关于x、y的一次解析式,所以又可叫做线性目标函数。

一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。那么,满足线性约束条件的解(x,y)叫做可行解,由所有可行解组成的集合叫做可行域。在上述问题中,可行域就是阴影部分表示的三角形区域。其中可行解(5,2)和(1,1)分别使目标函数取得最大值和最小值,它们都叫做这个问题的最优解。

2. 求线性目标函数在线性约束条件下的最优解的格式与步骤:

(1)寻找线性约束条件,线性目标函数;

(2)由二元一次不等式表示的平面区域做出可行域;

(3)在可行域内求目标函数的最优解。

[典型例题]

例1. 已知x、y满足不等式组,试求z=300x+900y取最大值时的整点的坐标,及相应的z的最大值。

分析:先画出平面区域,然后在平面区域内寻找使z=300x+900y取最大值时的整点。

解:如图所示平面区域AOBC,点A(0,125),点B(150,0),点C的坐标由方程组

得C(),

令t=300x+900y,

即y=-

欲求z=300x+900y的最大值,即转化为求截距的最大值,从而可求t的最大值,  因直线y=-与直线y=-x平行,故作y=-x的平行线,当过点A(0,125)时,对应的直线的截距最大,所以此时整点A使z取最大值,zmax=300×0+900×125=112500。

例2. 求z=600x+300y的最大值,使式中的x,y满足约束条件的整数值。

分析:画出约束条件表示的平面区域即可行域再解。

解:可行域如图所示:

四边形AOBC,易求点A(0,126),B(100,0)由方程组:

得点C的坐标为(69,91)

因题设条件要求整点(x,y)使z=600x+300y取最大值,将点(69,91),(70,90)代入z=600x+300y,可知当时,z取最大值为zmax=600×70+300×900=69000。

例3. 已知x、y满足不等式,求z=3x+y的最小值。

分析:可先找出可行域,平行移动直线:3x+y=0,找出可行解,进而求出目标函数的最小值。

解:不等式x+2y≥2,表示直线x+2y=2上及右上方的点的集合;

不等式2x+y≥1表示直线2x+y=1上及右上方的点的集合。

可行域如图所示:

作直线:3x+y=0,作一组与直线平行的直线:3x+y=t,(t∈R)。

∵x、y是上面不等式组表示的区域内的点的坐标。

由图可知:

当直线:3x+y=t通过P(0,1)时,t取到最小值1,即zmin=1。

评述:简单线性规划问题就是求线性目标函数在线性约束条件下的最优解,无论此类题目是以什么实际问题提出,其求解的格式与步骤是不变的:

(1)寻找线性约束条件,线性目标函数;

(2)由二元一次不等式表示的平面区域做出可行域;

例4. 已知甲、乙两煤矿每年的产量分别为200万吨和300万吨,需经过东车站和西车站两个车站运往外地。东车站每年最多能运280万吨煤,西车站每年最多能运360万吨煤,甲煤矿运往东车站和西车站的运费价格分别为1元/吨和1.5元/吨,乙煤矿运往东车站和西车站的运费价格分别为0.8元/吨和1.6元/吨。煤矿应怎样编制调运方案,能使总运费最少?

解:设甲煤矿向东车站运万吨煤,乙煤矿向东车站运万吨煤,那么总运费       z=x+1.5(200-x)+0.8y+1.6(300-y)(万元)。即z=780-0.5x-0.8y。

x、y应满足:

作出上面的不等式组所表示的平面区域。

设直线x+y=280与y轴的交点为M,则M(0,280)。

把直线l:0.5x+0.8y=0向上平移至经过平面区域上的点M时,z的值最小。

∵点M的坐标为(0,280),

∴甲煤矿生产的煤全部运往西车站,乙煤矿向东车站运280万吨,向西车站运20万吨时,总运费最少。

[模拟试题](答题时间:25分钟)

1. 画出不等式组表示的平面区域。

2. 求z=2x+y的最大值,使式中的x、y满足约束条件

3. 求z=3x+5y的最大值和最小值,使式中x、y 满足约束条件

4. 某纺纱厂生产甲、乙两种棉纱,已知生产甲种棉纱1吨需耗一级子棉2吨、二级子棉1吨;生产乙种棉纱需耗一级子棉1吨、二级子棉2吨,每1吨甲种棉纱的利润是600元,每1吨乙种棉纱的利润是900元,工厂在生产这两种棉纱的计划中要求消耗一级子棉不超过300吨、二级子棉不超过250吨。甲、乙两种棉纱应各生产多少(精确到吨),能使利润总额最大?

5. 要将甲、乙两种长短不同的钢管截成A、B、C三种规格,每根钢管可同时截得三种规格的短钢管的根数如下表所示:

   规格类型

钢管类型

 

A规格
B规格
C规格
甲种钢管
2
1
4
乙种钢管
2
3
1

今需A、B、C三种规格的钢管各13、16、18根,问各截这两种钢管多少根可得所需三种规格钢管,且使所用钢管根数最少。

 0  392306  392314  392320  392324  392330  392332  392336  392342  392344  392350  392356  392360  392362  392366  392372  392374  392380  392384  392386  392390  392392  392396  392398  392400  392401  392402  392404  392405  392406  392408  392410  392414  392416  392420  392422  392426  392432  392434  392440  392444  392446  392450  392456  392462  392464  392470  392474  392476  392482  392486  392492  392500  447090 

违法和不良信息举报电话:027-86699610 举报邮箱:58377363@163.com

精英家教网