谈一类简单线性规划问题最优解的发现.docVIP

谈一类简单线性规划问题最优解的发现 湖北省麻城实验高级中学 阮 晓 锋 摘要: 本文介绍了一种发现简单线性规划问题非负整数最优解的普适方法。它是在图解平移法基础上先对最优解在可行域中的位置进行有哪些信誉好的足球投注网站定位，再根据题意和不定方程知识进行估值处理，通过调整目标函数值并借助解不等式组筛选出最优解的办法。 关键词：简单线性规划；整点最优解 作为新课标增加内容，高中数学教材对简单线性规划这一部分的叙述不够清晰，甚至其描述有偏离，导致师生对它普遍缺乏认识，特别是对“当求得的理论最优解为非整数解时如何得到符合实际的非负整数最优解”普遍认识不足或认识有误。为达成真正理解并解决问题，下面结合教材例、习题谈谈我的发现。 由高中数学课本知，在可行域内与原点距离最近（或最远）的整点对应的解为整数最优解。但此法理论上可行，实践上却严重依赖于作图和观察，这就往往造成因误差而判断出错，甚至会造成因相关整点太多而无从下手的情况。因此，我们迫切希望能找到一种可操作性强的解决办法。其实，当理论最优解不是整数解时，我们可利用整数最优解的必要条件---目标函数值为整数，在目标函数理论最优值基础上通过逐步调整目标函数值，再将其代入约束条件通过解不等式组筛选出符合实际的最优解来。 例1 要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示： 规格类型 钢板类型 A规格 B规格 C规格 第一种钢板 2 1 1 第二种钢板 1 2 3 今需要A、B、C三种规格的成品分别为15、18、27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少? (新教材63页例4) 解:设需截第一种钢板x张,第二种钢板y张, 设所用钢板的张数为z张，则约束条件为： 2x+y≥15 x+2y≥18 x+3y≥27 x≥0,y≥0 目标函数为：z=x+y 可行域如上图所示(图1) 根据目标函数向可行域方向作出一组平行直线:x+y=t， 我们发现：在这些直线中，过直线x+3y=27和直线2x+y=15交点A（3.6，7.8）的直线经过可行域且与原点的距离最近。此时z取得理论上的最小值11.4。 显然3.6和7.8都不是整数,而最优解中,x和y必须为整数,故（3.6,7.8）不是最优解。 由x和y必须为整数知z为整数，又要求的是z的最小值，故可先将z调整为12，从而可将直线x+y=11.4向上平移到x+y=12,最优解就可能存在于此直线上。 由x+y=12变形得y=12-x,将它代入约束条件得，解之得。 ∴x＝3或4，将它们代入x+y＝12检验，得（3,9）、（4,8）均为符合题意的最优整数解。 答：略 根据上面解答过程，我们可得到对一般的简单线性规划问题其解题步骤如下： 1.根据题意设出变量x、y，再列出约束条件、建立线性目标函数； 2 利用约束条件画出可行域（即各约束条件所示区域的公共区域）； 3根据线性目标函数向可行域方向作一组平行直线ax+by=t(t为参数)，再观察图形以找 到当直线ax+by=t移动时使t取到欲求最值的位置,然后通过联立方程解方程组求得其 数学理论上的最优解，并求出相应的目标函数理论最优值； 4 若上述数学理论上的最优解不是符合实际要求的非负整数最优解，则需先通过分析 调整目标函数取值（即参数t的值），再据此将y用x表示出来，将它代入约束条件 通过解不等式组得到缩小的x的取值范围，然后再在此基础上筛选得出符合实际要 求的非负整数最优解。 例2 某人有房子一幢，室内面积共180m2，拟分隔成两类房间作为游客住房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？（新教材65页习题4） 解：设他应隔出大房间x间，小房间y间，能获得收益为z元。 18x+15y≤180 1000x+600y≤8000 x≥0，y≥0 目标函数：z=200x+150y 约束条件化简： 6x+5y≤60 5x+3y≤40 x≥0，y≥0 可行域如图所示（图2） 再根据目标函数作一组平行直线：4x+3y=t 由图知当这些直线中经过点B（）时直线与原点的距离最大。此时z取得理论上的最大值z=200×+150×=，但x，y均不为整数，故不是所求最优解。∵（200,150）=50且50|1850 ∴可将z先调整为1850，得