模型构建与求解的优化方法

在具有偏好序信息的家政服务人员与雇主双边匹配问题中，为了获得家政服务人员与雇主的稳定匹配方案，在考虑双边匹配稳定性的条件下，以家政服务人员和雇主的满意度最大为目标建立双目标优化模型，并采用模糊优化算法求解双目标优化模型来获得最优稳定匹配方案。

为了获得家政服务人员和雇主的最优稳定匹配方案，依据偏好排序rij和pij可以构建获得稳定匹配的双目标优化模型。设xij为0-1型决策变量，xij=1表示家政服务人员Si与Ej进行匹配；否则xij=0。

在模型（6.1a）—（6.1f）中，式（6.1a）—（6.1b）是目标函数，式（6.1a）表示使家政服务人员的满意度最大；式（6.1b）表示使雇主的满意度最大；式（6.1c）—（6.1f）为约束条件，式（6.1c）和式（6.1d）为匹配数量约束，式（6.1c）表示每个家政服务人员最多与一个雇主进行匹配，式（6.1d）表示每个雇主最多与一个家政服务人员进行匹配；式（6.1e）为家政服务人员与雇主的稳定匹配约束。

模型（6.1a）—（6.1f）是一个双目标的0-1整数规划模型，本书采用Zimmermann提出的求解多目标规划的模糊优化方法[387，393]进行求解。模糊优化方法的基本思想是将一个多目标线性规划问题转换为一个等价的具有单一目标的模糊线性规划问题。首先给出如下两个隶属函数的定义：

其中，和为单独考虑目标函数Z1的最大值和最小值，和为单独考虑目标函数Z2的最大值和最小值。

根据双边匹配理论中稳定匹配性质可知，采用Gale-Shapley算法可以获得家政服务人员的最优稳定匹配和雇主最优稳定匹配，并且。因此，通过Gale-Shapley算法可以计算Z1和Z2的最值，从而方便的构造隶属函数u1（Z1）和u2（Z2）。

通过式（6.2）和（6.3）中的两个隶属函数，可以将双目标的优化模型（6.1a）—（6.1f）转换为如下单目标的模糊目标规划模型（6.4a）—（6.4g）。

其中λ为满意度水平。

模型（6.4a）—（6.4g）是一个混合型的整数规划模型，可采用分支定界算法或使用一些优化软件如Lingo 14.0、Cplex 12.1等求解。(www.xing528.com)

综上所述，针对基于偏好序信息的家政服务人员与雇主双边匹配问题，本节给出的双边匹配方法的步骤如下：

步骤1 获得家政服务人员Si给出的关于雇主的偏好序值向量Ri，获得雇主Ej给出的关于家政服务人员的序值向量Pj；

步骤2 依据家政服务人员的偏好序值向量Ri和雇主Ej的偏好序值向量Pj，构建考虑匹配稳定性的优化模型（6.1a）—（6.1f）；

步骤3 采用Gale-Shapley算法分别获得家政服务人员的最优稳定匹配方案和；

步骤4 依据和，构建隶属函数（6.2）和（6.3）；

步骤5 采用模糊优化方法将多目标优化模型（6.1a）—（6.1f）转换为（6.4a）—（6.4g）；

步骤6 可采用分支定界算法或使用一些优化软件如Lingo、Cplex等求解单目标优化模型（6.4a）—（6.4g），获得最优稳定匹配方案。