线性规划整点问题

线性规划中求整点最优解的两种常用方法简单的线性规划是新教材的新增加内容，它在人们的生活和生产实践中有着广泛的应用，因此，它必将成为高考的一个新亮点，而在线性规划中，求整点最优解的问题是一个难点，下面介绍两种常用的方法.1、平移求解法步骤：1、作出可行域（若是实际问题，则首先应根据题意列出线性约束条件，找出线性目标函数）；2、找出最优解（当最优解不是整数解时，过最优解作与线性目标函数平行的直线）；3、平移直线族（在平面直角坐标系中，打出网格，在可行域内，平移步骤2中所作的直线，最先经过的整点即为所求的整点最优解）. 【范例引导】例1、要将两种大小不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格今需要A 、B 、C 三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少.解：设需截第一种钢板x 张，第二种钢板y 张，则⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥+≥+≥+0027*******y x y x y x y x 目标函数为：y x z +=.作出可行域，由⎪⎪⎩⎪⎪⎨⎧==⇒⎩⎨⎧=+=+539518152273y x y x y x ，所以A ⎪⎭⎫ ⎝⎛539,518.此时，5211=+y x ，因为A 点不是整点，它是非整点最优解，用平移求解法，打出网格，将平行直线族y x t +=中的5211=+y x 向右上方平移，由图可知，在可行域中最先经过的整点是B （3，9）和C （4，8），它们是所求的最优整点解，此时.12=+y x答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，一种是截第一种钢板3张、第二种钢板9张；二是截第一种钢板4张、第二种钢板8张. 2、调整优值法步骤：1、求出非整点的最优解及最优值（即对应最优解的目标函数值）；2、借助不定方程的知识调整最优值；3、筛选出符合条件的最优解. 【范例引导】例2、用“调整优值法” 解例1 .解:由⎪⎪⎩⎪⎪⎨⎧==⇒⎩⎨⎧=+=+539518152273y x y x y x ，所以A ⎪⎭⎫ ⎝⎛539,518，因为A 点不是整点，它是非整点最优解，此时，5211=+=y x t = 11.4不是整数，因而需要对t 进行调整，由于y x ,为整数，所以t 为整数，而与11.4最靠近的整数是12，故取t =12，即12=+y x ，将x y -=12代入到线性约束条件，解得：5.43≤≤x ，取4,3==x x 得整点的最优解为：B （3，9）和C （4，8），此时.12=+y x例3、已知y x ,满足不等式组：⎪⎪⎩⎪⎪⎨⎧∈∈≥≥≤+≤+Ny N x y x y x y x ;0;040356056（*）求y x z 150200+=的最大值. 解：根据约束条件画出可行域，由⎩⎨⎧=+=+40356056y x y x 得非整点最优解)760,720(，此时，711857760150720200=⋅+⋅=z 也是非整数.因为y x z 150200+=)34(50y x +=，又y x ,为整数，所以z 一定是50的倍数.令y x z 150200+==1850，则)437(31x y -=，代入到（*）式中得3212≤≤x ，故当3=x 时，325=y 为非整数解.令y x z 150200+==1800，则)436(31x y -=，代入到（*）式中得：40≤≤x ，经计算（0，12），（3，8）为其整数解，此时，1800=z . 【名师小结】在一定的约束条件下使某目标达到最大值或最小值的问题称为数学规划，而当约束条件和目标函数都是一次的（又称线性的），我们称这种规划问题为线性规划.例如，如何分配有限的资源以达到某种既定的目标（如利润最大，支付最小等），称为资源分配问题，而许多资源分配问题可以归结为线性规划模型来处理. 在解线性规划应用问题时的一般步骤为：（1）审题；（2）设出所求的未知数；（3）列出约束条件，建立目标函数；（4）作出可行域；（5）找出最优解. 【误区点拨】1、对于整点解问题，其最优解不一定是离边界点最近的整点，而先要过边界点作目标函数By Ax t +=的图象，则最优解是在可行域内离直线By Ax t +=最近的整点；2、熟练掌握二元一次不等式所表示的平面区域是解决线性问题的基础，因此，正确地作出可行域是我们解题的关键；3、一般的线性规划问题，其约束条件是平面上的一个多边形闭区域，或者是向某一方向无限延展的半闭区域，而目标函数必在边界取最值，且是边界的顶点处取最值，但不一定有最优整数解，这一点一定要注意. 【反馈训练】1、设y x ,满足⎪⎪⎩⎪⎪⎨⎧∈∈>>≤+<+zy z x y x y x y x ,0,01141023，求y x u 45+=的最大值. 2怎样搭配价格最低？3、有一化肥厂生产甲、乙两种混合肥料，生产1车皮甲种肥料或1车皮乙种肥料需要的主要原料和产生的利润分别是：磷酸盐4吨，硝酸盐18吨，利润10000元或磷酸盐1吨，硝酸盐15吨，利润5000元.工厂现有库存磷酸盐10吨，硝酸盐66吨，应生产甲、乙肥料各多少车皮可获得最大的利润？4、某工厂有甲、乙两种产品，计划每天各生产不少于15吨，已知生产甲产品1吨需煤9吨，电力4千瓦，劳动力3个；乙产品4吨需煤9吨，电力5千瓦，劳动力10个.甲产品1吨利润7万元，甲产品1吨利润12万元，但每天用煤不超过300吨，电力不超过200千瓦，劳动力只有300个，问每天生产甲、乙两种产品各多少，能使利润总额达到最大？ 【参考答案】1、最优整数解为（2，1），=m an u 14；2、10片A 和3片B 搭配价格最低为1.6元.3、最后归结为在约束条件⎪⎩⎪⎨⎧≥≥≤+≤+0,0661518104y x y x y x 下，求目标函数y x u 500010000+=的整数解问题，答案是生产甲、乙肥料各2车皮时可获得最大的利润30000元.4、最后归结为在约束条件⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+.15,15,300103,20054,30049y x y x y x y x 下，求目标函数y x u 127+=的整数解问题，答案是甲、乙两种产品各20吨、24吨，利润总额达到最大428元.。

对线性规划整点问题的探究一、精确图解法求整数最优解 ( 课本P88习题16 )某运输公司有7辆载重量为6t 的A 型卡车与4辆载重量为10t 的B 型卡车，有9名驾驶员。

在建筑某段高速公路中，此公司承包了每天至少搬运360t 沥青的任务。

已知每辆卡车每天往返的次数为A 型卡车8次，B 型卡车6次，每辆卡车每天往返的成本费A 型车160元，B 型车252元。

每天派出A 型车和B 型车各多少辆公司所花的成本费最低？解：设每天派出A 型车x 辆、B 型车y 辆，公司所花的成本为z 元，则0x 70y 4x y 968x 106y 360x,y Z ≤≤⎧⎪≤≤⎪⎪+≤⎨⎪⨯⨯+⨯⨯≥⎪∈⎪⎩即0x 70y 4x y 94x 5y 30x,y Z≤≤⎧⎪≤≤⎪⎪+≤⎨⎪+≥⎪∈⎪⎩ z=160x+252y. 如图可行域是ABCD 围成的区域，作直线160x+252y=0，图形中两直线160x+252y=0和4x+5y=30接近平行， 比较直线斜率k=160252->-45, 平移直线160x+252y=0，由图可知在A （7，25）处取到最小值，但A 不是整数解。

在可行域内共有（3，4），（4，3），（4，4），（5，2），（5，3），（6，2），（6，3），（7，1），（7，2）整数解，经检验只有（5，2）是最优解，此时z=160×5+252×2=1304元。

这种方法适用于区域是封闭区域，且区域内的整数点可数，坐标网络画出来容易在图上识别哪些整点在可行域内。

二、利用近似解估算整数最优解 (课本P63例4)要将两种不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示： 今需要A 、B 、C 三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需的三种规格成品，且所使用钢板张数最少。

解：设需截取第一种钢板x 张，第二种钢板y 张，则2x y 15x 2y 18x 3y 27x,y 0,x,y N+≥⎧⎪+≥⎪⎨+≥⎪⎪≥∈⎩ 目标函数z=x+y,如图可行域是阴影部分，目标函数在A 点取到最优解。

线性规划中整点最优解的求解策略作者：郭海鹰来源：《理科爱好者(教育教学版)》2018年第02期【摘要】随着中学数学教育的改革和发展，简单线性规划问题已经逐渐成为中学数学教学中的一个基本内容。

简单线性规划问题与我们的日常生活息息相关，它主要涉及人力、物力、资金等资源的最优配置。

在中学数学教学中，整点最优解问题是简单线性规划的核心内容，但教材对于具体的验算过程并没有作过多的描述，以致中学生在解题过程中对于具体的验算过程掌握还不够清晰。

在资料上也经常见到有关简单线性规划整点最优解问题的求解方法，如：网格法，穷举法，筛选法，最小距离法等。

本文将介绍利用平移法求整点最优解的两种具体的操作方法—平移交轨法，平移近值法。

【关键词】线性规划；平移；整点最优解【中图分类号】G633.6 【文献标识码】B 【文章编号】1671-8437（2018）10-0069-021 平移交轨法该方法主要是在平移直线过程中，利用直线间的交点来缩小最优值的存在范围，因此其主要思想是联立方程求解交点，然后确定最优解可能的存在范围。

例1 要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：根据目标函数作出一组平行直线：x+y=t。

这些直线中经过可行域且和原点距离最近的直线，此直线经直线x+3y=27和2x+y=15的交点A（），此直线与原点的距离最近，z取得最小值，即：z= x+y=显然和都不是整数，而最优解中，x和y必须为整数，故A不是最优解，故将直线x+y= 向上平移到x+y=12，最优解可能存在于此直线上。

最优解必须在可行域内，故应求出直线2x+y=15和x+3y=27与x+y=12的交点：可得交点坐标为B（3，9），D（，），故有：3≤x≤这样便更进一步的缩小了x的范围，即x=3或4，将其代入x+y=12，可得y=9或8。

即（3，9）和（4，8）均为所求的最优解。

根据上述的分析解答过程，我们可以看到利用平移交轨法解题对于一般的简单线性规划问题都是适用的，其解题步骤如下：（1）设出所求的未知数，列出约束条件，建立目标函数；（2）作出可行域；（3）确定平移直线，寻找非整最优解；（4）联立方程求交点确定x或y的范围；（5）对x，y进行整点搜索，并确定整点解。

线性规划中的整点最优解在组织社会化生产、经营管理活动中，我们经常会碰到最优决策的实际问题。

而解决这类问题的现代管理科学以线性规划为其重要的理论基础，其本质都是寻求整个问题的某项整体指标的最优解。

但在实际问题中，最优解(x,y) 通常要满足x,y∈N ，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解 .1．平移找解法作出可行域后，先打网格，描出整点，平移直线，最先经过或最后经过的整点便是整点最优解.例 1 有一批钢管，长度都是4000mm，要截成500mm和600mm两种毛坯，且这两种毛坯按数量比不小于配套，怎样截最合理？分析：先设出未知数，建立约束条件和目标函数后，再通过平移直线，使它经过整点的方法来求整点最优解．解：设截500mm的钢管x根，600mm的y根，总数为z根。

根据题意，得，目标函数为，作出可行域如图示阴影部分内的整点，要打出网格，描出整点，网格上的交叉点为整点．作一组平行直线x+y=t，经过可行域内的点且和原点距离最远的直线为过B（8，0）的直线，这时x+y=8.由于x,y为正整数，知（8，0）不是最优解。

显然要往下平移该直线，在可行域内找整点，使x+y=7，可知点（2，5），（3，4），（4，3），（5，2），（6，1）均为最优解．答：略．例 2 某运输公司接受了向抗洪抢险地区每天至少送180t支援物资的任务。

该公司有8辆载重为6t的A型卡车与4辆载重为10t的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车4次，B型卡车3次；每辆卡车每天往返的成本费A型车为320元，B型车为504元。

请你们为该公司安排一下应该如何调配车辆，才能使公司所花的成本费最低？解：设每天调出A型卡车x辆、B型卡车y辆，公司所花的成本为z元，则，目标函数z=320x+504y，作出可行域如图示阴影部分内的整点，打出网格，描出整点，网格上的交叉点为整点．作L0：320x+504y=0，往上平移直线L，当直线经过可行域内的点A（7.5，0）时可使Z 最小，但 A不是整点，继续往上平移，最先经过的整点是（8，0）．即只调配A 型卡车，所花最低成本费z=320×8=2560（元）．答：略．这种方法首先要充分利用非整点最优解的信息，结合精确的作图才行，当其可行域是有限区域且整点个数又较少，通常可行域是封闭的多边形，这时可以通过平移直线找到最优解．2．调整优值法先求出非整点最优解及最优值，再借助不定方程的知识调整最优值，最后筛选出整点最优解．例3 要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？解：设需截第一种钢板x张，第二种钢板y张，共需z张则作出可行域如图示阴影部分内的整点，目标函数为z =x+y．作出一组平行直线x+y=t, 其中经过可行域内的点且和原点距离最近的直线，经过直线 x +3y=27 和直线 2x+y=15 的交点A（），直线方程为x+y= . 由于都不是整数，所以（）不是最优解 .当时， z=11 ，可知当时，，令 x+y=12,y=12-x代入约束条件，可得，所以 x=3 或 4 ，即经过可行域内的整点且与原点距离最近的直线是x+y=12, 经过的整点是 B(3,9) 和C(4,8), 它们都是最优解.答: 要截得所需三种规格的钢板,且使所截两种钢板的张数最少的方法有两种:第一种截法是截第一种钢板3张.第二种钢板9张;第二种截法是截第一种钢板4张、第二种钢板8张.两种方法都最少要截两种钢板共12张．例4 某人承揽一项业务：需做文字标牌2个，绘画标牌3个。