优化决策理论与方法(ppt 90页).ppt

决策理论与方法 2 优化决策理论与方法 合肥工业大学管理学院2020年3月14日 决策理论与方法 优化决策理论与方法 确定性决策 确定性决策 指未来状态是确定的 即只有一种状态 一类决策问题 每一个行动方案对应着一个确定的结果值 此时决策函数仅依赖于决策变量 特点 状态是确定的 决策问题变为优化问题 决策的已知变量 决策变量及其取值范围解决问题的主要理论方法 最优化理论与方法注 最优化理论与方法 数学规划 也可以求解不确定性决策问题 随机性决策问题 决策理论与方法 优化决策理论与方法 确定性决策 优化决策方法的问题求解过程辨识目标C 确定优化的标准 如 利润 时间 能量等确定影响决策目标的决策变量x 形成目标函数C f x 明确决策变量的取值范围 形成约束函数设计求解算法 寻找决策目标在决策变量所受限制的范围内的极小化或极大化 最优化问题的一般形式为 决策理论与方法 优化决策理论与方法 优化问题分类 可行点与可行域 满足约束条件的x称为可行点 所有可行点的集合称为可行域 记为S 约束优化与无约束优化 当S Rn时 称为约束优化 当S Rn时 称为无约束优化 多目标优化 若f是多个目标函数构成的一个向量值函数 则称为多目标规划 线性规划与非线性规划 当f g h均为线性函数时称为线性规划 否则称为非线性规划 决策理论与方法 优化决策理论与方法 优化问题分类 整数规划 当决策变量的取值均为整数时称为整数规划 若某些变量取值为整数 而另一些变量取值为实数 则成为混合整数规划 动态规划与多层规划 若决策是分成多个阶段完成的 前后阶段之间相互影响 则称为动态规划 若决策是分成多个层次完成的 不同层次之间相互影响 则称为多层规划 决策理论与方法 优化决策理论与方法 优化决策理论与方法 1 线性规划2 非线性规划 约束和非约束 3 多目标规划4 组合优化与整数规划 决策理论与方法 优化决策理论与方法 线性规划 管理实例 食谱问题 假设市场上有n种不同的食物 第j种食物的单价为cj 人体正常活动过程中需要m种基本的营养成分 且每人每天至少需要摄入第i种营养成分bi个单位 已知第j种食物中包含第i种营养成分的量为aij个单位 问在满足人体基本营养需求的前提下什么样的配食方案最经济 设食谱中包含第j种食物的量为xj 则 决策理论与方法 优化决策理论与方法 线性规划 标准型 决策理论与方法 优化决策理论与方法 线性规划 单纯形算法 解空间分析可行域分析 n维空间 第一象限 m个超平面 最优解分析 在端点 或称为极点 极点向量中 至少有n m个0分量 处取极值 单纯形算法的基本思想从某个极点开始获得一个可行解 判断该可行解是不是目标解 若是 算法结束 否则寻找下一个极点 确定入基变量和出基变量 直至找到目标解 决策理论与方法 优化决策理论与方法 线性规划 内点算法 1972年 V Klee和G L Minty指出Dantzig的单纯形算法的迭代次数为O 2n 是一个指数时间算法 不是优良算法 那么是否存在求解线性规划问题的多项式时间算法 1984年 N Karmarkar提出了一种投影尺度算法 其计算效果能够同单纯形法相比较 掀起了线性规划内点算法的热潮 决策理论与方法 优化决策理论与方法 线性规划 内点算法 内点算法的思想已知线性规划问题的可行域是一个多面体 最优点在多面体的某个极点取到 在给定初始可行解后 沿着什么样的路径到达最优解呢 单纯形法是从某个基可行解开始 沿着多面体的边移动最终找到最优解 内点算法的思想是从可行域内的任意一点 任一可行解 出发 穿越可行域的内部达到最优解 N Karmarkar的投影尺度算法就是一种典型的内点算法 决策理论与方法 优化决策理论与方法 线性规划 内点算法 可行域 内点 初始基可行解 基可行解 目标函数 目标函数最速下降方向 决策理论与方法 优化决策理论与方法 线性规划 内点算法 投影尺度算法如何穿过可行域的内部快速达到最优解呢 Karmarkar发现 1 如果一个内点位于可行域 多胞形 多面体 的中心 那么目标函数的最速下降方向是比较好的方向 2 存在一个适当的变换 能够将可行域中给定的内点置于变换后的可行域的中心 基于这两点 Karmarkar构造了一种称为投影尺度算法的内点算法 决策理论与方法 优化决策理论与方法 线性规划 内点算法 X空间 内点 目标函数 目标函数最速下降方向 Y1空间 中心点 投影尺度变换1 目标函数最速下降方向 Y2空间 中心点 投影尺度变换2 决策理论与方法 优化决策理论与方法 线性规划 Matlab函数应用 OptimizationToolBoxMinfTxS t A x bAeq x beqlb x ub其中 f x b beq lb和ub均为向量 A和Aeq为矩阵 x fval linprog f A b Aeq beq lb ub 决策理论与方法 优化决策理论与方法 线性规划 Matlab函数应用 例 maxz x1 2x2S t x1 x2 402x1 x2 60 x1 0 x2 0解 将max变为min min z x1 2x2则 f 1 2 b 40 60 lb zeros 2 1 A 11 21 x fval linprog f A b lb x 0 40 fval 80 x1 x2 x1 x2 40 2x1 x2 60 Z x1 2x2 决策理论与方法 优化决策理论与方法 优化决策理论与方法 1 线性规划2 非线性规划 约束和非约束 3 多目标规划4 组合优化与整数规划 决策理论与方法 优化决策理论与方法 无约束非线性规划 标准型 Minf x x Rn其中f Rn R是一个非线性连续函数 对于任意点x Rn 它是函数f的最小点 或局部极小点 吗 例如 minf x ex1 4x12 2x22 4x1x2 2x2 1 决策理论与方法 优化决策理论与方法 无约束非线性规划 极小值存在条件 必要条件 设x 是f x 的局部极小点 则当f x 在x 点可微时 梯度 f x 0 当f x 在x 点二阶可微时 Hesse矩阵 2f x 是半正定的 即 d Rn 有dT 2f x d 0 充分条件 设f x 在x 点二阶可微 若梯度 f x 0且Hesse矩阵 2f x 是正定的 则x 是f x 的一个严格局部极小点 充要条件 设f x 是可微凸函数 则x 是f x 的全局最小点 当且仅当梯度 f x 0 决策理论与方法 优化决策理论与方法 无约束非线性规划 复习 梯度矩阵 Hesse矩阵 Taylor展开 决策理论与方法 优化决策理论与方法 无约束非线性规划 牛顿法 基本思想 在一个点附近 用目标函数f x 的二阶Taylor多项式近似f x 并用该Taylor多项式的最小点近似f x 的最小点 如果近似误差比较大 那么可在近似最小点附近重新构造f x 的二阶Taylor多项式 迭代 据此寻找新的近似最小点 重复以上过程直到求得满足一定精度要求的迭代点 决策理论与方法 优化决策理论与方法 无约束非线性规划 牛顿法 设xk是第k次迭代结果 记gk g xk f xk Gk G xk 2f xk 则f x f xk p k p f xk g xk Tp 1 2pTG xk p由于 k p 的最小点满足g xk G xk p 0 得p x xk G 1 xk g xk 因此 可近似得到迭代关系 xk 1 xk G 1 xk g xk 决策理论与方法 优化决策理论与方法 无约束非线性规划 牛顿法 牛顿迭代法步骤初始化 给定一个初始点x0以及参数e 0 记k 0 收敛性检验 计算g xk 若 g xk e 则算法终止 否则计算G xk 迭代改进 计算新的迭代点xk 1 即xk 1 xk G 1 xk g xk k 1 k 返回收敛性检验 决策理论与方法 优化决策理论与方法 无约束非线性规划 准牛顿法 牛顿法算法的优点是收敛速度快 利用了Hesse矩阵 但使用Hesse矩阵的不足之处是计算量大 Hesse矩阵可能非正定等 准牛顿法 Quasi Newtonmethod 是对牛顿法的改进 目前被公认为是比较有效的无约束优化方法 基本思想 在迭代过程中只利用目标函数f x 和梯度g x 的信息 构造Hesse矩阵的近似矩阵 由此获得一个搜索方向 生产新的迭代点 具体内容请参考相关书籍 决策理论与方法 优化决策理论与方法 无约束非线性规划 Matlab函数应用 OptimizationToolBoxMinf x Matlab提供了两个求解无约束非线性规划的函数 x fval fminunc fun x0 x fval fminsearch fun x0 用法相似 算法内部的搜索策略不同 fun为f x 的函数形式 x0为初始解向量 决策理论与方法 优化决策理论与方法 无约束非线性规划 Matlab函数应用 用法创建一个matlab文件 如myfun mfunctionf myfun x f f x 然后调用fminunc或fminsearch并指定初始搜索点 x0 x1 x2 xn x fval fminunc myfun x0 或 x fval fminsearch myfun x0 决策理论与方法 优化决策理论与方法 无约束非线性规划 Matlab函数应用 例 minf x ex1 4x12 2x22 4x1x2 2x2 1 解 创建一个matlab文件 如myfun mfunctionf myfun x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 调用无约束非线性规划函数x0 1 1 Startingguessoptions optimset LargeScale off x fval fminunc myfun x0 options 或者 x fval fminsearch myfun x0 options 决策理论与方法 优化决策理论与方法 无约束非线性规划 Matlab函数应用 fminunc结果 x 0 5000 1 0000 fval 1 0983e 015iterations 8algorithm medium scale Quasi Newtonlinesearch fminsearch结果 x 0 5000 1 0000 fval 5 1425e 010iterations 46algorithm Nelder Meadsimplexdirectsearch 决策理论与方法 优化决策理论与方法 约束非线性规划 标准型 其中f x 是目标函数 gi x 和hj x 为约束函数 约束条件 S x gi x 0 hj x 0 为可行域 有约束非线性规划问题 COP 是指f x gi x hj x 至少有一个是非线性的 且I或 至少有一个为非空 决策理论与方法 优化决策理论与方法 约束非线性规划 几个概念 积极 active 约束 设x0是COP问题的一个可行解 则它必须满足所有约束条件 对于gi x0 0 或者等号成立 或者大于号成立 称等号成立的约束为积极约束 有效约束 此时 x0处于该约束条件形成的可行域边界上 称大于号成立的约束为非积极 inactive 约束 无效约束 此时 x0不在该约束条件形成的可行域边界上 显然所有hj x0 约束均是积极约束 记J j gj x0 0 hj x0 0 称为积极约束指标集 决策理论与方法 优化决策理论与方法 约束非线性规划 几个概念 可行方向 设x0为COP问题的任一可行解 对某一方向d来说 若 0 0使得对于任意 0 0 均有x0 d S 称d为x0的一个可行方向 显然若d满足dT gi x 0 dT hj x 0 则d一定是可行方向 可用一阶Taylor公式分析 下降方向 设x0 S 对某一方向d来说 若 0 0使得对于任意 0 0 均有f x0 d f x0 则称d为x0点的一个下降方向 由f x0 d f x0 f x0 Td o 可知 若d满足dT f x0 0 有f x0 d f x0 则d一定是下降方向 可行下降方向 若x0的某一方向d既是可行方向又是下降方向则称其为可行下降方向 这个方向就是我们从x0出发寻求最优解的搜索方向 决策理论与方法 优化决策理论与方法 约束非线性规划 几个概念 例 minf x x1 x2S t g x 1 x12 x22 0图描述了该问题的相关概念 决策理论与方法 优化决策理论与方法 约束非线性规划 极小值存在条件 一阶必要条件几何特征 若x 是COP问题的局部极小点且函数f x gi x hj x 在x 处可微 则dT f x 0 d为x 的任意可行方向 f x d f x f x Td o 代数特征 KKT定理 若x 是COP问题的局部极小点且函数f x gi x hj x 在x 处可微 则存在实数 i 0 i I j R j 使得 f x i gi x i j hj x j gi x i 0 i 0 i I若x 满足KKT条件 则称x 为COP问题的一个KKT点 i j称为x 处的拉格朗日乘子 决策理论与方法 优化决策理论与方法 约束非线性规划 极小值存在条件 一阶充分条件设x S 若函数f x gi x hj x 在x 处可微 且对于x 的任意可行方向d 有dT f x 0 则x 为COP问题的一个严格局部极小点 凸规划问题 设f x 为凸函数 gi x 为凹函数 hj x 为线性函数 对于x S 若函数f x gi x 在x 处可微 且KKT条件成立 则x 为COP问题的全局最小点 决策理论与方法 优化决策理论与方法 约束非线性规划 极小值存在条件 二阶必要条件设x 是COP问题的局部极小点且满足KKT条件 若函数f x gi x hj x 在x 处二阶可微 则必有 dT xx2L x d 0其中 L x f x g x T h x T g x h x 分别为由gi x 和hj x 构成的向量值函数 分别为对应于g x 和h x 的拉格朗日乘子向量 二阶充分条件设x 是COP问题的KKT点 分别为对应于g x 和h x 的拉格朗日乘子向量 且函数f x gi x hj x 在x 处二阶可微 若dT xx2L x d 0 则x 为COP问题的一个严格局部极小点 决策理论与方法 优化决策理论与方法 约束非线性规划 极小值存在条件 例 minf x x12 x22S t x1 x2 4x1 x2 0解 g1 x x1 x2 4 0 g2 x x1 0 g3 x x2 0 f x 2x1 2x2 T g1 x 1 1 T g2 x 1 0 T g3 x 0 1 T 得到 2x1 1 22x2 1 3又 x1 x2 4 1 0 x1 2 0 x2 3 0 i 0若 1 0 则x1 x2 0 与题意不符 若 1 0 则x1 x2 4 0 x1 0 x2 0 因此有 2 3 0 所以x1 x2 1 2 得x1 x2 2 x 2 2 T为该问题的唯一KKT点 根据凸规划充分条件知x 为全局最小点 决策理论与方法 优化决策理论与方法 约束非线性规划 可行方向法 上面例题介绍了通过求解KKT方程获得问题解的方法 但KKT方程并不总是很好求解 下面介绍几种约束优化的求解方法 可行方向法 序列无约束化法和SQP法 可行方向法的应用条件 要求所有约束均为线性约束 称为线性约束的优化问题 LCO 可行方向法的基本思想 当某个可行方向同时也是目标函数的下降方向时 沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值 决策理论与方法 优化决策理论与方法 约束非线性规划 可行方向法 x1 x2 决策理论与方法 优化决策理论与方法 约束非线性规划 可行方向法 LCO问题 Minf x S t aiTx bi i IajTx bj j 设x0是LCO的一个可行解 若d是可行域在x0点的可行方向 则d满足AI x0 d 0 I x0 i aiTx0 bi i I A d 0 设x0是LCO的一个可行解 若d是可行域在x0点的下降方向 则d满足dT f x0 0 决策理论与方法 优化决策理论与方法 约束非线性规划 可行方向法 Zoutendijk可行方向法 其核心思想是通过求解下列线性规划问题 在可行方向的某个范围内获得目标函数的最速下降方向 MindT f x0 S t AI x0 d 0 I x0 i aiTx0 bi i I A d 0 d 1可以证明 当x0取得KKT点时当且仅当dT f x0 的最优值为零 决策理论与方法 优化决策理论与方法 约束非线性规划 序列无约束化法 求解约束优化的一类重要方法是用一个无约束优化问题的序列逼近约束优化问题 通过无约束优化问题的最优解序列逼近约束优化问题的最优解 基本思想 将约束条件通过某种转换与目标函数合并形成一个无约束优化问题 这种转换隐含着某种惩罚 即x偏离约束条件越远 受到的惩罚越大 因此也将此类方法称为罚函数法 所形成的无约束优化函数成为罚函数 决策理论与方法 优化决策理论与方法 约束非线性规划 序列无约束化法 二次罚函数法 罚函数 其中 gi max 0 gi 称为罚参数 且当 0时 Q x 的极小值趋于f x 的极小值 决策理论与方法 优化决策理论与方法 约束非线性规划 序列无约束化法 例 minf x1 x2S t x1 x22 0解 对于 0 定义二次罚函数MinQ x x1 x2 2 1 x1 x22 2Q x1 1 x1 x22 0Q x2 1 2x2 x1 x22 0解得 x 1 4 1 2 T Q 1 4 2当 0时得 x 1 4 1 2 T f 1 4 决策理论与方法 优化决策理论与方法 约束非线性规划 序列无约束化法 对数障碍函数法 障碍函数 其中 称为障碍参数 且当 0时 P x 的极小值趋于f x 的极小值 该方法的适用性 COP问题仅包含不等式约束函数 且可行域存在内点 即S0 x g x 0 决策理论与方法 优化决策理论与方法 约束非线性规划 序列无约束化法 例 min f x 2 x 1 解 构造对数障碍函数P x x 2 ln x 1 P x 1 2 x 1 0 得x 1 2 P 1 2 ln2 当 0时得x 1 f 1 2 决策理论与方法 优化决策理论与方法 二次规划 标准型 若有约束非线性规划的目标函数是决策变量x的二次函数且所有约束均为线性约束 称此类非线性规划问题为二次规划 QuadraticProgramming QP 问题 其标准型为 决策理论与方法 优化决策理论与方法 二次规划 标准型 其中Q QT Rn n n阶对称方阵 以aiT i I 为行向量的矩阵记为AI RI n 以ajT j 为行向量的矩阵记为A R n 对应的向量记为bI b 若目标函数的Hesse矩阵Q是半正定 或正定 的 则QP问题为 严格 凸二次规划 CQP 我们仅讨论凸二次规划问题 因为非凸二次规划的Q存在负特征根 求解很困难 决策理论与方法 优化决策理论与方法 二次规划 极小点存在条件 充要条件可行点x 是QP问题的局部极小点当且仅当x 为一个KKT点且对于任意非零可行方向d 有dTQd 0 对于凸二次规划 x 为全局极小点当且仅当x 为局部极小点 当且仅当x 为KKT点 二次规划的KKT定理形式为 Qx c AIT A T AIx bI 0二次规划的求解本质上就是求解上述KKT方程 决策理论与方法 优化决策理论与方法 约束非线性规划 SQP法 对于非线性约束优化 COP 问题 若x 是COP问题的一个局部最优解 则它对应一个纯等式约束优化问题 决策理论与方法 优化决策理论与方法 约束非线性规划 SQP法 因此如果事先知道积极约束指标集 那么带有不等式约束优化问题就可以转化为纯等式约束优化问题 并可用准牛顿法求解 这就是逐次二次规划 SequentialQuadraticProgramming SQP 法 基本思想 在迭代点处构造一个二次规划子问题 近似原来的约束优化问题 然后通过求解该二次规划子问题获得约束优化问题的一个改进迭代点 不断重复此过程 直到求出满足一定要求的迭代点 决策理论与方法 优化决策理论与方法 约束非线性规划 SQP法 对于等式约束优化问题Minf x S t h x 0拉格朗日函数记为L x f x Th x 则 L x f x h x h x T 0 显然问题的最优解 x 满足此式 设 xk k 是第k次迭代结果 根据牛顿法 有 决策理论与方法 优化决策理论与方法 约束非线性规划 SQP法 上述迭代过程等价于如下的二次规划的迭代 设给定迭代点 xk k 则 决策理论与方法 优化决策理论与方法 约束非线性规划 Matlab函数应用 OptimizationToolBoxMinf x s t c x 0ceq x 0A x bAeq x beqlb x ub x fval fmincon fun x0 A b Aeq beq lb ub nonlcon fun定义目标函数 x0定义初始可行解 nonlcon定义c x 和ceq x 决策理论与方法 优化决策理论与方法 约束非线性规划 Matlab函数应用 用法创建一个matlab文件 如myfun mfunctionf myfun x f f x 创建另一个matlab文件 如confun mfunction c ceq confun x c c x ceq ceq x 调用fmincon并指定初始搜索点以及其他向量 矩阵 x0 x1 x2 xn A b Aeq beq lb ub x fval fmincon myfun x0 A b Aeq beq lb ub confun 决策理论与方法 优化决策理论与方法 约束非线性规划 Matlab函数应用 例 minf x ex1 4x12 2x22 4x1x2 2x2 1 S t x1x2 x1 x2 1 5x1x2 10解 创建一个matlab文件 如myfun mfunctionf myfun x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 创建另一个matlab文件 如confun mfunction c ceq confun x c 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 ceq 决策理论与方法 优化决策理论与方法 约束非线性规划 Matlab函数应用 调用有约束非线性规划函数x0 1 1 Startingguessoptions optimset LargeScale off x fval fmincon objfun x0 confun options 运行结果 x 9 54741 0474 fval 0 0236iterations 8algorithm medium scale SQP Quasi Newton line search 决策理论与方法 优化决策理论与方法 二次规划 Matlab函数应用 OptimizationToolBoxMin0 5xTHx fTxs t A x bAeq x beqlb x ub x fval quadprog H f A b Aeq beq lb ub x0 x0定义初始可行解 可选 决策理论与方法 优化决策理论与方法 二次规划 Matlab函数应用 用法首先要将目标函数转换成二次规划标准型 从而得到H和f两个矩阵 调用quadprog并根据需要指定初始搜索点以及其他向量 矩阵 x0 x1 x2 xn A b Aeq beq lb ub x fval quadprog H f A b Aeq beq lb ub x0 决策理论与方法 优化决策理论与方法 二次规划 Matlab函数应用 例 minf x 1 2x12 x22 x1x2 2x1 6x2 S t x1 x2 2 x1 2x2 22x1 x2 3x1 x2 0解 改写f x 1 2 x12 2x22 x1x2 x1x2 2x1 6x2得 H 1 1 12 f 2 6 x x1 x2 表示其它矩阵或向量A 11 12 21 b 2 2 3 lb 0 0 Aeq beq ub 不指派初始解 决策理论与方法 优化决策理论与方法 二次规划 Matlab函数应用 调用二次规划函数 x fval quadprog H f A b lb 运行结果 x 0 6667 1 3333 fval 8 2222iterations 3algorithm medium scale active set 积极约束集方法 决策理论与方法 优化决策理论与方法 优化决策理论与方法 1 线性规划2 非线性规划 约束和非约束 3 多目标规划4 组合优化与整数规划 决策理论与方法 优化决策理论与方法 多目标规划 管理实例 物资调度 假设物资调度部门计划将某种物资从若干个存储仓库调运到若干个销售网点销售 考虑到物资的时效性和销售效益 调度部门希望物资在运输过程中尽可能快地到达目的地 同时 考虑到运输成本 调度部门还希望物资的总运输费用最小 试建立描述物资调运过程的数学模型 解 设共有m个仓库 第i个仓库的物资库存量为ai吨 有n个销售网点 第j个销售网点的销售量为bj吨 第i个仓库到第j个销售网点的距离为dij 单位物资的运费为cij 设从第i个仓库运到第j个销售网点的物资量为xij 决策理论与方法 优化决策理论与方法 多目标规划 管理实例 决策目标 运输速度最快 可用吨公里数 可观测变量 最小描述 总吨公里数为 i jdijxij 运输费用最小 总运输费用为 i jcijxij 约束条件每个仓库的运出量不超过仓库的库存量 jxij ai 运到每个销售网点的量与其销售能力相匹配 ixij bj 每个仓库的运出量非负 xij 0 决策理论与方法 优化决策理论与方法 多目标规划 管理实例 最后得到模型 模型包含2个目标 mn个决策变量 mn m n个约束 决策理论与方法 优化决策理论与方法 多目标规划 标准型 多目标规划 multi ObjectiveProgramming MOP 就是指在决策变量满足给定约束的条件下研究多个可数值化的目标函数同时极小化 或极大化 的问题 其一般形式如下 Minf x f1 x f2 x fp x T S t gi x 0 i Ihj x 0 j 决策理论与方法 优化决策理论与方法 多目标规划 Pareto最优解 设x 是可行域S上的一个点 对于 x S 均有 fi x fi x i 1 p 称x 为MOP问题的绝对最优解 若不存在x S 使得fi x fi x 或fi x fi x i 1 p 则称x 为MOP问题的有效解 或弱有效解 有效解通常也称为Pareto最优解 S x1 x2 f S f S f2 f2 f1 f1 绝对最优解 有效解 弱有效解 决策理论与方法 优化决策理论与方法 多目标规划 Pareto最优解存在条件 必要条件 假设向量值函数f f1 x fp x T g g1 x g I x T h h1 x h x T在x S处可微 若x 是MOP问题的有效解或弱有效解 则存在向量 R p R I R 使得 0 且 f x g x h x Tg x 0 决策理论与方法 优化决策理论与方法 多目标规划 求解方法 直接求解多目标规划问题的有效解集是NP 难问题 下面介绍多目标规划问题的间接解法 基本思路都是将多目标规划问题转化为一个或多个单目标优化问题 基于一个单目标问题的方法 将原来的多目标规划问题转化成一个单目标优化问题 然后利用非线性优化算法求解该单目标问题 所得解作为MOP问题的最优解 关键问题在于 保证所构造的单目标问题的最优解是MOP问题的有效解或弱有效解 决策理论与方法 优化决策理论与方法 多目标规划 求解方法 线性加权和法 Min Tf x k kfk x S t gi x 0 i Ihj x 0 j 权重设置要求 k k 1 k 0 k 1 2 p 主要目标法 Minf x f1 x 不妨设f1 x 为主要目标 S t gi x 0 i Ihj x 0 j fk x uk k 2 puk为专家经验值 决策理论与方法 优化决策理论与方法 多目标规划 求解方法 极小化极大法 在目标函数f x 的p个分量中 极小化f x 的最大分量 即minx Smax1 j pfj x 理想点法 分别求出f x 中每个分量fj x 的极小点fj0 得到理想点f0 f10 fp0 T 然后求解单目标优化问题 minx S f x f0 为范数的阶 可取1 2 决策理论与方法 优化决策理论与方法 多目标规划 求解方法 基于多个单目标问题的方法 将原来的多目标规划问题转化成具有一定次序的多个单目标优化问题 然后依次求解这些单目标优化问题 并把最后一个单目标优化问题的解作为MOP问题的最优解 关键问题在于 保证最后一个单目标优化问题的最优解是MOP问题的有效解或弱有效解 分层排序法 将目标函数按重要度依次排序 然后在前一个目标函数的最优解集中寻找下一个目标的最优解集 并把最后一个目标的最优解作为MOP问题的最优解 决策理论与方法 优化决策理论与方法 多目标规划 求解方法 minf1 x x S 不妨设f1 x 为第一层目标 得到最优解集S1 第j层 minfj x x Sj 1 j 2 p最后将Sp中的点作为多目标问题的最优解 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 OptimizationToolBoxMinmax fi x s t c x 0ceq x 0A x bAeq x beqlb x ub x fval fminimax fun x0 A b Aeq beq lb ub nonlcon Fun定义目标函数 x0定义初始可行解 nonlcon定义c x 和ceq x 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 用法创建一个matlab文件 如myfun mfunctionf myfun x f 1 f1 x f 2 f2 x f p fp x 创建另一个matlab文件 如confun mfunction c ceq confun x c c x ceq ceq x 调用fminimax并指定初始搜索点以及其他向量 矩阵 x0 x1 x2 xn A b Aeq beq lb ub x fval fminimax myfun x0 A b Aeq beq lb ub confun 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 OptimizationToolBoxMinx s t F x weight goalc x 0ceq x 0A x bAeq x beqlb x ub x fval fgoalattain fun x0 goal weight A b Aeq beq lb ub nonlcon Fun定义目标函数 goal为理想点 x0定义初始可行解 nonlcon定义c x 和ceq x weight为各目标的权重向量 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 用法创建一个matlab文件 如myfun mfunctionf myfun x f 1 f1 x f 2 f2 x f p fp x 创建另一个matlab文件 如confun mfunction c ceq confun x c c x ceq ceq x 调用fgoalattain并设定理想点 权重向量 指定初始搜索点以及其他向量 矩阵 x0 x1 x2 xn A b Aeq beq lb ub goal weight x fval fgoalattain myfun x0 goal weight A b Aeq beq lb ub confun 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 例 min f1 f2 f3 f4 f5 f 1 2 x 1 2 x 2 2 48 x 1 40 x 2 304 f 2 x 1 2 3 x 2 2 f 3 x 1 3 x 2 18 f 4 x 1 x 2 f 5 x 1 x 2 8 无约束 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 解 1 用fminimax求解 定义myfun m指定初始搜索点 x0 0 1 0 1 调用 x fval fminimax myfun x0 结果 x 4 00004 0000 fval 0 0000 64 0000 2 0000 8 0000 0 0000 iterations 7algorithm minimaxSQP Quasi Newton line search 决策理论与方法 优化决策理论与方法 多目标规划 Matlab函数应用 解 2 用fgoalattain求解 定义myfun m指定初始搜索点 x0 0 1 0 1 指定理想点 goal 1 60 5 10 1 指定权重 weight abs goal 调用 x fval fgoalattain myfun x0 goal weight 结果 x 3 97983 9596 fval 1 9395 62 8754 2 1412 7 9395 0 0605 iterations 7algorithm goalattainmentSQP Quasi Newton line search 决策理论与方法 优化决策理论与方法 优化决策理论与方法 1 线性规划2 非线性规划 约束和非约束 3 多目标规划4 组合优化与整数规划 决策理论与方法 优化决策理论与方