8-第8课-规划分析

1、第第8章章 规划分析规划分析线性规划线性规划目标规划目标规划整数规划整数规划动态规划动态规划内容内容v提出问题提出问题v相关知识导入相关知识导入v基本概念解释基本概念解释v线性规划求解过程线性规划求解过程图解法图解法v线性规划结果调整线性规划结果调整v小结小结要求要求v1 掌握线性规划的三要素掌握线性规划的三要素v2 根据题目给出的条件能够建立线性规划的根据题目给出的条件能够建立线性规划的模型模型v3 利用图解法能够找到目标函数的最优解利用图解法能够找到目标函数的最优解v4 理解线性规划结果的整数调整理解线性规划结果的整数调整提出问题提出问题v线性规划研究的问题：线性规划研究的问题： 1、在、

2、在现有现有的人、财、物等资源条件下，的人、财、物等资源条件下， 研究如何合理地计划、安排，可使得研究如何合理地计划、安排，可使得 某一某一目标目标达到最大，达到最大， 2、在、在任务任务确定后，如何计划、安排，使确定后，如何计划、安排，使 用用最少最少的人、财、物等资源，去实现的人、财、物等资源，去实现 该任务，该任务，寻求在一定约束条件下使某个指标达到最优寻求在一定约束条件下使某个指标达到最优如产量、利润等。如产量、利润等。如使生产成本、费用最少等。如使生产成本、费用最少等。给定一定量的给定一定量的人力、物力、人力、物力、资金等资源资金等资源完成的任务量最大完成的任务量最大经济效益最高经济效

3、益最高给定一项任务给定一项任务所耗的人力、所耗的人力、物力资源最少物力资源最少降低成本降低成本获取最大的利润获取最大的利润精打细算精打细算最优方案最优方案统筹安排统筹安排最佳方案最佳方案 7 7 1212360200300 9 4 3资源单耗资源单耗 产品产品单位产品价格单位产品价格 煤煤 电电 油油资源限量资源限量甲甲 乙乙资源资源v例例1 资源合理利用问题资源合理利用问题 某工厂在某一计划期内准备生产甲、乙两种某工厂在某一计划期内准备生产甲、乙两种产品，生产需要消耗煤、电、油三种资源。产品，生产需要消耗煤、电、油三种资源。有关数据列表如下。试拟订使计划期内总收有关数据列表如下。试拟订使计划

