具有行和列约束的r矩阵

Question

我需要求解一个受几个约束的n x n（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的优化包，但到目前为止还没有成功。

任何关于我如何处理这一问题的建议都将不胜感激。

谢谢！

Answer 1

测试数据：

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上有2N个约束）=3N-5参数）。

您没有说明是否需要整数解决方案--如果所以你需要更专业的工具。。。