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 です)

print 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 に答える