线性规划之最优整数解问题

《线性规划之最优整数解问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性规划之最优整数解问题河北省景县梁集高中张国营线性规划是高中数学新教材的新增内容，对学生及教师来说都不是太熟悉。教材对这一部分叙述的也不是很详细，所以学生学起来很费劲，教师教起来也不容易。这一内容在近几年高考中考察的知识点比较容易，一般以选择或填空题的形式出现。根据我多年的教学经验，我认为在学习本部分内容时，应注意以下几点：1.判定最优解：求线性目标函数z=ax+by(a0、b0)在线性约束条件下的最优解问题，可转化为求直线y=-在y轴上的截距的最大值和最小值问题。即根据直线在y轴上的截距和z的关系来判断何时z取得最大（小）值。我把这种方

2、法叫做截距判断法。具体情况如下：当b>0时，若取最大值，z也取得最大值，若取最小值，z也取得最小值；当b<0时，结果相反。2.求出最优解：根据动直线与可行域有公共点且t取最大（小）值时所经过的可行域内点的坐标来计算出最优解。3.求出最优整数解：这是最复杂的一步，也是最关键的一步。此处是学生学习这一部分的难点。这一步求解的方法很多，下面举例来说明常用的一些方法。例：要将两种大小不同的钢板截成A、B、C三种规格的小钢板，第一种钢板可截成A、B、C三种规格的小钢板分别为2块、1块、1块；第二种钢板可截成A、B、C三种规格的小钢板分别为1块、2块、

3、3块.现需要A、B、C三种规格的小钢板分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格的成品，且使用钢板总张数最少？解：设需截第一种钢板x张，第二种钢板y张，总钢板用z张，据题意得约束条件：①②③④目标函数为z=x+y，作出可行域，作直线l：x+y＝0，将直向右上方平移，用截距判断法易知当动直线经过可行域上的点A（3.6，7.8），即①②的解时z=x+y取最小值11.4，此为最优解。但此时钢板数不是整数，故不是最优整数解。下面给出此题求最优整数解的几种方法：法1、因为z=x+y取最小值11.4时，不是最优整数解，故取z的值为

4、12，即在直线x+y＝12上找坐标为整数的点（且在可行域内），将x=0,1,2,……,12分别代入目标函数验证，可得点B（3,9）、C（4,8）是最优整数解。法2、解方程组　和　　得到x+y＝12落在可行域内的两个端点B（3,9）、D（4.5，7.5），而在这两个端点之间（包含这两个端点）的整点只有B（3,9）、C（4,8）是最优整数解。法3、由x+y＝12得y＝12－x，代入约束条件得3≤x≤4.5且x∈N，所以x＝3,4，代入x+y＝12检验，得（3,9）、（4,8）均符合题意，为最优整数解。法4、结合约束条件和可行域，一一求出靠近边界

5、的整数点（0,15）、（1,13）、（2，11）、（3,9），（4,8）、（5,8）、（6,7）、……，（27,0），然后代入目标函数，求出z的最小值时的解即为最优解。总之，对这一部分内容一定要做到真正理解，才能灵活运用上述几种方法，针对不同的题目采用不同的方法，迅速求出最优整数解。邮编：053517手机：15932434455邮箱：zghbzgy@163.com