332简单的线性规划问题A.ppt

《332简单的线性规划问题A.ppt》由会员分享，可在线阅读，更多相关《332简单的线性规划问题A.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 不等式不等式3.3.2 3.3.2 简单的线性规划问题简单的线性规划问题复习复习判断二元一次不等式表示哪一侧平面区域的方法Oxy11x+y-1=0 x+y-10 x+y-10表示这一直线表示这一直线哪一侧的平面区域，特殊地，当哪一侧的平面区域，特殊地，当c0时常把原点作为此特殊点时常把原点作为此特殊点.复习回顾复习回顾1.在同一坐标系上作出下列直线在同一坐标系上作出下列直线:2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7xYo2.作出下列不等式组所表示的平面区域作出下列不等式组所表示的平面区域55x=1x-4y+3=03x+5y-25=01ABCC:(1.

2、00,4.40)A:(5.00,2.00)B:(1.00,1.00)Oxy问题问题1 1：x 有无最大（小）值？有无最大（小）值？问题问题2 2：y 有无最大（小）值？有无最大（小）值？问题问题3 3：2 2x+y 有无最大（小）值？有无最大（小）值？二二二二.提出问题提出问题提出问题提出问题把上面两个问题综合起来把上面两个问题综合起来把上面两个问题综合起来把上面两个问题综合起来:设设设设z=2x+y,z=2x+y,求满足求满足求满足求满足时时时时,z,z的最大值和最小值的最大值和最小值的最大值和最小值的最大值和最小值.55x=1x-4y+3=03x+5y-25=01ABCC:(1.00,4.

3、40)A:(5.00,2.00)B:(1.00,1.00)Oxy直线直线直线直线L L L L越往右平移越往右平移越往右平移越往右平移,t,t,t,t随之增大随之增大随之增大随之增大.以经过点以经过点以经过点以经过点A(5,2)A(5,2)A(5,2)A(5,2)的的的的直线所对应的直线所对应的直线所对应的直线所对应的t t t t值值值值最大最大最大最大;经过点经过点经过点经过点B(1,1)B(1,1)B(1,1)B(1,1)的直线所对的直线所对的直线所对的直线所对应的应的应的应的t t t t值最小值最小值最小值最小.线性规划问题：设z=2x+y，式中变量满足下列条件：求z的最大值与最小值

4、。目标函数（线性目标函数）线性约束条件任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域所有的所有的最优解最优解线性规线性规划问题划问题线性规划线性规划：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题 可行解：满足线性约束条件的解(x，y)叫可行解；可行域：由所有可行解组成的集合叫做可行域；最优解：使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。可行域可行域2x+y=32x+y=12(1,1)(5,2)线性规划练习练习1:解下列线性规划问题：求z=2x+y的最大值和最小值，使式中x、y满足下列条件：2x+y=02x+y=-3

5、2x+y=3答案：当x=-1,y=-1时，z=2x+y有最小值3.当x=2,y=-1时，z=2x+y有最大值3.线性规划练习练习2 解下列线性规划问题：求z=300 x+900y的最大值和最小值，使式中x、y满足下列条件：x+3y=0300 x+900y=0300 x+900y=112500答案：当x=0,y=0时，z=300 x+900y有最小值0.当x=0,y=125时，z=300 x+900y有最大值112500.解线性规划问题的步骤：解线性规划问题的步骤：（2 2）移移：在线性目标函数所表示的一组平行：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共线中，利用平移

6、的方法找出与可行域有公共点且纵截距最大或最小的直线；点且纵截距最大或最小的直线；（3 3）求求：通过解方程组求出最优解；：通过解方程组求出最优解；（4 4）答答：作出答案。：作出答案。（1 1）画画：画出线性约束条件所表示的可行域；：画出线性约束条件所表示的可行域；总结总结几个结论：几个结论：1、线性目标函数的最大（小）值一般、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界在可行域的顶点处取得，也可能在边界处取得。处取得。2、求线性目标函数的最优解，要注意、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义分析线性目标函数所表示的几何意义在在y轴上的截距或其相反数

7、。轴上的截距或其相反数。课本91页练习 1（1）课本91页练习 2例例5 营养学家指出，成人良好的日常饮食应该至少提供营养学家指出，成人良好的日常饮食应该至少提供0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白质，的蛋白质，0.06kg的的脂肪，脂肪，1kg食物食物A含有含有0.105kg碳水化合物，碳水化合物，0.07kg蛋白质，蛋白质，0.14kg脂肪，花费脂肪，花费28元；而元；而1kg食物食物B含有含有0.105kg碳水化合物，碳水化合物，0.14kg蛋白质，蛋白质，0.07kg脂肪，脂肪，花费花费21元。为了满足营养专家指出的日常饮食要求，元。为了满足营养专家指出的日常饮

8、食要求，同时使花费最低，需要同时食用食物同时使花费最低，需要同时食用食物A和食物和食物B多少多少kg？食物食物/kg碳水化合物碳水化合物/kg蛋白质蛋白质/kg脂肪脂肪/kgA0.1050.070.14B0.1050.140.07将已知数据列表得将已知数据列表得解解:设每天食用设每天食用xkg食物食物A,ykg食物食物B,总成本为总成本为z,那么那么目标函数为目标函数为z=28x+21y作出二元一次不等式组所表示的可行域作出二元一次不等式组所表示的可行域,如图如图:目标函数为目标函数为z=28x+21y答答:每天食用食物每天食用食物A约约143g,食物食物B约约571g,能够满足日常饮食要求能

9、够满足日常饮食要求,又使花又使花费最低费最低,最低成本为最低成本为16元元.例例6 要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A、B、C三三种种规规格格，每每张张钢钢板板可可同同时时截截得得三三种种规规格格的的小小钢钢板板的的块块数数如如下下表表所所示示：解解：设设需需截截第第一一种种钢钢板板x张张，第第一一种种钢钢板板y张张，一一共共使使用用z张张.则则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格212131作出可行域（作出可行域（如图如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为

10、三种规格的成品分别为15，18，27块，块，问各截这两问各截这两问各截这两问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。2x+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，目标函数目标函数

11、z=x+yB(3,9)C(4,8)M(18/5,39/5)调整优值法调整优值法调整优值法调整优值法作直线作直线x+y=12当直线经过点当直线经过点M时时z=x+y=11.4,但它不是最优整数解，但它不是最优整数解，解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)x0y2x+y=15x+3y=27x+2y=18x+y=0经经过过可可行行域域内内的的整整点点B(3,9)和和C(4,8)且且和和原原点点距距离离最最近近的直线是的直线是x+y=12，它们是最优解它们是最优解.答答:(略略)作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z=x+yB(3,9)C(4,8)M(18/5,39/5)打网格线法打网格线法打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点M时时z=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，x0y