0

我用 lp solve 来求解一个线性规划方程，这个解给出了一个向量

> 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)

基本上它的作用是解决 3x3 网格的优化问题：

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 必须是唯一的。

4

1 回答 1

2

您的公式的问题在于您所做的只是将值的总和限制为 45；有许多 9 个整数的集合，总和为 45，但不采用 1 到 9 的值。

您可能会发现用 81 个二进制值变量 x_ij 来表示它更容易，而不是用 9 个整数值变量来表示，其中每个变量表示 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-05T18:18:24.733 回答