scipy.linprog处理含绝对值的线性规划问题疑问

我已掌握scipy.linprog基础线性规划（LP）问题的实现方法，例如：

目标函数：max 2x+3y
约束条件：
2x-y <= 0
5x+y >= -10

对应实现代码：

from scipy.optimize import linprog
c = [-2, -3]
A = [[2, -1], [-5, -1]]
b = [0, 10]

但在处理含绝对值的复杂LP场景时，存在以下几处疑问，希望得到解答指引：

疑问1：辅助矩阵A_aux的形状逻辑 #

已知将目标函数Minimize 1*abs(x_0)+1*abs(x_1)+…+1*abs(x_n)转化为Minimize 1*y_0+1*y_1+…+1*y_n时，需添加约束-y_i <= x_i <= y_i。这里的A_aux是用来将这组约束转化为scipy.linprog要求的标准A@x <= b格式：

• 每个原始变量x_i对应两个线性约束：x_i <= y_i（整理为x_i - y_i <= 0）和-y_i <= x_i（整理为-x_i - y_i <= 0）；
• 若原始变量有N个，新增的辅助变量y_i也有N个，总变量数为N+N。对应需要添加2*N行约束，因此A_aux的形状为(2*N, 2*N)。比如5个原始变量的场景下，A_aux就是10×10的矩阵。

疑问2：目标系数向量c的构造逻辑 #

构造c = np.hstack((np.zeros(N), np.ones(N_AUX)))的核心逻辑是匹配转化后的目标函数：

• 转化后的目标是最小化y_0 + y_1 + … + y_n，原始变量x_i不再参与目标计算，因此它们的系数设为0；
• 辅助变量y_i的系数全部设为1，因为要最小化它们的和。最终得到的向量前半段对应原始变量，后半段对应辅助变量，比如[0,0,0,0,0,1,1,1,1,1]就是5个原始变量+5个辅助变量的场景。

疑问3：添加辅助矩阵A_aux的原因及构造逻辑 #

添加A_aux是为了将绝对值的非线性约束转化为线性约束——scipy.linprog仅支持线性目标和线性约束，无法直接处理绝对值：

• 原始约束矩阵A_orig只描述原问题自带的线性约束，而绝对值转化出的-y_i <=x_i <=y_i是新增的约束，必须用A_aux来定义；
• 构造时，每对x_i和y_i对应两行系数：
  1. 第一行：x_i位置为1，y_i位置为-1，其余为0（对应x_i - y_i <= 0）；
  2. 第二行：x_i位置为-1，y_i位置为-1，其余为0（对应-x_i - y_i <= 0）。
     以此类推生成所有行，就得到了对应维度的A_aux矩阵。

疑问4：变量边界bnds的设置依据 #

bnds = [(0, 50) for i in range(N)] + [(None, None) for i in range(N_AUX)]的设置完全贴合问题需求：

• 前N个(0,50)是原始变量x_i的业务/数学边界，比如x_i代表生产数量，不能为负且有最大产能50，这是原问题自带的约束，和绝对值转化无关；
• 辅助变量y_i的边界设为(None, None)（无限制），因为通过-y_i <=x_i <=y_i的约束，已经能自动保证y_i >= abs(x_i) >=0，无需额外添加非负限制。

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