《应用数学基础》课件第五章 最优化问题.pptx

1、 在日常生活、经济管理和科学研究等领域，人们经常会遇到一类决策问题：在一系列客观或主观限制条件下，寻求使所关注的指标达到最优(最大或最小)的决策。例如，资源分配要在有限资源约束下，制定最优分配方案，使资源产生的总效益最大；生产计划要按照产品生产流程和市场需求，制定原料、零件和部件的最佳订购时间点，尽量降低生产成本使利润最高；运输方案要在满足物资需求和装载条件下，安排从各供应点到需求点的最优路线和运量，使运输总费用最低等。上述几类决策问题通常称为最优化问题(简称为优化问题)，本章将简单介绍优化问题的数学模型，单变量和多变量优化问题的建模与求解等知识，为我们以后的工作和生活提供基本的优化思想。第第

2、一一节节 优化问题数学模型优化问题数学模型01第一节第一节 优化问题数学模型优化问题数学模型 设某产品的总成本(单位：元)函数为2()0.25151600C xxx产量，单位：千克)，求当产量为多少时，该产品的平均成本最小，最小平均成本是多少？该问题的目标是平均成本最小，设平均成本为2()0.2 51 51 6 0 0C x xx，则1600()0.2515C xxx于是，建立该问题的数学模型如下：1600min()0.2515C xxx一、一、几个引例几个引例 给定一条1 米长的铁丝，要求将其弯成一个矩形，使得该矩形的面积最大。目标函数目标函数 12max Sxx约束条件约束条件121222

3、=1.0,0 xxstxx借助EXCEL的“规划求解”工具，易求得120.25xx米时，矩形面积最大,最大面积为20.0625米第一节第一节 优化问题数学模型优化问题数学模型产品产品产品产品日允许消耗量日允许消耗量设设 备备A128（台时）原材料原材料B3012（100千克）原材料原材料C0515（100千克）某企业在计划期内要安排、两种产品的生产，已知每生产100千克产 品所需设备A及原材料B、C的消耗如表5-1所示。表5-1 生产设备和原材料消耗表 已知每生产100千克的产品可获利2万元，生产100千克的产品可获利5万元，问怎样安排生产，才能使每天获得的利润最大？第一节第一节 优化问题数学

4、模型优化问题数学模型1225zxx1228xx同理，因受原材料B、C的限制，可以得到以下两个不等式1312x 2515x 第一节第一节 优化问题数学模型优化问题数学模型综上所述，建立生产计划问题的数学模型为：目标函数目标函数 12max25zxx约束条件约束条件12121228312.5150,xxxstxxx0通过图解法或者借助EXCEL的“规划求解”工具，可得最优解为122,3,xx最优值为19。第一节第一节 优化问题数学模型优化问题数学模型某机械厂需要长80厘米的钢管800根，长60厘米的钢管200根，这两种长度不同的钢管由长200厘米的钢管截得。工厂该如何下料，使得用料最省？对于该问题

5、，首先必须找到可行的下料方式。由1根长200厘米的钢管去截得80厘米与60厘米两种型号的钢管，共有三种截取方法。一根长200厘米的钢管截得长80厘米的钢管2根；一根长200厘米的钢管截得长80厘米的钢管1根，长60厘米的钢管2根；一根长200厘米的钢管截得长60厘米的钢管3根。123zxxx第一节第一节 优化问题数学模型优化问题数学模型对于所需长80厘米的钢管：122800 xx对于所需长60厘米的钢管：2323200 xx综上所述，得钢管下料问题的数学规划模型为：目标函数目标函数 123min zxxx约束条件约束条件12232800.23200(1,2,3)ixxstxxxi为非负整数借助

