Назначьте веса в lpSolveAPI для определения приоритетов переменных

Я пытаюсь настроить решение для линейного программирования, используя lpSolveAPI и R, для решения задачи планирования. Ниже приведен небольшой образец данных; минуты, необходимые для каждого идентификатора сеанса, и их "предпочтительный" порядок / вес.

id <- 1:100
min <- sample(0:500, 100)
weight <- (1:100)/sum(1:100)
data <- data.frame(id, min, weight)

То, что я хочу сделать, это упорядочить / запланировать эти идентификаторы сеансов так, чтобы в день было максимальное количество сеансов, предпочтительно по их весу, и каждый день ограничивался в общей сложности 400 минутами.

Вот как я настроил это в настоящее время в R:

require(lpSolveAPI)

#Set up matrix to hold results; each row represents day
r <- 5
c <- 10
row <- 1

results <- matrix(0, nrow = r, ncol = c)
rownames(results) <- format(seq(Sys.Date(), by = "days", length.out = r), "%Y-%m-%d")

for (i in 1:r){
    for(j in 1:c){  
        lp <- make.lp(0, nrow(data)) 
        set.type(lp, 1:nrow(data), "binary")
        set.objfn(lp, rep(1, nrow(data)))
        lp.control(lp, sense = "max")
        add.constraint(lp, data$min, "<=", 400)
        set.branch.weights(lp, data$weight)

        solve(lp)
        a <- get.variables(lp)*data$id
        b <- a[a!=0]

        tryCatch(results[row, 1:length(b)] <- b, error = function(x) 0)

        if(dim(data[!data$id == a,])[1] > 0) {
            data <- data[!data$id== a,]
            row <- row + 1
        }
        break

    }
}

sum(results > 0)    

barplot(results) #View of scheduled IDs

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

Я попытался назначить разные веса, веса в обратном порядке и т. Д., Но по какой-то причине моя установка, кажется, не обеспечивает "set.branch.weights".

Я прочитал документацию по "set.branch.weights" из lpSolveAPI, но думаю, что я здесь что-то не так делаю. Я новичок в R кстати.

Любая помощь приветствуется. ТИА

Пример - Данные:

   id   min weight
    1   67  1
    2   72  2
    3   36  3
    4   91  4
    5   80  5
    6   44  6
    7   76  7
    8   58  8
    9   84  9
    10  96  10
    11  21  11
    12  1   12
    13  41  13
    14  66  14
    15  89  15
    16  62  16
    17  11  17
    18  42  18
    19  68  19
    20  25  20
    21  44  21
    22  90  22
    23  4   23
    24  33  24
    25  31  25

должно быть

    Day 1   67  72  36  91  80  44  76          
    Day 2   58  84  96  21  1   41  66  89      
    Day 3   62  11  42  68  25  44  90  4   33  31

Каждый день имеет накопленную сумму <= 480м.

Источник

2 ответа

Решение

Мой простой подход:

df = read.table(header=T,text="
 id   min weight
  1   67  1
  2   72  2
  3   36  3
  4   91  4
  5   80  5
  6   44  6
  7   76  7
  8   58  8
  9   84  9
  10  96  10
  11  21  11
  12  1   12
  13  41  13
  14  66  14
  15  89  15
  16  62  16
  17  11  17
  18  42  18
  19  68  19
  20  25  20
  21  44  21
  22  90  22
  23  4   23
  24  33  24
  25  31  25")
# assume sorted by weight 

daynr = 1
daymax = 480
dayusd = 0
for (i in 1:nrow(df))
{
  v = df$min[i]
  dayusd = dayusd + v
  if (dayusd>daymax)
  {
    daynr = daynr + 1
    dayusd = v
  }
  df$day[[i]] = daynr
}

Это даст:

 > df
    id min weight day
 1   1  67      1   1
 2   2  72      2   1
 3   3  36      3   1
 4   4  91      4   1
 5   5  80      5   1
 6   6  44      6   1
 7   7  76      7   1
 8   8  58      8   2
 9   9  84      9   2
 10 10  96     10   2
 11 11  21     11   2
 12 12   1     12   2
 13 13  41     13   2
 14 14  66     14   2
 15 15  89     15   2
 16 16  62     16   3
 17 17  11     17   3
 18 18  42     18   3
 19 19  68     19   3
 20 20  25     20   3
 21 21  44     21   3
 22 22  90     22   3
 23 23   4     23   3
 24 24  33     24   3
 25 25  31     25   3
 >
Источник

Я сосредоточусь на первом решении. Мы в основном решаем проблему ранца (цель + одно ограничение):

Когда я запускаю эту модель, как я получаю:

> solve(lp)
[1] 0
> x <- get.variables(lp)
> weightx <- data$weight * x
> sum(x)
[1] 14
> sum(weightx)
[1] 0.5952381

Теперь, когда я меняю цель на

Я получил:

> solve(lp)
[1] 0
> x <- get.variables(lp)
> weightx <- data$weight * x
> sum(x)
[1] 14
> sum(weightx)
[1] 0.7428571

Т.е. счет остался на 14, но вес улучшился.

Источник
Другие вопросы по тегам