Я изучаю некоторые задачи линейного программирования со всеми бинарными переменными, где необходимо подсчитать (а затем либо ограничить, либо максимизировать / минимизировать) количество различных элементов в решении.
Этопост, который я мог найти, который мне показался наиболее близким:
https://stats.stackexchange.com/questions/136608/constrained-assignment-problem-linear-programming-genetic-algorithm-etc
В этом случае подсчитываются «предметы», используемые центры снабжения.Я пытаюсь понять, подходит ли подход, предложенный в приведенном выше посте, для моих целей.
В ответе пользователя «TAS», пример - 3 магазина по 2 центрам снабжения, и идея такова (A) назначить один (и только один) центр снабжения каждому магазину так, чтобы: (B) пройденное расстояние было минимальным, (C) ни один центр снабжения не должен поставлять больше заданного максимального количества магазинов (в данном случае 3, т.е.без ограничений) и (D) максимальное общее количество используемых центров снабжения ограничено (в данном случае до 2).
Я попытался восстановить способ постановки задачи, начиная с набора данных, подобногоВ моем случае это было бы.
df <- cbind(expand.grid(shop=1:3,supply=1:2),distance=c(2.8,5.4,1.4,4.2,3.0,6.3))
df["Entry"] <- 1:dim(df)[[1]]
shop.mat <- table(df$shop,df$Entry)
shop.mat
1 2 3 4 5 6
1 1 0 0 1 0 0
2 0 1 0 0 1 0
3 0 0 1 0 0 1
supply.mat <- table(df$supply,df$Entry)
supply.mat
1 2 3 4 5 6
1 1 1 1 0 0 0
2 0 0 0 1 1 1
N_supply <- dim(supply.mat)[[1]]
N_shop <- dim(shop.mat)[[1]]
N_entry <- dim(df)[[1]]
Вектор решения будет иметь длину N_entry + N_supply, и каждая строка матрицы ограничений должна иметь одинаковую длину.
constr.mat <- NULL
dir <- NULL
rhs <- NULL
(A) решается путем ограничения каждой строки в shop.mat на == 1:
constr.mat <- rbind(constr.mat,cbind(shop.mat,matrix(0,N_shop,N_supply)))
dir <- c(dir,rep("==",N_shop))
rhs <- c(rhs,rep(1,N_shop))
(B) адресуется путем задания целевого вектора для расстояния для каждой записи и 0 для каждогомагазин (потому что естьне нужно тратить время на добавление еще одного центра снабжения, хотя в действительности это может быть):
obj <- c(aggregate(distance~Entry,df,c)[["distance"]],rep(0,N_supply))
(C) решается путем перестановки уравнения и превращения его в ограничение <= 0: </p>
constr.mat <- rbind(constr.mat,cbind(supply.mat,-diag(table(df$supply))))
dir <- c(dir,rep("<=",N_supply))
rhs <- c(rhs,rep(0,N_supply))
(D) решается путем добавления ограничения <= 2: </p>
constr.mat <- rbind(constr.mat,c(rep(0,N_entry),rep(1,N_supply)))
dir <- c(dir,"<=")
rhs <- c(rhs,2)
Затем проблему можно решить с помощью lpSolve
:
require(lpSolve)
sol <- lp("min", obj, constr.mat, dir, rhs, all.bin = TRUE,num.bin.solns = 1, use.rw=FALSE, transpose.constr=TRUE)
sol$solution
[1] 1 0 1 0 1 0 1 1
sol$objval
[1] 7.2
selected_Entry <- dimnames(shop.mat)[[2]][as.logical(sol$solution[1:N_entry])]
selected_Entry
[1] "1" "3" "5"
df[df$Entry %in% selected_Entry,]
shop supply distance Entry
1 1 1 2.8 1
3 3 1 1.4 3
5 2 2 3.0 5
Я вижу, чтов этом конкретном случае вектор решения вынужден (с помощью ограничений (C)) иметь «1» в любой из переменных «предложения», для которых выбрана хотя бы одна соответствующая запись.Если бы это было не так, суммы строк для ограничений (C) были бы> 0.
Но: предположим, что расстояния были разными и только центр снабжения 1 был выбран для всех 3 магазинов.Что помешало бы переменной вектора решения для центра снабжения 2 установить значение «1»?
Текущее решение дает:
constr.mat %*% sol$solution
[,1]
1 1
2 1
3 1
1 -1
2 -2
2
Но это альтернативное решение все равно будет отвечать всем ограничениям:
constr.mat %*% c(1,1,1,0,0,0,1,1)
[,1]
1 1
2 1
3 1
1 0
2 -3
2
, несмотря на то, что центр поставщиков 2 не использовался.
В этом случае это не повлияет на решение, так как затраты на включение центров снабжения не связаны (соответствующаяэлементами целевого вектора являются 0).
Но если бы я хотел получить из решения подсчет различных используемых центров снабжения , я думаю, что это не сработало бы.
Несколько лет назад я попросил совета по этой проблеме на другом форуме, и кто-то немедленно дал мне решение, однако сказал, что он / она «не был уверен, что это было наиболее эффективным».
Это былследующее: все то же, что и выше, а затем для каждого из центров снабжения добавьте к constr.mat
в два раза больше supply.mat
, дополненное отрицательной диагональной матрицей числазаписей на центр снабжения, ограничив первые N_supply
добавленных строк быть <= 0, а последние <code>N_supply строк быть> = 1 - диагональ упомянутой выше диагональной матрицы.
constr.mat <- rbind(constr.mat,cbind(supply.mat,-diag(table(df$supply))),cbind(supply.mat,-diag(table(df$supply))))
dir <- c(dir,rep("<=",N_supply),rep(">=",N_supply))
rhs <- c(rhs,rep(0,N_supply),1-table(df$supply))
Добавление этих ограничений гарантирует, что переменные «снабжения» в векторе решения равны 1, если и только если был использован соответствующий центр снабжения, и 0, если и только если он не использовался.
Например, оригинальное решение все еще будет работать:
paste(t(unlist(constr.mat %*% sol$solution)),dir,rhs)
[1] "1 == 1" "1 == 1" "1 == 1" "-1 <= 0"
[5] "-2 <= 0" "2 <= 2" "-1 <= 0" "-2 <= 0"
[9] "-1 >= -2" "-2 >= -2"
[Кстати, я бы не знал, как превратить это в оцененный логический вектор;Любая идея?]
, тогда как другое решение, которое ошибочно устанавливает переменную для центра снабжения 2 в 1, хотя этот центр снабжения не использовался, вместо этого будет недействительным:
paste(t(unlist(constr.mat %*% c(1,1,1,0,0,0,1,1))),dir,rhs)
[1] "1 == 1" "1 == 1" "1 == 1" "0 <= 0"
[5] "-3 <= 0" "2 <= 2" "0 <= 0" "-3 <= 0"
[9] "0 >= -2" "-3 >= -2"
(последнее ограничение не будет выполнено).
Q1 Считаете ли вы, что вышеизложенное имеет смысл, т. Е. Правда ли, что нам нужны дополнительные строки ограничений, которые я упомянул, чтобы убедиться, что переменные «питания» в векторе решения установлены правильно, илиЯ не прав?
Q2 Можете ли вы придумать более эффективный способ подсчета случаев появления различных предметов в таких задачах (пример здесь небольшой, но я часто имею дело с ОЧЕНЬ крупными,где добавление стольких ограничений не помогает, несмотря на все проблемы в мире)?
Спасибо!
Примечание: этот вопрос был изначально опубликованв другом сообществе.Я удалил его оттуда.
РЕДАКТИРОВАТЬ после просмотра страницы в Википедии по 'Проблема размещения некапитализированного объекта' , упомянутая в оригинальном сообщении, которое я связал выше.
На самом деле - это стоимость, связанная с открытием нового центра снабжения, поэтому вектор цели должен иметь не 0 в конце, а некоторую стоимость ($ f_i $ в формулировке Википедии).
Только тогда проблема $ \ sum_iy_i $, не всегда являющаяся числом открытых центров снабжения, исчезает, потому что ограничения $ \ sum_jx_ {i, j} \ le m \ cdot y_i $ по-прежнему гарантируют, что всякий раз, когда данный центриспользуется, соответствующий $ y_i $ равен 1;и не будет необходимости в других условиях, которые я наложил, потому что теперь есть стоимость, связанная с установкой 1 для каждого $ y_i $, поэтому только строго необходимые $ y_i $ s будут установлены в 1.
Короче говоря, если вектор цели построен правильно, с затратами на каждый центр снабжения, я могу обойтись без нескольких ограничений.
Фактически, в зависимости от значения для цены открытия центра снабжения, ограничение на максимальный итогчисло центров может быть даже заменено.
Тогда было бы интересно оценить предложение, сделанное в дискуссии в Википедии, а именно разделить ограничения «большого М» на несколько меньших.Если это правда, что это облегчает вычислительное решение проблемы, почему бы и нет ...