4、期内总收入最大的生产计划方案？入最大的生产计划方案？线性规划问题线性规划问题 4 5 10知识导入知识导入1.在同一坐标系上作出下列直线在同一坐标系上作出下列直线:2x+y=0; 2x+y=1;2x+y=-3;2x+y=4;2x+y=7平行。的直线与形如结论02)0(2:yxttyxxYo这些直线之间什么关系？这些直线之间什么关系？2.画出不等式2x+y-60表示的平面区域取原点（取原点（0 0，0 0），），代入不等式代入不等式解：先画出直线解：先画出直线2x+y-6=0(2x+y-6=0(画成画成虚线虚线) )得左得左=2=20 00 06 66060即原点即原点满足满足2x+y-602x

5、+y-60所以原点所以原点在在不等式表示不等式表示的平面的平面区域内区域内故不等式故不等式2x+y-602x+y-60在平面直角坐标系中表示直线在平面直角坐标系中表示直线Ax+By+C=0某一侧所有点组某一侧所有点组成的平面区域。成的平面区域。用不等式表示下列平面区域：用不等式表示下列平面区域：xyo1-1（1 1）xyo12（2 2）x-y+10 x+2y-20二元一次不等式区域的判断法：二元一次不等式区域的判断法：Ax+By=t 若若“”或或“”则把直线画成则把直线画成虚线虚线；若；若“”或或“” 则把直线画成则把直线画成实线实线由于对直线同一侧的所有点由于对直线同一侧的所有点(x,y)选

6、特殊选特殊点（点（0，0）（）（t不等于零）或（不等于零）或（0，1）（）（t等于零）等于零），把它代入不等式，把它代入不等式，满足满足即选即选这一侧，这一侧，反之反之另一侧另一侧 小结小结：画线定界，取点定域画线定界，取点定域实例分析：实例分析：设设x,y满足以下条件：满足以下条件： 求求z=2x+y的最大值与最小值。的最大值与最小值。 133065yxyyx线性约线性约束条件束条件 目标函数目标函数（线性目标函数）（线性目标函数）3.不等式组表示的区域的确定不等式组表示的区域的确定如图，分别作出如图，分别作出 三条三条直线，直线，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+

7、6y=30 再找出不等式组再找出不等式组所表示的平面区域的所表示的平面区域的公公共区域共区域。可行域可行域x二元一次不等式组表示平面区域：二元一次不等式组表示平面区域：二元一次不等式组所表示的平面区二元一次不等式组所表示的平面区域是各个不等式表示的平面点集的域是各个不等式表示的平面点集的交集交集，即各个不等式所表示的平面，即各个不等式所表示的平面区域的区域的公共部分公共部分。基本概念基本概念 由由x，y 的不等式的不等式(或方程或方程)组成的组成的不等式组不等式组称为称为x，y 的的约束条件约束条件。关于。关于x，y 的的一次一次不等式或方程组成的不不等式或方程组成的不等式组称为等式组称为x，

8、y 的的线性线性约束条件约束条件。 欲达到最大值或最小值所涉及的变量欲达到最大值或最小值所涉及的变量x，y 的解析式的解析式称为称为目标函数目标函数。关于。关于x，y 的一次目标函数称为的一次目标函数称为线性目线性目标函数标函数。 求线性目标函数在线性约束条件下的最大值或最小求线性目标函数在线性约束条件下的最大值或最小值问题称为值问题称为线性规划问题线性规划问题。 满足线性约束条件的解（满足线性约束条件的解（x，y）称为）称为可行解可行解。所有。所有可行解组成的集合称为可行解组成的集合称为可行域可行域。 使目标函数取得最大值或最小值的可行解称为使目标函数取得最大值或最小值的可行解称为最优最优解

9、解。1255334xyxyx设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.线性目线性目标函数标函数线性约线性约束条件束条件线性规线性规划问题划问题任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域所有的所有的最优解最优解x2504030201010203040 x1x2504030201010203040 x1x2504030201010203040 x12x1+x2 504x1+3x2 120 x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）x2504030201010

10、203040 x1x2504030201010203040 x1x2504030201010203040 x1Q2（15，20）线性规划模型的三要素：线性规划模型的三要素： 决策变量：决策变量：需决策的量，即待求的未知数。需决策的量，即待求的未知数。目标函数：目标函数：需优化的量，即欲达到的目标，需优化的量，即欲达到的目标，用决策变量的表达式表示。用决策变量的表达式表示。约束条件：约束条件：为实现优化目标受到的限制，用为实现优化目标受到的限制，用决策变量的等式或不等式表示。决策变量的等式或不等式表示。 某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产甲种产品已知生产甲种产品1t需消需

11、消耗耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产乙种产品；生产乙种产品1吨需吨需消耗消耗A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t。每。每1t甲种产品的利润甲种产品的利润是是600元元,每每1t乙种产品的利润是乙种产品的利润是1000元。元。 工厂在生产这两种产品的计划中要求消耗工厂在生产这两种产品的计划中要求消耗A种矿石不超种矿石不超过过300t、 消耗消耗B种矿石不超过种矿石不超过200t、消耗煤不超过、消耗煤不超过360t。 若你是厂长若你是厂长,你应如何安排甲乙两种产品的产量你应如何安排甲乙两种产品的产量(精确到精确到0.1t),才能使利润总额达到最大才能使利润

12、总额达到最大?例例请写出目标函数和约请写出目标函数和约束条件束条件决策变量是什么？决策变量是什么？v在本例中在本例中决策变量决策变量：甲、乙产品的计划产量，记为：甲、乙产品的计划产量，记为 ,目标函数目标函数：总收入记为：总收入记为 , 则则为体现追求极大化，在前面冠以极大号为体现追求极大化，在前面冠以极大号max；约束条件约束条件：分别来自资源煤、电、油限量的约束，：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为和产量非负的约束，表示为z1x2x211000600 xxz0,3004102004536094. .21212121xxxxxxxxtsjx2 , 1j2, 1,030

13、04102004536094.1000600max21212121jxxxxxxxtsxxzj解：解： 设甲、乙产品的产量分别为设甲、乙产品的产量分别为 个单位个单位（ ）, 获得总收入为获得总收入为z ，则上述问题的，则上述问题的数学模型为数学模型为线性规划模型的一个基本特点线性规划模型的一个基本特点v目标和约束均为变量的目标和约束均为变量的线性线性表达式表达式v如果模型中出现如如果模型中出现如v的非线性表达式，则不属于线性规划。的非线性表达式，则不属于线性规划。32211ln2xxx、求解过程求解过程图解法图解法实例分析：实例分析：设设x,y满足以下条件：满足以下条件： 求求z=2x+y的

14、最大值与最小值。的最大值与最小值。 133065yxyyx如图，分别作出如图，分别作出 三条三条直线，直线，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+6y=30 再找出不等式组再找出不等式组所表示的平面区域的公所表示的平面区域的公共区域。共区域。可行域可行域x设设z=0,画出直线画出直线l0，即即l0:2x+y=0。o5x+6y=30y=1y=3xyxl0:2x+y=0如图，平移直线如图，平移直线l0， 所对应的所对应的z随之增大；随之增大； 所对应的所对应的z随之减小。随之减小。当直线当直线l0向上平移时，向上平移时， 当直线当直线l0向下平向下平移移时时, o5x+6y=

15、30y=1y=3xyl0:2x+y=0l1:2x+y=2l2:2x+y=4l3:2x+y=-3(13,1) 此时所对应的此时所对应的Z最小；最小；(245,1)此时所对应的此时所对应的Z最大。最大。从而得到：从而得到：zminzmax=2 +1= =2 +1= 1324553535o5x+6y=30y=1y=3xyxABCl0:2x+y=0如图，在把如图，在把l0向上平移过程中，直线与平面区向上平移过程中，直线与平面区域首先相交于点域首先相交于点A ，当相交于点当相交于点B ，l1l2总结：总结： 从这个问题的求解过程可以从这个问题的求解过程可以看出，最优解一般在可行域的看出，最优解一般在可行

16、域的边边界上界上，而且通常在可行域的，而且通常在可行域的顶点顶点处处取得。取得。5x+4y=202x+3y=12线性目标函数线性目标函数),(M720712Z的最大值为的最大值为44已知实数已知实数x,y满足下列条件满足下列条件:5x+4y 202x+3y 12x 0y0求求z=9x+10y的最大值的最大值.最优解最优解可行域可行域9x+10y=0线性约束线性约束条件条件 01 2345 6123456xy图解法图解法转化转化线性约线性约束条件束条件可行域可行域转化转化线性目线性目标函数标函数Z=Ax+By一组平行线一组平行线B BZ Zx xy y 转化转化最优解最优解寻找平行线组寻找平行线

17、组的纵截距的纵截距 最值最值 四个步骤：四个步骤：1、列列4、答答3、移移2、画画三个转化三个转化转化转化转化转化转化转化四个步骤四个步骤：1、列（设出未知数、列（设出未知数,列出约束条件列出约束条件,确定目标函数）确定目标函数）三个转化三个转化4、答答（求出点的坐标，并转化为最优解）（求出点的坐标，并转化为最优解）3、移移（平移直线（平移直线L 。寻找使纵截距取得最值时的点）。寻找使纵截距取得最值时的点）2、画（画可行域）、画（画可行域）图解法图解法线性约束条件线性约束条件可行域可行域线性目标函数线性目标函数Z=Ax+By一组平行线一组平行线BZxy最优解最优解寻找平行线组的寻找平行线组的

18、最大（小）纵截距最大（小）纵截距 某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产甲种产品已知生产甲种产品1t需消需消耗耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产乙种产品；生产乙种产品1吨需吨需消耗消耗A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t.每每1t甲种产品的利润甲种产品的利润是是600元元,每每1t乙种产品的利润是乙种产品的利润是1000元元. 工厂在生产这两种产品的计划中要求消耗工厂在生产这两种产品的计划中要求消耗A种矿石不超种矿石不超过过300t、 消耗消耗B种矿石不超过种矿石不超过200t、消耗煤不超过、消耗煤不超过360t. 若你是厂长若你是厂

19、长,你应如何安排甲乙两种产品的产量你应如何安排甲乙两种产品的产量(精确到精确到0.1t),才能使利润总额达到最大才能使利润总额达到最大?例例分分析析问问题题:1.本问题给定了哪些原材料本问题给定了哪些原材料(资源资源)?2.该工厂生产哪些产品该工厂生产哪些产品?3.各种产品对原材料各种产品对原材料(资源资源)有怎样的要求有怎样的要求?4.该工厂对原材料该工厂对原材料(资源资源)有何限定条件有何限定条件?5.每种产品的利润是多少每种产品的利润是多少?利润总额如何计算利润总额如何计算? 原原 材材料料每吨产品消耗的原材料每吨产品消耗的原材料A种矿石种矿石B种矿石种矿石煤煤甲产品甲产品(t) x乙产

20、品乙产品(t)1054449原原 材料限材料限 额额300200360利利 润润6001000y把题中限制条件进行转化：把题中限制条件进行转化：约束条件约束条件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目标函数目标函数：设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x、y,利润总额为利润总额为z元元解解:设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x、y,利润总额为利润总额为z元元,那么那么10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.画画出以上不等式组所表示的可行域出以上不等式

21、组所表示的可行域作作出直线出直线L 600 x+1000y=0.解得交点解得交点M的坐标为的坐标为(12.4,34.4)5x+4y=2004x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:应生产甲产品约应生产甲产品约12.4吨，乙产品吨，乙产品34.4吨，能使利润总额达到最大。吨，能使利润总额达到最大。(12.4,34.4)经过可行域上的点经过可行域上的点M时时,目标函数目标函数在在y轴上截距最大轴上截距最大.9030 0 xy10 201075405040此时此时z=600 x+1000y取得最大值取得最大值.483429100

22、0411229360.y.x把直线把直线L向右上方平向右上方平移移？，2 . 1，7 . 0g。3000g、2000g、3600g。10g、5g、4;g3g、4g、9，利最大两种饮料各多少杯能获每天应配制全部售出料的使用限额内饮料能每天在原元乙种饮料每杯能获利元利如果甲种饮料每杯能获糖咖啡额为奶粉已知每天原料的使用限糖咖啡乙种饮料每杯含奶粉糖咖啡甲种饮料每杯含奶粉咖啡馆配制两种饮料y2 . 1x7 . 0z。y、x：咖啡馆每天获利杯乙种饮料杯设每天应配制甲种饮料解0y, 0 x,3000y10 x3,2000y5x4,3600y4x9xy03600y4x93000y10 x32000y5x40

23、y12x70y, 0 x,3000y10 x3,2000y5x4,3600y4x9y2 . 1x7 . 0zABCDC240，200C3000y10 x32000y5x4得解方程组实际问题实际问题线性规划问题线性规划问题寻找约束条件寻找约束条件建立目标函数建立目标函数列表列表设立变量设立变量转化转化1.约束条件要写全约束条件要写全; 3.解题格式要规范解题格式要规范. 2.作图要准确作图要准确,计算也要准确计算也要准确;注意注意: :总结总结解线性规划应用问题的步骤：解线性规划应用问题的步骤： （3）移：作出）移：作出z=Ax+By=0时的直线时的直线L，在线性目标函，在线性目标函数所表示的一

24、组平行线中，利用平移的方法找出与可数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；行域有公共点且纵截距最大或最小的直线； （4）答：通过解方程组求出最优解；）答：通过解方程组求出最优解； （1）列：设出未知数）列：设出未知数,列出约束条件列出约束条件,确定目标函数；确定目标函数；（2）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；注：注：1.线性目标函数的最大（小）值一般在可行域的顶线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得。点处取得，也可能在边界处取得。2.求线性目标函数的最优解，要注意分析线性目标函

25、数求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义所表示的几何意义 在在 y 轴上的截距或其相反数。轴上的截距或其相反数。结果调整结果调整某工厂现有两种大小不同规格的钢板可截成某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第二种钢板张，第二种钢板y张，张，钢板钢板总总张数为张数为Z,则则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y

26、15,x+2y18,x+3y27,x0y0 某顾客需要某顾客需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，块，若你是若你是经理经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。数最少。X张张y张张分分析析问问题题: :例例目标函数目标函数: z=x+y) )N Ny y, ,x x( ( x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, y0直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解

27、. 作出直线作出直线L:x+y=0，目标函数目标函数:z= x+yA(3.6,7.8)当直线当直线L经过点经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12约束条件约束条件:画可行域画可行域平移平移L找交点及交点坐标找交点及交点坐标) )N Ny y, ,x x( ( 调整优解法调整优解法1.满足哪些条件的解才是最优解满足哪些条件的解才是最优解?2.目标函数经过目标函数经过A(3.6,7.8)时时Z的值是多少的值是多少?Z的最小值可能是

28、多少的最小值可能是多少?C(4,8)B(3,9)x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)且和原点距离最近的直线是且和原点距离最近的直线是x+y=12，它们是最优解，它们是最优解.作出一组平行直线作出一组平行直线t = x+y，目标函数目标函数t = x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是

29、最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，1212182715978xy00y,0 x40y3x560y5x60y3x460y5x640y3x5满足约束条件使式中的的最大值求y, x，y150 x200zy150 x200z0y, 0 x8000y600 x1000180y15x18且8 , 3B12, 0C760,720A.12, 0C8 , 3B为所求或即 即先求非整数条件下的最优解，即先求非整数条件下的最优解，调整调整Z的值使不定方程的值使不定方程Ax+By=Z存在最大（小）存在最大（小）的整点值，最后筛选出整点最优解的整点值，最后筛选出整点最优解 即先打网格，

30、描出可行域内的即先打网格，描出可行域内的整点整点，平移直线，最先经过或最后经过的整点平移直线，最先经过或最后经过的整点坐标即为最优整解坐标即为最优整解线性规划求最优整数解的一般方法线性规划求最优整数解的一般方法:1. 1.平移找解法：平移找解法： 2. 2.调整优解法调整优解法：总结总结小小 结结实际问题实际问题列表列表设出变量设出变量寻找约束条件寻找约束条件建立目标函数建立目标函数转化转化建模建模线性规划问题线性规划问题图解法图解法最优解最优解三个转化三个转化四个步骤四个步骤作答作答调整调整最优整数解最优整数解平移找解法平移找解法调整优值法调整优值法常用方法常用方法目标函数目标函数距离距离,斜率等斜率等结论：结论：1.线性目标函数的最大（小）值一般在可线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得。行域的顶点处取得，也可能在边界处取得。2.求线性目标函数的最优解，要注意分析求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义线性目标函数所表示的几何意义 在在 y 轴上的截距或其相反数轴上的截距或其相反数。时间时间所需售货员所需售货员 人数人数星期日星期日28人人星期一星期一15人人星期二星期二24人人星期三星期三25人人星期四