交互式决策方法.ppt

《交互式决策方法.ppt》由会员分享，可在线阅读，更多相关《交互式决策方法.ppt（48页珍藏版）》请在三一办公上搜索。

1、现代决策方法,第7章 交互式决策方法,第7章 交互式决策方法,7.1 交互式决策方法概述7.2 逐步进行法7.3 序贯解法7.4 Zionts-Wallenius法,7.1 交互式决策方法概述,交互式决策方法一般都具有这样的特点：即在问题求解过程中，这类方法需要决策者与决策分析者不断对话，持续地参与决策过程，在决策者和分析者的相互作用中，逐步获得决策者的偏好结构，最后得出最满意的决策。由于描述决策者偏好的具体方式不同，如可以用参考点、置换率等，形成了多种不同的决策方法。,7.1 交互式决策方法概述,交互式决策方法的一般步骤如下：（1）明确决策问题，将问题用数学模型描述。（2）对现有决策问题，求

2、出一个决策者比较偏好的可行的非劣解。（3）与决策者交换信息，征求决策者对当前解的意见。（4）如果决策者很满意当前解或决策过程的终止判断被满足，当前解即为现有决策问题的最佳调和解，决策过程结束。否则，按下述步骤继续进行。（5）根据决策者的意见，修改决策方法，求出在相应偏好下新的比较偏好的非劣解，返回第（3）步。,7.2 逐步进行法,基本原理逐步进行法（Step Method)是Benayoun提出的，求解线性多目标决策问题最早的利用局部偏好信息的交互式决策方法之一，也是一种最直观、决策者易于理解的对话方法。若目标函数的个数为n，那么这种方法可以在不大于n步内得到满意解。这种交互式决策方法是以最佳

3、调和解距离理想点 有最小的组合偏差为前提去寻找出这个最佳调和解。,7.2 逐步进行法,设线性多目标决策问题的数学模型如下：（7-2-1）若用向量形式表示，则为,7.2 逐步进行法,求解步骤用逐步进行法求解问题的步骤如下：（1）求理想点，构造支付表；令迭代次数计算器，分别对 求解n个单目标优化问题：（7-2-2）,7.2 逐步进行法,求解问题（7-1-2）所得的最优解分别记为，其对应的目标函数值。把以上结果列入支付表7-1中的，即表中第 列元素为目标函数 在不同的 处的值，而第 行的元素为各个目标函数在 处的值。,表7-1 支付表,7.2 逐步进行法,（2）对，形成优化问题，求出比较偏好的非劣解

4、 根据前述讨论，其最佳调和解应是下列优化问题的解：（7-2-3）问题（7-2-3）等价于下面的线性规划问题：（7-2-4）,7.2 逐步进行法,在式（7-2-4）中参数 是各个目标函数的实际值距其理想值的偏差加权后上确界，求得的解 将使上确界 为极小；权被定义为（7-2-5）式中（7-2-6）,7.2 逐步进行法,(3)决策者对当前解作出反应，发表意见决策者对当前方案的目标函数值与理想点进行比较，得出以下三种情况：决策者认为当前解非常满意，这样当前解为最佳调和解，决策过程结束。如果决策者认为所有目标均不满意或者，且决策者仍没有找到他的满意解，说明这种方法不能求出该问题的最佳调和解，决策过程结束

5、。如果决策者认为当前方案的某些目标与理想点相比非常满意，而另一些目标与理想点相比不满意，则决策者要在这n个目标之间进行权衡，以换取主要目标的改进，使得对各个目标函数值均比较满意。,7.2 逐步进行法,(4)求出新的比较偏好的非劣解由决策者的反应形成新的优化问题，新问题的约束条件为 式中（7-2-8）相应的各个目标的权重为（7-2-9）（7-2-10）第q次交互迭代计算求解的问题为 式中，令 返回（3）继续进行。,7.2 逐步进行法,【例7-1】用逐步进行法求解下面的两目标决策问题,7.2 逐步进行法,（1）求解问题 得其解为：求解问题 得其解为。由上述计算结果得该 问题的支付表如表7-2。,7

6、.2 逐步进行法,表7-2 支付表（2）利用式（7-2-6）和式（7-2-5）计算得，。这样。形成第一个优化问题为求解该问题得,7.2 逐步进行法,（3）让决策者将 与 比较。这里假定决策者愿意将目标函数 的值降低1个单位，即从11.6降低到10.6。（4）形成新的约束集 为 式中，。由此，新的优化问题为 求解该问题得。返回第（3）步。（5）如果决策者对当前解 满意，停止决策过程，即为最佳调和解。否则，返回（3）继续进行。,7.3 序贯解法,基本原理多目标决策问题的序贯解法（SEMOP)是一种能被用来求解非线性多目标决策问题的交互式决策方法。它在每次迭代计算时，根据决策者的意见去修改目标的目的