6、EXCEL的“规划求解”工具，可得最优解为123=350,100,0 xxx第一节第一节 优化问题数学模型优化问题数学模型二、二、优化优化问题的数学模型问题的数学模型优化问题的数学模型一般包含三个要素：决策变量、目标函数和约束条件。1.决策变量决策变量在优化过程中经过逐步调整、最后达到最优值的参数，称为决策变量(简称变量)2.目标函数目标函数反映变量间相互关系的数学表达式称为目标函数，其值的大小可以用来评价优化方案的好坏。一般可表示为12max(min)(,)nzf x xx特别地，如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该问题的目标函数称为多目标函数。第

7、一节第一节 优化问题数学模型优化问题数学模型3.约束条件约束条件变量间应该遵循的限制条件的数学表达式称为约束条件或约束函数。约束条件一般可表示为：不等式约束12(,)0(0)ng x xx或等式约束12(,)0nh x xx其中，不带约束条件的优化问题称为无约束最优化问题。第一节第一节 优化问题数学模型优化问题数学模型4.优化问题数学模型的表示形式优化问题数学模型的表示形式121121211212max(min)(,)(,)0(,)0.t.(,)()0(,)()0nnmnnlnzf x xxh x xxhx xxsg x xxg x xx (5.1)式中满足所有约束条件的解称为，12(,)nx

8、 xx可行解的集合称为。求解优化问题(5.1)，就是从可行域中找到一个解，使目标函数取得最大值(或最小值)，这样的解称为，相应的目标函数值称为。第一节第一节 优化问题数学模型优化问题数学模型5.优化问题的基本类型优化问题的基本类型优化模型可以从不同的角度进行分类。根据决策变量的根据决策变量的数量数量：可以分为单变量优化问题和多变量优化问题根据决策变量在目标函数与约束条件中最高次项的次数是否大于根据决策变量在目标函数与约束条件中最高次项的次数是否大于1：可以分为线性规划问题和非线性规划问题根据决策变量是否要求取根据决策变量是否要求取整数整数：可以分为整数规划问题和连续优化问题根据有无根据有无约束

9、条件约束条件：可以分为无约束的优化问题和有约束的优化问题第一节第一节 优化问题数学模型优化问题数学模型 第第二二节节 单变量优化问题单变量优化问题02第二节第二节 单变量优化问题单变量优化问题一、一、单变量优化问题单变量优化问题 闭区间上的连续函数一定存在最大值和最小值，统称为。显然，最值只能在极值点或区间端点取得，而极值点的所有可能点只能是函数的驻点(使函数的导数为零的点)和函数导数不存在的点。因此，求函数的最值时只需考虑这三类点的函数值。按从小到大记为12,na x xx b3.求最大值和最小值，即计算在点12,na x xx b的函数值，并比较大小。第二节第二节 单变量优化问题单变量优化

