简单的线性规划典型例题Word下载.docx
《简单的线性规划典型例题Word下载.docx》由会员分享,可在线阅读,更多相关《简单的线性规划典型例题Word下载.docx(19页珍藏版)》请在冰点文库上搜索。
的平面区域,
容易求得,在其区域的整数解为(1,1)、(1,2)、(1,3)、(2,2)、(2,3).
这类题可以将平面直角坐标系用网络线画出来,然后在不等式组所表示的平面区域找出符合题设要求的整数点来.
例3求不等式组F引:
丁—1所表示的平面区域的面积.
b—卜|+1
本题的关键是能够将不等式组所表示的平面区域作出来,
判断其形状进而求出其面积.而要将平面区域作出来的关键又是能够对不等式组中的两个不等式进行化简和变形,如何变形?
需对绝对值加以讨论.
不等式〉僅|x+l|-l可化为y>
x(x>
-l)^y>
-x-2(a<
-1);
不等式),5-|冲+1可化为y<
-x+l(A>
0)^y<
x+l(x<
0).
在平面直角坐标系作岀四条射线
AB:
y=x(x>
-Y),AC:
y=-x-2(xv-l)
DE:
y=-x+l(x>
0),DFzy=x+\(x<
0)
则不等式组所表示的平面区域如图
由于A3与AC、DE与DF互相垂直,
所以平面区域是一个矩形.
根据两条平行线之间的距离公式可得矩形的两条边的长度分别为返和也.
22
所以其面积为
2
2x+y-12<
例4若x、y满足条#3x-2y+10>
0,求z=x+2y的最大值和最小
x-4y+10<
0.
值.
画出可行域,平移直线找最优解.
ri
作出约束条件所表示的平面区域,即可行域,如图所示.
作直线l:
x+2y=z,即y=-^x+^-z,它表示斜率为-十,纵截距厶乙乙
为三的平行直线系,当它在可行域滑动时,由图可知,直线/过2
点时,z取得最大值,当/过点B时,z取得最小值.
••Zmax=2+2x8=18・・Jin=—2+2x2=2
解决线性规划问题,首先应明确可行域,再将线性目标函
数作平移取得最值.
例5用不等式表示以A(l,4),B(-3,0),C(-2,-2)为顶点的三角形部的平面区域.
首先要将三点中的任意两点所确定的直线方程写出来,然
后结合图形考虑三角形部区域应怎样表示。
直线A3的斜率为:
kAl{==1,其方程为y=x+3.
1一(一3)
可求得直线的方程为y=-2x-6.直线AC的方程为y=2x+2.
AABC的部在不等式x-y+3>
0所表示平面区域,同时在不等式2x+y+6>
0所表示的平面区域,同时又在不等式2x-y+2<
0所表示的平面区域(如图).
x-y+3>
0,所以已知三角形部的平面区域可由不等式组2x+y+6>
0,表示.
2x一y+2v0
用不等式组可以用来平面的一定区域,注意三角形区域部
不包括边界线.
例6已知x+y-5>
0,x+y-10<
0.求x2+y2的最大、最小值.分析:
令z=F+目标函数是非线性的.而z=F+y2=(養弔可
可看做区域的点到原点距离的平方•问题转化为点到直线的距离问
题.
由f+得可行域(如图所示)为八孑j,
x+y-10S0,
题目中的目标函数是非线性的.解决的方法类似于线性规
划问题•可做出图,利用图进行直观的分析.
f4x+3y-20<
0,
例7设z=7x+5y式中的变量x、y满足下列条件«
x-3y-2<
0,求z
xeN*,y已N*・的最大值.
先作出不等式组所表示的可行域,需要注意的是这里的x、ywN*,故只是可行域的整数点,然后作出与直线7x+5y=0平等的直线再进行观察.
作出直线/1:
4x+3y-20=0和直线厶:
x-3y-2=0,得可行域如图所示.
解方程组严"
20=0得交点人(呈上).
x-3y-2=055
又作直线/:
7x+5y=0,平等移动过点A时,7x+5y取最大值,然而点A不是整数点,故对应的z值不是最优解,此时过点A的直线为7x+5y=34-,应考虑可行域中距离直线7x+5>
-=34-最近的整点,即B(2,4),有z⑻=7x2+5x4=34,应注意不是找距点A最近的整点,如点C(4,l)为可行域中距A最近的整点,但z(g=7x4+5x1=33,它小于z⑻,故z的最大值为34.
解决这类题的关键是在可行域找准整点.若将线性目标函
数改为非线性目标函数呢?
狈|8设z=x2+y29式中的变量x、y满足<
3x+5yS25,试求z的最大
值、最小值.
作出不等式组所表示的平面区域,本题的关键是目标函数2=疋+尸应理解为可行域中的点与坐标原点的距离的平方.
作出直线厶:
x-4y+3=0,Z2:
3x+5y-25=0,/3:
x=l得到如图所示的可行域.
由图可知:
当(x,刃为点C(l,l)时,z取最小值为2;
当(x,y)为点
A(5,2)时,z取最大值29・
若将该题中的目标函数改为z=-,如何来求z的最大值、
最小值呢?
请自己探求・(将目标函数理解为点(x,y)与点(0,0)边线的斜率)
似|9设20,y>
0,^>
0;
p=-3x+y+2z.,q=x-2y+4z,x+y+z=l,用图表不出点(#,g)的围.
题目中的"
,q与X,y,z是线性关系.可借助于X,yz的围确定(p,°
)的围.
3x_y_2z=_〃解:
i*x-2y+4z=q,
x+y+z=l,
x=#8+q_6“),
y=丄(14-5g+3p),由xhO,y>
0,z»
0得27
Z=^-(5+4p+3q\
6/7-67-8<
<
3/7-5^+14>
0,做出不等式所示平面区域如图所示.
3〃+4g+5>
题目的条件隐蔽,应考虑到已有的」y,z的取值围・借
助于三元一次方程组分别求出「八z,从而求出°
§
所满足的不等式组找出(P,g)的围.
例10某糖果厂生产A、B两种糖果,A种糖果每箱获利润40元,B种糖果每箱获利润50元,其生产过程分为混合、烹调、包装三道
工序,下表为每箱糖果生产过程中所需平均时间(单位:
分钟)
混合
烹调
包装
A
1
5
3
B
4
每种糖果的生产过程中,混合的设备至多能用12机器小时,烹
调的设备至多只能用机器30机器小时,包装的设备只能用机器15机
器小时,试用每种糖果各生产多少箱可获得最大利润.
找约束条件,建立目标函数.
设生产A种糖果x箱,〃种糖果y箱,可获得利润z元,则此x+2v<
720
5x+4j<
1800
问题的数学模式在约束条件-3x+y<
900下,求目标函数z=40x+50y
的最大值,作出可行域,其边界
OA:
y=0AB:
3x+y-900=03C:
5x+4y-1800=0
CD:
x+2y-720=0DO:
x=0
由z=40x+50v得y=--x+—,它表示斜率为
••550
截距为兰的平行直线系,2越大,乙越大,
55050
从而可知过C点时截距最大,z取得了最大值.
解方程组
“疝=40x120+50x300=19800即生产A种糖果120箱,生产B种
糖果300箱,可得最大利润19800元.
由于生产A种糖果120箱,生产3种糖果300箱,就使得
两种糖果共计使用的混合时间为120+2X300=720(分),烹调时间
5X120+4X300=1800(分),包装时间3X120+300=660(分人
这说明该计划已完全利用了混合设备与烹调设备的可用时间,但对包装设备却有240分钟的包装时间未加利用,这种“过剩”问题构成了该问题的“松驰”部分,有待于改进研究.
例11甲、乙、丙三种食物的维生素A、8含量及成本如下表:
甲
乙
丙
维生素A(单位/千
克)
600
700
400
维生素B(单位/千
800
500
成本(元/千克)
11
9
某食物营养研究所想用x千克甲种食物,〉,千克乙种食物,z千
克丙种食物配成100千克的混合食物,并使混合食物至少含56000单位维生素A和63000单位维生素B・
(1)用a-、y表示混合物成本C.
(2)确定x、y、z的值,使成本最低.
找到线性约束条件及目标函数,用平行线移动法求最优解.
解:
(1)依题意:
%、yxz满足x+y+z=100=>
z=100-x-y
示.
联立“
3x-y=13O
2x+3y=160=>
交点4(50,20)
作直线7x+5y+400=C则易知该直线截距越小,C越小,所以该直线过A(50,20)时,直线在y轴截距最小,从而C最小,此时7X50+5X20+400=c=850元
.・・X=5O千克,z=3O千克时成本最低.
例12某工厂有甲、乙两种产品,按计划每天各生产不少于15‘,
已知生产甲产品1/需煤9/,电力4好V,劳力3个(按工作日计算);
生产乙产品1/需煤4/,电力5&
W,劳力10个;
甲产品每吨价7万元,乙产品每吨价12万元;
但每天用煤最不得超过300吨,电力不得超过200kW,劳力只有300个•问每天各生产甲、乙两种产品多少才能既完成生产任务,又能为国家创造最多的财富.
先设每天生产甲、乙两种产品的产量分别为刃和W,建立约束条件和目标函数后,再利用图形直观解题.
设每天生产甲产品乙产品W,总产值S/,依题意约束条件为:
15,
i5,
9x+4y<
300.
4x+5y<
200,
3x+\0y<
300.
目标函数为S=7x+\2y・
约束条件表示的可行域是五条直线所围成区域的部的点加上它的
边线上的点(如图阴影部分).
=15
二
O
、
、、A
现在就要在可行域上找出使S=lx+\2y取最大值的点(x,y)・作直线S=7x+12y,随着S取值的变化,得到一束平行直线,其纵截距为占,
12可以看出,当直线的纵截距越大,S值也越大.
从图中可以看出,当直线S=7x+12y经过点A时,直线的纵截距最大,所以S也取最大值.
解方程组产+5y-200=0,
3x+10y-300=0,
得A(20,24)・故当x=20,y=24时,
S触大值=7x20+12x24=428(万元).
答:
第天生产甲产品20/,乙产品24/,这样既保证完成任务,又
能为国家创造最多的财富428万元.
解决简单线性规划应用题的关键是:
(1)找出线性约束条
件和目标函数;
(2)准确画出可行域;
(3)利用S的几何意义,求出最优解.如本例中,吉是目标函数S=7x+\2y的纵截距.
例]3有一批钢管,长度都是4000mm,要截成500mm和600mm两种毛坯,且这两种毛坯数量比大于+配套,怎样截最合理?
先设出未知数,建立约束条件和目标函数后,再按求最优
解是整数解的方法去求.
设截500mm的x根,600mm的y根,根据题意,得
5x+6y<
40,
y<
3x,
y>
作出可行域,如下图中阴影部分.
目标函数为“x+y,作一组平行直线经过可行域的点且
和原点距离最远的直线为过3(0,8)的直线,这时x+y=8.由x,y为正整数,知(0,8)不是最优解.
在可行域找整点,使x+y=7
可知点(2,5),(3,4),(4,3),(5,2),(6,1)均为最优解.
每根钢管截500mm的2根,600mm的5根,或截500mm的3
根,600mm的4根或截500nun的4根,600mm的3根或截500mm的
5根,600〃劝的2根或截500呦的6根,600呦的1根最合理.
本题易出现如下错解:
设截500mm的x根,600mm的y根,
[500x+600v<
4000.
X1
y3
丿>
0・
其中iy均为整数・作出可行域,如下图所示中阴影部分.目
标函数为z=作一组平行直线x+y“,经过可行域的点且和原
点相距最远的直线为过A点的直线.先求A点的坐标,
即x+y=7,调整为x=2,y=5.
故哙罟
经检验满足条件,所以每根截500mm的2根,600枷”的5根最合理.
本题解法错误主要是在作一组平行直线x+y=f时没能准确作出,而得到经过可行域的点且和原点距离最远的直线为过A点的直线.
此错误可检验如下:
如果直线通过A点,它是经过可行域的点且到原点距离最远的直线,那么巴+空“,即x+y=7・由于为整数,所以点人(1卩,5丄)
2323•2323
不是最优解但在可行域除A点外,不可能再有其他点满足x+〉,=7,只能在可行域找满足x+〉,=6的点.如果还没有整数点,则只能在可行域找满足x+y=5的整数点.但我们知道x=2,y=5满足题意,这样,就出现了矛盾,从而判断解法错误,即x+yw通过A点的直线并不是通过可行域的点且和原点距离最远的直线.
例14某工厂生产A.B两种产品,已知生产A产品1蚣要用煤9/,电力4kW,3个工作日;
生产B产品lkg要用煤4/,电力5kW,10个工作日.又知生产出q产品1匕可获利7万元,生产出〃产品1鏡可获利12万元,现在工厂只有煤360/,电力200AW,300个工作日,在这种情况下生产A,B产品各多少千克能获得最大经济效益.
在题目条件比较复杂时,可将题目中的条件列表.
产品
工作日
煤/
电力上W
利润/万元
A产品
7
B产品
10
12
设这个工厂应分别生产A,B产品xkg,ykg,可获利z万元.根
3x+10y<
300,
込=7x+12y(万元)•
画出如图所示的可行域,做直线八7x+12y=O,做一组直线7x+\2y=t与「平行,当/过点A时/最大.由(3%+10>,=300,得A点坐标⑷+5〉,=200,
为(20,24)•把A点坐标代入/的方程,得r=428(万元).
应生产A产品20/,3产品247,能获最大利润428万元.
把实际问题转化为线性规划问题的难点在于找出题目中的所有线性约束条件.同时本题的可行域形状较复杂,要注意分析目标函数的斜率和各边界斜率的关系:
从而确定在何处取得最优解.解应用题时还应注意设出未知量和做答这两个必要步骤.
例15某公司每天至少要运送180/货物•公司有8辆载重为6/的A型卡车和4辆载重为10/的B型卡车,A型卡车每天可往返4次,B型卡车可往返3次,A型卡车毎天花费320元,3型卡车每天花费504元,问如何调配车辆才能使公司每天花费最少.
设A型卡车x辆,〃型卡车〉,辆•问题转化为线性规划问题.同时应注意到题中的x,y只能取整数.
0<
x<
&
设A型卡车x辆,3型卡车y辆,则即x+y<
10,
24x+30y>
180,
4,
x+y<
4x+5y>
30,
目标函数z=320x+504y.做如图所示的可行域,
做直线八320x+504y=0.在可行域中打上网格,找出(8,0),(8,1),
(8,2),(7,1),(7,2),(7,3),…等整数点.做/:
320x+504v=r与/'
平行,可见当/过(8,0)时r最小,即zmin=8x320=2560(元)•
整数解的线性规划问题.如果取最小值时不是整数点,则考虑此点附近的整数点.
例16某工厂利用两种燃料生产三种不同的产品A、B、C,每消耗一吨燃料与产品A、B、C有下列关系:
产品A
产品B
产品(:
燃料甲
10(吨)
7(吨〉
5(吨)
燃料乙
9(吨)
13(吨〉
现知每吨燃料甲与燃料乙的价格之比为2:
3,现需要三种产品A、B、C各50吨、63吨、65吨.问如何使用两种燃料,才能使该厂成本最低?
由于该厂成本与两种燃料使用量有关,而产品A、3、C又与这两种燃料有关,且这三种产品的产量也有限制,因此这是一道求线性目标函数在线性约束条件下的最小值问题,这类简单的线性规划问题一般都可以利用二元一次不等式求在可行域上的最优解.
设该厂使用燃料甲x吨,燃料乙〉,吨,甲每吨2/元,
则成本为Z=2tx+3ty=t(2x+3y)・因此只须求2x+3y的最小值即可.
10x+5j>
50,
又由题意可得X、y满足条件<
7x+9y>
63,
5x+13y>
65.
作出不等式组所表示的平面区域(如图)
〔爲F得畤令
由严+263,得心,乌
5x+13y=65・2323
作直线/:
2x+3y=0,把直线/向右上方平移至可行域中的点B时,"
2x+3)u2xllZ+3x乩空・
232323
・・・最小成本为竺.
23
应用燃料甲丄吨,燃料乙四吨,才能使成本最低.
2323
本题中燃料的使用不需要是整数吨,若有些实际应用问题
中的解是整数解,又该如何来考虑呢?
例17咖啡馆配制两种饮料,甲种饮料每杯含奶粉9克、咖啡4克、
糖3克,乙种饮料每杯含奶粉4克、咖啡5克、糖10克.已知每天
原料的使用限额为奶粉3600克、咖啡2000克、糖3000克.如果甲种饮料每杯能获利0.7元,乙种饮料每杯能获利1.2元,每天在原料的使用限额饮料能全部售出,每天应配制两种饮料各多少杯能获利最大?
这是一道线性规划的应用题,求解的困难在于从实际问题
中抽象出不等式组.只要能正确地抽象出不等式组,即可得到正确的答案.
设每天配制甲各饮料*杯、乙种饮料〉,杯可获得最大利润,
利润总额为z元.
由条件知:
z=0.7x=1.2y・变量兀、y满足
3600,
4x+5y<
2000,
3x+10y<
300Ux>
0,y>
0・
作出不等式组所表示的可行域(如图)
0.7x+1.2y=0,把直线/向右上方平移至经过4点的位置时,
Z=0.7x+l・2y取最大值・
由方程组:
<
力+10y-3000=0,
4x+5y-2000=0.
得A点坐标4(200,240).
应每天配制甲种饮料200杯,乙种饮料240杯方可获利最大.