将绝对偏差编程为线性程序

Question

我正在尝试将绝对偏差之和转换为线性规划问题，以便我可以使用 CPLEX（或其他求解器）。我坚持如何设置矩阵。问题如下：

minimize abs(x1 - 5) + abs(x2 - 3)
s.t. x1 + x2 = 10

我设置了以下约束以将问题转换为线性形式：

  x1 - 5  <= t1
-(x1 - 5) <= t1 and 

  x2 - 3  <= t2
-(x2 - 3) <= t2

我已经将 objective 函数设置为

c = [0,0,1,1]

但我不知道如何设置

Ax <= b

矩阵形式。我目前拥有的是：

A = [[ 1, -1, 0, 0],
     [-1, -1, 0, 0],
     [ 0,  0, 1,-1],
     [ 0,  0,-1,-1]]
b =  [ 5, -5, 3,-3]

我已经在矩阵中设置了另一个约束为：

B =  [1, 1, 0, 0]
b2 = [10]

当我运行以下内容时：

linprog(c,A_ub=A,b_ub=b,A_eq=B,b_eq=b2,bounds=[(0,None),(0,None)])

我收到以下错误消息：

ValueError: Invalid input for linprog: A_eq must have exactly two dimensions, and the number of columns in A_eq must be equal to the size of c

我知道有一个解决方案，因为当我使用 scipy.optimize.minimize 时，它解决了 [6,4]。我确定问题是我没有正确地制定输入矩阵，但我不确定如何设置它们以便运行s.

编辑 - 这是不运行:

的代码

import numpy as np
from scipy.optimize import linprog, minimize

c = np.block([np.zeros(2),np.ones(2)])
print("c =>",c)

A = [[ 1, -1, 0, 0],
     [-1, -1, 0, 0],
     [ 0,  0, 1,-1],
     [ 0,  0,-1,-1]]

b =  [[ 5, -5, 3,-3]]
print(A)
print(np.multiply(A,b))

B = [ 1, 1, 0, 0]
b2 = [10]
print(np.multiply(B,b2))

linprog(c,A_ub=A,b_ub=b,A_eq=B,b_eq=b2,bounds=[(0,None),(0,None)],
        options={'disp':True})

Answer 1

我觉得这个消息很好。 B 应该是二维矩阵而不是一维向量。所以：

B =  [[1, 1, 0, 0]]

其次，边界数组太短。第三，您的变量排序不一致。 A 中的列是 x1,t1,x2,t2，而 B（和 c）中的列似乎是 x1,x2,t1,t2。他们需要遵循相同的方案。

将绝对偏差编程为线性程序

Programming absolute deviation as linear program

python

optimization

linear-programming

scipy-optimize