线性规划中的整点问题.ppt

《线性规划中的整点问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划中的整点问题xyo武穴实验高中杨耀平例1、某人有楼房一座，室内面积共180m2，拟分隔成两类房间作为旅游客房，大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？解：设隔出大房间x间，小房间y间，收益为z元，则Z=200x+150y，且x,y满足如图，可行域为阴影部分，作直线l0：200x+150y=0，即

2、4x+3y=0,将直线l0平移到A点时z最大。解方程组4x+3y=00248101418612162612144108xy6x+5y=605x+3y=40A由图可知目标函数取得最大值的整点分布在可行域上侧靠近边界的区域，考察可能的整点(0，12),(1，10),(2，9),(3，8),(4，6),(5，5),(6，3),(7，1),(8，0)将这些点分别代入Z=200x+150y,求出各点对应的值，得整点(0，12),(3，8)是最优解，此时z的最大值为1800。=4x+3y=00248101418612162612144108xy6x+5y=60

3、5x+3y=40A答：他应隔出大房间0间、小房间12间或者大房间3间、小房间8间，能获得最大收益每天1800元例2、要将两种大小不同的钢板截成Ａ．Ｂ．Ｃ三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：A规格Ｂ规格Ｃ规格第一种钢板211第二种钢板123今需要Ａ、Ｂ、Ｃ三种规格的成品分别为15，18，27块，各截这两种钢板多少张可以满足需要且使所用钢板数目最少？解：设需要截第一种钢板x张，第二种钢板y张，共需这两种钢板z张，则z=x+y,且2x+y≥15x+2y≥18x+3y≥27x≥0,y≥0作出可行域如图所示2x+y=15x+2y=1

4、8x+3y=27y+x=002481014186121626121422410816182024xyA作出直线l0:x+y=0并平移，由图可知，当直线z=x+y经过可行域上的点A时，截距z最小。解方程组得点A的坐标为.答：满足题意的截法有两种：截第一种钢板3张，第二种钢板9张，或者截第一种钢板4张，第二种钢板8张方法一：调整最值法：当目标函数系数不大时可以用调整最值法，一般步骤为：①平移直线寻找非整最优解；②调整最值，确定“目标直线”③由“目标直线”方程代入约束条件，并求变量范围：④确定“目标直线”上整数解。但目标直线在向可行域内平移过程中，若需平

5、移多次才能达到目的，将十分麻烦。方法二：整点验证法：当可行域较小、边界附近的整点较少时可以用整点验证法；将每个可能的整点代入目标函数确定最优解。但当可行域较大、边界附近的整点较多时运算量较大规律总结：EX1:某学校预算2000元购买单价为100元的桌子和40元的凳子，希望购买的桌凳总数尽可能多，但凳子不少于桌子，且不多于桌子的2倍，求该学校所购买的桌、凳数分别为多少？解：设学校购买的桌、凳数分别为x、y，总数为z，则z=x+y,且x、y满足：即作出可行域如图所示02481014186121626121422410816182024xy5x+2y=1

6、002x－y=0x-y=0x+y=0A答：该学校应购买11张桌子，22个凳子.02481014186121626121422410816182024xy5x+2y=1002x－y=0x-y=0x+y=0AEX2某商店计划同时销售某品牌电热水器和太阳能热水器，由于市场需求旺盛，这两种产品供不应求，因该商店根据具体情况（如成本、员工工资）确定产品的月采购量，具体数据如下，问这两种产品各采购多少时，才能使总利润最大？最大利润是多少？同学们再见！多谢指教