决策理论与方法(2)
——优化决策理论与方法
合肥工业大学管理学院
2013年4月19日
确定性决策
? 确定性决策：指未来状态是确定的（即只有一种状态）一类决策问
题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。
? 特点：状态是确定的；决策问题变为优化问题。 ? 决策的已知变量：
? 决策变量及其取值范围
? 解决问题的主要理论方法：最优化理论与方法
? 注：最优化理论与方法（数学规划）也可以求解不确定性决策问题、
随机性决策问题
确定性决策
? 优化决策方法的问题求解过程
? 辨识目标C，确定优化的标准，如：利润、时间、能量等 ? 确定影响决策目标的决策变量x，形成目标函数C=f(x) ? 明确决策变量的取值范围，形成约束函数
? 设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极
大化。
? 最优化问题的一般形式为：
优化问题分类
? 可行点与可行域：满足约束条件的x称为可行点，所有可行点的集
合称为可行域，记为S；
? 约束优化与无约束优化：当S?R
n
时，称为约束优化；当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 构造了一种
称为投影尺度算法 的内点算法。
线性规划—内点算法
线性规划—Matlab函数应用
? Optimization ToolBox
Min fTx S.t. A·x≤b Aeq·x=beq lb≤x≤ub
? 其中：f, x, b, beq, lb和ub均为向量；A和Aeq为矩阵。
[x, fval] = linprog(f,A,b,Aeq,beq,lb,ub)
线性规划—Matlab函数应用
? 例：max z=x1+2x2
S.t.
? x1+x2≤40 ? 2x1+x2≤60 ? x1≥0; x2≥0
解：将max变为min，min –z=-x1-2x2
则：f=[-1;-2]; b=[40;60]; lb=zeros(2,1); A=[1 1;2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0;40], fval= -80
优化决策理论与方法
1、线性规划
2、非线性规划（约束和非约束） 3、多目标规划
4、组合优化与整数规划
无约束非线性规划—标准型
?
Min f(x); x?Rn
? 其中f：R
n
→R是一个非线性连续函数。对于任意点x*?Rn, 它是函
数f的最小点(或局部极小点)吗？
? 例如：min f(x)=e
x1
(4x12+2x22+4x1x2+2x2+1)
无约束非线性规划—极小值存在条件
? 必要条件。设x
? 当f(x)在x
*
*
是f(x)的局部极小点，则
点可微时，梯度?f(x*)=0； *2*n
? 当f(x)在x点二阶可微时，Hesse矩阵▽f(x)是半正定 的，即??d?R，有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。
无约束非线性规划—复习
? 梯度矩阵
无约束非线性规划—牛顿法
? 基本思想：在一个点附近，用目标函数f(x)的二阶Taylor多项式近
似f(x)，并用该Taylor多项式的最小点近似f(x)的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造f(x)的二阶Taylor多项式(迭代)，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。
无约束非线性规划—牛顿法
? 设x
k
是第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(x
k
)+G(xk)p=0，得
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库决策理论与方法在线全文阅读。
相关推荐：