破解线性规划中的整点问题

《破解线性规划中的整点问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、破解线性规划中的整点问题河南省三门峡市卢氏一高（472200）赵建文Email:zhaojw1968@tom.com线性规划中的整点问题是高中数学线性规划中的重要一类问题，是高中数学的一个难点，本文将整数线性规划问题解法作以简单介绍供同学们学习时参考.单位产品所需资金月资金供应量（百元）电热水器太阳能热水器成本1030300工资105110单位利润86例某商店计划同时销售某品牌电热水器和太阳能热水器，由于市场需求旺盛，这两种产品供不应求，因该商店根据具体情况（如成本、员工工资）确定产品的月采购量，具体数据如下，问这两种产品各采购多少时，才能使总利润最大？最大利润是多少

2、？分析：本题是整数规划问题，设采购电热水器台、太阳能热水器台，列出约束条件和目标函数，用图解法解之.解析：设月采购电热水器台、太阳能热水器台，月总利润为元，则，即，目标函数为=作出可行域如图所示，作直线：=0，平移直线=知过M时，=10320，但=，=不是整数，所以可行域内点M不是整点最优解.求整点最优解解法一网格平移法首先在可行域内打网格，其次描出M附近的所有整点，接着平移直线：=0，会发现当移至（8，6）时，直线在轴上截距最大，即=10000元.解法二特值检验法由图可知目标函数取得最大值的整点应分布在可行域右上侧靠近边界的区域，一次取得满足条件的整点，（0，10）

3、，（1，9），（2，9），（3，9）（4，8），（5，8），（6，8），（7，7），（8，6），（8，5），（9，4），（10，2），（10，1），（11，0）.将这些点分别代入=，求出各点对应的值，经验证可知，在整点(8,6)处=10000元.解法三调整最优法由非整点最优解得=10320，∴且能被200整除，令，即，代入约束条件整理得无解，即，再令，即，代入约束条件整理得，，∴=7或=8，当=7时，（舍），当=8时，，故最优整点为（8，6）.故每采购热水器8台、太阳能热水器6台时，总利润最大，最大值为10000元.点评：对整数规划问题，先按一般规划问题求出最优解，若

4、最优解是整数，则此最优解就是整数规划的最优解，若最优解不是整数，则可用下边三种方法整点最优解：（1）网格平移法：打网格，找出可行域内整点，平移目标函数，找出最优整点；（2）特值验证法:在非整点最优解的附近靠近边界可行域内找整点，代人目标函数通过计算比较，找出最优解；（3）调整优值法:先求、取非整点最优解时目标函数的最大（小）值，根据不定方程整数解的知识知，目标函数的最值应是目标函数中、系数公约数的整数倍，据此调整目标函数的最大值，取比、取非整数最优解对时最大（小）值小（大）、与之最接近、能被目标函数中、系数公约数整除的数作为新最值，从中用把表示出来，代人约束条件，求出

5、的取值范围，在的取值范围中取出整数作为值，代入目标函数求出值，若值、值都是整数，则此、值就是最优整数解，若、值不是整数，则取与第二取得最值最近且能被目标函数中、系数公约数整除的数作为新最值，重复上述步骤，直到找出整点最优解.跟踪练习产品第一种木料第二种木料课桌0.180.08凳子0.090.141.某工厂有生产课桌与凳子的两种木料，第一种木料36，第二种木料28，生产一张课桌与一个凳子需要两种材料如表所示，生产一张课桌获利15元，生产一个凳子获利10元，该工厂在现有条件下，课桌与凳子各生产多少时，获得利润最多？2.某学校预算2000元购买单价为100元的桌子和40元的

6、凳子，希望购买的桌凳总数尽可能多，但凳子不少于桌子，且不多于桌子的2倍，求该学校所购买的桌、凳数分别为多少？3.某建筑公司有7量装载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车，驾驶员9人，在某项工程建设中，该公司承包每天至少360方土方任务，已知每天往返的次数为：A型卡车8次、B型卡车6次，每辆卡车每天的费用为：A型卡车160元、B型卡车256元，问该公司每天派出A型卡车B型卡车各多少辆时，既能完成任务又使成本费用最低?答案：1.解析：设该厂每天生产课桌张，凳子个，获得总利润为元，则约束条件为，即，目标函数为=，作出表示可行域如图所示，作出目标函数：=0，平移

7、知，：=过A点时，，解得A（190，120），即=190，=120时，=4050元，因=190，=120也是整数，∴也是原整数规划的解，∴当生产课桌190张，凳子120个时，总利润最大，最大利润为4050元.2.解析：设学校购买的桌、凳数分别为、，总数为，则约束条件为，即，目标函数为=，作出表示的可行域如图所示，作出目标函数：=0，平移直线知，直线：=过A点时，，解得，=，=，不为整数解，不是原规划问题的解，此时=，比小且接近的整数为33，令=33，则=，代人原约束条件解得=11，则=22，所以该学校应购买11张桌子，22个凳子.3.解析：设该公司每