1

我正在使用 CVXOPT 来解决这个简单的优化问题：

maximize X1 + X2 
s.t:
 X2 + X6      = 2
 X1 + X2 + X5 = 2
 X1 + X4      = 2
 X1           >=0
 X2           >=0

显然这有一个非常简单的解决方案

 X1 = 1 
 X2 = 1

（其余均为0）

但是，cvxopt 完全错误。这就是我所做的：

>>> print A
  [ 0.00e+00  1.00e+00  0.00e+00  0.00e+00  0.00e+00  1.00e+00]
  [ 1.00e+00  1.00e+00  0.00e+00  0.00e+00  1.00e+00  0.00e+00]
  [ 1.00e+00  0.00e+00  0.00e+00  1.00e+00  0.00e+00  0.00e+00]

>>> print b
[ 2.00e+00]
[ 2.00e+00]
[ 2.00e+00]

>>> print G
[-1.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00]
[ 0.00e+00 -1.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00]

>>> print h
 [ 0.00e+00]
 [ 0.00e+00]

>>> print c
[-1.00e+00]
[-1.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]

（以上都是“矩阵”类型的cvxopt）

打印 glpk.ilp(c,G,h,A,b,I=set([0,1,2,3,4,5]))[1]

GLPK Integer Optimizer, v4.43
5 rows, 6 columns, 9 non-zeros
6 integer variables, none of which are binary

Preprocessing...
3 rows, 5 columns, 7 non-zeros
5 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 3
Solving LP relaxation...

GLPK Simplex Optimizer, v4.43

3 rows, 5 columns, 7 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
PROBLEM HAS UNBOUNDED SOLUTION
None
4

2 回答 2

3

以下是实现上述内容的代码：

import cvxopt.glpk
import cvxopt
c=cvxopt.matrix([1,1,0,0,0,0])
G=cvxopt.matrix([[1.0,0,0,0,0,0], [0,1,0,0,0,0]])
h=cvxopt.matrix([0.0,0.0])
A=cvxopt.matrix([[0.0,1,0,0,0,6], [1,1,0,0,1,0], [1,0,0,1,0,0]])
b=cvxopt.matrix([2.0, 2, 2])
(status, c)=cvxopt.glpk.ilp(-c,-(G.T),-h,A.T,b,I=set([0,1,2,3,4,5]))
print(status, c)

结果是：

optimal [ 0.00e+00]
[ 2.00e+00]
[ 0.00e+00]
[ 2.00e+00]
[ 0.00e+00]
[ 0.00e+00]

我不确定如何获得所有解决方案...

于 2013-05-24T01:08:54.677 回答
0

根据您提供的 LP，GLPK 是正确的。

(0.5,0.5,1.5,1,1.5) 是可行的

极端射线是 (1,1,-1,-2,-1)。

于 2015-03-25T08:56:50.320 回答