7、值，并力图使目标函数值对给定的目的偏差为极小。基于这种方法，决策者提供的目的值是一个区间，而不是一个固定值，因此作为目的偏差的测度不再能使用前述的范数形式，需要采用目标函数的实际值和相应的区间目的的界值比。,7.3 序贯解法,决策者标定的区间目的及相应的区间测度有5中类型，见如下表7-3，除第一种情况外，都是目标函数的非线性函数。表7-3 区间目的的偏差测度,7.3 序贯解法,序贯解法是一种迭代的算法，在第 次迭代时，不仅要求决策者提供区间目的的值，还要求规定什么目标函数的值应严格处在区间之内。令目标的下标集为。设 为 的子集，决策者要求在第 次迭代的数学规划问题（称为主问题）为（7-3-1）

8、（7-3-2）上式中的q表示第q次迭代，表示第q次迭代时第j个目标函数的值自其区间目的的偏差，对于每个 严格处在标定的区间目的内。,7.3 序贯解法,为帮助决策者在迭代过程中调整区间目的，还需要向他提供另外的信息。这种信息是若干个辅助的子问题得到的。在q次迭代时，辅助问题共有 个，其中第 个辅助问题（）为（7-3-3）（7-3-4）式中 对于每个 严格处在标定的区间目的内，此外 也应严格处在标定的区间目的内。,7.3 序贯解法,由以上对辅助问题所作的规定可知，辅助问题和主问题的区别是，在辅助问题中多了一个约束条件，即规定第 个目标，应严格处在它的区间目的内。把主问题和辅助问题对比就可以知道，对

9、某一个目标，例如第 个目标的区间目的作了调整，将对其它目标产生何种影响。,7.3 序贯解法,序贯解法的计算步骤 第一次迭代 令，解以上的主问题和辅助问题：（1）主问题（7-3-5）（7-3-6）（2）辅助问题（第 个，）（7-3-7)(7-3-8)而 严格处于其区间目的内。,7.3 序贯解法,第q次迭代解以下主问题和辅助问题：主问题（7-3-9）（7-3-10）辅助问题（第 个，）（7-3-11)(7-3-12)迭代继续进行，直到决策人得到最佳调和解为止。,7.3 序贯解法,【例7-2】求解以下多目标决策问题：设该问题中两个目标的目的为上界（至多）型的，且它们的上界分为。由此可定义各目标的偏差

10、测度为,7.3 序贯解法,第一次迭代 主问题为 求解该问题得解集为,7.3 序贯解法,（2）求解两个辅助问题 第一个辅助问题为 其解为 第二个辅助问题为 其解为 将上述计算结果送给决策者判断，设决策者最终接受的第二个目标 目的值的上界为4。,7.3 序贯解法,第二次迭代 在第二次迭代中，只要求解主问题为 求解该问题得将该结果送给决策者，由于各个目标的实际值与其区间目的值比较一致，决策人对 的方案比较满意，该方案为最佳调和解。如果决策者对该方案不满意，可以修改区间目的值，继续计算。,7.4 Zionts-Wallenius法,ZiontsWallenius法（以下简称ZW法）是Zionts和Wa

11、llenius提出的一种处理一类多目标决策问题的交互式方法，这一类问题有如下特征。（1）所有约束是线性的，约束集合构成凸多面体。（2）所有目标函数是线性的或凸的（求极小值）。（3）决策者的价值函数或选好函数不能用公式表达出来，但是，知道这一函数的形式。这一形式是目标函数线性相加形式，或者是线性目标函数的凹函数。,7.4 Zionts-Wallenius法,基本原理 这一算法的原理可以用线性问题来说明。设有如下线性多目标问题：（7-4-1）式中 假设决策者的选好函数具有加法形式。虽然不知道这一函数的具体方程的参数，但是知道这一函数有如下形式：（7-4-2）,7.4 Zionts-Walleniu

12、s法,搜索最优 的方法 假设有式（7-4-2）形式的选好函数，则式（7-4-1）的多目标最优化问题将变成如下标量最优化问题：（7-4-3）由于假设，显然，式（7-4-3）的最优解是非劣解。这一方法是建立在如下主要思想之上的。由于式（7-4-3）是一个线性加权问题，其最优点必位于凸多面体（可行域X）的极点和由极点连接的边和面上。因此，用式（7-4-3）搜索选好最优解，只需在 的所有非劣极点或极射线中进行搜索即可。,7.4 Zionts-Wallenius法,为了进一步说明，设已求得一个非劣极点，其相应的单纯形表如表7-4所示。表7-4 单纯形表,7.4 Zionts-Wallenius法,由多目

13、标线性规划的原理，得出如下结论:（1）在单纯形表7-4中，如果非基本变量列j中，所有判别数 则将这一非基变量 引入基底各目标值均变坏，显然，这一非基变量 不能引入。（2）如果有非基变量列j，其中 不全大于零，即有的为正，有的为负，则将这一非基变量引入基底，将使有的目标变坏，有的目标变好，如果至少有一个，则这种非基变量才有可能进入基底。,7.4 Zionts-Wallenius法,设由单纯形表求得一个非劣极点，这时，由相应的单纯形表的判别数构造如下线性规划问题：（7-4-4）若，最优解，则 是有效非基变量，将 引入基底，将得到 的一个相邻非劣极点。,7.4 Zionts-Wallenius法,（

