决策理论与方法(5)

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.0000 4.0000]

fval = [0.0000 -64.0000 -2.0000 -8.0000 -0.0000] iterations: 7

algorithm: 'minimax SQP, 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.9798 3.9596]

fval =[1.9395 -62.8754 -2.1412 -7.9395 -0.0605] iterations: 7

algorithm: 'goal attainment SQP, Quasi-Newton, line_search'

优化决策理论与方法

1、线性规划

2、非线性规划（约束和非约束） 3、多目标规划

4、组合优化与整数规划

组合优化—基本概念

? 组合优化问题是指从一个有限的可行解集中寻找使某个性能函数取极值的最

优解。

? 给定一个有限集N={1,2,…,n}和权函数c:N→R。记N的某些子集的集合为F，则组合优化问题就是从F中找到一个具有最小权重的子集。

? 已经证明：求解组合优化问题的最优解是NP-难的。设计各类贪婪算法是求解

组合优化问题常用的思路。

组合优化—基本概念

? 常见的组合优化问题：

? 最短路问题 ：给定一定的路长分布，确定从某个地点到另一个地点使路长

最短的路径。(TSP 问题) ? 最大流问题 ：在一个有容量限制的网络中，如何使得从一个顶点到另一个顶点的流量达到最大？

? 装箱问题 ：如何将一定规格的物品装到箱子中，使得占用箱子的个数最少？

? 背包问题 ：如何挑选一些价值不同、尺寸有别的物品放到一个有限大的背包中，使得背包内的物品价值总量最大？

组合优化—最短路问题

? 给定一个网络N=(V, E, w)，其中w为权函数，最短路问题是指对于两个不同的

顶点s,t?V，寻找一条从s到t的路，使得路上所有弧的权和最小(权可看作弧长)。 ? 关联矩阵：A=(aij)|V|×|E|。aij=1(vi为ej的起点)；aij=-1(vi为ej的终点)；aij=0(其他情形)。引入0-1整型变量xj(ej?E)，记x=(x1,x2,...,x|E|)T。则最短路径问题可表示成如下的0-1整数规划问题：

min wTx s.t. asTx=1

atTx=-1

aiTx=0, i≠s,t x?0

组合优化—最短路问题

? 例：考虑如图所示的网络，定义权函数w=(1,2,2,3,1)

T

。试确定从s到t点的最短

路径。

TTT

? 解：as=(1 1 0 0 0)；at=(0 0 0 -1 -1)T;aa=(-1 0 1 1 0); ab=(0 -1 -1 0 1)，得到以下规划方程：

min x1+2x2+2x3+3x4+x5 s.t. x1+x2=1 -x4-x5=-1 -x1+x3+x4=0 -x2-x3+x5=0 x1,x2,x3,x4,x5?0

T ?

调用函数linprog(w,[],[],Aeq,beq,lb)得x=[0 1 0 0 1]? 表明从s出发经过第2、5条边到达t点最短。

整数规划—标准型

? 整数规划是一类特殊的组合优化问题。线性(混合)整数规划问题是

指在等式或不等式的线性约束下，极大化(或极小化)某个线性函数，其中要求某些变量必须取整数。

? 线性混合整数规划(MILP)：

max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p}

? x,y为决策变量向量，其中x包含n个整数变量，y包含p个实数变量；c为n维

向量；h为p维向量；A为m×n阶矩阵，G为m×p阶矩阵。

整数规划—标准型

? 整数规划的可行域：

S={(x,y)|Ax+Gy?b, x?Z+n, y?R+p}

? 例：P={x?Z

1

×R1|-x1+x2?1/2, 3x1+4x2?3, x2?0}

整数规划—解的特点

? 从整数规划的可行域分析可知，整数规划的解与其松弛问题(整数

规划问题的所有变量取值不受整数限制时的线性规划问题)既有密切的联系，又有本质的区别。

? 整数规划问题的可行解一定是松弛问题的可行解，但反之不一定。

所以整数规划问题的最优解不会优于其松弛问题的最优解。

? 求解方法：Gomory割平面法、分支定界法、分解算法。

