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