14、3）在单纯形表7-4中，判别数 表示当将非基变量 引入基底时，非基变量变化一单位，的变化率。因此，列向量 表示将 引入基底时，各目标函数之间的折中关系，即各目标的改善或变坏的数量关系。如果决策者愿意进行这一折中，那就表示将 引入基底，决策者的潜在的选好函数值将有所改善。如果决策者不愿意进行这一折中，这就表示将 引入基底，决策者的潜在的选好函数值变坏。如果决策者对这一折中认为与目前解没有差别，则表示将 引入基底，决策者的潜在的选好函数不变。,7.4 Zionts-Wallenius法,（4）设决策者的潜在的选好函数为 这一函数的参数 是不知道的，决策者不能给出具体数值。但是，如果引入 决策者感到

15、他的选好函数值有所改善，那就表示（7-4-5）但是，如果引入 决策者感到他的选好函数值变坏，那就表示（7-4-6）如果引入，决策者感到他的选好函数没有变化，那就表示（7-4-7）,7.4 Zionts-Wallenius法,（5）根据（3）和（4）的两个关键概念，可以给出搜索最优值的方法如下。引入基底会产生相邻非劣极点的非基变量为有效非基变量，将这一列的折中列向量提供给决策者，决策者经过判断，给出是否愿意进行折中的信息。如果愿意进行这一折中（引入这一非基变量），表示他的选好函数有；如果他不愿意进行这一折中，表示他的选好函数有；如果他认为这一折中没有什么差别，表示他的选好函数有 因此，根据决策者

16、是否愿意折中这一选好信息，可以由式（7-4-5）式（7-4-7）搜索决策者潜在最优权值。,7.4 Zionts-Wallenius法,求解步骤（1）选择一个适当的权向量，求解（7-4-3），得到一个初始非劣极点，设。（2）求 得所有导致相邻非劣极点的非基列。设这些非基列中尚未考查过的列下标集合为。（3）将每一个 的折中向量 提供给决策者，询问决策者是否愿意进行折中。（4）用单纯形法求解以前循环中构成的式（7-4-5）式（7-4-7）的可行解，要求满足，。令可行解为。令 返回（2）。,7.4 Zionts-Wallenius法,【例7-3】求解产品生产问题。生产安排的数学模型如下：为了对话需要，

17、假设决策者潜在的选好函数为,7.4 Zionts-Wallenius法,（1）任意选择，构成加权问题 用单纯形法求解，初始单纯形表7-5所示。,7.4 Zionts-Wallenius法,表7-5 初始单纯形表 将 引入基，退出基，经枢纽变换后的单纯形表7-6所示。,7.4 Zionts-Wallenius法,表7-6 枢纽变换后的单纯形表 得到非劣极点，目标值为。令。,7.4 Zionts-Wallenius法,第一循环：（2）求相邻非劣极点。有两个非基变量 和。在 列中，其判别数为，全部为正，故将 引入基底将使两个目标均变坏。故引入 不能得到非劣极点。在 列中，其判别数为，故可将 引入基底

18、。为判别将其引入基底后相邻极点的非劣性，可构造如下线性规划问题。,7.4 Zionts-Wallenius法,第一循环：（2）求相邻非劣极点。有两个非基变量 和。在 列中，其判别数为，全部为正，故将 引入基底将使两个目标均变坏。故引入 不能得到非劣极点。在 列中，其判别数为，故可将 引入基底。为判别将其引入基底后相邻极点的非劣性，可构造如下线性规划问题。求解后得,7.4 Zionts-Wallenius法,（3）对话阶段。决策者的选好函数不能以显式表达，为模拟决策者的对话过程，假设它的选好函数为 将计算得到的数据提供给决策者：目前的最优解是。如将 引入基底，则折中向量为，即B产品增加一件，将使

19、 减小0.1，使 增加0.5。问决策者是否愿意这一折中。决策者回答愿意这一折中，因为决策者判断其选好值将增加。于是可以构成式（7-4-5），即 或,7.4 Zionts-Wallenius法,（4）求解新的权值。由 可行解中取，令。返回（2）。,7.4 Zionts-Wallenius法,第二循环（5）求相邻非劣极点。构造加权问题：用单纯形法求解，由表7-6，将 引入基，退出基，经枢轴变换，得表7-7。,7.4 Zionts-Wallenius法,表7-7 枢轴变换后的单纯形表 得到非劣极点，非基变量有 和，只有 可以引入基。由于 引入导致相邻非劣极点已经研究过，故没有可以再引入的非基 变量。所以最优选好解为。,Thank You!,