Пакет R lpSolve не находит оптимального решения

Я пытаюсь решить следующую проблему оптимизации с помощью пакета R lpSolve:

1.007825*x1 +12.000000*x2 +15.99492*x3 +14.00307*x4 +31.97207*x5 +30.97376*x6 >= 10
1.007825*x1 +12.000000*x2 +15.99492*x3 +14.00307*x4 +31.97207*x5 +30.97376*x6 <= 15
       1*x1        - 2*x2       + 0*x3        -1*x4        +0*x5        -3*x6 <=  2
         xi >= 0, where i = [1,2,3,4,5,6]

Моя целевая функция:

1.007825*x1 +12.000000*x2 +15.99492*x3 +14.00307*x4 +31.97207*x5 +30.97376*x6

Создаю матрицу ограничений стандартного вида (A):

           [,1] [,2]      [,3]      [,4]      [,5]      [,6]
 [1,] -1.007825  -12 -15.99492 -14.00307 -31.97207 -30.97376
 [2,]  1.007825   12  15.99492  14.00307  31.97207  30.97376
 [3,]  1.000000   -2   0.00000  -1.00000   0.00000  -3.00000
 [4,] -1.000000    0   0.00000   0.00000   0.00000   0.00000
 [5,]  0.000000   -1   0.00000   0.00000   0.00000   0.00000
 [6,]  0.000000    0  -1.00000   0.00000   0.00000   0.00000
 [7,]  0.000000    0   0.00000  -1.00000   0.00000   0.00000
 [8,]  0.000000    0   0.00000   0.00000  -1.00000   0.00000
 [9,]  0.000000    0   0.00000   0.00000   0.00000  -1.00000

Создаю матрицу границ (б):

      [,1]
 [1,]  -10
 [2,]   15
 [3,]    2
 [4,]    0
 [5,]    0
 [6,]    0
 [7,]    0
 [8,]    0
 [9,]    0

и целевая функция (f):

f = c(1.007825, 12.000000, 15.99492, 14.00307, 31.97207, 30.97376)

Когда я вставляю это в код:

out = lp("min",f,A,rep("<=",9),b,all.int=TRUE),

Я получаю решение c (0,0,0,1,0,0), хотя знаю, что это решение c (0,1,0,0,0,0). Если изменить правую границу (вместо 15 я сделаю 13), все заработает. В чем может быть проблема?


linear-programming integer-programming
person Kirill    schedule 19.11.2016    source источник
comment
Это страшно, я бы предпочел другой решатель.   -  person Erwin Kalvelagen    schedule 21.11.2016

Ответы (1)


arrow_upward
2
arrow_downward

С lpSolveAPI проблема решается нормально:

library(lpSolveAPI)
lprec <- make.lp(0, ncol=6)
set.type(lprec, columns=seq(1,6), type="integer")
set.objfn(lprec, obj=c(1.007825, 12, 15.99492, 14.00307, 31.97207, 30.97376))

add.constraint(lprec, xt=c(1.007825, 12, 15.99492, 14.0030, 31.97207, 30.97376), type=">=", rhs=10)
add.constraint(lprec, xt=c(1.007825, 12, 15.99492, 14.0030, 31.97207, 30.97376), type="<=", rhs=15)
add.constraint(lprec, xt=c(1, -2, 0, -1, 0, -3), type="<=", rhs=2)

solve(lprec)
get.variables(lprec)

возвращается

[1] 0 1 0 0 0 0
person Karsten W.    schedule 21.11.2016
comment
Спасибо. Я проверю и дам вам знать. - person Kirill; 22.11.2016
comment
Ага, работает. Еще один вопрос: знаете ли вы, все ли MILP выдают приблизительные целые числа? Я имею в виду, что если число достаточно близко, то оно считается целым. - person Kirill; 23.11.2016
comment
См. LP-релаксацию для описания алгоритма, который вычисляет точные решения. - person Karsten W.; 23.11.2016