线性规划中的整点问题

线性规划中的整点问题,x,y,o,武穴实验高中 杨耀平,例,1,、某人有楼房一座，室内面积共,180m,2,，拟分隔成两类房间作为旅游客房，大房间每间面积为,18m,2,，可住游客,5,名，每名游客每天住宿费为,40,元；小房间每间面积为,15m,2,，可住游客,3,名，每名游客每天住宿费为,50,元；装修大房间每间需,1000,元，装修小房间每间需,600,元。如果他只能筹款,8000,元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？,解,：设隔出大房间,x,间，小房间,y,间，收益为,z,元，则,Z=200 x+150y,，且,x,y,满足,如图，可行域为阴影部分，,作直线,l,0,：,200 x+150y=0,，即,4x+3y=0,将直线,l,0,平移到,A,点时,z,最大。,解方程组,4x+3y=0,0,2,4,8,10,14,18,6,12,16,2,6,12,14,4,10,8,x,y,6x+5y=60,5x+3y=40,A,由图可知目标函数取得最大值的整点分布在可行域上侧,靠近边界的区域，考察可能的整点,(0,，,12),(,1,，,10,),(,2,，,9,),(,3,，,8,),(,4,，,6,),(,5,，,5,),(,6,，,3,),(,7,，,1,),(,8,，,0,),将这些点分别代入,Z=200 x+150y,求出各点对应,的值，得整点,(0,，,12),(3,，,8),是最优解，此时,z,的,最大值为,1800,。,=,4x+3y=0,0,2,4,8,10,14,18,6,12,16,2,6,12,14,4,10,8,x,y,6x+5y=60,5x+3y=40,A,答：他应隔出大房间,0,间、小房间,12,间或者大房间,3,间、,小房间,8,间，能获得最大收益每天,1800,元,例,2,、要将两种大小不同的钢板截成三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：,A,规格,规格,规格,第一种钢板,2,1,1,第二种钢板,1,2,3,今需要、,、,三种规格的成品分别为,15,，,18,，,27,块，各截这两种钢板多少张可以满足需要且使所用钢板数目最少？,解：设需要截第一种钢板,x,张，,第二种钢板,y,张，共需这两种,钢板,z,张，则,z=,x,+,y,且,2,x,+,y,15,x+2y,18,x+3y,27,x,0,y,0,作出可行域,如图所示,2x+,y=15,x+2,y=18,x+3y=27,y+x,=0,0,2,4,8,10,14,18,6,12,16,2,6,12,14,22,4,10,8,16,18,20,24,x,y,A,作出直线,l,0,:x+y=0,并平移，,由图可知，当直线,z=,x+y,经过可行域上的点,A,时，截距,z,最小。,解方程组,得点,A,的坐标为,.,答：满足题意的截法有两种：截第一种钢板,3,张，,第二种钢板,9,张，或者截第一种钢板,4,张，第二种钢板,8,张,方法一：调整最值法：,当目标函数系数不大时,可以用调整最值法，一般步骤为：,平移直线寻找非整最优解；调整最值，确定“目标直线”由“目标直线”方程代入约束条件，并求变量范围：确定“目标直线”上整数解。,但目标直线在向可行域内平移过程中，若需平移多次才能达到目的，将十分麻烦。,方法二：整点验证法：,当可行域较小、边界附近的整点较少时,可以用整点验证法；将每个可能的整点代入目标函数确定最优解。,但当可行域较大、边界附近的整点较多时运算量较大,规律总结：,EX1:,某学校预算,2000,元购买单价为,100,元的桌子和,40,元的凳子，希望购买的桌凳总数尽可能多，但凳子不少于桌子，且不多于桌子的,2,倍，求该学校所购买的桌、凳数分别为多少？,解：设学校购买的桌、凳数分别为,x,、,y,，总数为,z,，则,z=,x,+y,且,x,、,y,满足：,即,作出可行域如图所示,0,2,4,8,10,14,18,6,12,16,2,6,12,14,22,4,10,8,16,18,20,24,x,y,5x+2y=100,2x,y=0,x-y,=0,x,+,y,=0,A,答：,该学校应购买,11,张桌子，,22,个凳子,.,0,2,4,8,10,14,18,6,12,16,2,6,12,14,22,4,10,8,16,18,20,24,x,y,5x+2y=100,2x,y=0,x-y,=0,x,+,y,=0,A,EX2,某商店计划同时销售某品牌电热水器和太阳能热水器，由于市场需求旺盛，这两种产品供不应求，因该商店根据具体情况（如成本、员工工资）确定产品的月采购量，具体数据如下，问这两种产品各采购多少时，才能使总利润最大？最大利润是多少？,同学们再见！,多谢指教,