最优化方法第1章-第1节1课件.ppt

1、2022-12-22最优化方法1举 例例例1：对边长为：对边长为a的正方形铁板，在四个角处剪去相等的正方形的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？以制成方形无盖水槽，问如何剪法使水槽的容积最大？解解 设剪去的正方形边长为设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为，由题意易知，与此相应的水槽容积为要使其最大，则要使其最大，则xxaxf2)2()(令令0)6)(2()2()2)(2(2)(2xaxaxaxxaxf得两个驻点：得两个驻点：axax6121，因此，每个角剪去边长为因此，每个角剪去边长为6a的正方形可使所制成的水槽容积最大的正

2、方形可使所制成的水槽容积最大 2022-12-22最优化方法2举 例例例2：某单位拟建一排四间的车库，平面位置：某单位拟建一排四间的车库，平面位置如图所示由于资金及材料的限制，围墙和隔如图所示由于资金及材料的限制，围墙和隔墙的总长度不能超过墙的总长度不能超过40m，为使车库面积最大，为使车库面积最大，应如何选择长、宽尺寸？应如何选择长、宽尺寸？x2x1图1.12022-12-22最优化方法3举 例解：解：设四间车库长为设四间车库长为 ，宽为，宽为 .由题意可知面积为由题意可知面积为1x2x2121)(xxxxf，且变量且变量 ，应满足应满足 1x2x405221 xx1200 xx，即求即求2

3、121),(maxxxxxf1212254000 xxxx，2022-12-22最优化方法4举 例 例例3.（混合饲料配合）以最低成本确定满（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。设每天足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为需要混合饲料的批量为100磅，这份饲料磅，这份饲料必须含：必须含：至少至少0.8%而不超过而不超过1.2%的钙的钙;至少至少22%的蛋白质的蛋白质;至多至多5%的粗纤维。假定主要配的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：的主要营养成分为：2022-12-22最优化方

4、法5配料配料每磅配料中的营养含量每磅配料中的营养含量(%)钙钙蛋白质蛋白质纤维纤维每磅成本（元）每磅成本（元）石灰石石灰石谷物谷物大豆粉大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250举 例2022-12-22最优化方法6举 例 解:设 x1,x2,x3 是生产100磅混合饲料所需的石灰石、谷物、大豆粉的量（磅）。1231231231231232323123min(,)0.01640.04630.1250.1000.3800.0010.0020.012 1000.3800.0010.0020.008 10

5、00.090.500.22 1000.020.080.05 100000f xxxxxxs txxxxxxxxxxxxxxxx第第1章章 基本概念基本概念 1.1 最优化问题简介最优化问题简介 1.2 凸集和凸函数凸集和凸函数 1.3 最优性条件最优性条件 1.4 最优化方法概述最优化方法概述2022-12-22最优化方法72022-12-22最优化方法8第第1章章 基本概念基本概念1.1 最优化问题简介最优化问题简介（一）最优化（optimization）的定义 所谓最优化最优化就是在众多可行的方案或方法中找到最好的方案和方法。最优方案最优方案就是达到最优目标的方案。最优化方法最优化方法就是

6、搜寻最优方案的方法。2022-12-22最优化方法9（二）最优化问题的数学模型（二）最优化问题的数学模型 实际问题实际问题建立模型建立模型分析求解模型分析求解模型检验并评价模检验并评价模 型求得最优解型求得最优解1.1 最优化问题简介重点重点2022-12-22最优化方法101.1 最优化问题简介 建立最优化问题数学模型的三要素：建立最优化问题数学模型的三要素：（1）决策变量。决策变量是由数学模型的解确定的未知）决策变量。决策变量是由数学模型的解确定的未知量。量。（2）约束或限制条件。）约束或限制条件。由于现实问题的客观物质条件限制，模型必须包括把决由于现实问题的客观物质条件限制，模型必须包括

7、把决策变量限制在它们可行值之内的约束条件，而这通常是用策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。约束的数学函数形式来表示的。（3）目标函数。）目标函数。优化问题决策变量的一个数学函数，它用来衡量优化问题优化问题决策变量的一个数学函数，它用来衡量优化问题的效率，即优化问题追求的目标。的效率，即优化问题追求的目标。2022-12-22最优化方法11 模型的转换模型的转换1、2、1.1 最优化问题简介()()f xf xf(x)(x)(x)=-f(x)对对于于求求目目标标函函数数极极大大的的问问题题可可转转换换成成求求极极小小的的问问题题。max min max

8、min 其其中中()()()()()()0a xb xch xb xa xch x 的的不不等等式式约约束束可可通通过过令令转转换换成成的的不不等等式式约约束束形形式式。2022-12-22最优化方法121.1 最优化问题简介 最优化问题的划分（根据不同的性质对最最优化问题的划分（根据不同的性质对最优化有不同的划分）：优化有不同的划分）：离离散散最最优优化化（组组合合最最优优化化）整整数数规规划划，资资源源配配置置等等非非光光滑滑最最优优化化最最优优化化连连续续最最优优化化线线性性规规划划（线线性性最最优优化化）光光滑滑最最优优化化非非线线性性最最优优化化2022-12-22最优化方法131.

9、1 最优化问题简介 最最 优优 性性 条条 件件（无无 约约 束束 极极 值值 的的 必必 要要 条条 件件 等等）无无 约约 束束 最最 优优 化化 一一 维维 搜搜 索索（线线 性性 搜搜 索索 和和 信信 赖赖 域域 方方 法法 等等）最最 速速 下下 降降 法法，牛牛 顿顿 法法，共共 轭轭 梯梯 度度 法法，拟拟 牛牛 顿顿 法法 等等非非 线线 性性 最最 优优 化化最最 优优 性性 条条 件件（等等 式式 约约 束束 等等）二二 次次 规规 划划约约 束束 最最 优优 化化可可 行行 方方 向向 法法惩惩 罚罚 函函 数数 法法2022-12-22最优化方法141.1 最优化问题

10、简介（三）基本概念（三）基本概念1.约束最优化约束最优化问题（问题（1.1.1）是最优化问题的一般数学表现）是最优化问题的一般数学表现形式。只要在问题中存在任何约束条件，就称形式。只要在问题中存在任何约束条件，就称为约束最优化问题。为约束最优化问题。2022-12-22最优化方法151.1 最优化问题简介（1）等式约束最优化）等式约束最优化（2）不等式约束最优化）不等式约束最优化（3）混合约束最优化：）混合约束最优化：既有等式约束又有不等式约束的最优化问题既有等式约束又有不等式约束的最优化问题。2022-12-22最优化方法161.1 最优化问题简介2.无约束最优化无约束最优化如果问题中无任何

11、约束条件，则称为无约束最优化问题。如果问题中无任何约束条件，则称为无约束最优化问题。其数学模型为其数学模型为3.离散最优化离散最优化 最优化模型中决策变量的取值为离散的最优化问题。最优化模型中决策变量的取值为离散的最优化问题。4.连续最优化连续最优化 最优化模型中决策变量的取值为连续的最优化问题。最优化模型中决策变量的取值为连续的最优化问题。2022-12-22最优化方法171.1 最优化问题简介5.光滑最优化光滑最优化 连续最优化模型中函数为光滑的最优化问题。即模型连续最优化模型中函数为光滑的最优化问题。即模型（1.1.1）中所有函数都是连续可微的。只要有一个函数非）中所有函数都是连续可微的

12、。只要有一个函数非光滑的，则称为非光滑最优化。光滑的，则称为非光滑最优化。6.线性规划线性规划12(,)111Tnxxxx 对对于于连连续续光光滑滑的的最最优优化化问问题题，如如果果所所有有函函数数都都是是变变量量的的线线性性函函数数，则则称称（.）为为线线性性规规划划问问题题。2022-12-22最优化方法181.1 最优化问题简介线性规划问题的一般形式为：线性规划问题的一般形式为：2022-12-22最优化方法191.1 最优化问题简介线性规划问题的矩阵表示：线性规划问题的矩阵表示：2022-12-22最优化方法201.1 最优化问题简介7.二次规划问题（它为非线性规划问题）二次规划问题（

13、它为非线性规划问题）2022-12-22最优化方法211.1 最优化问题简介8.非线性最优化非线性最优化 模型（模型（1.1.1）中的函数中有一个关于）中的函数中有一个关于x是非线性的，就称为非线性最优是非线性的，就称为非线性最优化问题。化问题。9.可行点可行点（feasible point）10.可行域可行域（feasible region）所有可行点的全体称为可行域。所有可行点的全体称为可行域。2022-12-22最优化方法221.1 最优化问题简介11、有效约束、有效约束（active constraint）和无效约束（和无效约束（inactive constraint）2022-12-

14、22最优化方法23 例例1.11.1 最优化问题简介2022-12-22最优化方法241.1 最优化问题简介13、有效集、有效集在一个可行点，所有有效约束的全体被称为该可行在一个可行点，所有有效约束的全体被称为该可行点的有效集，记为点的有效集，记为14、可行域的内点、可行域的内点15、可行域的边界、可行域的边界不是内点的可行点称为可行域的边界点不是内点的可行点称为可行域的边界点2022-12-22最优化方法251.1 最优化问题简介15、最优解、严格最优解、最优解、严格最优解2022-12-22最优化方法261.1 最优化问题简介16、局部最优解、严格局部最优解、局部最优解、严格局部最优解则称

15、则称x*为最优化问题（为最优化问题（1.1.1）的局部最优解，如）的局部最优解，如果不等式严格成立，则称为严格局部最优解。果不等式严格成立，则称为严格局部最优解。2022-12-22最优化方法271.1 最优化问题简介 例例1.2 下图中的决策变量哪些是局部极小解，哪些是严格局下图中的决策变量哪些是局部极小解，哪些是严格局部极小解？部极小解？2022-12-22最优化方法281.1 最优化问题简介17、凸规划、凸规划如果最优化问题的目标函数是凸的，可行如果最优化问题的目标函数是凸的，可行域是凸集，则问题的任何最优解（不一定域是凸集，则问题的任何最优解（不一定唯一）必是全局最优解，这样的最优化问

16、唯一）必是全局最优解，这样的最优化问题称为凸规划。题称为凸规划。2022-12-22最优化方法291.2 凸集和凸函数凸集和凸函数（一）凸集（一）凸集1、凸集的定义、凸集的定义2022-12-22最优化方法30 2、凸集的例子凸集的例子1.2 凸集和凸函数凸集和凸函数2022-12-22最优化方法31 3、凸集的性质凸集的性质1.2 凸集和凸函数凸集和凸函数 12121212121212111,.(2),=nDDRDDx xDxDDDxy xDyDDDxy xDyDDDx xD (1 1)两两个个凸凸集集的的交交，和和以以及及差差仍仍然然是是凸凸集集。对对于于任任意意非非零零实实数数，凸凸集集

17、集集合合也也是是凸凸集集。2022-12-22最优化方法321.2 凸集和凸函数凸集和凸函数 1 =nTanHxR a x 例例：设设为为已已知知的的 维维向向量量，为为标标量量，集集合合称称为为超超平平面面，证证明明它它是是一一个个凸凸集集。0002 =nxN xxRxx 例例：证证明明以以为为中中心心的的 邻邻域域（，）是是一一个个凸凸集集。2022-12-22最优化方法331.2 凸集和凸函数凸集和凸函数2022-12-22最优化方法34证明证明：（归纳法）由：（归纳法）由凸集的凸集的定义知当定义知当m=2显然成立，显然成立，假设当假设当m=k时成立，验证当时成立，验证当m=k+1时成立。时成立。1.2 凸集和凸函数凸集和凸函数 11+11111+11111,0,1,1,1,=1-+1-iiikkkiikiiikiiikikikkikxDRikxxxxx 设设则则 精品课件精品课件！精品课件精品课件！2022-12-22最优化方法371.2 凸集和凸函数凸集和凸函数 111111111-=11-,.1-kkikiiikkkiiiiiikxxDxD ，令令有有