通过matlab的线性规划函数解决完美匹配问题
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点相切圆半径小些,增加了 护城河的宽度值。而前后两种算法的增减量之和是相同的。
完美匹配问题满足的规划问题如下:
由于护城河(moat)都是在相切圆之后确定的,因此先使护城河的宽度 为0,则上面的规划问题就变为了:
下面通过matlab来求解上述的线性规划问题。由于有10个坐标点,第一步求解点集间的距离矩阵如图5:
之后列 的约束不等式,由于有10个点,且 ,所以一共有9+8+....1=45个不等式。将其系数列入表格并且带入距离值可得:
使用matlab的linprog求解函数求解此线性规划问题的解,其中满足
求得的结果如图8所示:
此结果为每个坐标点为圆心的最大半径值,绘制出如图9所示:
根据上图可以简单地画出完美匹配问题的结果:
将其和GEODUAL软件中的结果对比,发现线段匹配的结果相同,但是相切圆的画法出现了问题,其中软件输出的B和G点相切圆半径差距较大,导致G圆无法与D圆相切从而产生 的护城河,但是根据笔者计算的结果左方的护城河集合应该是 。笔者认为,应该是线性规划所用的计算公式不同导致的,笔者的算法先省略了护城河的宽度,计算完相切圆半径后再确定护城河宽度,而GEOGUAL中是连带护城河宽度一起计算的,因此存在多组线性规划的最优解,其中一组是笔者的,G点相切圆半径大些,省去了 护城河的宽度值。而软件计算的是使G点相切圆半径小些,增加了 护城河的宽度值。而前后两种算法的增减量之和是相同的。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
光点科技
2023-08-15 广告
2023-08-15 广告
通常情况下,我们会按照结构模型把系统产生的数据分为三种类型:结构化数据、半结构化数据和非结构化数据。结构化数据,即行数据,是存储在数据库里,可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据,它们可以某种标准格式存在于文件...
点击进入详情页
本回答由光点科技提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询