软件数学实验-最优化

1、国防科技大学理学院数学与系统科学系数学实验最优化liuxiongweigfkd.mtn 一、最优化的一般概念1最优化问题举例 例1 纸盒容积问题： 有8尺5尺铁皮一块，将四角截去四个小方块，折叠成一个无盖盒子，试问截去小方块的尺寸是多少才能使得铁皮盒子的容积最大？（1）建立数学模型（2）选择方法求解FindMaximum(8 - 2 x) (5 - 2 x) x, 0 = x 1.一、最优化的一般概念1最优化问题举例 例2 两曲线之间距离问题：（1）建立数学模型（2）选择方法求解 已知两曲线 无交点，试求两曲线之间最短的距离。NMinimize(x1 - x2)2 + (x3 - x4)2,

2、2 Sinx1 - x3 = 0, x22 - x4 + 2 = 0, x1, x2, x3, x40.567353, x1 - 1.04091, x2 - 0.505432, x3 - 1.72573, x4 - 2.25546d = Sqrt%10.753228一、最优化的一般概念1最优化问题举例 例3 货栈选址问题：（1）建立数学模型（2）选择方法求解 设有 n 个市场，第 j 个市场的位置为 ，对某种货物的需求量为 。现在要求建立 m 个货栈，第 i 个货栈的容量为 。试确定货栈的位置，使得货栈到各市场的运输量与路程的乘积最小。一、最优化的一般概念1最优化问题举例 例3 货栈选址问题：

3、 某奶牛场每天每头牛需要：蛋白质700克，矿物质30克，维生素1克。现在有五种饲料可供选择，各饲料每公斤所含营养成分及其价格如下表所示：一、最优化的一般概念1最优化问题举例 例4 饲料选购问题：饲料种类12345需求量蛋白质（克/公斤）41532700矿物质（克/公斤）0.10.20.30.40.530维生素（克/公斤）0.020.010.040.050.031单击（元/公斤）0.20.70.40.90.8希望确定既满足营养需要又使得费用最省的方案。一、最优化的一般概念2最优化模型分类上面的各种问题可以归纳为：目标函数决策变量问题（*）的可行区域： 一、最优化的一般概念2最优化模型分类问题（*

4、）的可行区域： 二维、三维命令为RegionPlot或RegionPlot3D: RegionPlot1 x2 - y2 4 & x y 0 & y 0, x, 1, 2.5, y, 0, 1RegionPlot3Dx2 + y2 z2 & x2 + y2 + z2 35 一、最优化的一般概念2最优化模型分类上面的各种问题可以归纳为：(1) 当 全部为线性函数时，称（*）式为线性规划。一、最优化的一般概念2最优化模型分类上面的各种问题可以归纳为：(2) 当 为非线性函数且m = 0，称（*）式为无约束非线性规划。一、最优化的一般概念2最优化模型分类上面的各种问题可以归纳为：(3) 当 中至少一

5、个为非线性函数时，称（*）式为有约束非线性规划。二、无约束非线性规划设无约束非线性规划为 如果存在 ，使得对于任意的 ，总有 ，则称 为问题的全局最优解（或全局最小点）。 如果存在 ，使得对于 的一个 邻域，使得对于任意 ，总有 ，则称 为问题的局部最优解（或局部最小点）。1一维问题有解的条件与方法二、无约束非线性规划 在函数可微的情况下，它们这些点驻点，可能的极值点；在几何意义上讲就是具有水平切线或水平切平面的位置。当然也可能是不可微的位置。 在高等数学中我们介绍了解析求解的方法，但是在实际问题中，这些方法一般行不通。因此一般将问题转化为求导数的零点的方法，常见的零点求解方法有切线法（一维牛

6、顿法）、割线法、二次插值法等。 2多维问题有解的条件与方法二、无约束非线性规划(1) 有解的必要条件：若 是局部最优解，则必有(2) 有解的充分条件：若 使得 ，且，则 是局部最优解。其中：矩阵正定海塞矩阵Hessian2多维问题有解的条件与方法二、无约束非线性规划 对于多维问题的求解方法有梯度法，牛顿法，共轭方向法，拟牛顿法、方向加速法、步长加速法等方法。 优点：（1）方法简单，计算量小，存储量也小； （2）对初始点要求少，从一般初始点出发，都能收敛到某个局部极小值。 缺点：对于有些问题，收敛速度十分缓慢；稳定性较差。 梯度法：2多维问题有解的条件与方法二、无约束非线性规划 最突出的优点：收

