Question

通过matlab的线性规划函数解决完美匹配问题

Answer 1

前文《GEODUAL软件说明书之完美匹配问题》中介绍了使用软件求解完美匹配问题的步骤和理论。现在通过matlab的线性规划求解器，从问题源头出发，手动求解完美匹配问题。本例采用10个点的匹配问题。坐标如图1，2所示：

完美匹配问题满足的规划问题如下：

由于护城河（moat）都是在相切圆之后确定的，因此先使护城河的宽度 为0，则上面的规划问题就变为了：

下面通过matlab来求解上述的线性规划问题。由于有10个坐标点，第一步求解点集间的距离矩阵如图5：

之后列 的约束不等式，由于有10个点，且 ，所以一共有9+8+....1=45个不等式。将其系数列入表格并且带入距离值可得：

使用matlab的linprog求解函数求解此线性规划问题的解，其中满足

求得的结果如图8所示：

此结果为每个坐标点为圆心的最大半径值，绘制出如图9所示：

根据上图可以简单地画出完美匹配问题的结果：

将其和GEODUAL软件中的结果对比，发现线段匹配的结果相同，但是相切圆的画法出现了问题，其中软件输出的B和G点相切圆半径差距较大，导致G圆无法与D圆相切从而产生 的护城河，但是根据笔者计算的结果左方的护城河集合应该是 。笔者认为，应该是线性规划所用的计算公式不同导致的，笔者的算法先省略了护城河的宽度，计算完相切圆半径后再确定护城河宽度，而GEOGUAL中是连带护城河宽度一起计算的，因此存在多组线性规划的最优解，其中一组是笔者的，G点相切圆半径大些，省去了 护城河的宽度值。而软件计算的是使G点相切圆半径小些，增加了 护城河的宽度值。而前后两种算法的增减量之和是相同的。