You need to enable JavaScript to run this app. 基于CPLEX的Python脚本求解两椭圆最短距离实现咨询
优惠活动
大模型
产品
解决方案
定价
更多

基于CPLEX的Python脚本求解两椭圆最短距离实现咨询

CPLEX求解两椭圆最短距离的Python实现方案

问题核心属性

  • 该模型属于凸二次约束二次规划(QCQP):目标函数为两点距离平方的凸函数,椭圆约束满足b²-4ac<0时对应凸闭集,不存在局部最优陷阱,CPLEX可直接求解得到全局最优解
  • 最终最短欧氏距离为目标函数最优值的算术平方根

分步实现逻辑

  1. 环境准备
    • 安装CPLEX本体,配置Python接口环境,推荐使用官方封装的docplex建模库降低建模复杂度
  2. 椭圆文件读取与校验
    • 逐行读取ellipse.txt内容,跳过空行,按空格拆分每行的6个数值作为椭圆系数
    • 逐行校验每个椭圆的b²-4ac<0判定条件,不满足则抛出参数非法的错误,避免后续建模异常
  3. 优化模型构建
    • 定义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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.08 15:06:04