项目组合多目标规划问题的交互式求解法

摘自PM圈子网—项目管理牛人聚集地

在在项目组合管理中&＃xff0c;如何在确保实现企业战略目标的基础上&＃xff0c;兼顾各个项目的计划目标&＃xff0c;并自上而下地平衡和协调各个项目的资源使用&＃xff0c;从而使得企业的有限资源得到最大化地利用是项目组合资源优化管理中一大难题。

在实际问题中&＃xff0c;项目管理办公室可能会同时考虑以下这些方面都达到最优&＃xff1a;项目&＃xff21;完工时间必须最短&＃xff0c;项目&＃xff22;预算成本最低&＃xff0c;项目&＃xff23;质量最好&＃xff0c;项目&＃xff24;所使用的人员最少等。在这种情况下&＃xff0c;往往很难利用线性规划来解决问题。因为线性规划只研究在满足一定条件下&＃xff0c;单一目标函数取得最优解。这个最优解若是超过了实际的需要&＃xff0c;很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待&＃xff0c;这也不符合项目群中各个项目的优先级往往不同的实际情况。

为了弥补线性规划问题的局限性&＃xff0c;解决有限资源和计划指标之间的矛盾&＃xff0c;在线性规划基础上&＃xff0c;建立多目标规划方法&＃xff0c;从而使一些线性规划无法解决的问题得到满意的解答。 先将目标等级化&＃xff1a;将目标按重要性的程度不同依次分成一级目标、二级目标&＃xff0c;…&＃xff0c;最次要的目标放在次要的等级中。我们可以把目标优先级作如下约定&＃xff1a;

• 对同一个目标而言&＃xff0c;若有几个决策方案都能使其达到&＃xff0c;可认为这些方案就这个目标而言都是最优方案&＃xff1b;若达不到&＃xff0c;则与目标差距越小的越好。

• 不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失&＃xff0c;任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时&＃xff0c;首先从较高级别的目标达到的程度来决策&＃xff0c;然后再其次级目标的判断。

• 同一级别的目标可以是多个。各自之间的重要程度可用数量&＃xff08;权数&＃xff09;来描述。因此&＃xff0c;同一级别的目标的其中一个的损失&＃xff0c;可有其余目标的适当收获来弥补。

• 若多目标规划问题的解能使所有的目标都达到&＃xff0c;就称该解为多目标规划的最优解&＃xff1b;若解只能满足部分目标&＃xff0c;就称该解为多目标规划的次优解&＃xff1b;若找不到满足任何一个目标的解&＃xff0c;就称该问题为无解。

线性多目标规划问题(LMP)的数学表达式标准型为&＃xff1a;

min Z &＃61; C Y

s.t AX &＃43; Y’&＃43; Y” &＃61; b

X&＃xff0c;Y&＃xff0c;Y’ Y” > 0

这里 C、Y、A、X、Y’、Y” 、 b均为矩阵或向量的形式。

与线性规划相比&＃xff0c;多目标规划标准型的特点在于&＃xff1a;

1、 偏差列向量Y’ 、Y” 。Y’ 、Y” 分别为 负、正偏差列向量&＃xff0c;各有 m&＃xff08;m是约束方程的个数&＃xff09;个元素Y’、Y” 。负偏差变量的经济含义为当实际值小于目标值时&＃xff0c;实际值与目标值的偏差为负偏差&＃xff0c;正偏差变量的经济含义与之恰恰相反。

2、 价值系数行向量C。C的元素最多不超过 2m个&＃xff0c;由目标优先权等级 Pi和目标优先权系数η组成&＃xff0c;即 C &＃61; (c1,c2…&＃xff0c;c2m&＃xff09; &＃61; (η[1] * P[1], η[2] * P[2],…, η[2m] * P[2m])。目标优先权排序 P[1],P[2]&＃xff0c;…&＃xff0c;P[2m]给出了多目标规划迭代过程中实现目标的顺序。在实 现某一优先级目标后&＃xff0c;应依顺序考虑一个优先级能否实现。但是不能为实现较低目标而使较高级目标的实现受到影响。

3、 在多目标规划的目标函数中&＃xff0c;出现的变量 只能是偏差变量。也就是说&＃xff0c;列向量 y以正偏差变量和负偏差变量为元素。目标优先权等级 P[i]既不是变量&＃xff0c;也不是常数&＃xff0c;它只是说明不同目标实现的先后顺序&＃xff0c;这种优先等级的确定一般是由企业决策部门根据企业具体情况及各目标的轻重缓急加以确定 的。而目标优先级系数&＃xff0c;则说明同一优先级目标相互之间的比例关系。

4、 由于多目标规划的目标函数是向量值函数&＃xff0c;一般情况下不存在通常意义的最优解。因此多目标规划主要考虑使问题的向量目标在某种意义下非劣的有效解。而在无穷多个有效解中&＃xff0c;我们必须根据决策者的满意程度在有效集中寻找到最终满意解。

多目标规划的解法主要有单纯形法和图解法。图解法一般只适用于两个决策变量的情形。单纯形法对于求解多目标规划有普遍意义&＃xff0c;是一种较为传统的方法。该算法沿可行域逐步搜索极点&＃xff0c;直至得到所有的有效解&＃xff0c;然后再根据偏好从中选择一个满意解。在这一过程&＃xff0c;决策者并未参与其中&＃xff0c;使得搜索过程显得繁琐且计算量大。

在实际工作中&＃xff0c;项目管理办公室可以采用交互式单纯型算法让决策者参与搜索过程&＃xff0c;每次选择最适合自己偏好的进基向量&＃xff0c;这样每次得到的既是有效的极点解&＃xff0c;又向着最终满意解不断得到改善&＃xff0c;直至最终得到满意的解。具体算法步骤如下&＃xff1a;

(i) 构造LMP问题&＃xff0c;并求出一个初始有效极点解x’及对应的基&＃xff22;&＃xff1b;

(ii) 建立对应于基&＃xff22;的单纯型表&＃xff0c;计算n个目标函数在x’处的函数值Z&＃61;(z[1], z[2], …, z[n])&＃xff0c;如果决策者满意&＃xff0c;则得到最终的满意解&＃xff0c;否则转(iii);

(iii) 决策者根据理想点和偏好给出目标函数值的增减量Z’&＃61;(z[1]’, z[2]’, …, z[n]’)&＃xff0c;并求出x’的所有相邻有效极点解&＃xff0c;构成有效变量集K’&＃xff0c;并根据K’做凸规划&＃xff0c;得到弱有效解子集G。

(iv) 从G中&＃xff0c;挑选出有限个让决策者满意的解。并随机给定一组系数来构造

Q &＃61;{λ[1], λ[2],…, λ[n]},

λ[i] 取值在[0,1]之间&＃xff0c;且∑ λ[i] &＃61; 1&＃xff0c;从而到得

x”&＃61;{ λ[1] * X[1] &＃43; λ[2] * X[2], …, λ[n] * X[n] }。

若x”的正负符号与(iii)中一致&＃xff0c;则转(vi)&＃xff0c;否则转(v)&＃xff1b;

(v) 对&＃xff31;进行优先排序或加权优先排序&＃xff0c;并重新计算Z&＃xff0c;如果该解可以被决策者接受&＃xff0c;转(vi)&＃xff0c;否则转(iii).

(vi) 接受可行解Z&＃xff0c;并加以分析。

以上交互式规划法虽然不能给出全部解&＃xff0c;但可以保证每一步得到的解均为有效的极点解。而且在实现上容易用编程来实现&＃xff0c;从而在项目组合中的项目计划和筛选决策中起一定的辅助作用。