确定最优匹配方案的优化方法

时间：2023-07-17 理论教育版权反馈

【摘要】：定理5.1 在考虑互惠偏好的双边匹配问题中，若对于Ai∈A，Bj∈B，θi+λj=1，则贪婪算法获得的匹配方案一定是稳定匹配。由于贪婪算法中的排序向量元素mij＞0，因此，匹配方案μ不可能被个体阻塞，即μ一定是个体理性匹配。定理5.2 贪婪算法获得的匹配方案一定是帕累托弱有效匹配。

确定最优匹配方案的优化方法

（1）双边匹配优化模型的构建与求解

依据Ai对Bj的总体满意度αij和Bj对Ai的总体满意度βij，可以构建以双边主体满意度最大为目标的多目标优化模型。设xij为0-1型决策变量，xij=1表示Ai与Bj进行匹配；否则xij=0。

在模型（5.7a）—（5.7h）中，式（5.7a）—（5.7b）是目标函数，式（5.7a）表示使甲方主体的总体满意度最大；式（5.7b）表示使乙方主体的总体满意度最大；式（5.7c）—（5.7h）为约束条件，式（5.7c）表示每个甲方主体最多与一个乙方主体进行匹配，式（5.7d）表示每个乙方主体最多与一个甲方主体进行匹配，式（5.7e）为一对一双边匹配的稳定性约束，其中M是一个足够大的正数；式（5.7f）能够保证不可接受对不能实现匹配。

模型（5.7a）—（5.7h）是一个多目标的0-1整数规划模型，本书采用基于隶属函数的加权和方法进行求解[141]。首先，采用的两个隶属函数μZ1和μZ2如下：

其中，Zmin1和Zmax1为单独考虑目标函数Z1的最小值和最大值；Zmin2和Zmax2为单独考虑目标函数Z2的最小值和最大值，0≤μZ1，μZ2≤1。

然后，将多目标优化模型（5.7a）—（5.7h）转换为如下的单目标优化模型：

其中，ω1和ω2分别表示目标函数Z1和Z2的重要性，且有0≤ω1，ω2≤1，ω1+ω2=1，为保证双边主体匹配的公平性，令ω1=ω2=0.5。

模型（5.10a）—（5.10b）是一个单目标的0-1整数规划模型，当双边匹配主体的数量较小时，可采用分支定界算法进行求解；当双边匹配主体的数量较大时，可采用优化软件包（如Lingo、Cplex等）或设计智能优化算法（如遗传算法、模拟退火算法等）进行求解。

（2）贪婪算法设计

由式（5.5）和式（5.6）可知，当θi+λj=1时，式（5.6）可化简为βij=（1-θi）q2（rij）+θiq1（sij）ij，由式（5.1）、式（5.2）、式（5.3）和式（5.4）可知，此时αij=βij。针对θi+λj=1这类问题的特点，设计了一个简单、快速获得稳定匹配的贪婪算法。具体算法的流程如下：

令μ为匹配对的集合，μ=∅，k=0；

Step 1：构建满意度矩阵M0=[mij]m×n，其中mij=αij=βij；

Step 2：将满意度矩阵M0中mij＞0的元素进行降序排列，并记排序向量为Tk；

Step 3：选择排序向量Tk中排在第一位的元素mij，令μ=μ∪{（Ai，Bj）}，删除Tk中的元素mig和mhj，g=1，2，…，n；h=1，2，…，m，并令k=k+1；

Step 4：若排序向量Tk为空，则算法停止；否则，转到Step 3。

上述贪婪算法的时间复杂度为O（mn×log（mn）），其中m和n分别表示甲方主体和乙方主体的数量或规模，由此可以看出本书设计的贪婪算法具有很高的求解效率，非常适用于求解大规模的双边匹配问题。

本书设计的贪婪算法不仅具有很高的求解效率，同时通过贪婪算法获得的匹配方案具有一些优良的性质，比如贪婪算法获得的匹配方案是稳定的、帕累托弱有效的等，下面给出具体的证明。

定理5.1 在考虑互惠偏好的双边匹配问题中，若对于∀Ai∈A，∀Bj∈B，θi+λj=1，则贪婪算法获得的匹配方案一定是稳定匹配。

