科目:数学年级:高二教师:贾鲁津2001—2002年第一学期第十二周课题:线性规划内容提要:线性规划是辅助我们进行科学管理的一种数学方法,是运筹学的一个重要分支,在工农业生产,交通运输,财贸工作等各个领域都有极广泛的应用.线性规划研究的对象是:(一)任务确定后,如何统筹安排,使得用最少的人力物力资源去完成它.(二)在现有人力物力资源条件下如何组织安排,使得完成任务最多.这是一个问题的两个方面,实质是一个极值问题,属于最优化的范畴.线性规划就是求一组变量的值,使它满足一组线性式子,并使一个线性函数的值最大(或最小)的数学方法.学习目标:理解二元一次不等式表示平面区域,了解线性规划的意义,并能应用线性规划问题的图解方法,解决简单的实际问题.通过线性规划的实习作业,进一步理解线性规划的意义,了解线性约束条件,线性目标函数、可行域、可行解、最优解等有关基本概念,同时培养解决实际问题的能力.学法指导:1.理论联系实际2.数形结合,用图解法.教学进度§7.4简单线性规划4课时§7.5实习作业1课时撰搞说明为开阔眼界,培养同学对数学学习的浓厚兴趣,本稿件选用了高等数学中的一些初步知识,因此某些内容与记号在接受上有一定的困难,这些内容并不要求掌握,有的只泛泛了解即可,不必深究,望同学在学习的过程中参照教材的程度去把握尺度.由于篇幅所限,对于二元一次不等式表示平面区域的问题,内容较为简单,在这里不加累赘.但此部分知识为后面学习的基本工具,尤为重要,请同学结合课堂教学,在理解的基础上多加练习,一定要正确熟练地掌握.为了使同学有更多的见题机会,本稿没有选用书上的例题,然而这些例题是学习的范本请自觉认真地阅读,并与本稿例题进行比较,争取能从多角度,多方位去把握知识,灵活快捷地解决简单的实际问题.重点分析讲解与典型应用线性规划问题的数学模型包括决策变量、约束条件和目标函数三个要素.某班有男生30人、女生20人、星期天准备去植树,根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水.问应怎样安排,才能使植树最多?(包括挖坑、栽树、浇水)解:设男生中挖坑、栽树、浇水的人数分别为x11、x12、x13,女生中挖坑、栽树、浇水的人数分别为x21、x22、x23,S为植树棵数.由题意,问题的数学形式为:求一组变量xij(i=1,2;j=1,2,3)的值,使其满足约束条件x11+x12+x13=30x21+x22+x23=2020x11+10x21=30x12+20x22=25x13+15x23xij0(i=1,2;j=1,2,3)并使目标函数S=20x11+10x21的值最大(植树分为三个环节,应适当分配人数使每个挖出的坑,都有人去栽上树,而每棵栽好的树都有人去浇水.)例2.用长度为500cm的条形钢材,截成长度分别为98cm和78cm的两种规格的材料,要求共截出长98cm的钢材10000根,78cm的20000根,问怎样截法才使所用的原材料最少?解:根据题意,考虑将一根原材料截成两种钢材的所有可能的截取方式,计算每种截取方式所剩下的余料数量,将所得数据绘制成表格.截取方式截出钢材的数量钢材规格B1B2B3B4B5B6钢材需要量98(cm)5432101000078(cm)01235620000剩料的长度(cm)103050701232设用Bi种方式截得条材的数量为Xi件(i=1,2…,6),S为条材总数,则可求一组变量xi(i=1,2…6)的值,使其满足约束条件.5x1+4x2+3x3+2x4+x5=10000x2+2x3+3x4+5x5+6x6=20000xi0(i=1,2,…6)并使目标函数61iixs的值最小.(也可选用剩料数量和作为目标函数)例3.某商店制订某商品7-12月进货售货计划,已知商店仓库容量不得超过500件,6月底已存货200件,以后每月初进货一次,假设各月份某商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收最多?月789101112买进(元)282425272323售出(元)292426282225解:设7-12月各月初进货数量为xi件,而各月售货数量为yi件(i=1,2…6),S为总收入.由题意,得问题的数学形式为:求一组变量xi,yi(i=1,2,3,…6)的值,使其满足约束条件.y1200+x1500y2200+x1-y1+x2500y3200+x1-y1+x2-y2+x3500y4200+x1-y1+x2-y2+x3-y3+x4500y5200+x1-y1+x2-y2+x3-y3+x4-y4+x5500y6200+x1-y1+x2-y2+x3-y3+x4-y4+x5-y5+x6500xi0,yi0(i=1,2,…6),且xiz,yiz.并使目标函数S=29y1+24y2+26y3+28y4+22y5+25y6-(28x1+24x2+25x3+27x4+23x5+23x6)的值最大.(注意每个月只有月初进货,而售货在整个月的任何时候均有发生,售货量当然不能高于存货量,而存货量包括上个月的余量与本月的进货量的和.)在上述问题中,所给出的每个约束条件以及目标函数均是关于所设变量的一次等式或不等式,因此也称为线性约束条件,与线性目标函数,一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.以例2为例,满足约束条件的解(x1,x2,x3,x4,x5,x6)叫做可行解,由所有可行解组成的集合叫做可行域,在可行域中寻求到的使目标函数取得最大值或最小值的解称为这个问题的最优解.由于所学知识及认识水平的局限性,我们只对于含有两个变量的线性规划问题进行详细研究,寻求最优解.步骤如下:1.根据约束条件画出可行域2.将S作为参数作平行等值线,找出最优解或确定没有最优解.例4.用图解法解下列线性规划问题.(1)maxS=2x1+x2x1+x25(求S的最大值)x1-x23x1,x20解:由图4-1可知,问题的可行域为图中的凸四边形OABC令目标函数S的值为0,2,…,作平行直线族,由图4-1可见,S值愈增,直线离开原点愈远,显然,B点的坐标,既满足约束条件,且使目标函数取得最大值.x1+x2=5x1=4x1-x2=3x2=1即B点坐标为(4,1).所以最优解为:x1=4,x2=1,目标函数的最大值为:S=2×4+1=9ACOBx1x2图4-15(2)maxS=2x1+2x2:x1-x23x1,x20解:由图4-2可知,问题的可行域仍为凸多边形OABC令目标函数的值为0,2,…,作平行直线族,由图4-2可见,线段AB上任一点的坐标都是问题的最优解,这个目标函数的最大值为S=2×4+2×1=10x1+x23(3)maxS=2x1+x2x1-x33x1,x20解:由图4-3可知,问题的可行域为凸区域ABCD,这是个无界区域.令S=3,10,…,作平行直行族,当平行直线族的直线无限远离原点时,都可以与凸区域ABCD相交,目标函数无最大值,因此问题无最优解.x1+x23(4)minS=2x1+x2x1-x23x1,x20解:问题的目标函数和约束条件都与上题相同,不同的是,求目标函数的最小值,由图4-3可知,目标函数的最小值在B点达到.所以问题的最优解为x1=0,x2=3目标函数的最小值S=2×0+3=3x1+x24(5)minS=2x1+x2,x1-x25x1,x20解:由图4-4可知,同时满足四个不等式的点不存在,所以问题无可行解,因此也没有最优解.AOCBx1x2图4-2OCx2图4-3ABDx2可知,线性规划问题的解:有唯一最优解有可行解有无穷多最优解无最优解无可行解例5.某厂用甲、乙两种原料生产A、B两种产品,制造A、B一吨产品,分别需要的各种原料数,可得利润以及工厂现有各种原料数如下表所示.每吨产品所产品需原料(吨)原料AB现有原料(吨)甲乙12412842每吨产品可得利润(万元)75问:(1)在现有原料的条件下,如何组织生产,才能使利润最大.(2)如果原料甲增加到42吨,原最优解是否改变.(3)如果每吨产品B的利润增加到7万元,原最优解是否改变.(4)每吨产品B的利润限制在什么范围内变化,原最优解才不改变.(5)如果原问题增加一个新的约束条件,即生产A产品每吨要用煤5吨,生产B产品每吨要用煤4吨,现该厂只存煤60吨,问原最优解是否改变.解:(1)设生产A产品x1吨,B产品x2吨,可得总利润为S元,那么这一问题的数学形式为:maxS=7x1+5x2,x1+2x2284x1+x242这是两个变量的线性规划问题,可用图解法求解.由图5-1可知,问题的可行域为凸四边形OABCAOBCDx1x2图4-4COx1x2BA'B'A图5-1=0,50,…,作平行直线族.容易看出,最大值在B点达到.解:x1+2x2=284x1+x2=42得最优解为x1=8,x2=10目标函数的最大值为:S=7×8+5×10=106即产品A生产8吨,产品B生产10吨时,可得最大利润106万元.(2)如果原料甲增加到42吨,那么约束条件x1+2x228改为x1+2x242.由图5-1可知,新条件下的可行域为凸四边形CBOA''.由于目标函数没有改变,容易看出,新问题的最大值在'B达到.解x1+2x2=424x1+x2=42得最优解为x1=6,x2=18目标函数的最大值为S=7×6+5×18=132最优解改为产品A生产6吨,产品B生产18吨,可得最大利润132万元.(3)如果每吨产品B的利润增加到7万元,那么目标函数就改为S=7x1+7x2,由图5-2可知,新问题最优值仍在B点达到.最优解仍为x1=8,x2=10目标函数的最大值为:S=7×8+7×10=126即最优解改为产品A生产8吨,产品B生产10吨,可得最大利润126万元.(4)设每吨产品B的利润为b(b0)万元,这时目标函数就成为S=7x1+bx2,由图5-1可知,要目标函数的最优值在A点达到,必须有直线x1+2x2=28的倾斜角小于直线7x1+bx2=0的倾斜角,即直线x1+2x2=28的斜率小于直线7x1+bx2=0的斜率,也即b721,得b14.也就是说,当产品B每吨的利润大于14万元时,最优值在A点达到,最优解为x1=0,x2=14.同样,由图5-1可知,要目标函数的最优值在C点达到,必须有直线4x1+x2=42的倾斜角大于直线7x1+bx2=0的倾斜角,即直线4x1+x2=42的斜率大于直线7x1+bx2=0的斜率.即-4-b7,得0b47