线性规划新手咨询：L1距离目标函数构建与LP问题求解

问题分析与修正点 #

1. 约束矛盾导致异常结果：你代码里同时添加了solver.Add(x<=5.0)和solver.Add(x>=7.0)，这两个约束完全冲突，x不可能同时满足，要么删除其中一个，要么调整为合理区间（比如x∈[5,7]）。
2. L1距离的线性化处理：L1距离是|x - x_pd| + |y - y_pd|，但线性规划求解器无法直接处理绝对值，必须引入辅助变量将绝对值转化为线性约束：
   • 对x方向的绝对值|x - x_pd|，引入辅助变量s_x，添加约束：x - x_pd <= s_x和x_pd - x <= s_x，这样s_x就等价于|x - x_pd|
   • 同理对y方向引入s_y，添加约束：y - y_pd <= s_y和y_pd - y <= s_y
3. 目标函数修正：将目标函数设为s_x + s_y，即可实现最小化两点间的L1距离。

修正后的完整代码 #

from ortools.linear_solver import pywraplp
from ortools.init import pywrapinit

solver = pywraplp.Solver.CreateSolver('GLOP')

# 预定义点
x_pd = 6
y_pd = 4 

# 决策变量：待求解的点(x,y)
x = solver.NumVar(0.0, 12.0, 'xr')
y = solver.NumVar(0.0, 8.0, 'yr')

# 辅助变量：用于线性化绝对值
s_x = solver.NumVar(0.0, solver.infinity(), 's_x')
s_y = solver.NumVar(0.0, solver.infinity(), 's_y')

# 修正后的约束（示例改为x∈[5,7]，避免矛盾）
solver.Add(x >= 5.0)
solver.Add(x <= 7.0)
solver.Add(y - y_pd <= 0)  # 保留原y的约束：y <= 4

# 线性化绝对值的约束
solver.Add(x - x_pd <= s_x)
solver.Add(x_pd - x <= s_x)
solver.Add(y - y_pd <= s_y)
solver.Add(y_pd - y <= s_y)

# 目标函数：最小化L1距离
solver.Minimize(s_x + s_y)

status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print('Solution:')
    print('Objective value (L1距离) =', solver.Objective().Value())
    print('x =', x.solution_value())
    print('y =', y.solution_value())
elif status == pywraplp.Solver.INFEASIBLE:
    print('问题无解：约束存在矛盾，请检查约束条件')
else:
    print('无法找到最优解')

代码解释 #

• 辅助变量s_x和s_y的取值范围设为0到无穷大，因为绝对值结果是非负的
• 修正后的x约束改为[5,7]，你可以根据实际需求调整区间或约束条件
• 目标函数s_x + s_y等价于两点间的L1距离，求解器会找到满足所有约束的点中，离预定义点L1距离最小的点

LP建模与约束规划参考资料 #

• 《线性规划导论》：入门级经典教材，从基础概念到建模方法讲解透彻，适合新手快速上手
• OR-Tools官方文档：Google的OR-Tools自带大量线性规划示例和教程，结合你使用的工具直接实践效率很高
• 《运筹学导论》：全面覆盖各类优化问题，包括线性规划、整数规划等，适合系统学习运筹学知识

内容的提问来源于stack exchange，提问作者Ken Adams