简单线性规划(整点解问题).ppt

,7.4简单的线型规划(3) 整点解问题,一、朝花夕拾,图解法解简单线性规划问题的步骤,(1)画可行域；,(2)比较斜率，画目标直线l；,(3)平移l，找最优解；,(4) 求交算出最优解，并求最值,解简单线性规划应用题的步骤,已知,2x+y 15,x+2y 18,x+3y 27,x 0,y0,求z=x+y的最小值,A,解：,如图，作出可行域,并作出直线l：x+y=z,显然，当l过点A时，z最小,z,x+y=z,由,2x+y = 15,x+3y =27,故当x=,，y=,时，zmin=,问题,二、探索研究,（1）,(列),（2）,设：,所需截第一种钢板x张，第二种钢板y张，两种钢板共z张.,（3）,写：,线性约束条件,目标函数：,几何画板演示,（6）定:,平移找解法:打网格,描整点,平移目标函数线, 确定首先经过的整点.,要求作图准确，易出现模糊点，可操作性不强！,优值调整法:,当直线x+y=z 移至A(3.6,7.8)时,zmin=11.4,由x,y取整数知: z 必为整数,先将z调整为12, 即x+y=12, y=12-x或 x=12-y,将y=12-x代入约束条件得：,若调整z=12仍无整数解，应继续调整，直到找到为止.,y=8,第一变：,已知,2x+y 15,x+2y 18,x+3y 27,xN,yN,求z=2x+3y的最小值,解：,如图，作出可行域,并作出直线l：2x+3y=z,显然，当l移至过A(3.6,7.8)时,zmin=30.6,但由x,y N知: z N,先将z调整为31, 即2x+3y=31,得y=(31-2x)/3,代入线性约束条件,整理得,3.5x 4,故x=4，,y=23/3,不合题意,再将z调整为32, 即2x+3y=32,得y=(32-2x)/3,代入线性约束条件,整理得,3.25x 5,故,x=4,x=5,y=22/3,或,(舍),即当x=4，y=8时,zmin=32,第二变：,已知,2x+y 15,x+2y 18,x+3y 27,xN,yN,求z=10x+10y的最小值,解：,如图，作出可行域,并作出直线l：10x+10y=z,显然，当l移至过A(3.6,7.8)时,zmin=114,但由x,y N知:,z是10的倍数,先将z调整为120,得y=12-x,代入线性约束条件,整理得,3x 4.5,即10x+10y=120,y=9,故,x=3,x=4,y=8,或,即当x=3，y=9，,或当x=4，y=8时,zmin=120,某公司承揽了一项业务, 需做文字标牌2个,绘画标牌3个.现有两种规格原料,甲种规格每张3m2,可做文字标牌1个,绘画标牌2个;乙种规格每张2m2,可做文字标牌2个,绘画标牌1个,求两种规格的原料各用多少张,才能使总的用料面积最小?,分析:列,1,2,3,2,1,2,2,3,三、练习反馈,约束条件为:,解:,设用甲种规格原料x张,乙种规格原料y张,所用总面积为 z m2.则目标函数为z=3x+2y,作出可行域如图:,作直线l0:3x+2y=0,平移l 0,用甲、乙两种原料各为1张时，可使总用料面积最小为5m2.,答：,B(1,1),到经过可行域内点 时, z有最小值，,可得经过可行域内整点B(1,1)时, zmin=5(m2),z=3x+2y,此时z=3x+2y,调整z=,5，,其步骤是,寻找“整点”最优解的方法：,四、本课小结,打网格，平移找解法:,优值调整法:,(1)寻找非整点最优解；,(2