7、敛速度快，为二阶收敛。 缺点：要求函数二阶可微，迭代多次使用 ，这个比较困难，计算量大；另外对初始点有比较苛刻的要求。 牛顿法：2多维问题有解的条件与方法二、无约束非线性规划 优点：（1）计算公式简单，存储量小，对初始点要求少，对二次函数具有二次终止性质（即通过有限步可以得到最小值点） （2）收敛速度介于上面两种方法之间，对高维（维数较大时）的一般非线性函数有较高的效率）。 缺点：共轭方法的一些理论支撑还不够完善，对于一维搜索依赖性很强，对于其执行的影响需要进一步探索。共轭方法：2多维问题有解的条件与方法二、无约束非线性规划 优点：具有较快的收敛速度和对二次函数具有二次终止的性质，一般情况下优

8、于共轭梯度法； 缺点：存储容量要求大，对于大型问题带来不便，但具有较高的数值稳定性。因此，该方法受到人们的重视和欢迎，在实际应用中与其他方法结合的话，能收到很好的效果。拟牛顿法：2多维问题有解的条件与方法二、无约束非线性规划 优点：（1）方法形象直观，容易掌握和了解； （2）对目标函数要求较少，适用范围广； （3）在直接方法中收敛速度较快，受到重视。 缺点：在目标函数维数较大时，可能使得方法无效，目前有很多人在对该方法进行改进。方向加速法：2多维问题有解的条件与方法二、无约束非线性规划 优点：（1）方法简单，易于理解和掌握，在计算机上易于实现； （2）对目标函数要求较少，适用范围广； （3）大

9、量数值试验表明效果好，在实际应用中比较成功。 缺点：是收敛速度慢，特别是到达最优点附近情况更是如此。步长加速法：3Mathematica中无约束非线性规划的求解二、无约束非线性规划调用格式为：适用于各种连续可微的函数：FindMinimumf(x),x1,x10,x2,x20,.,Options 适用于某些连续而不一定可微的函数：FindMinimumf(x),x1,a1,b1,x2,a2,b2,.,Options Options可选参数，包含有算法（梯度法Gradient，共轭梯度法ConjugateGradient，牛顿法Newton，BFGS拟牛顿法QuasiNewton，以及L-M方法

10、LevenbergMarquardt等）的选择，变量计算的精度，梯度处理方式，最大迭代次数。 3Mathematica中无约束非线性规划的求解二、无约束非线性规划例1 选用牛顿法，计算精度要求为，初始点取的无约束非线性规划问题： In1:= FindMinimum x13 + x23 + x33 - 3 (x1 + 4 x2 + 9 x3), x1, 4, x2, 4, x3, 4, Method - Newton, PrecisionGoal - 10-6 Out1= -72., x1 - 1., x2 - 2., x3 - 3. 3Mathematica中无约束非线性规划的求解二、无约束非

11、线性规划例2 FindMinimum-3/(1 + Sqrtx12 + x22), x1, -1, 2, x2, -1, 1-3., x1 - 4.06087*10-11, x2 - 3.73719*10-11 ，求其极小值。因为在原点连续但不可微，所以使用第二种方法： 三、有约束非线性规划有约束非线性规划模型为 其求解方法有SUMT外点法（惩罚法）、SUMT内点法（碰壁法）、精确罚函数法、乘子罚函数法、复合形法 。三、有约束非线性规划 前面的五种方法总称为罚函数方法，其思路是通过构造罚函数，将有约束问题转化为无约束优化问题来求解。内点法与外点法思路清晰，罚函数构造简单，迭代过程比较简单，计算

12、机上容易实现，在实际应用中效果较好。它存在明显的缺点，就是在约束最优点处，辅助函数的Hessian矩阵呈病态现象，直接影响算法的精度与收敛性。乘子法在罚函数结构上与迭代过程相对几种方法来说虽要复杂一些，但它克服了前面几种方法所存在的缺点，从理论角度来看，它优于其他几种方法。 其求解方法有SUMT外点法（惩罚法）、SUMT内点法（碰壁法）、精确罚函数法、乘子罚函数法、复合形法 。三、有约束非线性规划 其求解方法有SUMT外点法（惩罚法）、SUMT内点法（碰壁法）、精确罚函数法、乘子罚函数法、复合形法 。 复合形法优于在迭代中只用到了目标函数与约束函数的函数值，不需要导数值，因此对函数的要求十分宽

