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

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