证明：设采用贪婪算法获得的匹配方案为μ。由于贪婪算法中的排序向量元素mij＞0，因此，匹配方案μ不可能被个体阻塞，即μ一定是个体理性匹配。下面证明在贪婪算法中不可能出现可接受对（Ai，Bj）阻塞μ的情况，依据阻塞对的定义5.2可分为以下几种情况：

（i）μ（Ai）=Ai，μ（Bj）=Bj。μ（Ai）=Ai和μ（Bj）=Bj说明算法结束时Ai和Bj都没有匹配对象，而由于（Ai，Bj）是可接受对，即αij=βij=mij＞0，由此表明在算法结束时mij没有被删除而仍然在排序向量中。这显然与贪婪算法的结束条件矛盾，因此可接受对Ai和Bj是不会出现同时没有匹配对象的情况的。

（ii）μ（Ai）=Ai，μ（Bj）=Ak且βij＞βkj。由于βij=αij=mij＞βkj=αkj=mkj，因此，在排序向量中mij排在mkj之前。由贪婪算法的步骤可知，对于任意的Ap和Bq，只要在算法的第t（t≥3）步中Ap和Bq进行了匹配，那么在任意的第t′＞t步中Ap和Bq仍然是匹配对而不会出现Ap和Bq放弃对方的情况。μ（Ai）=Ai说明Ai在整个算法过程中一直没有匹配对象，而μ（Bj）=Ak且mij排在mkj之前，说明在mij成为排序向量中排在第1位的元素时，Ai和Bj都没有匹配对象，那么此时Ai和Bj一定会进行匹配，而不可能出现Ak和Bj进行匹配的情况。

同理可证μ（Ai）=Bh，μ（Bj）=Bj且αij＞αih的情况。

（iii）μ（Ai）=Bh，μ（Bj）=Ak且αij＞αih，βij＞βkj。由αij=βij=mij＞αih=βih=mih以及βij=αij=mij＞βkj=αkj=mkj可知，在排序向量中mij排在mih和mkj之前。由贪婪算法的步骤可知，任意的Ap和Bq，只要Ap和Bq在算法的第t（t≥3）步中进行了匹配，那么在任意的第t′＞t步Ap和Bq就不会放弃当前匹配对象与其他匹配主体进行重新匹配。μ（Ai）=Bh，μ（Bj）=Ak且在排序向量中mij排在mih和mkj之前，说明在mij成为排序向量中排在第1位的元素时，Ai和Bj都没有匹配对象，那么此时Ai和Bj一定会进行匹配，而不会出现Ai和Bh、Ak和Bj进行匹配的情况。

综上可知，通过贪婪算法获得的匹配方案中一定不会出现阻塞对，即贪婪算法获得的匹配方案一定是稳定匹配。

定理5.2 贪婪算法获得的匹配方案一定是帕累托弱有效匹配。

证明：设通过贪婪算法获得的匹配方案为ν，那么由定理5.1可知ν一定是稳定匹配。假设ν不是帕累托弱有效匹配，且存在一个匹配方案μ帕累托弱占优ν。那么由定义5.8和定义5.9可知，对于∀Ai∈A一定满足条件（1a）或（1b），对于∀Bj∈B一定满足条件（2a）或（2b）。下面证明满足这样条件的Ai和Bj并不存在。

（1）假设∃Ai∈A，μ（Ai）=Bg，ν（Ai）=Bh，且αig＞αih。若ν（Bg）=Bg，那么由于βig=αih＞αig=βih，因此是（Ai，Bg）匹配方案ν的阻塞对，显然这与ν是稳定匹配矛盾；若ν（Bg）=Ai，由于匹配方案μ帕累托弱占优ν，那么，由定义5.9可知，Bg对μ中匹配对象Ai的满意度大于对ν中匹配对象Ak的满意度，即βig＞βkg。又由于αig＞αih，因此，（Ai，Bg）是匹配方案ν的阻塞对，这与ν是稳定匹配矛盾。

（2）假设∃Ai∈A，ν（Ai）=Ai，μ（Ai）=Bg且αig＞αih=0。若ν（Bg）=Bg，由于βig=αig＞0，显然（Ai，Bg）是匹配方案ν的阻塞对，这与ν是稳定匹配矛盾；若ν（Bg）=Ak，由于μ占优ν，因此，Bg对μ（Bj）的满意度大于对ν中匹配对象的满意度，即βig＞βkg。又由于αig＞0，那么（Ai，Bg）一定是匹配方案ν的阻塞对，显然这与ν是稳定匹配矛盾。(www.xing528.com)

