Как реализовать двоичное ограничение в LPSolve? - PullRequest
Новая
       71

Как реализовать двоичное ограничение в LPSolve?

0 голосов
/ 22 апреля 2020

Я пытаюсь решить проблему оптимизации с помощью линейного программирования. У меня есть список продуктов, по которым я знаю содержание нескольких питательных веществ. Цель состоит в том, чтобы найти комбинацию продуктов, которая дает наиболее близкое решение для определенной потребности в питательных веществах. В RI написали сценарий, который способен решить эту проблему. 

library(lpSolveAPI)

# Required nutrients
nitrogen = 1500
phosphate = 530

# Product properties (sample dataset, this will later be expanded with more products and nutrients)
products <- data.frame(
  p1 = c(0.2, 0.1),
  p2 = c(0.8, 0),
  p3 = c(0.15, 0.2),
  p4 = c(0.1, 0.25),
  p5 = c(0, 0.4)
)

# Create model
model <- make.lp(nrow = 2, ncol = ncol(products))

# Add the products as decisions
for (p in 1:ncol(products)) {
  set.column(model, p, products[, p])
}

# Set the required amount as constraint 
set.constr.value(model, rhs = c(nitrogen, phosphate))
set.constr.type(model, types = c(2,2))

# Set the objective function
set.objfn(model, rep(1, ncol(products)))
lp.control(model, sense='min')

solve(model)
get.objective(model)

Однако теперь я хочу добавить ограничение, согласно которому можно использовать не более определенного количества (например, 2) продуктов. Я думал о добавлении бинарного ограничения, но не могу понять, как это реализовать. Единственный вариант, который мне удалось определить, - это установить переменную решения в двоичную форму, но это не дает возможности использовать несколько единиц товара.

Так как же добавить ограничение, чтобы не использовать более 2 или 3 продукта?

1 Ответ

1 голос
/ 22 апреля 2020

Всегда сначала записывайте математическую модель. Особенно это касается низкоуровневых форматов ввода. Шаг от идеи к коду слишком велик.

Таким образом, у вас есть в основном: 

min sum(j, x(j))
st  sum(j, a(i,j)*x(j)) >= b(i)  for i=1,2
    x(j) >= 0

Теперь вы хотите считать ненулевые переменные. Это требует дополнительных двоичных переменных и некоторых границ для x (j). 

min sum(j, x(j))
st  sum(j, a(i,j)*x(j)) >= b(i)  for i=1,2
    x(j) <= U(j)*y(j)
    sum(j, y(j)) <= 2 (or 3)
    y(j) ∈ {0,1} 
    0 <= x(j) <= U(j)

Я оставлю вам право переписать это в код. Обратите внимание, что CVXR или OMPR может быть проще в использовании, чем LpSolveAPI, когда модель становится немного более сложной.

...