10、问题 求函数32()392f xxxx，在a,b上的最大值和最小值。2()3693(1)(3)fxxxxx第二步，求可能的最值点，令0)(xf，解得1213xx、即所有可能的最值点为122,13,6axxb 、第三步，求最大值和最小值，计算各可能点的函数值(2)0,(1)7,ff(3)25,(6)56ff，比较大小，得函数的最大值为(6)56f，最小值为(3)25f 第二节第二节 单变量优化问题单变量优化问题求函数23()2(1)f xx在0,9上的最大值和最小值。23322()(1)331fxxx 第二步，求可能的最值点，令0)(xf，但当1x 时，()fx无意义，0,19axb、第三步，求

11、最大值和最小值，计算各可能点的函数值(0)1,(1)2,(9)2fff 比较大小，得函数的最大值为(1)2f，最小值为1x 第二节第二节 单变量优化问题单变量优化问题某租户有100间房子出租，若每间租金定为200元能够全部租出去，但每间每增加10元租金就有一间租不出去，且每租出去一间，就需要增加20元管理费。问租金定为多少才能获得最大利润？,由题意得，租出的房间数为20010010p2001002024002,10pp第二节第二节 单变量优化问题单变量优化问题 R p 出租的间数 价格/每间2200100120,1010pppp L p 收入成本2120(24002)10ppp2=122240

12、0.10pp第二节第二节 单变量优化问题单变量优化问题求导得 122.5pLp 0Lp令得唯一可能的最值点610p 即当每间房子的出租价格定为610元时，可获得最大利润。由于该实际问题确实存在最大值，因此利润函数在610p 有最大值。第二节第二节 单变量优化问题单变量优化问题二二、限制条件下双限制条件下双变量优化问题变量优化问题接下来我们讨论在限制条件(,)0g x y 下二元函数(,)f x y的优化问题。求函数22(,)2f x yxy在限制条件(,)10g x yxy 下的最小值。由10 xy，可得=1yx 222()2(1)321h xxxxx 故求导数，得()62h xx 0h x令

13、，得*13x（1）当13x()0h x时，在区间1(,)3内单调递减；（2）当13x()0h x时，在区间1(,)3内单调递增。因此*13x 是最小值点此时21 22,(,)33 33yf故(,)f x y在限制条件(,)=0g x y的最小值为23第二节第二节 单变量优化问题单变量优化问题 第第三三节节 多多变量优化问题变量优化问题03第三节第三节 多变量优化问题多变量优化问题一一、线性规划线性规划(1)有一组决策变量12,nx xxL(2)存在一组约束条件，且表示约束条件的数学式子都是线性等式或不等式。(3)有一个目标函数，且目标函数是线性函数。112211 11221n121 12222

14、n21 122nmax(min)()().()0(1,2,).nnnnmmmnmjzc xc xc xa xa xa xba xa xa xbsta xaxaxbxjn 、第三节第三节 多变量优化问题多变量优化问题求解引例3对应的线性规划模型。因为120 xx0、，所以满足约束条件的点落在第一象限及坐标轴的正半轴上。在坐标系中画出直线1228xx，这条直线将坐标平面分成两个半平面，满足约束条件1228xx的所有点落在直线1228xx上及原点所在一侧的半平面内。割线的原点所在一侧的半平面内；同理，满足约束条件1312x 的所有点位于直线1312x 上及以该直线为分满足约束条件2515x 的所有点

15、位于直线2515x 原点所在一侧的半平面内；上及以该直线为分割线的第三节第三节 多变量优化问题多变量优化问题上述三个平面点集在第一象限的交集即为可行域，如下图5-1所示可行域内任意一点的坐标都是该线性规划问题的可行解。图5-1 唯一最优解情形第三节第三节 多变量优化问题多变量优化问题(2)绘制目标函数等值线绘制目标函数等值线.0,5zz，画出相应的等值线。的值越大的值越大(3)确定确定最优解最优解最优解必须是满足约束条件，并使目标函数达到最优值的解，故12xx、的值只能在可行域OABCD中去寻找。当等值线移动到与可行域相切时，切点就是代表最优解的点。1228xx和2515x 的交点，坐标为(2

16、,3)，所以，最优解为122,3xx最优值为19第三节第三节 多变量优化问题多变量优化问题 （1）根据约束条件画出可行域；（2）根据目标函数的表达式画出目标函数等值线0z，并标明目标函数值增加的方向；（3）在可行域中，寻求符合要求的等值线与可行域边界相切的点或 点集，并求出最优解和最优值。第三节第三节 多变量优化问题多变量优化问题 求解线性规划问题12121212max24,28,312,.515,0.zxxxxxstxxx0,第三节第三节 多变量优化问题多变量优化问题12240 xx,当等值线向右上方移动时，图5-2 无穷多最优解情形 这时在B点、C点及BC线段上的任意点都使目标函数值达到最

17、大，即该线性规划问题有无穷多最优解，若取最优点B，则最优解为124,2xx最优值为16。第三节第三节 多变量优化问题多变量优化问题求解线性规划问题12121212max,24,.2,0,0.zxxxxstxxxx 第三节第三节 多变量优化问题多变量优化问题图5-3 无最优解情形120 xx容易看出，等值线离原点越远，目标函数值越大。由于问题可行域无界，等值线可以无限制地向右上方移动，即目标函数值可以增大至无穷大。该情况下称问题具有无界解或无最优解。第三节第三节 多变量优化问题多变量优化问题 求解线性规划问题12121212min3,2,.3,0,0.zxxxxstxxxx第三节第三节 多变量优

18、化问题多变量优化问题122xx它在第一象限的部分表示为区域1；123xx它在第一象限的部分表示为区域2；容易看出区域1与区域2没有公共部分，即该问题的可行域为空集，所以此问题没有可行解，当然也就没有最优解。图5-4 无可行解情形第三节第三节 多变量优化问题多变量优化问题 图解法虽然只能用来求解只含两个变量的线性规划问题，但通过它的解题思路和几何直观所得到的一些性质，对线性规划问题解的理解有很大的帮助。（1）有可行解且有唯一最优解，如例5；（2）有可行解且有无穷多最优解，如例6；（3）有可行解但无最优解，如例7；（4）无可行解，如例8。上述结论可以推广到变量多于两个的一般情形，得线性规划问题解的

19、性质如下：求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解、无可行解。若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解）一定可以在基可行解(顶点)中找到。第三节第三节 多变量优化问题多变量优化问题 当变量多于两个时，线性规划问题不能用图解法，此时，我们一般借助软件求解。本章将介绍使用EXCEL 2007(或以上版本)的“规划求解”工具求解简单规划问题。EXCEL 的“规划求解”工具可以解决最多有200个变量，100个外在约束和400个简单约束(决策变量整数约束的上下边界)的线性规划与非线性规划问题。求解线性规划问题：12312312312123max2122

20、6.390,0,0zxxxxxxxxxstxxxxx第三节第三节 多变量优化问题多变量优化问题 第一步：第一步：输入数据。为了使输入的线性规划问题数据清晰明了，一般把工作表分成若干区域(具体根据实际情况确定)，并用关键词加以标注。如本例中，区域B1:D1表示目标函数系数，区域B2:D2表示决策变量值，区域B4:D6表示约束条件左端系数，区域E4:E6表示约束条件左端值，区域F4:F6表示约束条件右端值，区域F1表示目标函数值。具体如图5-5所示。图5-5 数据输入第三节第三节 多变量优化问题多变量优化问题第二步：第二步：描述约束条件左端和目标函数表达式。在E4单元格中输入“=$B$2*B4+$

21、C$2*C4+$D$2*D4”，并拖曳至E6单元格。在F1单元格中输入“=B1*B2+C1*C2+D1*D2”，由于EXCEL默认的决策变量初始值等于0，故描述的目标函数和约束条件左端值均等于0。如图5-6所示。图5-6 描述约束条件左端和目标函数表达式第三节第三节 多变量优化问题多变量优化问题第三步：第三步：设置求解参数。单击【数据】中的【规划求解】命令，在弹出的规划求解对话框中输入各项参数在“规划求解参数”对话框中选中“最大值”前的单选按钮，设置目标单元格为“$F$1”，可变单元格为“$B$2:$D$2”单击“规划求解参数”对话框中的【添加】按钮，打开【添加约束】对话框，单击单元格引用位置

22、文本框，然后选定工作表中的E4：E6单元格，则在文本框中显示“$E$4:$E$6”，选择“=”约束条件；单击约束值文本框，然后选定工作表中的F4:F6单元格因为是线性规划问题，所以选择求解方法为“单纯线性规划”，勾选“使无约束变量为非负数”。求解参数设置如图5-7所示。第三节第三节 多变量优化问题多变量优化问题第三步：第三步：设置求解参数。单击【数据】中的【规划求解】命令，在弹出的规划求解对话框中输入各项参数图5-7 设置求解参数第三节第三节 多变量优化问题多变量优化问题求解模型。在【规划求解参数】对话框中单击【求解】按钮，弹出图5-8所示的【规划求解结果】对话框，选中【保存规划求解结果】单选

23、按钮，点【确定】，规划求解的结果如图5-9所示。图5-8 “规划求解结果”对话框第三节第三节 多变量优化问题多变量优化问题图5-9 规划求解结果从图5-9可以很容易看出，当变量1236,0,6xxx时，目标函数的最大值为max12z 使用“规划求解”工具解线性规划问题时，EXCEL只能帮我们判断最优解是否存在并找到一个最优解，并不能确定是否为唯一的最优解。第三节第三节 多变量优化问题多变量优化问题二二、非线性规划非线性规划如果一个优化问题的目标函数和约束条件中，至少有一个表达式是非线性关系产品产品产品产品日允许消耗量日允许消耗量工时工时37300（工时）电力电力45250（千瓦）原材料原材料9

24、4420（千克）某公司生产和销售两种产品，已知每生产单位产品的工时、电力和原材料消耗如表5-2所示。表5-2 工时、电力和原材料的消耗表两种产品的单价与销量之间存在负线性关系，分别为1122300050,325080pq pq工时、用电量和原材料的单位成本分别是10、12和50，总固定成本是10000。该 公司怎样安排生产，所获利润最大。第三节第三节 多变量优化问题多变量优化问题 (1)建立问题的数学模型：建立问题的数学模型：则销售收入分别为11223000503250 80 x xxx产品的可变成本为11(3 10+4 129 50)528xx 产品的可变成本为22(7 10+5 124 5

25、0)330 xx 总固定成本是10000，因此利润函数可表示为1122122211223000503250805283301000024725026228010000zxxxxxxxxxx 由于工时每天可供使用量不能超过300，而生产1单位产品需要3个工时，生产1单位产品需要7个工时，故有1237300 xx同理，因受电力、原材料的限制，可以得到以下两个不等式12124525094420 xxxx第三节第三节 多变量优化问题多变量优化问题第三节第三节 多变量优化问题多变量优化问题综上所述，建立问题的数学模型为：22112212121212z247250262280100003730045250

26、94420,0Maxxxxxxxxxstxxx x第三节第三节 多变量优化问题多变量优化问题(2)使用使用EXCEL求解该模型：求解该模型：第一第一步：步：输入数据。其中，区域B5:C5表示表示决策变量值，区域B4:C6表示约束条件左端系数，区域D4:D6表示约束条件左端值(即实际需求量)，区域E4:E6表示约束条件右端值(即最大可供应量)，区域E5表示目标函数值。具体如图5-10所示。图5-10 数据输入第三节第三节 多变量优化问题多变量优化问题 第二第二步：步：描述目标函数表达式和约束条件左端。在E5单元格中输入目标函数表达式“=2472*B5-50*B52+2622*C5-80*C52-

27、10000”；在D2单元格中输入第一个约束条件的左端表达式“=B2*$B$5+C2*$C$5”，然后单击D2单元格，将鼠标移至D2单元格右下角，当光标变为小黑十字时，按住鼠标左键，拖曳至D4单元格。结果如图5-11所示图5-11 描述约束条件左端和目标函数表达式第三节第三节 多变量优化问题多变量优化问题第三步：第三步：设置求解参数。(1)设置设置目标单元格和可变单元格目标单元格和可变单元格 选中“最大值”前的单选按钮，设置目标单元格为“$E$5”，可变单元格为“$B$5:$C$5”(2)添加约束条件添加约束条件单击“规划求解参数”对话框中的【添加】按钮，打开【添加约束】对话框，单击单元格引用位置文本框，然后选定工作表中的D2:D4单元格，则在文本框中显示“$D$2:$D$4”，选择“=”约束条件；单击约束值文本框，然后选定工作表中的E2:E4单元格。(3)选择选择求解方法求解方法因为是非线性规划问题，所以选择求解方法为“非线性GRG”，勾选“使无约束变量为非负数”。求解参数设置如图5-12所示。第三节第三节 多变量优化问题多变量优化问题图5-12 设置求解参数第三节第三节 多变量优化问题多变量优化问题第四步：第四步：求解模型。求解的结果如图5-13所示。图5-13 规划求解结果从图5-13可以看出，当产量1224.7216.39xx，时，最大利润为42037.93。