第7章交互式决策方法课件

《现代决策方法》第7章交互式决策方法第7章

交互式决策方法7.1交互式决策方法概述7.2逐步进行法7.3序贯解法7.4Zionts-Wallenius法7.1交互式决策方法概述交互式决策方法一般都具有这样的特点：即在问题求解过程中，这类方法需要决策者与决策分析者不断对话，持续地参与决策过程，在决策者和分析者的相互作用中，逐步获得决策者的偏好结构，最后得出最满意的决策。由于描述决策者偏好的具体方式不同，如可以用参考点、置换率等，形成了多种不同的决策方法。7.1交互式决策方法概述交互式决策方法的一般步骤如下：（1）明确决策问题，将问题用数学模型描述。（2）对现有决策问题，求出一个决策者比较偏好的可行的非劣解。（3）与决策者交换信息，征求决策者对当前解的意见。（4）如果决策者很满意当前解或决策过程的终止判断被满足，当前解即为现有决策问题的最佳调和解，决策过程结束。否则，按下述步骤继续进行。（5）根据决策者的意见，修改决策方法，求出在相应偏好下新的比较偏好的非劣解，返回第（3）步。7.2逐步进行法基本原理逐步进行法（StepMethod)是Benayoun提出的，求解线性多目标决策问题最早的利用局部偏好信息的交互式决策方法之一，也是一种最直观、决策者易于理解的对话方法。若目标函数的个数为n，那么这种方法可以在不大于n步内得到满意解。这种交互式决策方法是以最佳调和解距离理想点有最小的组合偏差为前提去寻找出这个最佳调和解。7.2逐步进行法设线性多目标决策问题的数学模型如下：

（7-2-1）若用向量形式表示，则为

7.2逐步进行法

（2）对，形成优化问题，求出比较偏好的非劣解

根据前述讨论，其最佳调和解应是下列优化问题的解：

（7-2-3）问题（7-2-3）等价于下面的线性规划问题：

（7-2-4）

7.2逐步进行法

在式（7-2-4）中参数是各个目标函数的实际值距其理想值的偏差加权后上确界，求得的解将使上确界为极小；权被定义为

（7-2-5）式中

（7-2-6）

7.2逐步进行法

(3)决策者对当前解作出反应，发表意见决策者对当前方案的目标函数值与理想点进行比较，得出以下三种情况：①决策者认为当前解非常满意，这样当前解为最佳调和解，决策过程结束。②如果决策者认为所有目标均不满意或者，且决策者仍没有找到他的满意解，说明这种方法不能求出该问题的最佳调和解，决策过程结束。③如果决策者认为当前方案的某些目标与理想点相比非常满意，而另一些目标与理想点相比不满意，则决策者要在这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.2逐步进行法

表7-2支付表

（2）利用式（7-2-6）和式（7-2-5）计算得，。这样。形成第一个优化问题为求解该问题得

1186137.2逐步进行法（3）让决策者将与比较。这里假定决策者愿意将目标函数的值降低1个单位，即从11.6降低到10.6。

（4）形成新的约束集为

式中，

。由此，新的优化问题为

求解该问题得。返回第（3）步。

（5）如果决策者对当前解满意，停止决策过程，即为最佳调和解。否则，返回（3）继续进行。

7.3序贯解法基本原理多目标决策问题的序贯解法（SEMOP)是一种能被用来求解非线性多目标决策问题的交互式决策方法。它在每次迭代计算时，根据决策者的意见去修改目标的目的值，并力图使目标函数值对给定的目的偏差为极小。基于这种方法，决策者提供的目的值是一个区间，而不是一个固定值，因此作为目的偏差的测度不再能使用前述的范数形式，需要采用目标函数的实际值和相应的区间目的的界值比。

7.3序贯解法决策者标定的区间目的及相应的区间测度有5中类型，见如下表7-3，除第一种情况外，都是目标函数的非线性函数。表7-3区间目的的偏差测度

决策者标定的目的的类型偏差测度（1）上界（至多）

（2）下界（至少）

（3）

相等

（4）在一区间之内

（5）在一区间之外

