线性规划中的整点问题.pdf

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

1、高中数学教与学2015年线性规划中的整点问题=商史立霞秦振l2(山东省枣庄市第三中学西校，277100)一2整点的最优解是线性规划中经常遇到的C．如果一个单位的午餐、晚餐的费用分别是∞问题，如房间的分配问题、汽车的调运安排问2．5元和4元，那么要满足上述的营养要求，并题、材料的截取问题等等．而可行域中最优解且花费最少，应当为该儿童分别预订多少单又不是整数时，就需要考虑相应的方法和技位的午餐和晚餐?巧．解设需要预订满足要求的午餐和晚餐一、逐点验证法分别为个单位和Y个单位，所花的费用为当可行域是有限区域且整点个数比较元．则根据题意，得=2．5x+4y，且，y满足少，或最优解涉及的整点较少时，可

2、将整点的≥0，Y≥0，r≥0，Y≥0，，坐标代人目标函数求值，经过比较求出最优J2+8y≥64,即J3x+2y≥16，解．l6x+6y≥42，l+Y≥7，例1(2010年高考广东题)某营养师要t6x+10y≥54．t3x+5y≥27．为某个儿童预订午餐和晚餐．已知一个单位画出可行区域如图1所示，其中fn：2．5x+的午餐含12个单位的碳水化合物，6个单位的4y=0，Z1：3x+2y=16，Z2：+Y=7，f3：3x+蛋白质和6个单位的维生素C．一个单位的晚5y=27．z在可行域的四个顶点A(9，0)，B(4，餐含8个单位的碳水化合物，6个单位的蛋白3)，C(2，5)，D(0，8)处的值分别

3、是=22．5，质和l0个单位的维生素c．另外该儿童这两=22，=25，=32．根据目标函数的几餐需要的营养中至少含64个单位的碳水化合何意义，的最小值必在A、B、C、D中取得，比物，42个单位的蛋白质和54个单位的维生素较可知。最小，所以应当为该儿童预订4个单“●⋯·●⋯·●⋯·●⋯●⋯o0⋯·●⋯．0o⋯●·”●⋯‘●⋯‘●⋯●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●⋯●⋯·●⋯·●⋯·●⋯·●⋯·●⋯·●”删cos

4、NBx化简得(t+1)(m+4)=3m；①图8又AC：2MN，所以有m=2~／3一t．②由此易求得平面APC和平面PCB的法向由①、②，得t=1，m=2√2．量分别为nt：(t，0，一1),／12=(詈，1，o)，由此易得棱锥P—A曰c的体积为．·10·第6聊高中数学教与学位的午餐和3个单位的晚餐，就可满足要求画出可行域如图2所示，其中：6x+lOy=0，Z，：0．18x+0．09y=72，Z，：0．08x+0．28y：56．把直线fn向右上方平移至Z。的位置时，直线y＼＼＼、，I(经过可行域上点肘时，=6x+lOy取得最大值．解方程组f0·18x+0·09)，72，tO．08x+0．28

5、y=56．得点的坐标(350，100)．图1答：应生产圆桌350张，生产衣柜100个能评注此类问题涉及的整点个数较少，使利润总额达到最大．首先确定出可行域的顶点坐标，根据题意，再评注如果图中的点处不是最优解，代入验证即可得到结果．可将直线左移，寻找最优解．二、网格法三、逼近求解法即先画网格找整点，再平移直线，最先经就是将直线由非整数最鼗优解的方向不断地过的或最后经过的点就是最优整数解．这种向相反方向平移，分别求出它与可行域边界的方法充分利用准确的作图解决，适用于可行交点，从而可以确定一个坐标范围，进而判断在域较小的问题．此范围内是否存在整点，直到找到离原点距离例2某木器厂生产圆桌和衣柜两种

6、产最近或最远且通过第一个整点坐标的一条直品．现有两种木料，第一种有72m，第二种有线．逼近求解法适用于比较复杂的问题．56m，假设生产每种产品都需要用两种木料，例3某人有一套房，室内面积共180生产一张圆桌和一个衣柜所需的木料如下表m，拟分隔成两类房间作为旅游客房．大房间图2目标函数z=200x+150y=50(4x+3y)，可行·11·高中数学教与学2015冬域如图3阴影部分，其中Z0：4x+3y=0，Zl：6x求S=7x+5y的最大值．+5y：60，f2：5x+3y=40，而交点为分析可行区域如图4所示，直线4+3)，一20=0与一3y一2：0的交点A(，)．过点A(，)时，=857丁

7、1，但22A(是：了2060不是最优解＼5，)是，y∈R时的最优解，但是不是整，，，：．设平行于直线4+3y=0的直线为4+数最优解，还需将A(，÷)代入．s=7+5y，转化为不等式组解决．3ym，即m，由上知m<37了1，下面依次验证m=37，m=36是否满足要求．由4x+3y=m，得Y=1(m一4x)，代人’5≥m一90，约束条件，得≤40一m．0≤≤詈．当m=37，得2．5≤≤3，夹逼出整数=3，=0的交点是A(，