Пакет lpSolve, кажется, дает странные результаты

Я использую пакет R "lpSolve", загруженный по ссылке Cran И вроде странные ответы дает. Я хотел убедиться, что это не я все испортил (что, вероятно, так и есть).

Например, проблема, которую я пытаюсь решить,

maximize -3x-2y
s.t       5x -y <=  1
         -2x-2y <= -1
         -3x-2y <=  0

Настройки, которые у меня есть в R:

> obj
   -3 -2
> cond
    5   -1
   -2   -2
   -3   -2
> dir
   "<=" "<=" "<="
> rhs
   1 -1  0

С этим применяется к функции lp в lp.solve

> lp(direction="max", objective.in=obj, const.mat=cond, const.dir=dir, const.rhs=rhs)$objval

Это возвращает -1, однако я знаю, что решение равно 0 вместо -1.

Я также попытался вместо этого установить цель как «мин», и я получаю:

> lp(direction = "max", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)$objval
[1] -1
> lp(direction = "min", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)$objval
[1] 0

Как это возможно, что я получаю большее значение, когда пытаюсь минимизировать цель? Это как-то связано с отрицательным коэффициентом при x? Я просмотрел руководство по пакету и не увидел никаких связанных требований к целевой функции.


r linear-programming convex-optimization lpsolve
person Yue Y    schedule 20.11.2017    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Вы правы в том, что (x, y) = (-1, 1.5) дает объективное значение 0, которое, исходя из ограничений, явно является максимально возможным.

То, что удерживает вас от получения этого, это следующая строка в ?lp:

Обратите внимание, что предполагается, что каждая переменная >= 0!

В предположении, что каждая переменная неотрицательна, действительно -1 - это лучшее, что вы можете сделать.

Чтобы решить исходную задачу, вы можете определить неотрицательные переменные решения x+ и x- для представления положительных и отрицательных частей x и сделать то же самое для y. Вот результирующая модель оптимизации:

mod <- lp(direction = "max",
          objective.in = c(obj, -obj),
          const.mat = cbind(cond, -cond),
          const.dir = dir,
          const.rhs = rhs)
mod$objval
# [1] 0
mod$solution[1:2] - mod$solution[3:4]
# [1] -1.0  1.5

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

Наконец, причина, по которой ваша минимизация выглядела так, как будто она давала вам объективное значение 0, заключается в том, что она на самом деле не ограничена и не установила значение objval в своем ответе:

lp(direction = "min", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)
# Error: status 3
person josliber♦    schedule 20.11.2017