7.3序贯解法序贯解法是一种迭代的算法，在第次迭代时，不仅要求决策者提供区间目的的值，还要求规定什么目标函数的值应严格处在区间之内。令目标的下标集为。设为的子集，决策者要求在第次迭代的数学规划问题（称为主问题）为

（7-3-1）

（7-3-2）

上式中的q表示第q次迭代，表示第q次迭代时第j个目标函数的值自其区间目的的偏差，，对于每个严格处在标定的区间目的内。

7.3序贯解法为帮助决策者在迭代过程中调整区间目的，还需要向他提供另外的信息。这种信息是若干个辅助的子问题得到的。在q次迭代时，辅助问题共有个，其中第个辅助问题（）为

（7-3-3）

（7-3-4）

式中对于每个严格处在标定的区间目的内，此外也应严格处在标定的区间目的内。

7.3序贯解法由以上对辅助问题所作的规定可知，辅助问题和主问题的区别是，在辅助问题中多了一个约束条件，即规定第个目标，，应严格处在它的区间目的内。把主问题和辅助问题对比就可以知道，对某一个目标，例如第个目标的区间目的作了调整，将对其它目标产生何种影响。

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】求解以下多目标决策问题：

设该问题中两个目标的目的为上界（至多）型的，且它们的上界分为

。

由此可定义各目标的偏差测度为

7.3序贯解法第一次迭代

主问题为

求解该问题得解集为

7.3序贯解法（2）求解两个辅助问题

①第一个辅助问题为

其解为

②第二个辅助问题为

其解为

将上述计算结果送给决策者判断，设决策者最终接受的第二个目标

目的值的上界为4。

7.3序贯解法第二次迭代

在第二次迭代中，只要求解主问题为

求解该问题得将该结果送给决策者，由于各个目标的实际值与其区间目的值比较一致，决策人对的方案比较满意，该方案为最佳调和解。如果决策者对该方案不满意，可以修改区间目的值，继续计算。

7.4Zionts-Wallenius法Zionts—Wallenius法（以下简称ZW法）是Zionts和Wallenius提出的一种处理一类多目标决策问题的交互式方法，这一类问题有如下特征。（1）所有约束是线性的，约束集合构成凸多面体。（2）所有目标函数是线性的或凸的（求极小值）。（3）决策者的价值函数或选好函数不能用公式表达出来，但是，知道这一函数的形式。这一形式是目标函数线性相加形式，或者是线性目标函数的凹函数。

7.4Zionts-Wallenius法基本原理

这一算法的原理可以用线性问题来说明。设有如下线性多目标问题：

（7-4-1）式中

假设决策者的选好函数具有加法形式。虽然不知道这一函数的具体方程的参数，但是知道这一函数有如下形式：

（7-4-2）

7.4Zionts-Wallenius法搜索最优的方法假设有式（7-4-2）形式的选好函数，则式（7-4-1）的多目标最优化问题将变成如下标量最优化问题：

（7-4-3）

由于假设，显然，式（7-4-3）的最优解是非劣解。这一方法是建立在如下主要思想之上的。由于式（7-4-3）是一个线性加权问题，其最优点必位于凸多面体（可行域X）的极点和由极点连接的边和面上。因此，用式（7-4-3）搜索选好最优解，只需在

的所有非劣极点或极射线中进行搜索即可。

7.4Zionts-Wallenius法为了进一步说明，设已求得一个非劣极点，其相应的单纯形表如表7-4所示。表7-4单纯形表

7.4Zionts-Wallenius法由多目标线性规划的原理，得出如下结论:（1）在单纯形表7-4中，如果非基本变量列j中，所有判别数

则将这一非基变量

引入基底各目标值均变坏，显然，这一非基变量

不能引入。（2）如果有非基变量列j，其中不全大于零，即有的为正，有的为负，则将这一非基变量引入基底，将使有的目标变坏，有的目标变好，如果至少有一个，则这种非基变量才有可能进入基底。

7.4Zionts-Wallenius法设由单纯形表求得一个非劣极点，这时，由相应的单纯形表的判别数构造如下线性规划问题：

（7-4-4）若，最优解，则是有效非基变量，将引入基底，将得到的一个相邻非劣极点。