整数规划—Matlab函数应用

? Optimization ToolBox

Min f’·x s.t. A·x?b

Aeq·x=beq x：0-1

? [x,fval] =bintprog(f, A, b, Aeq, beq, x0)

? x0定义初始可行解(可选)；bintprog仅适合求解0-1整数规划问题。

__

决策理论与方法(3)

——随机决策理论与方法(1)

合肥工业大学管理学院

2013年4月19日

随机性决策

? 风险性决策（随机性决策）：指有多种未来状态和相应后果，但只

能得到各种状态发生的概率而难以获得充分可靠信息的决策问题。

? 特点：状态的随机性；决策结果的效用特性。 ? 决策的已知变量：

? 状态空间的概率分布<Θ,P>={,< ?2,p2 >,…, }

? 后果的效用函数(或损失函数)：u(cij)，cij表示采取方案ai时出现状态?j的后

果

? 解决问题的主要理论方法：概率论与数理统计

随机决策理论与方法

1、主观概率 2、效用函数 3、决策准则 4、贝叶斯决策分析

主观概率—概率的定义

? 古典概率的定义：在相同条件下进行了n次试验（随机试验），其中事件A发

生的次数nA称为事件A发生的频数，比值nA/n称为事件A发生的频率，记为fn(A)，则古典概率的定义为：p(A)=limn→∞fn(A)

? Laplace的定义：p(A)=k/n；其中k为事件A所包含的基本事件数，n为基本事件ei的总数。（基本事件数有限，每个基本事件等概率）

? 公理化定义：E是随机事件，S是E的样本空间，对E的每一事件A，对应有确定的实数p(A)，若p(A)满足：①非负性：p(A)≥0；②规范性：p(S)=1；③列可加性：对两两不相容事件Ak，有p(∪kAk)=Σkp(Ak)。(Ai∩Aj=Φ,i≠j)

主观概率—概率的定义

? 客观(Objective)概率：上述三种定义的概率是在多次重复试验（随机试验）

中，随机事件A发生的可能性的大小的度量，称为客观概率。 ? 主观(Subjective)概率：在实际管理决策中，许多事件的发生概率是无法通过随机试验获得的，或条件不允许，或事件本身不允许。因此需要一种方法来人为设定事件发生的概率，称为主观概率。主观概率是人们根据经验、各方面的知识以及了解到的客观情况进行分析、推理、综合判断，对特定事件发生的可能性的信念（或意见、看法）的度量(Savage,1954)。

主观概率—先验分布与先验假设

? 先验分布(Prior Distribution)：根据先验信息所确定的概率分布叫先验分布，

获得先验分布是贝叶斯分析的基础。决策中先验分布的获得具有高度的主观性。

? 先验假设 ：为使先验分布估计规范化，需要做一定的假设。

? 连通性假设：指事件A和事件B发生的可能性是可比的，即p(A)>p(B), p(A)~p(B),

p(A)

? 传递性假设：若对事件A、B、C，有p(A)>p(B), p(B)>p(C), 则p(A)>p(C)。（满足连通性和传递性的二元关系才能构成完全序）

? 部分与全体关系假设：若事件A是事件B的一部分，则p(B)≥p(A)。

主观概率—先验分布估计:比较法

? 比较法1-离散型（对事件发生的各种状态加以比较确定相对似然率）

? 某气象专家对当年的气候状况进行评估，认为当年气候正常(?1)与受灾的可

能性之比约为3:2；如果受灾，则水灾(?2)、旱灾(?3) 的可能性相当。据此，我们可推算出当年气候状况的先验分布：

?(?1)+?(?2)+?(?3)=1; ?(?1)/(?(?2)+?(?3))=3/2; ?(?2)=?(?3) 解得： ?(?1)=0.6，?(?2)=0.2，?(?3)=0.2

? 思考：设某决策问题有n个状态，有m个专家对各状态发生的可能性进行了比较评估，我们如何综合利用所有专家的评估结果得到最终的先验分布？

主观概率—先验分布估计：比较法

? 比较法2-连续型

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库决策理论与方法(5)在线全文阅读。