0

我正在尝试优化一组盒子的布局 wrt 他们的衣架位置 st 盒子与他们的衣架最对齐并且不会相互排挤。使用四驱。

吉文斯：

1.  box hanger x-locations (P). =710  850  990 1130
2.  box-sizes (W). =690 550 690 130 
3.  usable x-spread tuple (S). =-150 2090
4.  number of boxes (K). =4
5.  minimum interbox spread (G). =50
6.  box x-locations (X). =objective

我们可以看到所需的总 x-spread 为 sum(W) + 3G = 2060 + 150 = 2210，而可用的 x-spread 为 S[2] - S 1 = 2240。因此，应该存在解决方案。

分钟：

sumof (P[i] – X[i])^2

s.t.:

(1) X[i+i] – X[i] >= G + ½ ( W[i+1] + W[i] ); i = 1..(K-1)，即盒子不会互相排挤

        -X[i] + X[i+1] >= -( -G – ½ (W[i+1] + W[i]) )

(2) X 1 >= S[left] + ½ W 1和 (3) X[K] <= S[right] – ½ W[K]，即盒子在给定的 x-spread 内

        X[1] >= - ( S[left] + ½ W[1] )
        -X[K] >= - ( S[right] – ½ W[K] )

总共有 5 个约束 - 3 个用于跨箱传播，2 个用于四肢。

在 R 中：

> Dmat = matrix(0,4,4)
> diag(Dmat) = 1
> dvec = P, the hanger locations
[1]  710  850  990 1130
> bvec 
[1] -670 -670 -460 -195 2025
> t(Amat)
     [,1] [,2] [,3] [,4]
[1,]   -1    1    0    0
[2,]    0   -1    1    0
[3,]    0    0   -1    1
[4,]    1    0    0    0
[5,]    0    0    0   -1
> solve.QP(Dmat, dvec, Amat, bvec)
Error in solve.QP(Dmat, dvec, Amat, bvec) : 
  constraints are inconsistent, no solution!

很明显我错过或错误指定了问题（包'quadprog'）！我正在使用 quadprog，因为我找到了它的 JavaScript 端口。

非常感谢。

4

2 回答 2

1

问题在于 的设置Amat，bvec或两者兼而有之。solve.QP试图找到b二次规划问题的解 , , 受以下约束

t(Amat)*b >= bvec

在您的示例中扩展此约束，我们希望找到一个b := c(b[1], b[2], b[3], b[4])满足条件的向量：

  • -b[1] + b[2] >= -670,

  • -b[2] + b[3] >= -670,

  • -b[3] + b[4] >= -460,

  • b[1] >= -195

  • 和-b[4] >= 2025（即，b[4] <= -2025）。

但是，通过将前四个不等式加在一起，我们有b[4] >= -670-670-460-195 = -1995. 换句话说，b[4]必须大于-1995和小于-2025。这是一个矛盾，因此solve.QP无法找到解决方案。

-b[4] >= -2025通过设置尝试这个例子与约束bvec = c(-670, -670, -460, -195, -2025)产生一个解决方案。无需过多介绍上述公式，也许这是有意的（或者这些值中的另一个应该是积极的）？

于 2015-07-12T20:48:16.577 回答
1

我不确定这是否可以解决您的物理问题，但下面的代码似乎可以解决您所说的优化问题。我已将其推广到可变数量的框，并包含一个图来检查解决方案。

  library(quadprog)
  p  <- c(710,  850,  990, 1130)   # hanger positions
  w  <- c(690, 550, 690, 130)      # box widths
  g <- 50                          # min box separation
  s <- c(-150, 2390)               # min and max postions of box edges

  k <- length(w)                   # number of boxes
  Dmat <- 2*diag(nrow=k)
  dvec <- p
# separation constraints
  Amat <- -diag(nrow=k,ncol=(k-1))
  Amat[lower.tri(Amat)] <- unlist(lapply((k-1):1, function(n) c(1,numeric(n-1))))
  bvec <- sapply(1:(k-1), function(n) g + (w[n+1]+w[n])/2)
# x-spread constraints
  Amat <- cbind(Amat, c(1,numeric(k-1)), c(numeric(k-1),-1))
  bvec <- c(bvec, s[1] + w[1]/2, -(s[2] - w[k]/2))

  sol <- solve.QP(Dmat, dvec, Amat, bvec)
  plot(x=s, y=c(0,0), type="l", ylim=c(-2.5,0))
  points(x=p, y=numeric(k), pch=19)
  segments(x0=sol$solution, y0=-1, x1=p, y1=0)
  rect(xleft=sol$solution-w/2, xright=sol$solution+w/2, ytop=-1.0, ybottom=-2, density=8)

在此处输入图像描述

于 2015-07-13T12:43:00.870 回答