例析线性规划中的整点最优解.doc

例析线性规划中的整点最优解

浙江 徐志平

【大 中 小】【关闭】

　　在组织社会化生产、经营管理活动中，我们经常会碰到最优决策的实际问题。而解决这类问题的现代管理科学以线性规划为其重要的理论基础，其本质都是寻求整个问题的某项整体指标的最优解。但在实际问题中，最优解 (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，往上平移直线L0，当直线经过可行域内的点A（7.5，0）时可使Z 最小，但 A不是整点，继续往上平移，最先经过的整点是（8，0）．
即只调配A 型卡车，所花最低成本费 z=320×8=2560（元）．
答：略．这种方法首先要充分利用非整点最优解的信息，结合精确的作图才行，当其可行域是有限区域且整点个数又较少，通常可行域是封闭的多边形，这时可以通过平移直线找到最优解．
2．调整优值法 先求出非整点最优解及最优值，再借助不定方程的知识调整最优值，最后筛选出整点最优解．
例3 要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：
规格类型
钢板类型
A规格
B规格
C规格
第一种钢板
2
1
1
第二种钢板
1
2
3
今需要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个。现有两种规格的原料，甲种规格每张3 , 可做文字标牌1个、绘画标牌2个；乙种规格每张2 ,可做文字标牌2个、绘画标牌1个。求这两种规格的原料用多少张才能使总的用料面积最小？解：设用甲种规格原料x张，乙种规格原料y张，则可做文字标牌x+2y个，绘画标牌2x+y个．由题意可得 ，所用原材料的总面积 ，作出可行域如图示阴影部分内的整点，作直线 ，作一组与直线 平行的直线 。当直线 通过2x+y=3与直线x+2y=2的交点 时，t取得最小值
因为 不是整点，所以它不是最优解。当 时， ，可知当 时， 代入约束条件，可得 ，即经过可行域内的整点，点B（1，1）满足3x+2y=5，使t最小，所以最优解为B（1，1）．
答：用 甲种规格的原料1张，乙种规格的原料1张，能使总的用料面积最小，为5 。求整点最优解时，可先放松可行解必须为整点的要求，转化为普通线性规划求解。若所求得的最优解不是整点时，再借助不定方程的知识调整最优值，最后求出整点最优解，特别适用于可行域是一侧为开放的无限大的平面区域这类问题。3.逐一校验法 由于作图有时有误差，有时仅有图象不一定就能准确而迅速地找到最优解，此时可将若干个可能解逐一校验即可见分晓．
例5 　某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房．大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为 15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？最大收益是多少？
解：设隔出大、小房间分别为 x 间、 y 间，收益为 z 元，则目标函数 z=200x+150y. 其中 x 、 y 满足约束条件 作出可行域 如图示阴影部分内 的整点 ，由图解法易得z=200x+150y过点 时，目标函数z取得最大值．但x、y必须是整数，还需在可行区域内找出使目标函数z取得最大值的整点。显然目标函数z取得最大值的整点一定是分布在可行区域的右上侧，则利用枚举法进行逐一校验即可求出整点最优解．这些整点有：(0 12) ，(1 10)，(2 9) (3 8) (4 6) (5 5) (6 3) (7 1) (8 0) 分别代入z=200x+150y，逐一校验，可得取整点(0，12) 或(3，8)时，zmax=200×0+150×12=200×3+150×8=1800(元) ．答：要获得最大收益，有两种方案：（1）只隔出小房间12间；（2）隔出大房间3间，小房间8间。最大收益为1800元．
例6 一批长4000mm 的条形钢材，需要将其截成长分别为518mm与698mm的甲、乙两种毛坯，求钢材的最大利用率．
解：设甲种毛坯截 x 根，乙种毛坯截 y 根，钢材的利用率为 P ，则 ①，目标函数为 ②，线性约束条件①表示的可行域是图中阴影部分的整点．②表示与直线518x+698y4000平行的直线系。所以使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%．
解线性规划问题的关键步骤是在图（可行域）上完成的，所以作图时应尽可能精确，图上操作尽可能规范，但考虑到作图时必然会有误差，假如图上的最优点并不十分明显易辨时，不妨将几个有可能是最优点的坐标都求出来，然后逐一进行校验，以确定整点最优解.