7.4Zionts-Wallenius法（3）在单纯形表7-4中，判别数

表示当将非基变量

引入基底时，非基变量变化一单位，

的变化率。因此，列向量

表示将

引入基底时，各目标函数之间的折中关系，即各目标的改善或变坏的数量关系。如果决策者愿意进行这一折中，那就表示将

引入基底，决策者的潜在的选好函数值将有所改善。如果决策者不愿意进行这一折中，这就表示将

引入基底，决策者的潜在的选好函数值变坏。如果决策者对这一折中认为与目前解没有差别，则表示将

引入基底，决策者的潜在的选好函数不变。

7.4Zionts-Wallenius法（4）设决策者的潜在的选好函数为

这一函数的参数是不知道的，决策者不能给出具体数值。但是，如果引入决策者感到他的选好函数值有所改善，那就表示

（7-4-5）但是，如果引入

决策者感到他的选好函数值变坏，那就表示

（7-4-6）如果引入

，决策者感到他的选好函数没有变化，那就表示

（7-4-7）

7.4Zionts-Wallenius法（5）根据（3）和（4）的两个关键概念，可以给出搜索最优值的方法如下。引入基底会产生相邻非劣极点的非基变量为有效非基变量，将这一列的折中列向量提供给决策者，决策者经过判断，给出是否愿意进行折中的信息。①

如果愿意进行这一折中（引入这一非基变量

），表示他的选好函数有；②

如果他不愿意进行这一折中，表示他的选好函数有

；③

如果他认为这一折中没有什么差别，表示他的选好函数有因此，根据决策者是否愿意折中这一选好信息，可以由式（7-4-5）～式（7-4-7）搜索决策者潜在最优权值。

7.4Zionts-Wallenius法求解步骤

（1）选择一个适当的权向量

，求解（7-4-3），得到一个初始非劣极点

，设

。

（2）求

得所有导致相邻非劣极点的非基列。设这些非基列中尚未考查过的列下标集合为

。

（3）将每一个

的折中向量

提供给决策者，询问决策者是否愿意进行折中。

（4）用单纯形法求解以前循环中构成的式（7-4-5）～式（7-4-7）的可行解，要求满足

，

。令可行解为

。令

返回（2）。

7.4Zionts-Wallenius法【例7-3】求解产品生产问题。生产安排的数学模型如下：

为了对话需要，假设决策者潜在的选好函数为

7.4Zionts-Wallenius法（1）任意选择

，构成加权问题

用单纯形法求解，初始单纯形表7-5所示。

7.4Zionts-Wallenius法表7-5初始单纯形表

将

引入基，

退出基，经枢纽变换后的单纯形表7-6所示。

7.4Zionts-Wallenius法表7-6枢纽变换后的单纯形表

得到非劣极点

，目标值为

。

令

。

7.4Zionts-Wallenius法第一循环：（2）求相邻非劣极点。有两个非基变量

和

。在

列中，其判别数为

，全部为正，故将

引入基底将使两个目标均变坏。故引入

不能得到非劣极点。在

列中，其判别数为

，故可将

引入基底。为判别将其引入基底后相邻极点的非劣性，可构造如下线性规划问题。

7.4Zionts-Wallenius法第一循环：（2）求相邻非劣极点。有两个非基变量

和

。在

列中，其判别数为

，全部为正，故将

引入基底将使两个目标均变坏。故引入

不能得到非劣极点。在

列中，其判别数为

，故可将

引入基底。为判别将其引入基底后相邻极点的非劣性，可构造如下线性规划问题。

求解后得

7.4Zionts-Wallenius法（3）对话阶段。决策者的选好函数不能以显式表达，为模拟决策者的对话过程，假设它的选好函数为

将计算得到的数据提供给决策者：目前的最优解是

。如将

引入基底，则折中向量为

，即B产品增加一件，将使

减小0.1，使

增加0.5。问决策者是否愿意这一折中。决策者回答愿意这一折中，因为决策者判断其选好值将增加。于是可以构成式（7-4-5），即或

7.4Zionts-Wallenius法（4）求解