资源描述：
《线性规划中整点问题的求解策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、线性规划中整点问题的求解策略四川省武胜飞龙中学校梁洪斌郑秋华(638402)在有关线性规划的求解问题中，经常会碰到最优化决策的整点问题，而解决此类问题一般以线性规划为其重要的理论基础。然而在实际求解屮，对于最优解(x,y)通常要满足x,yeN,这种最优解称为整点最优解时，很多同学感到束手无策，下而通过具体例了谈谈如何求整点最优解的问题.1.平移找解法作出可行域后，先打网格，描出整点，然后平移直线/,直线/最先经过或最后经过的那个整点便是整点最优解.例1、某木器厂生产圆桌和衣柜两种产品，现冇两种木料，第一种冇72m3,
2、第二种有56m3,假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜nJ获利10元.木器厂在现有木料条件下，圆桌和衣柜各生产多少，才使获得利润M多?产品木料(单位m3)第一种第二种圆桌0.180.08衣柜0.090.280.18x+0.09y<72解:设生产圆桌x只，生产衣柜y个，利润总额为z元，那么0.08x4-0.28^<56x>0y>Qz=6x+10y.如图所示,作出以上不等式组所表示的平而区域即对行域.作直线/:6x+10y=0,即k3x+5
3、y=0,把直线/向右上方平移至厶的位置时，总线经过可行域上点M,且与原点距离最人，此时z=6x+10y取最大值。解方程组J0，18X+0,09>=72,WM点10.08%+0.28y=56坐标(350,100).答：应生产圆桌350只，生产衣柜100个，能使利润总额达到最大.点评：本题的最优点恰为直线0.18x+0.09y=72和0.08X+0.28尸56的交点Mo例2冇一批钢管，长度都是4000mm,要截成500nmi和600nini两种毛坯，且这两种毛坯按数量比不小于丄配套，怎样截最合理？/£3xX€3解:设截
4、500mm的钢管x根,600mm的y根,总数为z根。根据题意，得作出如图所示的可行域内的整点，作一组平行直线x+y二t,经过可行域内的点且和原点距离最远的直线为过8(8,0)的直线，这时x+y=8.由于x,y为正整数，知(8,0)不是最优解。显然要往下平移该直线，在可行域内找整点，使x+y=7,可知点(2,5),(3,4),(4,3),(5,2),(6,1)均为授优解.答：略.点评：本题与上题的不同Z处在于，肓线x+y=t经过可行域内且和原点距离最远的点B(8,0)并不符合题意，此时必须往下平移该直线，在可行域内找整
5、点，比如使x+y=7,从而求得最优解。从这两例也可看到，平移找解法一般适用于其可行域是有限区域且整点个数乂较少，但作图要求较高。二、整点调整法先按“平移找解法”求出非整点最优解及最优值，再借助不定方程的知识调整最优值,最后筛选出整点最优解.2x-y-3>0例3.已知X』满足不等式组2兀+3y-6v0,求使x+y収最大值的整数3兀一5)—15v0解：不等式组的解集为三直线2兀一)一3=0,/2:2兀+3y—6=0,/3:3x-5^-15=0所围成的三角形内部(不含边界)，设厶与厶，厶与厶，厶与厶交点分别为1537512
6、A』,C,则A,B,C坐标分别为A(—3(0,—3),C(—,一一),841919作一纟r平行线/：兀+),=/平行于片:兀+)=0,当/往厶右上方移动时，/随Z增大，可取1,2,3,••曲过C点时宀最大为譽但不是整数解,乂由0*鲁知兀当兀=1时，代入原不等式组得y=-2,Ax+y=-1；当x=2时，得y=0或一1,•••兀+y=2或1；fx=2fx=3当x=3时，y=-bAx+y=2,故兀+y的最大整数解为｛或｛•=0=-13•逐一检验法由于作图有时有谋差，有吋仅有图象不一定就能准确而迅速地找到最优解，此时可将若干
7、个可能解逐一校验即可见分晓.例4一批长4000mm的条形钢材，需要将具截成长分别为518mm与698mm的甲、乙两种r518»ffij<400D&尸卑毛坯，求钢材的最人利用率.解：设甲种毛坏截X根，乙种毛坏截y根，钢材的利用率为P，则P■洒"碗尸.]00—①，1=1标函数为4000②，线性约朿条件①表示的可行域是图屮阴影部分的整点.②表示•直线518x+698y=4000平行的直线系。所以使P取得最大值的最优解是阴影内最靠近直线518x+698y=4000的整点坐标.如图看到(0,5),(1,4),(2,4),(3,
8、3),(4,2),(5,2),(6,1),(7,0)都有可能是最优解，将它们的坐标逐一代入②进行校验，可知当x=5,y=2时，^=W.答：当甲种毛坯截5根，乙种毛坯截2根，钢材的利用率最大，为99.65%.解线性规划问题的关键步骤是在图（可行域）上完成的，所以作图时应尽可能精确，图上操作尽可能规范，但考虑到作图时必然会冇谋差，假如图上的最优点并
