第6章代数方程与最优化问题的计算机求解讲解.ppt

*星期六, 2008-9- 6, 13:09:29 Yi Cao 在 Gianluca Dorini 贡献的Pareto解集提取程序的基础上，开发了改进的快速提取程序 函数调用格式 其中， 为可行解、离散点构成的列向量，K 向量为标志向量，指示可行解离散点是否为Pareto解集中的点 *星期六, 2008-9- 6, 13:09:29 例 6.50 采用上述的离散点分析方法重新研究下述的多目标优化问题 对原始问题中花费的钱数取一系列离散点 *星期六, 2008-9- 6, 13:09:29 原始问题可以改写成单目标的线性规划问题 对不同的加权求解最优化问题 得出 Perato 解集 *星期六, 2008-9- 6, 13:09:29 MATLAB求解语句： *星期六, 2008-9- 6, 13:09:29 例 6.51 重新考虑例6.44，试提取其Pareto解集 *星期六, 2008-9- 6, 13:09:29 MATLAB求解语句： *星期六, 2008-9- 6, 13:09:29 6.6.5 极小极大问题求解 极小极大问题的数学描述 极小极大问题是在最不利的条件下寻找最有利决策方案的一种方法 *星期六, 2008-9- 6, 13:09:29 直接求解极小极大问题的函数调用格式 其中，目标函数为向量形式描述，用匿名函数、inline()函数和M-函数均可以表示新目标函数 *星期六, 2008-9- 6, 13:09:29 例 6.52 试求解下面的极小极大问题 可以写出目标函数 调用fminimax函数求解 *星期六, 2008-9- 6, 13:09:29 选择随机数为初值 *星期六, 2008-9- 6, 13:09:29 有了fminimax()函数，还可以求解相关的变形问题 极小极小问题 极小极大问题 *星期六, 2008-9- 6, 13:09:29 6.6.6 目标规划问题求解 最优化问题求解过程中，发现找不到可行解时，要放松约束条件。如，不等式约束条件 改写成 将偏差对 引入目标函数 使得严格的不等式约束尽可能小地被突破，相应的最优化问题称为目标规划问题。 *星期六, 2008-9- 6, 13:09:29 数学描述形式 其中，F(x) 为原始的多目标向量，w 为各目标函数的加权系数，g为用户人为引入的目标 函数 *星期六, 2008-9- 6, 13:09:29 例 6.53 试用目标规划方法求解下式 求解 *星期六, 2008-9- 6, 13:09:29 6.7 动态规划及其在路径规划中的应用 图的矩阵表示方法 有向图的路径寻优 无向图的路径最优搜索 *星期六, 2008-9- 6, 13:09:29 6.7.1 图的矩阵表示方法 图是由节点和边构成的。边是连接两个节点的直接路径。如果边是有向的，则图称为有向图，否则称为无向图 在计算机中，图用矩阵表示，即关联矩阵 MATLAB语言还支持关联矩阵的稀疏矩阵表示方法 *星期六, 2008-9- 6, 13:09:29 构造关联矩阵的稀疏矩阵函数调用格式 其中， 为起始节点向量， 为终止节点向量， 为边权值向量，这里 各个向量最后的一个值使得关联矩阵为方阵 *星期六, 2008-9- 6, 13:09:29 稀疏矩阵可以由full()函数变换成常规矩阵，而常规矩阵可以由sparse()函数转换成稀疏矩阵 注意：在若第i和j节点间不存在边，则可令 ，当然，也有的算法要求 *星期六, 2008-9- 6, 13:09:29 6.7.2 有向图的路径寻优 有向图最短路径问题的手工求解 有向图搜索及图示 Dijkstra最短路径算法及实现 *星期六, 2008-9- 6, 13:09:29 有向图最短路径问题的手工求解 有向图与最优路径搜索是很多领域都能遇到的常见问题 应用动态规划理论，通常需要由终点反推回起点，搜索最优路径 *星期六, 2008-9- 6, 13:09:29 例 6.56 有向图路径如下，数字为从该路径所花费的时间，试求出从节点①到节点⑨的最优路径。 最短路径为： *星期六, 2008-9- 6, 13:09:29 动态规划问题的手工求解 最短路径为： *星期六,