1

我需要解决一些约束条件下的 anxn（n 通常 <12）矩阵：

1.满足预定的行和列总和。

2.矩阵中行号大于列号的每个元素都必须为零（所以基本上唯一的非零元素必须在右上角）。

3.对于给定的行，右边第一个非零元素超过三列的每个元素也必须为零。

因此，一个 4x4 矩阵可能看起来像这样（行和列约束在实践中会大得多，通常在 1-3 百万左右）：

|3 2 1 0| = 6
|0 2 1 1| = 4
|0 0 2 1| = 3
|0 0 0 4| = 4
 3 4 4 6

我一直在尝试使用一些求解器方法在 excel 中执行此操作，并且还尝试了一些基于 R 的优化包，但到目前为止都没有成功。

任何关于我如何解决这个问题的建议都将不胜感激。

谢谢！

4

1 回答 1

3

测试数据：

x <- c(2,2,2,1,1,1,1)
rowVals <- c(6,4,3,4)
colVals <- c(3,4,4,6)

从 (3N-5) 参数构造适当测试矩阵的函数：

makeMat <- function(x,n) {
    ## first and last element of diag are constrained by row/col sums
    diagVals <- c(colVals[1],x[1:(n-2)],rowVals[n])
    ## set up off-diagonals 2,3
    sup2Vals <- x[(n-1):(2*n-3)]
    sup3Vals <- x[(2*n-2):(3*n-5)]
    ## set up matrix
    m <- diag(diagVals)
    m[row(m)==col(m)-1] <- sup2Vals
    m[row(m)==col(m)-2] <- sup3Vals
    m
}

目标函数（行和列偏差的平方和）：

objFun <- function(x,n) {
    m <- makeMat(x,n)
    ## compute SSQ deviation from row/col constraints
    sum((rowVals-rowSums(m))^2+(colVals-colSums(m))^2)
}

优化：

opt1 <- optim(fn=objFun,par=x,n=4)
## recovers original values, although it takes a lot of steps

opt2 <- optim(fn=objFun,par=rep(0,length(x)),n=4)
makeMat(opt2$par,n=4)
##      [,1]     [,2]      [,3]      [,4]
## [1,]    3 2.658991 0.3410682 0.0000000
## [2,]    0 1.341934 1.1546649 1.5038747
## [3,]    0 0.000000 2.5042858 0.4963472
## [4,]    0 0.000000 0.0000000 4.0000000
## 

## conjugate gradients might be better
opt3 <- optim(fn=objFun,par=rep(0,length(x)),n=4,
              method="CG")

这个问题似乎有多种解决方案，这并不奇怪（因为 (N-2)+(N-1)+(N-2)= 3N-5 个参数有 2N 个约束）。

您没有说是否需要整数解决方案-如果需要，您将需要更专业的工具...

于 2013-07-25T15:37:37.497 回答