использование cvxopt для задач LP только с Aeq=beq (без ограничений с A*x‹=b)

Я пытаюсь решить задачу линейного программирования вида

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

для транспортной задачи.

Однако использование CVXOPT требует определения переменных G.x ‹= h для решателя lp(G,h,A,b).

Я попытался создать свои матрицы A и b, а для матриц G и h я использую единичную матрицу для G (умноженную на -1) и вектор нулей для h, чтобы наложить ограничения x>=0.

Однако, когда я запускаю свой код, он возвращает «сингулярную матрицу KKT».

Может ли кто-нибудь помочь мне с проблемой, или как я могу запустить решатель CVXOPT без переменных G и h.


python linear-programming convex-optimization
person mtigger    schedule 22.02.2013    source источник
comment
Почему бы вам не использовать решатель LP (линейное программирование)? CVXOPT предназначен для выпуклой оптимизации, которая намного сложнее, чем LP. См. мой предыдущий ответ здесь.   -  person Ali    schedule 22.02.2013
comment
Да, сейчас я пытаюсь использовать PuLP и Pyglpk. Благодарность! @Али   -  person mtigger    schedule 23.02.2013

Ответы (2)


arrow_upward
0
arrow_downward

Оптимальное решение транспортной задачи ищется с помощью потенциального метода. Чтобы использовать потенциальный метод, вы должны решить трехуровневое уравнение. Сетевые проблемы, такие как транспортная проблема, должны решаться с помощью двойной задачи, пожалуйста.

person GMHMH    schedule 13.06.2013

arrow_upward
0
arrow_downward

Ваше решение (-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]
person nampi    schedule 26.04.2015