线性规划中整点最优解的求解策略
在工程设计、经营管理等活动中,经常会碰到最优化决策的实际问题,而解决此类问题一般以线性规划为其重要的理论基础。然而在实际问题中,最优解 (x,y) 通常要满足x,y∈N ,这种最优解称为整点最优解,下面通过具体例子谈谈如何求整点最优解 .
1.平移找解法
作出可行域后,先打网格,描出整点,然后平移直线l,直线l最先经过或最后经过的那个整点便是整点最优解.
例1、某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有72m3,第二种有56m3,假设生产每种产品都需要用两种木料,生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜可获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?
解:设生产圆桌x只,生产衣柜y个,利润总额为z元,那么
0.18x0.09y720.08x0.28y56 而z=6x+10y. x0
y0
如图所示,作出以上不等式组所表示的平面区域,即可行域.
作直线l:6x+10y=0,即l:3
x+5y=0,把直线l向右上方平移至l1的位置时,直线经过可行域上点M,且与原点距离最大,此时z=6x+10y取最大值。
0.18x0.09y72解方程组,得M点坐标(350,100). 0.08x0.28y56
答:应生产圆桌350只,生产衣柜100个,能使利润总额达到最大.
点评:本题的最优点恰为直线0.18x+0.09y=72和0.08x+0.28y=56的交点M。
例 2 有一批钢管,长度都是4000mm,要截成500mm和600mm两种毛坯,且这两种1毛坯按数量比不小于配套,怎样截最合理? 3
解:设截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)均为最优解.
答:略.
点评:本题与上题的不同之处在于,直线x+y=t经过可行域内且和原点距离最远的点B(8,0)并不符合题意,此时必须往下平移该直线,在可行域内找整点,比如使x+y=7,从而求得最优解。
从这两例也可看到,平移找解法一般适用于其可行域是有限区域且整点个数又较少,但作图要求较高。
二、整点调整法
先按“平移找解法”求出非整点最优解及最优值,再借助不定方程的知识调整最优值,最后筛选出整点最优解. y l
2xy30例3.已知x,y满足不等式组2x3y60,求使xy
3x5y150
取最大值的整数x,y.
解:不等式组的解集为三直线l1:2xy30,l2:
2x3y60,l3:3x5y150所围成的三角形内部(不1A O l3 C x l
2
l1与l3,含边界),设l1与l2,则A,B,C坐标分别为A(l2与l3交点分别为A,B,C,
C(7512,), 1919
作一组平行线l:xyt平行于l0:xy0,
当l往l0右上方移动时,t随之增大,
∴当l过C点时xy最大为153,),B(0,3),8463,但不是整数解, 19
75知x可取1,2,3, 19
当x1时,代入原不等式组得y2, ∴xy1;
当x2时,得y0或1, ∴xy2或1;
当x3时,y1, ∴xy2,
x2x3故xy的最大整数解为或.
y0y1又由0x
3.逐一检验法
由于作图有时有误差,有时仅有图象不一定就能准确而迅速地找到最优解,此时可将若干个可能解逐一校验即可见分晓.
例4 一批长4000mm 的条形钢材,需要将其截成长分别为518mm与698mm的甲、乙两种毛坯,求钢材的最大利用率.
解:设甲种毛坯截 x 根,乙种毛坯截 y 根,钢材
的利用率为 P ,则
①,目
标函数为
②,线性约束条
件①表示的可行域是图中阴影部分的整点.②表示与
直线518x+698y=4000平行的直线系。所以使P取得
最大值的最优解是阴影内最靠近直线
518x+698y=4000的整点坐标.如图看到(0,5),(1,
4),(2,4),(3,3),(4,2),(5,2),(6,1),(7,
0)都有可能是最优解,将它们的坐标逐一代入②进行
校验,可知当x=5,y=2时,
.
答:当甲种毛坯截5根,乙种毛坯截2根,钢材的利用率最大,为99.65%.
解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确,图上操作尽可能规范,但考虑到作图时必然会有误差,假如图上的最优点并不十分明显易辨时,不妨将几个有可能是最优点的坐标都求出来,然后逐一进行校验,以确定整点最优解.
线性规划中整点最优解的求解策略
在工程设计、经营管理等活动中,经常会碰到最优化决策的实际问题,而解决此类问题一般以线性规划为其重要的理论基础。然而在实际问题中,最优解 (x,y) 通常要满足x,y∈N ,这种最优解称为整点最优解,下面通过具体例子谈谈如何求整点最优解 .
1.平移找解法
作出可行域后,先打网格,描出整点,然后平移直线l,直线l最先经过或最后经过的那个整点便是整点最优解.
例1、某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有72m3,第二种有56m3,假设生产每种产品都需要用两种木料,生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜可获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?
解:设生产圆桌x只,生产衣柜y个,利润总额为z元,那么
0.18x0.09y720.08x0.28y56 而z=6x+10y. x0
y0
如图所示,作出以上不等式组所表示的平面区域,即可行域.
作直线l:6x+10y=0,即l:3
x+5y=0,把直线l向右上方平移至l1的位置时,直线经过可行域上点M,且与原点距离最大,此时z=6x+10y取最大值。
0.18x0.09y72解方程组,得M点坐标(350,100). 0.08x0.28y56
答:应生产圆桌350只,生产衣柜100个,能使利润总额达到最大.
点评:本题的最优点恰为直线0.18x+0.09y=72和0.08x+0.28y=56的交点M。
例 2 有一批钢管,长度都是4000mm,要截成500mm和600mm两种毛坯,且这两种1毛坯按数量比不小于配套,怎样截最合理? 3
解:设截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)均为最优解.
答:略.
点评:本题与上题的不同之处在于,直线x+y=t经过可行域内且和原点距离最远的点B(8,0)并不符合题意,此时必须往下平移该直线,在可行域内找整点,比如使x+y=7,从而求得最优解。
从这两例也可看到,平移找解法一般适用于其可行域是有限区域且整点个数又较少,但作图要求较高。
二、整点调整法
先按“平移找解法”求出非整点最优解及最优值,再借助不定方程的知识调整最优值,最后筛选出整点最优解. y l
2xy30例3.已知x,y满足不等式组2x3y60,求使xy
3x5y150
取最大值的整数x,y.
解:不等式组的解集为三直线l1:2xy30,l2:
2x3y60,l3:3x5y150所围成的三角形内部(不1A O l3 C x l
2
l1与l3,含边界),设l1与l2,则A,B,C坐标分别为A(l2与l3交点分别为A,B,C,
C(7512,), 1919
作一组平行线l:xyt平行于l0:xy0,
当l往l0右上方移动时,t随之增大,
∴当l过C点时xy最大为153,),B(0,3),8463,但不是整数解, 19
75知x可取1,2,3, 19
当x1时,代入原不等式组得y2, ∴xy1;
当x2时,得y0或1, ∴xy2或1;
当x3时,y1, ∴xy2,
x2x3故xy的最大整数解为或.
y0y1又由0x
3.逐一检验法
由于作图有时有误差,有时仅有图象不一定就能准确而迅速地找到最优解,此时可将若干个可能解逐一校验即可见分晓.
例4 一批长4000mm 的条形钢材,需要将其截成长分别为518mm与698mm的甲、乙两种毛坯,求钢材的最大利用率.
解:设甲种毛坯截 x 根,乙种毛坯截 y 根,钢材
的利用率为 P ,则
①,目
标函数为
②,线性约束条
件①表示的可行域是图中阴影部分的整点.②表示与
直线518x+698y=4000平行的直线系。所以使P取得
最大值的最优解是阴影内最靠近直线
518x+698y=4000的整点坐标.如图看到(0,5),(1,
4),(2,4),(3,3),(4,2),(5,2),(6,1),(7,
0)都有可能是最优解,将它们的坐标逐一代入②进行
校验,可知当x=5,y=2时,
.
答:当甲种毛坯截5根,乙种毛坯截2根,钢材的利用率最大,为99.65%.
解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确,图上操作尽可能规范,但考虑到作图时必然会有误差,假如图上的最优点并不十分明显易辨时,不妨将几个有可能是最优点的坐标都求出来,然后逐一进行校验,以确定整点最优解.