多目标最优化数学模型

第六章第六章 最优化数学模型最优化数学模型 1 最优化问题最优化问题 1 1 最优化问题概念 1 2 最优化问题分类 1 3 最优化问题数学模型 2 经典最优化方法经典最优化方法 2 1 无约束条件极值 2 2 等式约束条件极值 2 3 不等式约束条件极值 3 线性规划线性规划 3 1 线性规划 3 2 整数规划 4 最优化问题数值算法最优化问题数值算法 4 1 直接搜索法 4 2 梯度法 4 3 罚函数法 5 多目标优化问题多目标优化问题 5 1 多目标优化问题 5 2 单目标化解法 5 3 多重优化解法 5 4 目标关联函数解法 5 5 投资收益风险问题 第六章第六章 最优化问题数学模型最优化问题数学模型 1 最优化问题 1 1 最优化问题概念 1 最优化问题 在工业 农业 交通运输 商业 国防 建筑 通信 政府机关等各部门各 领域的实际工作中 我们经常会遇到求函数的极值或最大值最小值问题 这一 类问题我们称之为最优化问题最优化问题 而求解最优化问题的数学方法被称为最优化方 法 它主要解决最优生产计划 最优分配 最佳设计 最优决策 最优管理等 求函数最大值最小值问题 最优化问题的目的有两个 求出满足一定条件下 函数的极值或最大值 最小值 求出取得极值时变量的取值 最优化问题所涉及的内容种类繁多 有的十分复杂 但是它们都有共同的 关键因素 变量 约束条件和目标函数 2 变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量 一般来说 它们都有一些限制条件 约束条件 与目标函数紧密关联 设问题中涉及的变量为 我们常常也用表示 n xxx 21 21n xxxX 3 约束条件 在最优化问题中 求目标函数的极值时 变量必须满足的限制称为约束条件约束条件 例如 许多实际问题变量要求必须非负 这是一种限制 在研究电路优化设 计问题时 变量必须服从电路基本定律 这也是一种限制等等 在研究问题时 这些限制我们必须用数学表达式准确地描述它们 用数学语言描述约束条件一般来说有两种 等式约束条件 miXgi 2 1 0 不等式约束条件 riXhi 2 1 0 或 riXhi 2 1 0 注 在最优化问题研究中 由于解的存在性十分复杂 一般来说 我们不考虑 不等式约束条件或 这两种约束条件最优化问题最优解的存0 Xh0 Xh 在性较复杂 4 目标函数 在最优化问题中 与变量有关的待求其极值 或最大值最小值 的函数称为 目标函数 目标函数 目标函数常用表示 当目标函数为某问题的效益函数 21n xxxfXf 时 问题即为求极大值 当目标函数为某问题的费用函数时 问题即为求极小 值等等 求极大值和极小值问题实际上没有原则上的区别 因为求的极小值 Xf 也就是要求的极大值 两者的最优值在同一点取到 Xf 1 2 最优化问题分类 最优化问题种类繁多 因而分类的方法也有许多 可以按变量的性质分类 按有无约束条件分类 按目标函数的个数分类等等 一般来说 变量可以分为确定性变量 随机变量和系统变量等等 相对应 的最优化问题分别称为 普通最优化问题 统计最优化问题和系统最优化问题 按有无约束条件分类 无约束最优化问题 有约束最优化问题 按目标函数的个数分类 单目标最优化问题 多目标最优化问题 按约束条件和目标函数是否是线性函数分类 线性最优化问题 线性规划 非线性最优化问题 非线性规划 按约束条件和目标函数是否是时间的函数分类 静态最优化问题和动态最 优化问题 动态规划 按最优化问题求解方法分类 解析法 间接法 图克定理库恩 极大值原理 有约束 古典变分法 古典微分法 无约束 数值算法 直接法 随机搜索法 单纯形法 方向加速法 步长加速法 坐标轮换法 多维搜索法 插值法 黄金分割法 斐波那西法 一维搜索法 数值算法 梯度法 复形法 法 法 化有约束为无约束 梯度投影法 可行方向法 有约束梯度法 变尺度法 共轭梯度法 拟牛顿法 最速下降法 无约束梯度法 SWIFT SUMT 多目标优化方法 目标关联函数法 多重目标化方法 单目标化方法 网络优化方法 1 3 最优化问题的求解步骤和数学模型 1 最优化问题的求解步骤 最优化问题的求解涉及到应用数学 计算机科学以及各专业领域等等 是 一个十分复杂的问题 然而它却是需要我们重点关心的问题之一 怎样研究分 析求解这类问题呢 其中最关键的是建立数学模型和求解数学模型 一般来说 应用最优化方法解决实际问题可分为四个步骤进行 步骤步骤 1 建立模型 建立模型 提出最优化问题 变量是什么 约束条件有那些 目标函数是什么 建立最 优化问题数学模型 确定变量 建立目标函数 列出约束条件 建立模型建立模型 步骤步骤 2 确定求解方法 确定求解方法 分析模型 根据数学模型的性质 选择优化求解方法 确定求解方法确定求解方法 步骤步骤 3 计算机求解 计算机求解 编程序 或使用数学计算软件 应用计算机求最优解 计算机求解计算机求解 步骤步骤 4 结果分析 结果分析 对算法的可行性 收敛性 通用性 时效性 稳定性 灵敏性和误差等等作 出评价 结果分析结果分析 2 最优化问题数学模型 最优化问题的求解与其数学模型的类型密切相关 因而我们有必要对最优 化问题的数学模型有所掌握 一般来说 最优化问题的常见数学模型有以下几 种 无约束最优化问题数学模型 由某实际问题设立变量 建立一个目标函数且无约束条件 这样的求函数 极值或最大值最小值问题 我们称为无约束最优化问题无约束最优化问题 其数学模型为 目标函数 min 21n xxxf 例如 求一元函数和二元函数的极值 xfy yxfz 又例如 求函数的极值和取 323121 2 3 2 2 2 1321 242643 xxxxxxxxxxxxf 得极值的点 有约束最优化问题数学模型 由某实际问题设立变量 建立一个目标函数和若干个约束条件 等式或不 等式 这样的求函数极值或最大值最小值问题 我们称为有约束最优化问题有约束最优化问题 其数学模型为 目标函数 min 21n xxxf 约束条件mixxxg ni 2 10 21 有约束最优化问题的例子 求函数在约束条件条件 n xxxxxxf 31321 下的最大值和取得最大值的点 nixxxx in 2 1 0 2008 31 线性规划问题数学模型 由某实际问题设立变量 建立一个目标函数和若干个约束条件 目标函数 和约束条件都是变量的线性函数 而且变量是非负的 这样的求函数最大值最 小值问题 我们称为线性最优化问题 简称为线性规划问题线性规划问题 其标准数学模型 为 目标函数 nnn xcxcxcxxxf 221121 min 约束条件 0 2 1 2211 i inimii x mibxaxaxa 矩阵形式 目标函数XCXf T min 约束条件 0 X BAX 其中 T n xxxX 21 T n cccC 21 T m bbbB 21 mnmm n n aaa aaa aaa A 21 22221 11211 在线性规划问题中 关于约束条件我们必须注意以下几个问题 注 1 非负约束条件 一般来说这是实际问题要求的需要 2 1 0nixi 如果约束条件为 我们作变量替换 如果约束条件为 ii dx 0 iii dxz 我们作变量替换 ii dx 0 iii xdz 注 2 在线性规划的标准数学模型中 约束条件为等式 如果约束条件不是等式 我们引入松驰变量 化不等式约束条件为等式约 束条件 情况 1 若约束条件为 引入松驰变量 inimii bxaxaxa 2211 0 2211 inimiii bxaxaxaz 原约束条件变为 iinimii bzxaxaxa 2211 情况 2 若约束条件为 引入松驰变量 inimii bxaxaxa 2211 0 2211 nimiiii xaxaxabz 原约束条件变为 iinimii bzxaxaxa 2211 在其它最优化问题中 我们也常常采取上述方法化不等式约束条件为等式 约束条件 实际问题中 我们经常遇到两类特殊的线性规划问题 一类是 所求变量 要求是非负整数 称为整数规划问题整数规划问题 另一类是所求变量要求只取或 称为01 0 1 规划问题规划问题 例如 整数规划问题 21 3minxxz 且为整数0 0 2853422 13 3 21 21 2 xx xx x ts 又例如 0 1 规划问题 321 523maxxxxz 10 64 3 44 22 321 32 21 321 321 或xxx xx xx xxx xxx ts 非线性规划问题数学模型 由某实际问题设立变量 建立一个目标函数和若干个约束条件 如果目标 函数或约束条件表达式中有变量的非线性函数 那么 这样的求函数最大值最 小值问题 我们称为非线性规划最优化问题 简称为非线性规划问题非线性规划问题 其数学 模型为 目标函数 min 21n xxxf 约束条件mixxxg ni 2 10 21 其中目标函数或约束条件中有变量的非线性函数 例如 非线性规划问题 yxyxf 2 1 min 0 02 2 1 yyxg yxyxg 上述最优化问题中 目标函数是非线性函数 故称为非线性规划问题 前面介绍的四种最优化数学模型都只有一个目标函数 称为单目标最优化 问题 简称为最优化问题 多目标最优化问题数学模型 由某实际问题设立变量 建立两个或多个目标函数和若干个约束条件 且 目标函数或约束条件是变量的函数 这样的求函数最大值最小值问题 我们称 为多目标最优化问题多目标最优化问题 其数学模型为 目标函数sixxxf ni 2 1 min 21 约束条件mixxxg ni 2 10 21 上述模型中有 个目标函数 个等式约束条件 sm 例如 生产商如何使得产值最大而且消耗资源最少问题 投资商如何使得 投资收益最大而且风险最小问题 等都是多目标最优化问题 2 经典最优化方法经典最优化方法 经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种 不 等式约束条件极值问题可以化为等式约束条件极值问题 经典的极值理论 首先 根据可微函数取极值的必要条件确定可能极值点 其次 根据函数取极值的充分条件判断是否取极值 是极大值 还是极小值 这种方法已经几百年的历史了 2 1 无约束条件极值 设元函数 求的极值和取得极值的点 这是n 21n xxxfXf Xf 一个无约束条件极值问题 经典的极值理论如下 定理定理 1 极值必要条件 极值必要条件 设元函数具有偏导数 则n 21n xxxfXf 在处取得极值的必要条件为 Xf XX ni x f XX i 2 10 定理在此不给出证明 读者可自己参看有关资料 注 1 对于一元函数上述定理当然成立 只是偏导数应为导数 注 2 定理只是在偏导数存在的前提下的必要条件 如果函数在某一点偏导数 不存在 那在这一点处仍然可能取得极值 注 3 如果函数在某一点偏导数存在 且偏导数都等于零 那么函数在这一点 处也不一定取得极值 例如 函数在点处偏导数不存在 但在这一点处函 232 yxyxf 0 0 数仍然取得极小值零 函数在点处偏导数存在 且偏导数 53 yxyxf 0 0 都等于零 但在这一点处函数不取极值 定理 1 的作用在于 求出函数的可能极值点 然后 我们再研究这些点是 否取得极值 对于许多实际问题来说 函数一定能够取得极大值或极小值 而函数的可 能极值点 满足必要条件的点 又只有一点 则这一点当然是函数取得极大值 或极小值的点 对于一般函数而言 我们怎样判定函数在某点是否取极值 是极大值 还 是极小值 我们有下面的极值的充分条件定理 定理定理 2 极值充分条件 极值充分条件 设元函数具有二阶偏导数 n 21n xxxfXf 则在处取得极值的充分条件为 Xf XX 1 ni x f XX i 3 20 2 黑塞矩阵在处正定或负定 2 2 2 2 1 2 2 2 2 2 2 12 2 1 2 21 2 2 1 2 nxn n n x f xx f xx f xx f x f xx f xx f xx f x f XX 3 黑塞矩阵在处正定时 函数取极小值 负定时 函数取极大 XX 值 本章内容简要讲解理论 注重实际应用 对于许多经典的定理都不进行证 明 读者可自己参看有关资料 例 1 求函数的极值 3221 2 3 2 2 2 1321 22462 xxxxxxxxxxf 解 1 根据极值存在的必要条件 确定可能取得极值的点 21 1 24xx x f 312 2 2212xxx x f 23 3 28xx x f 令 解得 0 321 x f x f x f 0 0 0 321 xxx 2 根据极值存在的充分条件 确定是否是极值点 0 0 0 321 xxx 计算 4 2 1 2 x f 12 2 2 2 x f 8 2 3 2 x f 2 21 2 xx f 0 31 2 xx f 2 32 2 xx f 函数的黑塞矩阵为 820 2122 024 0 0 0 2 f 因为 04 044 122 24 0320 820 2122 024 所以黑塞矩阵负定 故函数在处取得极大值 0 0 0 321 xxx0 0 0 0 f 2 2 等式约束条件极值 下面我们研究的是有若干个等式约束条件下 一个目标函数的极值问题 其数学模型为 目标函数 min 21n xxxf 约束条件mixxxgts ni 2 10 21 拉格朗日 拉格朗日 Lagrange 乘数法乘数法 1 令 21 1 21ni m i in xxxgxxxfL 称为上述问题的拉格朗日乘数函数 称为拉格朗日乘数 i 2 设和均可微 则得到方程组 21n xxxf 21ni xxxg nixxxg L nj x g x f x L ni i m i j i i jj 2 10 2 10 21 1 3 若是上述方程组的解 则点可能 2121mn xxx 21n xxx 为该问题的最优点 拉格朗日 Lagrange 乘数法的本质是 将求有约束条件极值问题转化为求 无条件极值问题 所求得的点 即是取得极值的必要条件点 拉格朗日乘数法没有解决极值的存在性问题 但是 如果拉格朗日乘数函数 具有二阶连续偏导数 我们也可以应用黑塞矩阵来判定函数是否取得极值 在具体问题中 点是否为最优点通常可由问题的实际意义决定 21n xxx 例 2 求表面积为定值 而体积为最大的长方体的体积 2 a 解 设长方体的三棱长为 体积为 zyx V 建立数学模型如下 xyzV max 0 0 0 222 2 zyx ayzxzxy ts 构造拉格朗日乘数函数 则有 222 2 axzyzxyxyzzyxL 0 2 0 2 0 2 yxxy z L zxxz y L zyyz x L 解得 为所求 azyx 6 6 3 36 6 maxaV 2 3 不等式约束条件极值 对于不等式约束条件极值问题 目标函数 min 21n xxxf 约束条件mixxxgts ni 2 10 21 我们有与拉格朗日乘数法密切相关的方法库恩 图克定理 定理定理 3 库恩 库恩 图克定理 图克定理 对于上述不等式约束条件极值问题 设 和均可微 令 21n xxxf 21ni xxxg 21 1 21ni m i in xxxgxxxfL 假设存在 则在最优点处 必满足下述条件 i XX 21n xxx 1 m i j i i jj nj x g x f x L 1 2 10 2 mixxxg ni 2 10 21 3 mixxxg nii 2 10 21 4 0 i 根据库恩 图克定理我们可以求解许多不等式约束条件极值问题 值得注意 的是应用库恩 图克定理求解不等式约束条件极值问题 定理并没有解决最优 解的存在性问题 因此 我们必须另行判断 例 3 求解最优化问题 最优解存在 yxyxf 2 1 min 0 02 2 1 yyxg yxyxg 解 构造函数 2 1 21 2 yyxyxzyxL 根据库恩 图克定理则有 0 0 0 0 2 01 0 1 2 21 2 1 21 1 y yx y L x x L 解得 所求最优解为 最优值为 1 0 0 1 21 yx 0 1 yx0 3 线性规划线性规划 3 1 线性规划 设线性规划标准数学模型为 目标函数 nnn xcxcxcxxxf 221121 min 约束条件 nix mibxaxaxa ts i inimii 2 10 2 1 2211 矩阵形式 目标函数XCXf T min 约束条件 0 X BAX 其中 T n xxxX 21 T n cccC 21 T m bbbB 21 线性规划问题的求解有一整套理论体系 一般来说 应用单纯形法求解 此 方法尽管比较复杂 然而在计算机上实现并不困难 解线性规划问题的单纯形 法已在许多数学计算软件中实现 我们求解线性规划问题可根据需要 应用数 学计算软件求解即可 在此 我们不系统研究其理论 只是简单介绍线性规划 的穷举法和单纯形法的基本思想 3 2 线性规划的穷举法 1 穷举法基本原理和步骤 步骤步骤 1 1 将线性规划问题化成矩阵的标准形式 设系数矩阵的秩 则mAR 对应线性方程组的基础解系自由变量的个数为个 mn 步骤步骤 2 2 穷举法求解 令 解得对应线性方程组一组解0 21 mniii xxx 为 对应目标函数值为 21n xxx in fxxxf 21 从个变量中选个作为自由变量 令它们的值为 0 可得到nxmn 组解 mn n m n CC 步骤步骤 3 3 确定最优解 如果最优解存在 则上述求解得到的对应个目 mn n m n CC 标函数值中 最小者 或最大者 即为所求最小 或最大 最优值 对应的解为 最优解 步骤步骤 4 4 证明解为最优解 将最优解对应的自由变量看成参数 解对应线性方程组得 21 mn ttt nitbtbtbbx mnmniiiii 2 1 22110 将对应线性方程组解nitbtbtbbx mnmniiiii 2 1 22110 代入目标函数得 22110mnmn tdtdtdff 如果 则所求为最小值最优解 否则 线性规划问题无nidi 2 1 0 最小值最优解 如果 则所求为最大值最优解 否则 线性规划问题无nidi 2 1 0 最大值最优解 例 1 目标函数 321 32 maxxxxXf 5 4 3 2 1 0 4 102 5 52 421 31 ix xx xxx xx ts i 解 约束条件的增广矩阵为 10010 01021 00101 A3 AR 令 解得 0 21 xx5 4 10 5 0 0 XfX 令 无解 0 31 xx 令 解得 不满足非负条件 舍去 0 41 xx 1 0 5 5 0 X 令 解得 0 51 xx17 0 2 5 4 0 XfX 令 解得 0 32 xx10 4 5 0 0 5 XfX 令 解得 不满足非负条件 舍去 0 42 xx 4 0 5 0 10 X 令 无解 0 52 xx 令0 43 xx 解得 2 35 2 3 0 0 2 5 5 XfX 令 解得 不满足非负条件 舍去 0 53 xx 0 3 0 4 5 X 令 解得 0 54 xx19 0 0 3 4 2 XfX 所以 最优解为 19 max Xf 0 0 3 4 2 X 证明 令解得 sxtx 54 目标函数 5 1 0 23 4 22 3 2 1 ix stx sx stx i stXf 19 因为非负 所以 故最优解存在 sxtx 54 19 max Xf 2 单纯形法基本原理和步骤 将线性规划问题化成矩阵的标准形式 设系数矩阵的秩 则对应mAR 线性方程组的基础解系的个数为个 即有个自由参数变量 mn mn 选取个非基变量基变量 自由参数变量 不妨假设为 mn nmjxj 1 解得线性规划问题的典式典式 njx mixff mixx j n mj jj n mj jijii 2 10 2 1 min 2 1 1 0 1 定理定理 1 如果线性规划问题的上述典式中所有 nmj j 1 0 则为最优解 0 0 21 m X 定理定理 2 如果线性规划问题的上述典式中存在某个 且对应0 km 则线性规划问题无最优解 mi kmi 2 1 0 由定理 1 和定理 2 知 如果我们选择适当的个非基变量 就可以根据mn 所求得的典式判断最优解的存在与否 从而求解该线性规划问题 单纯形法的思想是 选择适当的基变换 进基和退基 不断地变换典式 使得典式中目标函数值不断下降 从而求得最优解 其核心为如何选择进基和 退基 进基规则和退基规则 进基规则进基规则 正检验数最小下标规则 即选取 由此确 0 min j js 定为进基 s x 退基规则退基规则 选取这样的下标 表示第 个基变量的下标 r J i Ji 0 min is is i 0 min is is i ir JJ 由此确定离基 r J x 单纯形法的基本步骤 步骤 1 化线性规划问题为标准形式 步骤 2 确定基变量 求得基本可行解和典式 是否满足最优解定理或最优解不存在定理的条件 判断最优解的情况 步骤 3 根据进基规则和退基规则 选择进基和退基 进行基变换 求得对应 典 式 重复进行基变换 直到求出最优解或判断出无最优解为止 例 2 解线性规划问题 21 2minxxf 5 4 3 2 1 0 2126 0 5 521 421 321 ix xxx xxx xxx ts i 解 1 约束条件的增广矩阵为 10026 01011 00111 A3 AR 所以非基变量个数为两个 2 选取作为非基变量 作为基变量 解得典式为 21 x x 543 xxx 5 1 0 2min 2621 5 21 215 214 213 ix xxf xxx xxx xxx i 不满足最优解定理和最优解不存在定理的条件 故必须进行基变换 3 进行基变换 选取进基 01 02 21 根据得为进基 0 min j js 1 x 选取退基 6 21 6 21 1 5 min 根据 得为离基 0 min is is i 0 min is is i ir JJ 5 x 进行基变换 求新基的典式 5 1 0 3 1 3 1 7min 6 1 3 1 2 7 6 1 3 4 2 7 6 1 3 2 2 3 52 521 524 523 ix xxf xxx xxx xxx i 判断 不满足最优解定理和最优解不存在定理的条件 故继续进行基变换 4 继续进行基变换 选取进基 根据得为进基 0 3 1 2 0 min j js 2 x 选取退基 4 9 2 21 8 21 4 9 min 根据 得为离基 0 min is is i 0 min is is i ir JJ 3 x 进行基变换 求新基的典式 5 1 0 4 1 2 1 4 31 min 4 1 2 1 4 11 2 1 2 2 1 4 1 2 3 4 9 53 531 534 532 ix xxf xxx xxx xxx i 满足最优解定理的条件 根据定理最优解为 4 31 min 0 2 1 0 4 9 4 11 fX 3 2 整数规划 设纯整数线性规划数学模型为 目标函数 nnn xcxcxcxxxf 221121 min 约束条件 nixx mibxaxaxa ts ii inimii 2 1 0 2 1 2211 为整数 这一类问题与一般线性规划比较起来 似乎是变简单了 但实际上恰恰相反 由于解集是一些离散的整数点集 使得单纯形法失去了应用的基础 求解变得 困难而复杂 整数线性规划目前还缺乏统一的解法 这里只介绍分枝定界法 它是目前求解纯整数线性规划和混合整数线性规划最常用的方法 计算机求解 整数线性规划的大多数程序也是以它为基础的 分枝定界法 考虑上述纯整数线性规划问题 1 解对应线性规划问题 目标函数 nnn xcxcxcxxxf 221121 min 约束条件 nix mibxaxaxa ts i inimii 2 10 2 1 2211 若无最优解 则原纯整数线性规划问题无最优解 若有最优解 最优点 目标函数最优值 21n xxx 210n xxxfz 若最优点全为整数 则为原纯整数线性规划问题的最优解 21n xxx 若最优点不全为整数 则进行下一步 21n xxx 2 定界和分枝 定界 定界 00210 minmzxxxfM n 其中取原纯整数线性规划问题中 满足约束条件的某一整数可行解所对 0 M 应的目标函数值 原纯整数线性规划问题的最优解必须满足定界条件 分枝 分枝 选取中一个不为整数所对应的分枝 21n xxx k x 1 R nix mibxaxaxa xx i inimii kk 2 10 2 1 2211 2 R nix mibxaxaxa xx i inimii kk 2 10 2 1 2211 和称为对应线性规划问题的两枝 也是两个新线性规划问题的约束条 1 R 2 R 件 显然 原纯整数线性规划问题的最优解满足或 1 R 2 R 3 对和进行剪枝和分枝 1 R 2 R 解对应的线性规划问题 对其进行剪枝和分枝 1 R 若无最优解 则原纯整数线性规划问题在内无最优解 不需要对该区域 1 R 继续讨论 剪枝剪枝 若有最优解 最优点 目标函数的最优值 21n xxx 211n xxxfz 若 则原纯整数线性规划问题在内无最优解 0211 Mxxxfz n 1 R 不需要对该区域继续讨论 剪枝剪枝 若最优点全为整数 则可能为原纯整数线性规划问题的最优 21n xxx 解 定界 定界 记 则 本 0211 MxxxfM n 0211 minmxxxfM n 分枝求解结束 若最优点不全为整数 对继续进行分枝 21n xxx 1 R 完全类似 解对应线性规划问题 对其进行剪枝和分枝 2 R 依此类推 对所有分枝进行求解 剪枝 分枝 定界 直至求得最优解 4 最优解的确定 若某 则为最优解 求解结束 0 mMk 若所有分枝求解结束 则最后的上界即为最优解 k M 例 3 应用分枝定界法 求解整数线性规划问题 21 3minxxz 且为整数0 0 2853422 13 3 21 21 2 xx xx x ts 解 设原整数线性规划问题目标函数的最优值为 z 1 求解线性规划问题 21 3minxxz 0 0 2853422 13 3 21 21 2 xx xx x ts 得最优解为 13 3 12 8 21 xx51 17min z 记约束区域为 0 0 2853422 13 3 21 21 2 xx xx x R 2 对进行分枝 选取最优解中不是整数的变量 例如 将分成两个子R 1 xR 区域 21 R R 0 0 2853422 13 3 9 21 21 2 1 1 xx xx x x R 0 0 2853422 13 3 8 21 21 2 1 2 xx xx x x R 3 定界 确定最优值的上下界 由 1 中求得的最优值知 而 z51 17 z 的上界可由内的任意一个可行解确定 例如 即为一个可 zR4 7 21 xx 行解 故 从而 19 z19 51 17 z 4 在内求最优解 得 1 R13 3 9 21 xx39 18min z 5 在内求最优解 得 2 R21 3 8 21 xx62 17min z 6 因为内最优解不全是整数 因而必须继续对分枝 1 R 1 R 0 0 2853422 13 3 9 4 21 21 2 1 2 11 xx xx x x x R 0 0 2853422 13 3 9 3 21 21 2 1 2 12 xx xx x x x R 7 显然内无解 剪枝 12 R 在内求最优解 得 为整数可行解 11 R4 9 21 xx21min z 但因 而 故剪枝 19 51 17 z1921 8 因为内最优解不全是整数 因而必须继续对分枝 2 R 2 R 0 0 2853422 13 3 8 4 21 21 2 1 2 21 xx xx x x x R 0 0 2853422 13 3 8 3 21 21 2 1 2 22 xx xx x x x R 9 显然内无解 剪枝 22 R 在内求最优解 得 21 R4 77 6 21 xx77 18min z 10 因为内最优解不全是整数 因而必须继续对分枝 21 R 21 R 0 0 2853422 13 3 8 4 7 21 21 2 1 2 1 211 xx xx x x x x R 0 0 2853422 13 3 8 4 6 21 21 2 1 2 1 212 xx xx x x x x R 11 在内求最优解 得 212 R5 4 6 21 xx 5 19min z 因大于的上界 故剪枝 5 19min z z 12 在内求最优解 得 211 R4 7 21 xx19min z 所求原整数规划问题的最优解为 4 7 21 xx19min z 4 最优化问题数值算法最优化问题数值算法 最优化问题的数值算法很多 常用的算法多为搜索法 本节只介绍搜索法 的基本思想 无约束最优化问题的最速下降法 梯度法 和有约束最优化问题 的罚函数法 4 1 搜索算法 考虑无约束最优化问题 min 21n xxxf 我们已经讨论了这类问题的最优解条件 这必须用到函数的解析性质 我 们的方法是 先利用必要条件求出平稳点 再应用充分条件判断是否是极值点 但是 我们必须求解一个个变量个方程的方程组 并且常常是非线性的 nn 这只有在特殊的情况下 才能求出它的精确解 在一般情况下 都不能用解析 法求得精确解 更何况许多实际问题中 函数的解析表达式很难得到 因此 我们必须寻求一些切合实际问题的行之有效的数值解法 搜索算法搜索算法就是我们常 用的方法 1 搜索算法的基本思想 搜索算法的基本思想 假定目标函数极小值问题 首先 确定 Xf 目标函数的初始点 然后 按照一定规则产生一个点列 这种规 Xf 0 X k X 则称为算法 规则必须满足 1 点列收敛 2 点列收敛到目标 k X k X 函数的极小值点 Xf 2 搜索算法的基本步骤 搜索算法的基本步骤 选定初始点 越接近最优点越好 允许误差 令 0 X0 0 k 假定已得非最优点 则选取一个搜索方向 满足 k X k S 目标函数下降 或 Xf0 kk SXgradf 选定搜索步长 满足 0 k kkkk SXX 1 1kkkkk XfSXfXf 判断是否是最优点或是满足要求的近似解 1 k X 假定给定精度要求为 常用确定求近似解搜索结束的方法有 0 梯度模确定法 1k Xgradf 目标函数差值绝对误差法 1kk XfXf 相邻搜索点绝对误差法 1kk XX 如果满足给定精度要求 则搜索完成 近似最优点为 1 k X 1 k XX 如果不满足给定精度要求 令返回 2 继续搜索 1 k X1 kk 注意 1 我们的搜索算法一般得到的都是局部最优解 注意 2 确定求近似解搜索结束的方法还有 目标函数差值相对误差法 1 k kk Xf XfXf 相邻搜索点相对误差法 1 k kk X XX 3 搜索算法的关键因素 搜索算法的关键因素 从搜索算法的基本步骤中 我们知道 搜索算 法的关键因素为 一是搜索方向 二是搜索步长 搜索方向的选择 一般考虑既要使它尽可能的指向极小值点 又要不至于 花费太多的计算量 搜索步长的选择 既要确保目标函数的下降性质 又要考虑近似解的精度 要求 还要考虑算法的计算量 问题十分复杂 常用方法有 固定步长法 最 优步长法和变步长法 固定步长法 简单算法 是选取为固定值 方法简单 但是有时不0 k 能保证目标函数的下降性质 最优步长法 一维搜索算法 是选取使得 k min kkkkk SXfSXf 这是一个关于单变量的函数求极小值问题 这样确定的步长称为最优步 长 变步长法 可接受点算法 是任意选取 只要使得即可 k 1kk XfXf 这种选取步长的方法 确保了目标函数的下降性质 尽管每次选取的步长不是 最 优的 但实践证明 方法能达到更好的数值效果 总之 当搜索方向确定以后 步长就是决定最优化算法好坏的重要因素 因此 我们必须特别注重步长的选取问题 4 搜索算法的收敛性 搜索算法的收敛性 搜索算法的收敛性是指 由某算法得到的点列 能够在有限步骤内收敛到目标函数的最优点或能够在有限步骤内达 k X Xf 到满足精度要求的目标函数的最优点的近似值 显然 只有具有收敛性质 Xf 的算法才有意义 搜索算法的收敛速度 搜索算法的收敛速度 作为一个好的算法 还必须要求它以较快的速度收 敛于最优解 阶收敛定义阶收敛定义 对于收敛于最优解的序列 若存在与无关的数 X k Xk 和 当从某个开始时 有 01 k 0 k 成立 1 XXXX kk 则称序列收敛的阶为 或称阶收敛 k X 当时 称迭代序列为线性收敛 当时 称迭代序列1 k X21 为超线性收敛 当时 称迭代序列为二阶收敛 k X2 k X 一般来说 线性收敛是比较慢的 而二阶收敛则是很快的 超线性收敛介 于二者之间 如果一个算法具有超线性以上的收敛速度 我们就认为是一个好 的算法了 4 2 无约束最优化问题的梯度法 无约束最优化问题 min 21n xxxf 的计算方法很多 无约束最优化问题的计算方法分为两大类 一类是解析法 包括经典最优化方法 最速下降法 梯度法 共轭梯度法 牛顿法和变尺度法 等 另一类是直接法 包括坐标轮换法 步长加速法 方向加速法和单纯形法 等 所谓解析法就是在方法的计算过程中 应用到了函数的解析性质 可导性 质等 所谓直接法就是在方法的计算过程中 仅仅涉及目标函数值的计算 而 不涉及函数导数等解析性质 我们在这里只介绍最速下降法 梯度法 最速下降法理论根据 早在 1847 年 法国著名数学家 Cauchy 就曾提出 从 任意给定点出发 函数沿哪个方向下降最快的问题 这个问题已从理论上解决 了 即沿着函数在该点的负梯度方向前进时 函数下降最快 这就是最速下降 法的理论根据 最速下降法的搜索步骤 搜索步骤 步骤 1 选定初始点 越接近最优点越好 允许误差 令 0 X0 0 k 步骤 2 假定已得非最优点 计算梯度 k X k Xgradf 选取搜索方向 kk XgradfS 步骤 3 选定搜索步长 满足 0 k kkkk SXX 1 min 0 kkkkk SXfSXf 步骤 4 判断是否是最优点或是满足要求的近似解 1 k X 根据精度要求 检验是否满足收敛性判断准则 或或 1k Xgradf 1kk XfXf 1kk XX 如果满足给定精度要求 则搜索完成 近似最优点为 1 k X 1 k XX 如果不满足给定精度要求 令返回 2 继续搜索 1 k X1 kk 例 1 应用最速下降法求解 2 2 2 1 25 minxxXf 解 1 选定初始点 允许误差 置 2 2 0 X2 0 0 k 收敛判断准则 1kk XfXf 2 计算梯度 选取搜索方向 k Xgradf kk XgradfS k XXk xxXgradf 50 2 21 k XXk xxS 50 2 21 第一点搜索计算 100 4 0 Xgradf 100 4 0 S 3 选定搜索步长 满足 0 k kkkk SXX 1 min 0 kkkkk SXfSXf 第一点搜索计算 求最优步长 22 00 0 1002 25 42 min SXf 解得 02 0 0 4 判断是否是最优点或是满足要求的近似解 1 k X 第一点搜索计算 0 92 1 1 X 验证收敛判断准则 不满足 继续搜索 02 0 31 100 01 XfXf 依次类推 直到搜索到最优解或满足精度要求为止 搜索计算列表如下 搜索步长 k 搜索方向 kS 搜索点 k X函数值 k Xf 2 2 0 X 104 02 0 0 100 4 0 S 0 92 1 1 X 69 3 5 0 1 0 84 3 1 S 0 0 2 X 0 0 0 2 S 为最优解 0 0 2 X 4 3 罚函数法 对于约束最优化问题也有许多种方法 本段只介绍把约束最优化问题转化为 无约束最优化问题的一种求解方法 罚函数法 分为等式约束最优化问题和 不等式约束最优化问题两种情况讨论 1 等式约束最优化问题的罚函数法 首先 考虑等式约束最优化问题 minXf miXgts i 2 10 假定上述等式约束最优化问题的最优解存在 若记 2 1 0 n i RXmiXgXD 构造辅助函数 罚函数罚函数 m i i XgMXfMXT 1 2 其中 罚因子罚因子 是一个充分大的正数 0 M 定理定理 1 若对于某确定数 无约束最优化问题0 M m i i XgMXfMXT 1 2 min 的最优解 则必为原等式约束最优化问题的最优解 DX X 证明 设无约束最优化问题 m i i XgMXfMXT 1 2 min 的最优解 则有 DX miXgi 2 10 而当时 DX XfMXT 所以 min minXfMXTMXTXf 即为原等式约束最优化问题的最优解 X 定理定理 2 设和均为连续函数 XfmiXgi 2 1 0 若对于任意正数 无约束最优化问题0 M m i i XgMXfMXT 1 2 min 的最优解 且 DMX limXMX M 则为原等式约束最优化问题的最优解 limXMX M 定理 2 的证明请参看有关参考资料 根据定理 1 和定理 2 我们就可以将通过构造罚函数的方法化为无约束最 优化问题求解 这种方法称为罚函数法罚函数法 罚函数法的步骤 等式约束最优化问题罚函数法 步骤 1 构造罚函数 m i i XgMXfMXT 1 2 选定 允许误差 令 0 1 M0 1 k 步骤 2 求无约束问题 的最优解 min k MXT k X 步骤 3 判断是否是最优点或是满足要求的近似解 k X 根据精度要求 检验是否满足收敛性判断准则 miXg ki 2 1 或 m i ki Xg 1 2 如果满足收敛性判断准则 则 结束搜索 k XX 否则 令 取 返回 2 继续搜索 1 kk0 1 kk MM 下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法 例 2 应用罚函数法求解非线性规划问题 2 2 2 1 minxxXf 01 2 xts 解 构造罚函数 2 2 2 2 2 1 1 xMxxMXT kk 求罚函数的最优解 应用解析法 1 1 2x x T 1 22 22 2 xMx x T k 令上述两式等于零 解得 k k M M xx 1 0 21 令得 为所求最优解 k M1 0 21 xx 2 不等式约束最优化问题的罚函数法 对于 不等式约束最优化问题 minXf miXgts i 2 10 假定上述不等式约束最优化问题的最优解存在 由于不等式约束条件等价于等式约束条件miXgi 2 1 0 miXgi 2 1 0 0min 因而 上述不等式约束最优化问题可以转化为问题 minXf miXgts i 2 10 0min 类似问题 1 构造罚函数 m i i XgMXfMXT 1 2 0 min 则将上述等式约束最优化问题的求解转化为下面无约束最优化问题的求解 m i i XgMXfMXT 1 2 0 min min 定理定理 3 若对于某确定数 无约束最优化问题0 M m i i XgMXfMXT 1 2 0 min min 的最优解 则必为原不等式约束最优化问题的最优解 DX X 其中 2 1 0 n i RXmiXgXD 定理定理 4 设 1 和均为连续函数 XfmiXgi 2 1 0 2 原不等式约束最优化问题的最优解存在 X 3 数列满足且 k M k MMM 21 0 k k Mlim 4 对任意 问题的最优解都存0 k M minMXT kk MXX 在 且有界 5 点列存在极限点 k X 则 点列的极限点是原不等式约束最优化问题的最优解 k X 罚函数法的步骤 不等式约束最优化问题罚函数法 步骤 1 构造罚函数 m i i XgMXfMXT 1 2 0 min 选定 允许误差 令 0 1 M0 1 k 步骤 2 求无约束问题 的最优解 min k MXT k X 步骤 3 判断是否是最优点或是满足要求的近似解 k X 根据精度要求 检验是否满足收敛性判断准则 miXg ki 2 1 或 m i ki Xg 1 2 如果满足收敛性判断准则 则 结束搜索 k XX 否则 令 取 返回 2 继续搜索 1 kk0 1 kk MM 例 3 应用罚函数法求解非线性规划问题 21 minxxXf 0 0 12 2 2 11 xXg xxXg ts 解 构造罚函数 m i i XgMXfMXT 1 2 0 min 0 min 0 min 2 1 2 2 2 121 xxxMxxMXT kk 求的极小值点 k MXT 0min 22 0 min 21 121 3 1 1 xxxxM x T k 0 min 21 2 2 1 2 xxM x T k 当时 显然上两式不能同时等于零 0 0 12 2 1 xxx或 所以 此时不存在极小值点 k MXT 当时 有0 0 12 2 1 xxx 121 3 1 1 2 22 21xMxxxM x T kk 21 2 2 1 2 xxM x T k 令上面两式等于零 0 1 x T 0 2 x T 解得的极小值点为 k MXT 2 1 22 1 22 1 2 kkk k MMM X 当取不同值时 可得到相应的值 计算如下表 k M k X k M 1101001000 k M 1 x 0 25 0 04545 0 004950 0 00049950 2 x 0 4375 0 1415 0 004975 0 00049980 根据定理得 原问题的极小值点为 极小值为 0 0 X0 Xf 5 多目标优化问题多目标优化问题 在许多实际的最优化问题中 常常遇到目标函数是几个的情况 这一类问 题我们称之为多目标优化问题 例如 投资方向选择问题 我们不仅要求投资的收益最大 而且要求投资 的风险最小 再例如 购买商品问题 我们既要考虑商品的价格 又要考虑商品的质量 甚至还要考虑商品的性能等等 所谓多目标优化问题是指 目标函数是两个或两个以上的最优化问题 其 数学模型为 目标函数sixxxf ni 2 1 min 21 约束条件mixxxg ni 2 10 21 例 1 求解多目标优化问题 和 2 minxymin 1 1 y x ts 解 易求时 1 0 yx0min 2 x1min y 例 2 求解多目标优化问题 和 2 maxxymin 1 1 y x ts 解 显然 无最优解 5 1 多目标优化问题的解 多目标优化问题解的存在性极其复杂 这是由多目标优化问题的目标函数 多个性和目标函数相互之间的复杂性质决定的 由于目标函数在很多情况下不 可能同时达到最大值或最小值 因而 多目标最优化问题很少有最优解 而实 际问题又要求我们做出决择 求得一个比较好的解 什么样的解才是我们需要 的解呢 对于同一个问题不同的要求导致不同的求解标准 从而就会得到不同 的求解结果 为此 我们给出多目标最优化问题的条件最优解概念 最优解 满足约束条件且使所有目标函数达到要求的最大值或最小值的点 称为多目标优化问题的最优解 可行解 满足多目标优