基于CPLEX的Python脚本求解两椭圆最短距离实现咨询
CPLEX求解两椭圆最短距离的Python实现方案
问题核心属性
- 该模型属于凸二次约束二次规划(QCQP):目标函数为两点距离平方的凸函数,椭圆约束满足
b²-4ac<0时对应凸闭集,不存在局部最优陷阱,CPLEX可直接求解得到全局最优解 - 最终最短欧氏距离为目标函数最优值的算术平方根
分步实现逻辑
- 环境准备
- 安装CPLEX本体,配置Python接口环境,推荐使用官方封装的
docplex建模库降低建模复杂度
- 安装CPLEX本体,配置Python接口环境,推荐使用官方封装的
- 椭圆文件读取与校验
- 逐行读取
ellipse.txt内容,跳过空行,按空格拆分每行的6个数值作为椭圆系数 - 逐行校验每个椭圆的
b²-4ac<0判定条件,不满足则抛出参数非法的错误,避免后续建模异常
- 逐行读取
- 优化模型构建
- 定义4个无边界连续决策变量:对应两个椭圆上点的坐标
(x1,y1)、(x2,y2) - 目标函数设置为最小化
(x1-x2)**2 + (y1-y2)**2 - 写入二次约束时修正原始模型的笔误:将错写的一次项
a1x21、c2y2替换为正确的二次项a1*x1**2、c2*y2**2,保证椭圆约束的正确性
- 定义4个无边界连续决策变量:对应两个椭圆上点的坐标
- 求解与结果输出
- 调用CPLEX求解引擎求解模型,提取目标值、最优坐标点,计算得到实际欧氏最短距离
核心参考代码
from docplex.mp.model import Model def load_ellipse_coeffs(file_path): ellipses = [] with open(file_path, "r", encoding="utf-8") as f: for line in f: stripped_line = line.strip() if not stripped_line: continue coeffs = list(map(float, stripped_line.split())) if len(coeffs) != 6: raise ValueError("椭圆系数行必须包含a,b,c,d,e,f共6个数值") a, b, c, d, e, f = coeffs if b**2 - 4*a*c >= 0: raise ValueError(f"当前系数不满足椭圆判定条件: b²-4ac = {b**2 -4*a*c:.2f} ≥0") ellipses.append(coeffs) if len(ellipses) !=2: raise ValueError("ellipse.txt 必须存储两个合法椭圆的全部系数") return ellipses def calc_min_ellipse_distance(e1_coeffs, e2_coeffs): # 初始化CPLEX模型 mdl = Model(name="ellipse_min_distance") # 定义决策变量 x1, y1 = mdl.continuous_var(name="x1"), mdl.continuous_var(name="y1") x2, y2 = mdl.continuous_var(name="x2"), mdl.continuous_var(name="y2") # 设置目标函数: 最小化距离平方 mdl.minimize((x1 - x2)**2 + (y1 - y2)**2) # 写入椭圆约束 a1, b1, c1, d1, e1, f1 = e1_coeffs mdl.add_constraint( a1*x1**2 + b1*x1*y1 + c1*y1**2 + d1*x1 + e1*y1 + f1 <= 0, ct_name="ellipse1_boundary" ) a2, b2, c2, d2, e2, f2 = e2_coeffs mdl.add_constraint( a2*x2**2 + b2*x2*y2 + c2*y2**2 + d2*x2 + e2*y2 + f2 <= 0, ct_name="ellipse2_boundary" ) # 执行求解 sol = mdl.solve(log_output=False) if not sol: raise RuntimeError("模型求解失败,无可行解") # 提取结果 dist_square = sol.objective_value min_dist = dist_square ** 0.5 p1 = (sol.get_value(x1), sol.get_value(y1)) p2 = (sol.get_value(x2), sol.get_value(y2)) return min_dist, p1, p2 if __name__ == "__main__": ellipses = load_ellipse_coeffs("ellipse.txt") min_dist, point_e1, point_e2 = calc_min_ellipse_distance(ellipses[0], ellipses[1]) print(f"两椭圆最短欧氏距离: {min_dist:.4f}") print(f"椭圆1上的最近点坐标: ({point_e1[0]:.4f}, {point_e1[1]:.4f})") print(f"椭圆2上的最近点坐标: ({point_e2[0]:.4f}, {point_e2[1]:.4f})")
关键注意事项
- 因问题本身是凸优化,无需开启CPLEX的非凸全局搜索参数(
optimalitytarget=3),默认求解配置即可达到1e-9以上的求解精度 - 可通过示例文件的几何化简结果校验代码正确性:示例文件中的两个椭圆化简后分别为中心(1,-2)、长半轴5的椭圆,和中心(-5,4)、短半轴3的椭圆,求解结果应和几何推算值匹配
- 若出现求解收敛慢的问题,可适当调整QCQP求解器的迭代上限,不建议随意修改目标和约束的数学形式
内容的提问来源于stack exchange,提问作者sss2411
相关产品推荐
相关产品推荐

