1 理学院 最优化原理与算法 实验指导书 王凯编写 适用专业：信息与计算科学、数学与应用数学 贵州大学 二 O 一一年二月 2 前言 最优化原理与算法课程是我校信息与计算科学的必修课，同时是数学与应用数学专业的选修课程。如何使学生掌握所学优化方法，并将其在实践问题中获得检验，以及如何将理论、方法、求解问题等环节有机结合是该门课程的宗旨；因此该实验课程经过实践环节的训练，学生在实验中，掌握数学规划方法的实际使用，培养学生解决实际问题、掌握优化方法的能力和培养团队合作精神。此课程以介绍线性规划作为切入点，逐层次对几种类型优化问题详细介绍一些经典的优化方法，并借助 Matlab 工具箱，介绍若干优化方法的具体操作流程，内容深入浅出，学生易于掌握。要求学生能熟练应用 Matlab 优化工具箱解决课本上各种测试优化问题及综合性实验内容。在所有实验项目中，实验七为综合性实验，共 6学时，其它为验证性实验，共 30 学时。注意：信息与计算科学专业必须完成指导书中所有实验，数学与计算数学专业必须完成实验七，并在其余实验中任选三项完成。 3 目录 1、实验一：Matlab 优化工具箱4 2、实验二：线性规划6 3、实验三: 无约束非线性规划7 4、实验四: 约束非线性规划8 5、实验五: 多目标规划10 6、实验六: 离散型优化算法12 7、实验七: 最优化问题的应用举例13 4 实验一 1 熟悉 Matlab 优化工具箱求解优化问题的类型 Matlab优化工具箱 实验学时：2 实验类型：验证 实验要求：必修 一、实验目的 了解 Matlab 中 Optimization Toolbox 所包括的优化方法、使用范围；熟悉和理解该工具箱的英文表述。 二、实验内容 2 了解 help 工具箱中求解优化问题的各种语法功能， 并理解各种语法下的例子， 具体如下： （1）线性规划 XfTbAXmin 语法：),(bAflpX = （2）二次规划 XCHXXTTbAX+ 21min 语法：),(bACHqpX = （3）非负最小二乘法 20|minbAXX语法：),(bAnnlsX = （4）无约束一元函数极小问题 )(minxfx语法：), min(xffx = （5）无约束非线性规划 )(minxxf 语法：), (minXfufX = （6）约束非线性规划 )(min 0)(xfXG语法：), (XfgconstrX = （7）目标规划 goalWXFX)(min语法：), (WgoalXfattgoalX = （8）最小最大问题 )(maxmin 0)(XFXG语法：), max(minXfgiX = 5 （9）非线性最小二乘法 )(*)(minXFXFX语法：), (XfleastsqX = （10）解非线性方程 0)(=XF 语法：), (XffsolvexX = （11）半无穷下的非线性规划 WWXtsXfX, 0),(. .)(min语法：), (minXnftfseX = 6 实验二 线性规划 实验学时：2 实验类型：验证 实验要求：必修 一、实验目的 要求学生能用 Optimization Toolbox 求解线性规划问题，并力求了解高维线性规划问题的求解方法。 二、实验内容 利用事例说明用 Matlab 解线性规划的方法 （1）问题： XfTbAXmin 应用 Matlab 求解步骤： 将一般的线性规划问题转化为以上标准形式； 输入bAf,； 使用命令窗口程序 ),(bAflpX =； 回车，获解。 （2）例 求解下列优化问题 0,41232642. .5324321431432143214321+xxxxxxxxxxxxxxxtsxxxx第一步骤： ;0 , 0 , 0 , 0 , 4 ,12, 6;1, 0 , 0 , 0 ; 0 , 0 , 1, 0 ; 0 , 0 , 0 , 1; 1 , 1 , 0 , 1 ; 1 , 1, 3 , 2 ; 1, 4 , 2 , 1 ,5, 3 , 1, 2=bAf第二步骤：),(bAflpx = 第三步骤：回车 （3）自己构造一个非标准形式的线性规划问题，并求解。 要求：维数 20 维；含有等式约束；含 10 个以上不等式约束。 （4）分析 Matlab 求解线性规划问题的能力。 7 实验三 无约束非线性规划 实验学时：4 实验类型：验证 实验要求：必修 一、实验目的 要求学生掌握求解非约束规划的几种不同类型优化方法，并能在 Matlab 和 VC+环境下熟练应用。 二、实验内容 （1） 应用 Matlab 求解非约束优化问题。 例 1 求2minxex+第一步：利用文件编辑器编写 M 文件 ; 2)exp()(xxfxfunfunctionf+=（2） 第二步：在命令窗口中输入 （3） );, min(; 1xfunfxx=（4） 第三步：回车 （5） 例 2 求 （6） ) 12424()(2212 22 112min+=xxxxxexfxRx（7） 第一步：利用文件编辑器编写 M 文件 （8） );1)2(*2)2(*) 1 (*42)2(*22)1 (*4(*)1 (exp()(+=xxxxxxfxfunfunctionf（9） 第二步：在命令窗口中输入 （10） );, 0, (min,;1 , 10optionsxfunufoptionsxoptionsx=（11） 第三步：回车 （12） 应用 Matlab 和 VC+编写平分法、黄金分割法、牛顿法。 （13） 根据课本中 P141-143 所给出的流程图，利用 C+编写程序，并设计事例进行求解。 8 实验四 约束非线性规划 实验学时：3 实验类型：验证 实验要求：必修 一、实验目的 要求学生掌握课程中介绍的各种约束优化方法，特别是约束优化问题非约束化的处罚法，并能应用 Matlab 求解。 二、实验内容 介绍解约束非线性规划的若干方法，并用 VC+及 Matlab 进行实现：二次规划、Lemeke方法、惩罚函数法、乘子法。 （1）二次规划 bAXtsXcHXXTT+. . 21min解决此类问题的步骤如下： 第一步：输入 A，H，c, b 第二步：调用优化程序 );,(bAcHqpX =第三步：回车 利用以上方法解下列二次线性规划问题 0,024. .96min212112 22 1+xxxxtsxxx（2）约束非线性规划问题 0)(. .)(minxgtsxf解决此类问题的步骤如下： 第一步：输入 定义目标约束函数 ?;)2(?;) 1 ()(,=gg？；fxfungffunction约束函数输入目标函数9 第二步：调用优化程序 x0=a,b; options=; x,options=constr(fun,x0,option) 若变量有约束限制，则 vlb=a1,a2,.,vub=b1,b2,.; x,options=constrfun,xo,options,vlb,vub 第三步：回车 例 应用以上方法解下列问题 101005 . 1. .) 12424()(21212112212 22 112min+=xxxxxxxtsxxxxxexfxRx220 , 20324. .)3)(4min(2121212 12 12=+xxxxxxxtsxx（14） 用 C+语言编写 P146-150 的流程图程序，并求解具体的优化问题（以上面的例 2 为例） 10 实验五 多目标规划 实验学时：2 实验类型：验证 实验要求：必修 一、实验目的 要求学生初步掌握多目标规划中几种基本的求解方法，并能寻求最优的决策方案。 二、实验内容 多目标优化问题单目标化及方法应用。 问题 0)(. .)(),.,(),()(min21=XGtsXfXfXfXfm求解方法：通过引入加权因子，将上问题转化为单目标约束优化问题，然后利用单目标约束优化方法求解。 执行步骤如下： 第一步：输入目标约束函数 ?)2(?;) 1 (.,.,)(,22112121=+=ggfwfwfwFfffwwwXfungFfunctionmmmm定义约束函数定义目标函数输入子目标函数输入加权值第二步：调用优化程序 x0=a,b; options=; x,options=constr(fun,x0,option) 若变量有约束限制，则 vlb=a1,a2,.,vub=b1,b2,.; x,options=constrfun,xo,options,vlb,vub 第三步：回车 例 解下列多目标优化问题 11 10 , 10 , 043)(,2)()(),()(2122 121221121min=+=xxxxxxXfxxXfXfXfXfDx12 实验六 离散型优化算法 实验学时： 2 实验类型：验证 实验要求：必修 一、实验目的 要求学生掌握简单的离散型优化问题求解方法、了解网络优化、遗传算法。 二、实验内容 线性整数规划、0-1 规划的隐枚举法。 利用 P152-153 的流程图编写分支定界法及遗传算法的程序，并求解下列问题： 1 , 0,14424204. .4352min43214321432143214321=+=xxxxxxxxxxxxxxxxtsxxxxz13 实验七（综合性实验） 最优化问题的应用举例 实验学时： 3 实验类型：综合性 实验要求：必修 一、实验目的 学生在计算机上求解实际优化问题，并写出综合实验报告分析材料。 二、实验内容 人力计划问题、炼油厂的优化问题。 （1） 人力资源计划 人力资源计划是公司用人的关键方案，对公司的生产效率有直接的影响，现根据课本P136 的案例 5 对人力资源计划介绍的内容，设计人力资源优化模型，及利用已经学过的组合优化方法确定最优的人力资源计划方案。 实