使用cvxopt解决仅有Aeq=beq的线性规划问题（无A*x<=b约束）

Question

我正在尝试解决一个线性规划问题，具体是一个运输问题。

minimise cT.x
A.x = b
x >= 0

不过，使用CVXOPT这个工具时，需要定义变量G.x <= h，以便给lp(G,h,A,b)这个求解器使用。

我已经尝试创建我的A和b矩阵，而对于G和h矩阵，我用一个单位矩阵（乘以-1）作为G，h则用一个全零的向量，这样可以强制要求x>=0的约束。

但是，当我运行我的代码时，出现了“奇异的KKT矩阵”的错误。

有没有人能帮我看看问题出在哪里，或者我如何能在没有G和h变量的情况下运行CVXOPT求解器。

Answer 1

你的解决方案（-G 是单位矩阵，h 是零向量）应该是有效的。你可以把你的数据发到这里。

比如说：

from cvxopt import matrix, solvers
c = matrix([ 2.0, 1.0 ])
G = matrix(-np.eye(2))
h = matrix(np.zeros(2)) 
A = matrix(np.eye(2))
b = matrix([1., 2.])
sol = solvers.lp(c, G, h, A, b)
print(sol['x'])

Optimal solution found.
[ 1.00e+00]
[ 2.00e+00]

Answer 2

运输问题的最佳解决方案是通过潜力法来寻找的。要使用潜力法，你需要解决三个层次的方程。像运输问题这样的网络问题必须通过对偶问题来解决。