规划数学单纯形法和复形法

单纯形法 0 5学时 复合形法 0 5学时 习题课 1学时 重点 单纯形法 复合形法的步骤及软件求解 非线性规划方法总结 难点 单纯形法 复合形法的思路基本要求 理解单纯形法和复合形法的步骤的思路 了解两种方法的联系及特点 掌握用软件实现单纯形法和复合形法 第10讲单纯形法 复合形法及习题课 单纯形法 一 单纯形法的思路 单纯形定义 线性独立 为构成的凸包 则称 单纯形 单纯形法的思路 单纯形法 simplexmethod 最直接法中最基本的方法 通过构造单纯形来逼近极小点 每构造一个单纯形 确定其最高点和最低点 然后通过扩展或压缩 反射构造新的单纯形 目的是使极小点能够包含于单纯形中 对于二维变量问题 单纯形为下图所示的由 及 六个点构成的多面体 二 单纯形法的步骤 用单纯形法求解无约束问题的算法步骤如下 1 选取初始单纯形反映系数紧缩系数扩展系数收缩系数精度置k 0 2 将单纯形的n 1个顶点按目标函数的大小重新编号 使顶点的编号满足 3 令 若 停止迭代 输出 否则转 4 4 计算若 转 5 否则当时转 6 若转 7 5 计算 若转 2 否则转 6 6 令 转 2 7 令 计算 若 令 转 2 否则转 4 8 令 转 2 单纯形法的计算框图 三 单纯形法的Matlab实现 函数 minSimpSearch 功能 用单纯形法求解多维函数的极值 调用格式 x minf minSimpSearch f X alpha sita gama beta var eps 其中 f 目标函数 X 初始单纯形 alpha 反映系数 sita 紧缩系数 gama 扩展系数 beta 收缩系数 var 自变量向量 eps 自变量精度 x 目标函数取最小值的自变量值 minf 目标函数的最小值 单纯形法举例 例1用单纯形法求解下面函数的极小值 取初单纯形 取参数 解 在Matlab命令窗口中输入 symsx1x2 f 3 x1 2 x2 2 x1 x2 3 x2 5 x 1018 1048 x mf minSimpSearch f x 1 2 0 5 2 0 3 x1x2 所得结果为 x 0 2729 1 6364mf 7 4545 四 单纯形法的优缺点 优点 计算简单 不需要求函数 偏 导数 可以没有函数的解析式 只要有函数值即可应用 缺点 收敛速度慢 适合场合 各种无约束极值问题 复合形法 一 复合形法的思路 复合形法来源于无约束问题的单纯形法 通过构造复合形来求得最优解 新的复合形通过替换旧的复合形中的坏点 目标函数值最大或次打的点 得到 替换方式仍然是单纯形的反射 压缩 扩展这几个基本方法 二 复合形法的步骤 用复合形法求解有约束极值问题的算法步骤如下 1 选取初始复合形反映系数紧缩系数扩展系数收缩系数精度置k 0 2 将复合形的n 1个顶点按目标函数的大小重新编号 使顶点的编号满足 3 令 若 停止迭代 输出 否则转 4 转 5 否则当时转 6 当转 7 5 计算 检验是否在可行域内 若不在将扩展系数减小 直到在可行域内 若令 转 2 否则转 6 6 令 转 2 7 令 计算检查是否在可行域内 若不在 将压缩系数减小 直到在可行域内 若令 转 2 否则转 4 8 令 转 2 4 计算检查是否在可行域内 即是否满足若不在可行域 将反射系数减小 直到在可行域内 计算 若 三 复合形法的Matlab实现 函数 minSimpSearch 功能 用复合形法求解多维函数的极值 调用格式 x minf minconSimpSearch f X alpha sita gama beta var eps 其中 f 目标函数 X 初始单纯形 alpha 反映系数 sita 紧缩系数 gama 扩展系数 beta 收缩系数 var 自变量向量 eps 自变量精度 x 目标函数取最小值的自变量值 minf 目标函数的最小值 复合形法举例 例2用复合形法求解下有约束极值问题 取初复合形 取参数 解 在Matlab命令窗口中输入 f x1 2 2x2 2 4 x1 8 x2 15 g 9 x1 2 x2 2 x1 x2 x 121 2 21 52 5 x mf minSimpSearch f x 1 2 0 5 2 0 3 x1x2 所得结果为 x 2 00001 9999mf 3 0000 四 复合形法的优缺点 优点 计算简单 不需要求函数 偏 导数