同理可证不存在∀Bj∈B满足（2c）或（2d），因此，不存在匹配方案μ弱占优匹配方案ν，所以贪婪算法获得的匹配方案一定是帕累托弱有效匹配。

定理5.3 贪婪算法获得的匹配方案不一定是帕累托有效匹配。

下面通过一个反例来说明定理5.3的正确性。

设双边主体的满意度矩阵为

满意度矩阵降序排列后的排序向量T0=（m13，m11，m21，m22，m33），然后采用贪婪算法获得的稳定匹配为ν={（A1，B3），（A2，B1）}。同时存在一个稳定匹配方案μ={（A1，B1），（A2，B2），（A3，B3）}。显然与匹配方案ν相比，在匹配方案μ中，在没有降低A1、A2、B1和B3的满意度的情况下，A3和B2获得了更高的满意度。因此，依据定义5.7和定义5.8可知，μ占优ν，ν不是帕累托有效匹配。

定理5.4 若对于∀Ai∈A，∀Bj∈B，θi+λj=1且αih≠αik（h≠k），βfj≠βgj（f≠g），则贪婪算法获得的匹配方案一定是帕累托有效匹配。

证明：设通过贪婪算法获得的稳定匹配为ν，若要证明ν是帕累托有效匹配可以证明不存在匹配方案占优ν。假设存在一个匹配方案μ占优ν，那么依据定义5.7可知，至少存在一个Ai满足（1c）或（1d）或至少存在一个Bj满足（2c）或（2d）。下面证明满足这样条件的Ai或Bj并不存在。

（i）假设存在ν（Ai）=Bh，μ（Ai）=Bg且αig＞αih。若ν（Bg）=Bg，显然（Ai，Bg）是匹配方案ν的阻塞对，这与ν是稳定匹配矛盾；若ν（Bg）=Ak，由于μ占优ν，因此，Bg对μ中匹配对象Ai的满意度不小于对ν中匹配对象Ak的满意度，即βig≥βkg。又由于∀Bj∈B，βhj≠βkj，h≠k，由此可得βig＞βkg。此外又由于αig＞αih，因此，（Ai，Bg）是匹配方案ν的阻塞对，即ν不是稳定匹配，显然这与ν是稳定匹配矛盾。

（ii）假设ν（Ai）=Ai，μ（Ai）=Bg且αig＞αi=0。若ν（Bg）=Bg，显然（Ai，Bg）是匹配方案ν的阻塞对，这与ν是稳定匹配矛盾；若ν（Bg）=Ak，由于μ占优ν，因此，Bg对μ（Bj）的满意度不小于对ν中匹配对象的满意度，那么一定存在βig≥βkg。又由于∀Bj∈B，βhj≠βkj，h≠k，由此可得βig＞βkg，并且由于αig＞0，因此（Ai，Bg）是匹配方案ν的阻塞对，即ν不是稳定匹配，显然这与ν是稳定匹配矛盾。

由（i）和（ii）可知满足条件（1c）或（1d）的Ai不存在，同理可证满足条件（2c）或（2d）的Bj不存在。因此，匹配方案μ占优ν的假设不成立，所以贪婪算法获得的稳定匹配ν一定是帕累托有效匹配。

定理5.5 若对于∀Ai∈A，∀Bj∈B，θi+λj=1且αih≠αik，h≠k，βfj≠βgj，f≠g，则考虑互惠偏好的双边匹配问题只有唯一的稳定匹配。

证明：设通过贪婪算法获得的稳定匹配为，其中，。

。

由于，由此可知，是满意度矩阵M0中的最大值，即，且h1≠ht，g1≠gt。此外，由于，因此，若与集合中的元素进行匹配或与集合中的元素进行匹配，则一定是阻塞对。换言之，只要和不进行匹配，则）一定是阻塞对，即在稳定匹配方案中，和一定是匹配对。

那么显然若与）或与进行匹配，则一定会形成阻塞对。此外，由于是满意度矩阵M0中除和之外的最大值，若与集合中的元素进行匹配或与集合中的元素进行匹配，则一定是阻塞对。因此，只要和不进行匹配，形成的匹配方案中就一定存在阻塞对，即在稳定匹配方案中，和一定是匹配对。以此类推，对于，只要和不形成匹配对，则形成的匹配方案就不是稳定匹配，即在稳定匹配中和一定是匹配对。