双目标0-1整数规划模型求解与ε-约束算法

模型（4.7a）—（4.7h）是双目标的0-1整数规划模型，本书采用ε-约束算法进行求解[388，389]。ε-约束算法解决双目标优化模型的基本思想是将其中一个目标函数转换为约束条件，从而将双目标优化模型转换为单目标优化模型进行求解。本书以模型（4.7a）—（4.7h）中目标函数Z2作为约束条件为例来说明ε-约束算法求解双目标优化模型的具体流程。

令S表示目标函数值集合，S=∅；迭代步长为θ。

Step 1：计算模型的正理想点）和负理想点）。其中，和分别表示当模型（4.7a）—（4.7h）只考虑目标函数Z1时的最优解对应的Z1和Z2值；和分别表示当模型（4.7a）—（4.7h）只考虑目标函数Z2时的最优解对应的Z2和Z1值。

Step 2:。

Step 3：若，则转向Step 4；否则，转向Step 5。

Step 4：采用分支定界算法或优化软件包Lingo、Cplex等求解如下的单目标优化模型（4.10a）—（4.10h）。令，其中和分别为模型（4.7a）—（4.7h）取得最优解时，目标函数Z1和Z2的值，且，转向Step 3。

Step 5：算法结束。S中的点即为算法获得的帕累托有效解。

依据ε-约束算法的基本理论，容易证明模型（4.10a）—（4.10h）的每个最优解都是双目标优化模型（4.7a）—（4.7h）的帕累托有效解。(www.xing528.com)

综上所述，针对基于序区间信息且考虑双边主体稳定性的一对多双边匹配问题，本章给出的双边匹配方法的步骤如下：

步骤1 依据Ai给出Bj的序区间信息和Ai匹配的理想位置[1，1]，采用式（4.1）计算，依据和Ai匹配的负理想位置[n，n]，采用式（4.2）计算；

步骤2 依据Bj给出的Ai序区间偏好信息和Bj匹配的理想位置[1，1]，采用式（4.4）计算，依据和Bj匹配的负理想位置[m，m]，采用式（4.5）计算；

步骤3 依据和采用式（4.3），计算Ai给出的乙方主体Bj的排序位置与理想位置的相对贴近度；依据和采用式（4.6）计算Bj给出的甲方主体Ai的排序位置与理想位置的相对贴近度；

步骤4 在考虑一对多稳定匹配基础上，构建以双边主体匹配对象与理想匹配对象排序位置的相对贴近度最大为优化目标的多目标优化模型（4.7a）—（4.7h）；

步骤5 采用ε-约束算法将多目标优化模型（4.7a）—（4.7h）转化为单目标优化模型（4.10a）—（4.10h）；

步骤6 采用分支定界法或Cplex 12.0、Lingo 11.0等软件，迭代求解模型（4.10a）—（4.10h），获得帕累托有效解。