简单的线性规划典型例题
例1
xy20,
画出不等式组xy40,表示的平面区域.
x3y30.
分析:采用“图解法”确定不等式组每一不等式所表示的平面区域,然后求其公共部分.
解:把x0,y0代入xy2中得0020
∴ 不等式xy20表示直线xy20下方的区域(包
括边界),
即位于原点的一侧,同理可画出其他两部分,不等式组所表
示的区域如图所示.
说明:“图解法”是判别二元一次不等式所表示的区域行之有效的一种方法.
例2 画出2x3y3表示的区域,并求所有的正整数解(x,y).
分析:原不等式等价于
y2x3,
而求正整数解则意味着x,y
y3.
x0,y0,xz,yz,
有限制条件,即求.
y2x3,y3.
解:依照二元一次不等式表示的平面区域,知2x3y3表示的区域如下图:
x0,y0,
xz,yz,
对于2x3y3的正整数解,先画出不等式组.所表示
y2x3,y3.
的平面区域,如图所示.
(1,2)、(1,3)、(2,3).(2,2)、容易求得,在其区域内的整数解为(1,1)、
说明:这类题可以将平面直角坐标系用网络线画出来,然后在不等式组所表示的平面区域内找出符合题设要求的整数点来.
例3
yx11
求不等式组所表示的平面区域的面积.
yx1
分析:本题的关键是能够将不等式组所表示的平面区域作出来,判断其形状进而求出其面积.而要将平面区域作出来的关键又是能够
对不等式组中的两个不等式进行化简和变形,如何变形?需对绝对值加以讨论.
解:不等式yx1可化为yx(x1)或yx2(x1); 不等式yx1可化为yx1(x0)或yx1(x0). 在平面直角坐标系内作出四条射线
AB:yx(x1), AC:yx2(x1) DE:yx1(x0),DF:yx1(x0)
则不等式组所表示的平面区域如图
由于AB与AC、DE与DF互相垂直, 所以平面区域是一个矩形.
根据两条平行线之间的距离公式可得矩形的两条边的长度分别为
232
和. 22
所以其面积为.
3
2
例4
值.
2xy120,
若x、y满足条件3x2y100,求zx2y的最大值和最小
x4y100.
分析:画出可行域,平移直线找最优解.
解:作出约束条件所表示的平面区域,即可行域,如图所示. 作直线l:x2yz,即yxz,它表示斜率为,纵截距为的平行直线系,当它在可行域内滑动时,由图可知,直线
l过点时,z取得最大值,当l过点B时,z取得最小值.
121212
z2
∴ zmax22818 ∴ zmin2222
说明:解决线性规划问题,首先应明确可行域,再将线性目标函数作平移取得最值.
例5 用不等式表示以A(1,4),B(3,0),C(2,2)为顶点的三角形
内部的平面区域.
分析:首先要将三点中的任意两点所确定的直线方程写出来,然后结合图形考虑三角形内部区域应怎样表示。
解:直线AB的斜率为:kAB
40
1,其方程为yx3. 1(3)
可求得直线BC的方程为y2x6.直线AC的方程为y2x2.
ABC的内部在不等式xy30所表示平面区域内,同时在不等
式2xy60所表示的平面区域内,同时又在不等式2xy20所表示的平面区域内(如图).
xy30,
所以已知三角形内部的平面区域可由不等式组2xy60,表
2xy20
示.
说明:用不等式组可以用来平面内的一定区域,注意三角形区域内部不包括边界线.
例6 已知xy50,xy100.求x
2
2
2
y2的最大、最小值.
2
2
分析:令zxy,目标函数是非线性的.而zxyxy
2
2
2
可看做区域内的点到原点距离的平方.问题转化为点到直线的距离问题.
xy50,解:由得可行域(如图所示)为zx2y2
xy100,
x
2
y
2
,
2
而(0,0)到xy50,xy100的距离分别为
510
和.
22
所以z的最大、最小值分别是50和
25
. 2
说明:题目中的目标函数是非线性的.解决的方法类似于线性规
划问题.可做出图,利用图进行直观的分析.
例7
4x3y200,
设z7x5y式中的变量x、y满足下列条件x3y20,求z
xN*,yN*.
的最大值.
分析:先作出不等式组所表示的可行域,需要注意的是这里的故只是可行域内的整数点,然后作出与直线7x5y0平等x、yN*,
的直线再进行观察.
解:作出直线l1:4x3y200和直线l2:x3y20,得可行域如图所示.
4x3y200224
解方程组得交点A(,).
55x3y20
7x5y0,平等移动过点A时,7x5y取最大值,然而又作直线l:
点A不是整数点,故对应的z值不是最优解,此时过点A的直线为
44
7x5y34,应考虑可行域中距离直线7x5y34最近的整点,即
55
B(2,4),有z(B)725434,应注意不是找距点A最近的整点,如
点C(4,1)为可行域中距A最近的整点,但z(C)745133,它小于
z(B),故z的最大值为34.
说明:解决这类题的关键是在可行域内找准整点.若将线性目标函数改为非线性目标函数呢?
例8
x4y3,
设zx2y2,式中的变量x、y满足3x5y25,试求z的最大
x1.
值、最小值.
分析:作出不等式组所表示的平面区域,本题的关键是目标函数
zx2y2应理解为可行域中的点与坐标原点的距离的平方.
解:作出直线l1:x4y30,l2:3x5y250,l3:x1得到如图所示的可行域.
由
x4y30
得A(5,2)
3x5y250
由由
x4y30
得C(1,1)
x1
3x5y25022
得B(1,).
5x1
由图可知:当(x,y)为点C(1,1)时,z取最小值为2;当(x,y)为点
A(5,2)时,z取最大值29.
说明:若将该题中的目标函数改为z,如何来求z的最大值、最小值呢?请自己探求.(将目标函数理解为点(x,y)与点(0,0)边线的斜率)
x
y
例9 设x0,y0,z0;p3xy2z,qx2y4z,xyz1,
用图表示出点(p,q)的范围.
分析:题目中的p,q与x,y,z是线性关系.可借助于x,y,
z的范围确定(p,q)的范围.
1x(8q6p),273xy2zp,
1
(145q3p),由x0,y0,z0得解:由x2y4zq,得y27xyz1,
1
z(54p3q),276pq80,
3p5q140,做出不等式所示平面区域如图所示.
3p4q50,
说明:题目的条件隐蔽,应考虑到已有的x,y,z的取值范围.借助于三元一次方程组分别求出x,y,z,从而求出p,q所满足的不等式组找出(p,q)的范围.
例10
某糖果厂生产A、B两种糖果,A种糖果每箱获利润40元,
50元,其生产过程分为混合、烹调、包装三道
B种糖果每箱获利润
工序,下表为每箱糖果生产过程中所需平均时间(单位:分钟)
每种糖果的生产过程中,混合的设备至多能用12机器小时,烹调的设备至多只能用机器30机器小时,包装的设备只能用机器15机
器小时,试用每种糖果各生产多少箱可获得最大利润.
分析:找约束条件,建立目标函数.
解:设生产A种糖果x箱,B种糖果y箱,可获得利润z元,则此
x2y7205x4y1800
问题的数学模式在约束条件3xy900下,求目标函数z40x50y
x0y0
的最大值,作出可行域,其边界
OA:y0 AB:3xy9000 BC:5x4y18000 CD:x2y7200 DO:x0
z
,它表示斜率为50
4zz
,截距为的平行直线系,越大,z越大,55050
由z40x50y得yx
4
5
从而可知过C点时截距最大,z取得了最大值.
解方程组
x2y720
C120,300
5x4y1800
∴ zmax401205030019800即生产A种糖果120箱,生产B种糖果300箱,可得最大利润19800元.
说明:由于生产A种糖果120箱,生产B种糖果300箱,就使得两种糖果共计使用的混合时间为120+2×300=720(分),烹调时间5×120+4×300=1800(分),包装时间3×120+300=660(分),这说明该计划已完全利用了混合设备与烹调设备的可用时间,但对包装设备却有240分钟的包装时间未加利用,这种“过剩”问题构成了该问题的“松驰”部分,有待于改进研究.
例11
甲、乙、丙三种食物的维生素A、B含量及成本如下表:
某食物营养研究所想用x千克甲种食物,y千克乙种食物,z千克丙种食物配成100千克的混合食物,并使混合食物至少含56000单
y表示混合物成本C.位维生素A和63000单位维生素B.(1)用x、(2)
确定x、y、z的值,使成本最低.
分析:找到线性约束条件及目标函数,用平行线移动法求最优解. 解:(1)依题意:x、y、z满足xyz100z100xy ∴ 成本C11x9y4z7x5y400(元) (2)依题意
600x700y400z56000
800x400y500z63000
2x3y160
∵ z100xy ∴3xy130
x0,y0
作出不等式组所对应的可行域,如图示.
3xy130联立
2x3y160交点A50,20
所
作直线7x5y400C则易知该直线截距越小,C越小,所以该直
线过A50,20时,直线在y轴截距最小,从而C最小,此时7×50+5×20+400=C=850元
∴ x50千克,z30千克时成本最低.
例12 某工厂有甲、乙两种产品,按计划每天各生产不少于15t,已知生产甲产品1t需煤9t,电力4kW,劳力3个(按工作日计算);生产乙产品1t需煤4t,电力5kW,劳力10个;甲产品每吨价7万元,乙产品每吨价12万元;但每天用煤最不得超过300吨,电力不得超过200kW,劳力只有300个.问每天各生产甲、乙两种产品多少t,才能既保定完成生产任务,又能为国家创造最多的财富.
分析:先设每天生产甲、乙两种产品的产量分别为xt和yt,建立约束条件和目标函数后,再利用图形直观解题.
解:设每天生产甲产品xt,乙产品yt,总产值St,依题意约束条件为:
x15,y15,9x4y300,
4x5y200,3x10y300.
目标函数为S7x12y.
约束条件表示的可行域是五条直线所围成区域的内部的点加上它的边线上的点(如图阴影部分).
现在就要在可行域上找出使S7x12y取最大值的点(x,y).作直线S7x12y,随着S取值的变化,得到一束平行直线,其纵截距为可以看出,当直线的纵截距越大,S值也越大.
从图中可以看出,当直线S7x12y经过点A时,直线的纵截距最大,所以S也取最大值.
4x5y2000,解方程组 3x10y3000,S,12
得A(20,24).故当x20,y24时,
S最大值7201224428(万元).
答:第天生产甲产品20t,乙产品24t,这样既保证完成任务,又能为国家创造最多的财富428万元.
说明:解决简单线性规划应用题的关键是:(1)找出线性约束条件和目标函数;(2)准确画出可行域;(3)利用S的几何意义,求出最优解.如本例中,S是目标函数S7x12y的纵截距. 12
例13 有一批钢管,长度都是4000mm,要截成500mm和600mm两种毛坯,且这两种毛坯数量比大于配套,怎样截最合理?
分析:先设出未知数,建立约束条件和目标函数后,再按求最优解是整数解的方法去求.
解:设截500mm的x根,600mm的y根,根据题意,得 13
5x6y40,y3x,且x,yz. x0,
y0.
作出可行域,如下图中阴影部分.
目标函数为zxy,作一组平行直线xyt,经过可行域内的点且和原点距离最远的直线为过B(0,8)的直线,这时xy8.
由x,y为正整数,知(0,8)不是最优解.
在可行域内找整点,使xy7
可知点(2,5),(3,4),(4,3),(5,2),(6,1)均为最优解.
答:每根钢管截500mm的2根,600mm的5根,或截500mm的3根,600mm的4根或截500mm的4根,600mm的3根或截500mm的5根,600mm的2根或截500mm的6根,600mm的1根最合理.
说明:本题易出现如下错解:设截500mm的x根,600mm的y根,则
,500x600y40005x6y40,x1y3x,,y3即 x0,x0,
y0.y0.
其中x、y均为整数.作出可行域,如下图所示中阴影部分.目标函数为zxy,作一组平行直线xyt,经过可行域内的点且和
原点相距最远的直线为过A点的直线.先求A点的坐标,
40xy3x解得23, 5x6y40y120
23
故A40120,即xy7,调整为x2,y5. ,2323
经检验满足条件,所以每根截500mm的2根,600mm的5根最合理.
本题解法错误主要是在作一组平行直线xyt时没能准确作出,而得到经过可行域内的点且和原点距离最远的直线为过A点的直线. 此错误可检验如下:
如果直线xyt通过A点,它是经过可行域内的点且到原点距离最远的直线,那么
A(140120t,即xy7.由于x,y为整数,所以点2323175,5)不是最优解但在可行域内除A点外,不可能再有其他点满2323
足xy7,只能在可行域内找满足xy6的点.如果还没有整数点,则只能在可行域内找满足xy5的整数点.但我们知道x2,y5满足题意,这样,就出现了矛盾,从而判断解法错误,即xyt通过A点的直线并不是通过可行域内的点且和原点距离最远的直线.
例14 某工厂生产A、B两种产品,已知生产A产品1kg要用煤9t,电力4kW,3个工作日;生产B产品1kg要用煤4t,电力5kW,10个工作日.又知生产出A产品1kg可获利7万元,生产出B产品1kg可获利12万元,现在工厂只有煤360t,电力200kW,300个工作日,在这种情况下生产A,B产品各多少千克能获得最大经济效益. 分析:在题目条件比较复杂时,可将题目中的条件列表.
解:设这个工厂应分别生产A,B产品xkg,ykg,可获利z万元.根
3x10y300,9x4y360,据上表中的条件,列出线性约束条件为目标函数为4x5y200,
x0,y0,
z7x12y(万元).
画出如图所示的可行域,做直线l':7x12y0,做一组直线
3x10y300,7x12yt与l'平行,当l过点A时t最大.由得A点坐标4x5y200,
为(20,24).把A点坐标代入l的方程,得t428(万元).
答:应生产A产品20t,B产品24t,能获最大利润428万元. 说明:把实际问题转化为线性规划问题的难点在于找出题目中的
所有线性约束条件.同时本题的可行域形状较复杂,要注意分析目标函数的斜率和各边界斜率的关系:从而确定在何处取得最优解.解应用题时还应注意设出未知量和做答这两个必要步骤.
例15 某公司每天至少要运送180t货物.公司有8辆载重为6t的A型卡车和4辆载重为10t的B型卡车,A型卡车每天可往返4次,B型卡车可往返3次,A型卡车每天花费320元,B型卡车每天花费504元,问如何调配车辆才能使公司每天花费最少.
分析:设A型卡车x辆,B型卡车y辆.问题转化为线性规划问题.同时应注意到题中的x,y只能取整数.
0x8,0y4,解:设A型卡车x辆,B型卡车y辆,则即xy10,24x30y180,
0x8,0y4, xy10,4x5y30,
目标函数z320x504y.做如图所示的可行域,
做直线l':320x504y0.在可行域中打上网格,找出(8,0),(8,1),(8,2),(7,1),(7,2),(7,3),…等整数点.做l:320x504yt与l'平行,可见当l过(8,0)时t最小,即zmin83202560(元).
说明:整数解的线性规划问题.如果取最小值时不是整数点,则考虑此点附近的整数点.
例16 某工厂利用两种燃料生产三种不同的产品A、B、C,每消耗一吨燃料与产品A、B、C有下列关系:
现知每吨燃料甲与燃料乙的价格之比为2:3,现需要三种产品A、B、C各50吨、63吨、65吨.问如何使用两种燃料,才能使该厂成本最低?
分析:由于该厂成本与两种燃料使用量有关,而产品A、B、C又与这两种燃料有关,且这三种产品的产量也有限制,因此这是一道求线性目标函数在线性约束条件下的最小值问题,这类简单的线性规划问题一般都可以利用二元一次不等式求在可行域上的最优解.
解:设该厂使用燃料甲x吨,燃料乙y吨,甲每吨2t元, 则成本为z2tx3tyt(2x3y).因此只须求2x3y的最小值即可.
10x5y50,又由题意可得x、y满足条件7x9y63,
5x13y65.
作出不等式组所表示的平面区域(如图)
由
由10x5y50,2756得A(,) 11117x9y63.7x9y63,11770,) 得B(23235x13y65.
作直线l:2x3y0,把直线l向右上方平移至可行域中的点B时,
117704443. 232323
444t. ∴最小成本为23
11770答:应用燃料甲吨,燃料乙吨,才能使成本最低. 2323z2x3y2
说明:本题中燃料的使用不需要是整数吨,若有些实际应用问题中的解是整数解,又该如何来考虑呢?
例17 咖啡馆配制两种饮料,甲种饮料每杯含奶粉9克、咖啡4克、糖3克,乙种饮料每杯含奶粉4克、咖啡5克、糖10克.已知每天原料的使用限额为奶粉3600克、咖啡2000克、糖3000克.如果甲种饮料每杯能获利0.7元,乙种饮料每杯能获利1.2元,每天在原料的使用限额内饮料能全部售出,每天应配制两种饮料各多少杯能获利最大?
分析:这是一道线性规划的应用题,求解的困难在于从实际问题中抽象出不等式组.只要能正确地抽象出不等式组,即可得到正确的答案.
解:设每天配制甲各饮料x杯、乙种饮料y杯可获得最大利润,利润总额为z元.
由条件知:z0.7x1.2y.变量x、y满足
,9x4y36004x5y2000, ,3x10y3000
x0,y0.
作出不等式组所表示的可行域(如图)
0.7x1.2y0,作直线l:把直线l向右上方平移至经过A点的位置时,
z0.7x1.2y取最大值.
3x10y30000,由方程组: 4x5y20000.
得A点坐标A(200,240).
答:应每天配制甲种饮料200杯,乙种饮料240杯方可获利最大.