excel - 如何建立一个矩阵相乘的简单优化模型？

Question

我已经使用标准 Solver 在 Excel 中创建了一个优化模型，现在想在 R 中制作一个类似的模型，因为这将允许我制作像这样的更大模型。不幸的是，我很难找到可以为我的概念建模的好例子。因此，我想问你是否有人能给我一些关于如何在 R 中制作类似模型的提示。

我已将我的 Excel 表格上传到 http://dl.dropbox.com/u/9641130/R/Positioning%20Optimization%20R.xlsx

基本思想是通过将 E10:L19 范围内的最多 8 个单元格更改为 1 个单元格来最大化单元格 B3。 B3 单元格包括范围 E10:L19 的 sumproduct() 和许多类似范围。

我期待看到一些关于如何在 R 中构建类似模型的提示。

谢谢!
约赫姆

========

按照大通的建议更新

我想用一些可重复的 R 代码来澄清我的问题。这与您在上面的 Excel 代码中找到的模型大致相同。

初始矩阵集:

A <- as.matrix(structure(list(X0 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.1 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.2 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.3 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.4 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.5 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.6 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L), X0.7 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L)), .Names = c("X0", "X0.1", "X0.2", "X0.3", "X0.4", "X0.5", "X0.6", "X0.7"), class = "data.frame", row.names = c(NA, -9L)))
B <- as.matrix(structure(list(X1 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.1 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.2 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.3 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X.100000 = c(-100000L, -100000L, -100000L, -100000L, 1L, 1L, 1L, 1L, 1L), X.100000.1 = c(-100000L, -100000L, -100000L, -100000L, 1L, 1L, 1L, 1L, 1L), X.100000.2 = c(-100000L, -100000L, -100000L, -100000L, 1L, 1L, 1L, 1L, 1L), X.100000.3 = c(-100000L, -100000L, -100000L, -100000L, 1L, 1L, 1L, 1L, 1L)), .Names = c("X1", "X1.1", "X1.2", "X1.3", "X.100000", "X.100000.1", "X.100000.2", "X.100000.3"), class = "data.frame", row.names = c(NA, -9L)))
C <- as.matrix(structure(list(X1 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.1 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.2 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.3 = c(1L, 1L, 1L, 1L, 1L, -100000L, 1L, 1L, 1L), X1.4 = c(1L, 1L, 1L, 1L, 1L, -100000L, 1L, 1L, 1L), X1.5 = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), X1.6 = c(1L, 1L, 1L, 1L, 1L, -100000L, 1L, 1L, -100000L), X1.7 = c(1L, 1L, 1L, 1L, -100000L, -100000L, 1L, 1L, -100000L)), .Names = c("X1", "X1.1", "X1.2", "X1.3", "X1.4", "X1.5", "X1.6", "X1.7"), class = "data.frame", row.names = c(NA, -9L)))
D <- as.matrix(structure(list(X775 = c(385L, 1233L, 1067L, 5L, 730L, 1123L, 837L, 5L, 3087L), X704 = c(625L, 1338L, 804L, 110L, 659L, 1363L, 942L, -165L, 3350L), X704.1 = c(625L, 1338L, 804L, 110L, 659L, 1363L, 942L, -165L, 3350L), X944 = c(625L, 1263L, 898L, 35L, 899L, 1363L, 867L, -65L, 3110L), X775.1 = c(385L, 1233L, 1067L, 5L, 730L, 1123L, 837L, 5L, 3087L), X775.2 = c(385L, 1233L, 1067L, 5L, 730L, 1123L, 837L, 5L, 3087L), X944.1 = c(625L, 1263L, 898L, 35L, 899L, 1363L, 867L, -65L, 3110L), X944.2 = c(625L, 1263L, 898L, 35L, 899L, 1363L, 867L, -65L, 3110L)), .Names = c("X775", "X704", "X704.1", "X944", "X775.1", "X775.2", "X944.1", "X944.2"), class = "data.frame", row.names = c(NA, -9L)))

函数 sum(A*B*C*D) 的结果当前为 0。这是合乎逻辑的，因为在矩阵 A 中，所有单元格的值都为 0。但是，我想知道用什么公式可以最大化函数总和(A*B*C*D)。

sum(A*B*C*D)
[1] 0

我想通过将矩阵 A 中的值从 0 更改为 1 来做到这一点。此外，应考虑以下约束。
1. 每行只能包含一个值为 1 的单元格。
2.每列只能包含一个值为1的单元格；这意味着我们最多可以在矩阵 A 中放置值 1 的八倍。

有人对如何实现这一点有建议吗？

Answer 1

您的决策变量(A 中的单元格值)是 bool 值(0 或 1)，您的目标和约束是这些变量的线性函数，这将您置于称为混合整数线性规划的优化问题类别中。这些问题可以使用 Rglpk 来解决。以包为例。这是我的解决方案:

n1 <- nrow(A)
n2 <- ncol(A)

# objective coefficients
obj <- as.vector(B*C*D) # objective

# matrix of constraints weights
mat <- matrix(0, n1+n2, n1*n2)
for (i in 1:n1) {
   mat[i, ] <- as.numeric(row(A) == i)
}
for (j in 1:n2) {
   mat[n1+j, ] <- as.numeric(col(A) == j)
}

dir   <- rep("<=", n1+n2) # constraint directions
rhs   <- rep(1, n1+n2)    # constraints upper-bounds
types <- rep("B", n1*n2)  # variable types (boolean)

library(Rglpk)
opt <- Rglpk_solve_LP(obj, mat, dir, rhs, types,
                      max = TRUE, verbose = TRUE)
opt

# $optimum
# [1] 9950

# $solution
#  [1] 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
# [39] 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
# [77] 0 1 0 0

# $status
# [1] 0

opt.A <- matrix(opt$solution, n1, n2)
opt.A

#       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#  [1,]    0    0    0    1    0    0    0    0
#  [2,]    0    0    1    0    0    0    0    0
#  [3,]    0    1    0    0    0    0    0    0
#  [4,]    1    0    0    0    0    0    0    0
#  [5,]    0    0    0    0    0    0    0    0
#  [6,]    0    0    0    0    0    0    1    0
#  [7,]    0    0    0    0    0    1    0    0
#  [8,]    0    0    0    0    0    0    0    1
#  [9,]    0    0    0    0    0    0    0    0
# [10,]    0    0    0    0    1    0    0    0

是 9950您还为 sum(A*B*C*D) 获得的最佳值(value)? (我这台电脑上没有 Excel……)