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

《例析线性规划中的整点最优解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例析线性规划中的整点最优解浙江徐志平【大中小】【关闭】　　在组织社会化生产、经营管理活动中，我们经常会碰到最优决策的实际问题。而解决这类问题的现代管理科学以线性规划为其重要的理论基础，其本质都是寻求整个问题的某项整体指标的最优解。但在实际问题中，最优解(x,y)通常要满足x,y∈N，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解.1．平移找解法作出可行域后，先打网格，描出整点，平移直线，最先经过或最后经过的整点便是整点最优解.例1有一批钢管，长度都是4000mm，要截成500mm和600mm两种毛坯，且这两种毛坯按数量比不小于配套，怎样截最合理？分析：先设出未知数，

2、建立约束条件和目标函数后，再通过平移直线，使它经过整点的方法来求整点最优解．解：设截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支援物资

3、的任务。该公司有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不是整点，继续往上平移，最先经过的整点是

4、（8，0）．即只调配A型卡车，所花最低成本费z=320×8=2560（元）．答：略．这种方法首先要充分利用非整点最优解的信息，结合精确的作图才行，当其可行域是有限区域且整点个数又较少，通常可行域是封闭的多边形，这时可以通过平移直线找到最优解．2．调整优值法先求出非整点最优解及最优值，再借助不定方程的知识调整最优值，最后筛选出整点最优解．例3要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得

5、所需三种规格成品，且使所用钢板张数最少？解：设需截第一种钢板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),它们都是最优解.答:要截得所需三种规格的钢板,且使所截两种钢板的张

6、数最少的方法有两种:第一种截法是截第一种钢板3张.第二种钢板9张;第二种截法是截第一种钢板4张、第二种钢板8张.两种方法都最少要截两种钢板共12张．例4　某人承揽一项业务：需做文字标牌2个，绘画标牌3个。现有两种规格的原料，甲种规格每张3,可做文字标牌1个、绘画标牌2个；乙种规格每张2,可做文字标牌2个、绘画标牌1个。求这两种规格的原料用多少张才能使总的用料面积最小？解：设用甲种规格原料x张，乙种规格原料y张，则可做文字标牌x+2y个，绘画标牌2x+y个．由题意可得，所用原材料的总面积，作出可行域如图示阴影部分内的整点，作直线，作一组与直线平行的直线。当直线通过2x+y=3与直线x

7、+2y=2的交点时，t取得最小值因为不是整点，所以它不是最优解。当时，，可知当时，代入约束条件，可得，即经过可行域内的整点，点B（1，1）满足3x+2y=5，使t最小，所以最优解为B（1，1）．答：用甲种规格的原料1张，乙种规格的原料1张，能使总的用料面积最小，为5。求整点最优解时，可先放松可行解必须为整点的要求，转化为普通线性规划求解。若所求得的最优解不是整点时，再借助不定方程的知识调整最优值，最后求出整点最优解，特别适用于可行域是一侧为开放的无限大的平面区域这类问