13、松，适用范围非常广泛；且其计算量小，在维数越高其优越性相对于其它方法来说更具有优越性；不受随机因素干扰，均能稳定收敛于约束问题的最优点；也不受初始点的影响，常常能够收敛于约束问题的全局极小点。 缺点是方法虽然形象直观，但是结构比较粗糙，计算精度较低，对某些目标函数，附近的顶点可能退化到一个低维空间中，使得迭代无法继续。 三、有约束非线性规划有约束非线性规划问题的Mathematica求解方法：例1 求解下面问题：In1:= NMinimize(x1 + x2 + x3)/( x12 + x2 x3), 3 x1 + 4 x2 + 5 x3 = 0, x2 = 0, x3 = 0, x1, x2

14、, x3Out1= 0.2, x1 - 5., x2 - 0., x3 - 0. 三、有约束非线性规划如果目标函数多出了二次项，则称为二次规划。 例2 求解下面二次规划问题 In2:= NMinimizex12 + 2 x22 - x1*x2 - x1 - 10 x2, -3 x1 - 2 x2 = -6, x1 = 0, x2 = 0, x1, x2Out2= -13.75, x1 - 0.5, x2 - 2.25 例1 四、线性规划 如果优化模型中的目标函数与约束函数均为线性函数，则这个模型称为线性规划模型。 如果令 坐标形式矩阵形式四、线性规划 如果优化模型中的目标函数与约束函数均为线性

15、函数，则这个模型称为线性规划模型。 例1 松弛变量剩余变量标准形式四、线性规划 线性规划标准形式的一般写法为： 满秩 四、线性规划 线性规划问题的Mathematica解法 ： LinearProgrammingc,A,b 约束右端向量b分量可正，可负或为0。例1 求解下列线性规划问题： 四、线性规划 线性规划问题的Mathematica解法 ： LinearProgrammingc,A,b In1:= c = 1, -2, -3; b = -6, 12, 20, -20; A = -1, -1, -1, 1, -2, 4, 3, 2, 4, -3, -2, -4; LinearProgram

16、mingc, A, bOut1= 0, 2, 4In2:= c.%Out2= -16 四、线性规划例1 求解下列线性规划问题： In3:= NMaximize-x1 + 2 x2 + 3 x3, x1 + x2 + x3 = 12, 3 x1 + 2 x2 + 4 x3 = 20, x1 = 0, x2 = 0, x3 = 0, x1, x2, x3Out3= 16., x1 - 0., x2 - 2., x3 - 4. 五、整数规划例1 背包问题： 在一个数学规划中，如果它的全部（或部分）自变量要求取为整数时，则这个规划为一个纯整（或混整）规划，简称为整数规划。在特殊情况下，如果这些整数只限

17、于0或1，则称这样的规划为0-1规划。 假设一小商贩从山下要携带一些商品到山上销售，他的背包最多只能装10公斤，现在有三种商品可供挑选，每种物品的重量与利润为已知，如下表： 商品123重量（公斤/件）345利润（元/件）456试问应该选装哪些商品，件数多少，才能使得总的效益（利润）最大？ 五、整数规划例1 背包问题： 商品123重量（公斤/件）345利润（元/件）456背包最多只能装10公斤设应该携带商品的数量分别为 ,模型为：In1:= NMaximize4 x1 + 5 x2 + 6 x3, 3 x1 + 4 x2 + 5 x3 = 0, x2 = 0 & x3 = 0, x1, x2,

18、x3 Element Integers, x1, x2, x3Out1= 13., x1 - 2, x2 - 1, x3 - 0 六、全局优化例1 求解全局优化问题：在Mathematica中全局优化的计算主要使用NMaximize和NMinimize来完成，通过带用不同参数得到需要的结果。In1:= NMinimize(*目标函数*)E(-0.3 x) Sin2 x,(*声明变量*)x,(*参数之一：算法选择及算法的参数*) Method - DifferentialEvolution, SearchPoints - 4(*种群规模5n10n*), ScalingFactor - 0.1(*搜索步长*), RandomSeed - 3(*随机种子(01000)*)(*参数二*), MaxIterations - 10(*迭代次数*) / TimingOut1= 0.047, -1.27996, x - -0.859843六、全局优化思考题：决策问题 必须要选修的课程只有一门（2个学分）；可供限定选修的课程有8门，任意选修课程有10门。由于课程之间有联系，所以可能在选修某门课程中必须同时选修其他课程，18门课学分数和要求信