要求整數優化變量取唯一的值

我用LP解決求解線性規劃方程，並將該溶液給出了一個矢量要求整數優化變量取唯一的值

> lp("max", obj, con, ineqs, rhs, all.int=TRUE,)$solution 
[1] 5 0 13 11 4 0 1 11 0

這是很好的，但我想在該載體中的每個條目是一個整數在1-9之間，每個整數只能使用一次。例如像下面的矢量。

[1] 3 4 8 9 2 5 1 6 7

有沒有什麼辦法可以做到這一點？先謝謝你！

編輯

這是我用過的LP功能

obj<-c(1,1,1,1,1,1,1,1,1) 
con<-matrix(c(1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1),nrow=5,byrow=TRUE) 
ineqs<-c("=", "=", "=", "=", "=") 
rhs<-c(45,20,17,27,15)

基本上代碼這樣做是它解決了3×3的網格優化問題：

x1 x2 x3 
x4 x5 x6 
x7 x8 x9

在哪裏約束是x1 + x2 + x4 + x5 = 20，x2 + x3 + x5 + x6 = 17，x4 + x5 + x7 + x8 = 27，x5 + x6 + x8 + x9 = 15，每個x必須是1和9，每個x必須是唯一的。

來源

2014-11-05 calculator

您的預期結果與您顯示的輸出爲lp模型的示例輸出有什麼關係？如果是這樣，怎麼樣？ – 2014-11-05 16:14:41

你好，我編輯了這些問題，以便你能理解lp函數的作用。「x必須是1到9之間的整數並且每個x必須是唯一的」的約束是我認爲我出錯的地方。 – calculator 2014-11-05 16:58:56

您的表述存在的問題是，您所做的只是將值的總和限制爲45;有許多9個整數的集合，總和爲45，但不取值1到9.

而不是用9個整數值變量來表示它，你可能會發現用81個二元 - 值變量x_ij，其中每個變量指示x_i（在原始公式中）取值j。

# Helper functions to index variables 
unit <- function(idx) as.numeric((1:9) == idx) 
ivals <- function(i) { ret <- rep(0, 81) ; ret[(9*i-8):(9*i)] <- 1:9 ; ret } 
ivars <- function(i) rep(unit(i), each=9) 
jvars <- function(j) rep(unit(j), 9) 

# Setup and solve optimization model 
obj <- rep(0, 81) 
const <- rbind(do.call(rbind, lapply(1:9, jvars)), # Each value once 
       do.call(rbind, lapply(1:9, ivars)), # Each var once 
       ivals(1) + ivals(2) + ivals(4) + ivals(5), 
       ivals(2) + ivals(3) + ivals(5) + ivals(6), 
       ivals(4) + ivals(5) + ivals(7) + ivals(8), 
       ivals(5) + ivals(6) + ivals(8) + ivals(9)) 
ineqs <- rep("=", 22) 
rhs <- c(rep(1, 18), 20, 17, 27, 15) 
library(lpSolve) 
res <- lp("max", obj, const, ineqs, rhs, all.bin=TRUE) 
apply(matrix(res$solution, nrow=9), 2, which.max) 
# [1] 3 7 5 6 4 1 9 8 2

來源

2014-11-05 18:18:24 josliber

要求整數優化變量取唯一的值

回答

相關問題