安康学院数学与统计系 应用数学教研室前言前言一、什么是最优化一、什么是最优化 最优化是一门应用性相当广泛的学科，它讨论决策最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现些计算方法的理论性质及其实际计算表现应用范围：信息工程及设计、经济规划、生产管理、交应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域通运输、国防工业以及科学研究等诸多领域1 1安康学院数学与统计系 应用数学教研室二、包含的内容二、包含的内容按照优化思想分为经典方法与现代方法按照优化思想分为经典方法与现代方法经典方法主要包括：线性规划、非线性规划、整数规经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等算法、遗传算法、禁忌搜索和人工神经网络等我们学习的内容主要是经典的最优化方法我们学习的内容主要是经典的最优化方法。
内容包括线性规划及其对偶规划，无约束最优化方法、内容包括线性规划及其对偶规划，无约束最优化方法、约束最优化方法等主要内容约束最优化方法等主要内容2 2安康学院数学与统计系 应用数学教研室目录目录第一章第一章 最优化问题概述最优化问题概述第二章第二章 线性规划线性规划第三章第三章 无约束最优化方法无约束最优化方法第四章第四章 约束最优化方法约束最优化方法3 3安康学院数学与统计系 应用数学教研室第一章最优化问题概述安康学院数学与统计系 应用数学教研室1.1 最优化问题的数学模型最优化问题的数学模型与基本概念与基本概念5 5安康学院数学与统计系 应用数学教研室例例 1.1.1 运输问题运输问题设有设有m个水泥厂个水泥厂A1,A2, , Am,年产量各为年产量各为a1, a2, ,am吨吨.有有k个城市个城市B1,B2, Bk用这些水泥用这些水泥厂生产的水泥厂生产的水泥,年需求量年需求量b1,b2, ,bk吨吨.再设由再设由Ai到到Bj每吨水泥的运价为每吨水泥的运价为cij元元.假设产销是平衡假设产销是平衡的的,即即:试设计一个调运方案试设计一个调运方案,在满足需要的同时使总在满足需要的同时使总运费最省运费最省.6 6安康学院数学与统计系 应用数学教研室A1 由题意可画出如下的运输费用图由题意可画出如下的运输费用图:B2AmB1A2Bk产量产量需求量需求量设设AiBj的水泥量为的水泥量为xij,已知已知AiBj单价为单价为cij,单单位为元位为元,则总运费为则总运费为:7 7安康学院数学与统计系 应用数学教研室数学模型数学模型:注注:平衡条件平衡条件 作为已知条件并不作为已知条件并不出现在约束条件中出现在约束条件中.8 8安康学院数学与统计系 应用数学教研室例例1.1.2 生产计划问题设某工厂有设某工厂有m种资源种资源B1,B2, ,Bm,数量分别为数量分别为: b1,b2, , bm,用这些资源产用这些资源产n种产品种产品A1,A2, , An.每生产一个单位的每生产一个单位的Aj产品需要消耗资源产品需要消耗资源Bi的的量为量为aij,根据合同规定根据合同规定,产品产品Aj的量不少于的量不少于dj.再再设设Aj的单价为的单价为cj.问如何安排生产计划问如何安排生产计划,才能既完成合同才能既完成合同,又使该又使该厂总收入最多厂总收入最多?9 9安康学院数学与统计系 应用数学教研室假设产品假设产品Aj的计划产量为的计划产量为xj.由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图:B1B2BmAnA2A1消耗消耗1010安康学院数学与统计系 应用数学教研室数学模型数学模型1111安康学院数学与统计系 应用数学教研室例例 1.1.3 指派问题指派问题设有四项任务设有四项任务B1,B2,B3,B4派四个人派四个人A1,A2, A3,A4去完成去完成.每个人都可以承担四项任务中的每个人都可以承担四项任务中的任何一项任何一项,但所消耗的资金不同但所消耗的资金不同.设设Ai完成完成Bj所所需资金为需资金为cij.如何分配任务如何分配任务,使总支出最少使总支出最少?设变量设变量指派指派Ai完成完成bj不指派不指派Ai完成完成bj1212安康学院数学与统计系 应用数学教研室则总支出可表示为则总支出可表示为:数学模型数学模型:1313安康学院数学与统计系 应用数学教研室例例 1.1.4 数据拟合问题数据拟合问题 在实验数据处理或统计资料分析中常遇在实验数据处理或统计资料分析中常遇到如下问题到如下问题.设两个变量设两个变量x和和y,已知存在函数关已知存在函数关系系,但其解析表达式或者是未知的或者虽然为但其解析表达式或者是未知的或者虽然为已知的但过于复杂已知的但过于复杂.设已取得一组数据设已取得一组数据: (xi,yi) i=1,2,m.根据这一组数据导出函数根据这一组数据导出函数y=f(x)的一个简单而的一个简单而近似的解析表式近似的解析表式.1414安康学院数学与统计系 应用数学教研室最小二乘法最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法,以一个以一个简单的函数序列简单的函数序列j j1(x), j j2(x), j jn(x)为基本函数为基本函数.一般选取一般选取1,x,x2,xn为基本函数为基本函数,即以即以作为近似表达式作为近似表达式.1515安康学院数学与统计系 应用数学教研室最小二乘法最小二乘法系数的选取要使得下面得平方和最小系数的选取要使得下面得平方和最小:因此因此,数据拟合问题得数学模型为数据拟合问题得数学模型为其中其中xi,yi(i=1,2,m)及及j jj(x)(j=0,1,n)为已知为已知.1616安康学院数学与统计系 应用数学教研室最优化问题最优化问题最优化问题的一般形式为最优化问题的一般形式为最优化问题的一般形式为最优化问题的一般形式为: :(1.1)(目标函数目标函数)(1.3)(不等式约不等式约束束)(1.2)(等式约束等式约束)其中其中x是是n维向量维向量.在实际应用中在实际应用中,可以将求最大值的目标函数取可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式.我们总是讨论我们总是讨论P:P:1717安康学院数学与统计系 应用数学教研室相关定义相关定义定义定义1.1.1 (可行解可行解) 满足约束条件满足约束条件(1.2)和和(1.3)的的x称为可行解称为可行解,也称为可行点或容许点也称为可行点或容许点.定义定义1.1.2 (可行域可行域)全体可行解构成的集合称全体可行解构成的集合称为可行域为可行域,也称为容许集也称为容许集,记为记为D,即即:D=x|hi(x)=0,i=1,m,gj(x)0, j=1,p,xRn.若若hi(x), gj(x)为连续函数为连续函数,则则D为闭集为闭集.1818安康学院数学与统计系 应用数学教研室定义定义1.1.3 (整体最优解整体最优解) 若若x*D,对于一切对于一切xD恒有恒有f(x*)f(x),则称则称x*为最优化问题为最优化问题(P)的的整体最优解整体最优解.若若x*D,xx*, 恒有恒有f(x*) f(x),则称则称x*为最优为最优化问题化问题(P)的严格整体最优解的严格整体最优解.相关定义相关定义1919安康学院数学与统计系 应用数学教研室定义定义定义定义1.1.4 (1.1.4 (局部最优解局部最优解局部最优解局部最优解) ) 若若若若x*D,存在存在存在存在x*的某邻域的某邻域的某邻域的某邻域N Ne e e e( (x x*),*),使得对于一切使得对于一切使得对于一切使得对于一切x xD D N Ne e e e( (x x*),*),恒有恒有恒有恒有f(x*)f(x),则则则则称为最优化问题称为最优化问题称为最优化问题称为最优化问题(P)(P)的局部最优解的局部最优解的局部最优解的局部最优解, ,其中其中其中其中N Ne e e e( (x x*)=*)=x x| | |x x- -x x*|*|0.0.当当当当x x x x* *时时时时, ,若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称x x* *为问为问为问为问题题题题(P)(P)的严格局部最优解的严格局部最优解的严格局部最优解的严格局部最优解. .显然显然显然显然, ,整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解, ,而局部最优解不而局部最优解不而局部最优解不而局部最优解不一定是整体最优解一定是整体最优解一定是整体最优解一定是整体最优解. .x*对应的目标函数值对应的目标函数值f(x*)称为最优值，记为称为最优值，记为f *.相关定义相关定义2020安康学院数学与统计系 应用数学教研室求解最优化问题求解最优化问题求解最优化问题求解最优化问题( (P P), ),就是求目标函数就是求目标函数就是求目标函数就是求目标函数f f( (x x) )在约束条件在约束条件在约束条件在约束条件(1.2),(1.3)(1.2),(1.3)下的极小点下的极小点下的极小点下的极小点, ,实际上是求可行域实际上是求可行域实际上是求可行域实际上是求可行域D D上的整体上的整体上的整体上的整体最优解最优解最优解最优解. .但是但是但是但是, ,在一般情况下在一般情况下在一般情况下在一般情况下, ,整体最优解是很难求出整体最优解是很难求出整体最优解是很难求出整体最优解是很难求出的的的的, ,往往只能求出局部最优解往往只能求出局部最优解往往只能求出局部最优解往往只能求出局部最优解. .在求解时需要范数的概念，以下给出定义。
在求解时需要范数的概念，以下给出定义在求解时需要范数的概念，以下给出定义在求解时需要范数的概念，以下给出定义相关定义相关定义2121安康学院数学与统计系 应用数学教研室向量范数向量范数定义定义1.1.5 如果向量如果向量xRn 的某个实值函数的某个实值函数|x|,满足条件满足条件(1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性);(2)| x|=| |x|(对于任意对于任意 R);(3) |x+y|x|+|y|(三角不等式三角不等式);则称则称|x|为为Rn 上的一个向量范数上的一个向量范数.2222安康学院数学与统计系 应用数学教研室常用的向量范数常用的向量范数1-范数范数2-范数范数(欧氏范数欧氏范数)-范数范数p-范数范数-范数是范数是p-范数的极限范数的极限2323安康学院数学与统计系 应用数学教研室常用的向量范数常用的向量范数对向量对向量x=(1,-2,3)T,有有|x|p是是p的单调递减函数的单调递减函数.2424安康学院数学与统计系 应用数学教研室最优化问题的分类最优化问题的分类根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类:线线性最优化问题性最优化问题,非线性最优化问题非线性最优化问题,二次规划二次规划,多多目标规划目标规划,动态规划动态规划,整数规划整数规划,0-1规划规划.2525安康学院数学与统计系 应用数学教研室1.2 最优化问题的一般算法最优化问题的一般算法2626安康学院数学与统计系 应用数学教研室迭代算法迭代算法迭代算法迭代算法 选取一个初始可行点选取一个初始可行点x0D,由这个由这个初始可行点出发初始可行点出发,依次产生一个可行点列依次产生一个可行点列:x1,x2,xk,记为记为xk,使得某个使得某个xk恰好是问题的一个最优解恰好是问题的一个最优解,或者该。