对线性规划整点问题的探究(蒋政)

对线性规划整点问题的探究精确图解法求整数最优解(课本P88习题16)x+y=94x+5y=30x+y=94x+5y=30160x+252y=0ABCD解：设每天派出A型车x辆、B型车y辆，公司所花的本钱为z元，那么即z=160x+252y.如图可行域是ABCD围成的区域，作直线160x+252y=0，图形中两直线160x+252y=0和4x+5y=30接近平行，比拟直线斜率k=>-,平移直线160x+252y=0，由图可知在A〔7，〕处取到最小值，但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规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需的三种规格成品，且所使用钢板张数最少。xxOy解：设需截取第一种钢板x张，第二种钢板y张，那么目标函数z=x+y,如图可行域是阴影局部，目标函数在A点取到最优解。解方程组得A〔，〕但不是整数解，此时,z=+=,那么在可行域内取到整数解的z=12.即经过可行域内的整点，且与原点距离最近的直线是x+y=12，那么整点一定在B、C之间。解方程组，得B〔3，9〕；解方程组，得C〔，〕；那么整点的横坐标3≤x≤，所以满足条件的最优解是〔3，9〕，〔4，8〕.本来近似解z=，而=11.4也不约等于12，学生不理解为什么z=12。这不是近似解约等于多少的问题，而是由于不是可行域内的整数解，可行域内的整数解至少要大于。这种方法先由图解法观察出最优解在哪个点处取到，再由精确值估算出整数解，一定注意整数解的估算不是四舍五入取整，而是在可行域内的整数解。xOxOy3224AB例2．求以下区域内整数点的个数解：如图区域是阴影局部的直角三角形，把它补为矩形。那么矩形区域内的整点有33×25=825个。而线段AB上的整点〔含端点〕是不定方程3x+4y=96的非负整数解。又x=32-,那么y一定被3整除，满足条件的y有0，3，6…，24共9个，即线段AB上的整点有9个。那么阴影局部区域内的整点有=417个。四、利用穷举法求整数最优解某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房，大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？xyxyO18x+15y=1801000x+600y=8000A200x+150y=1800A200x+150y=1800z=200x+150y如图可行域是阴影局部，作直线L：200x+150y=0，即4x+3y=0,将直线L平移到A点时与原点距离最大。解方程组得A〔〕，但不是整数解。此时z=200×=。又z=200x+150y=50〔4x+3y〕，那么z取到的最优解一定被50整除，那么z的最大值是1850。即4x+3y=37，又4x+3y=37的所有整数解是〔1，11〕，〔4，7〕〔7，3〕，而〔1，11〕不满足6x+5y≤60，舍去；〔4，7〕不满足5x+3y≤40，舍去；〔7，3〕不满足5x+3y≤40，舍去。所以z的最大值不可能是1850。那么z的最大值可能是1800、1750、1700…，直到在可行域内找到满足条件的最优解。假设z=1800，即4x+3y=36，又4x+3y=36的所有整数解是〔0，12〕，〔3，8〕〔6，4〕，〔9，0〕，经检验只有〔0，12〕，〔3，8〕在可行域内，所以当x