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

Question

Я пытаюсь настроить линейное программирование с использованием 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 BT.

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

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

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 

Каждый день имеет кумулятивный сумму < = 480M.

Answer 1

Мой простой непредвзятый подход:

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 
> 

Answer 2

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

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

> 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 

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