-1

我有一个问题，其中给出了二维数组的每一行和每一列的总和，我们必须在数组的每个单元格中分配数量。将有一些单元格将被锁定，您不能将它们用于分发。此外，行/列的总量可以是十进制值。

例如，我们有一个 4*3 二维数组

 A   B   C
 D   E   F
 G   H   I
 J   K   L

其中每行之和为 10,20,30,35，每列之和为 35,30,30。

E、I 和 K 被锁定，因此方程变为

 E = I = K = 0

 A + B + C = 10 
 D + F = 20 
 G + H = 30
 J + L = 35

 A + D + G + H = 30
 B + H = 30 and 
 C + F + L = 30

我使用 Python scipy 和 IBM CPLEX(C#) 尝试了线性 f(x) = Min(x) 和二次求解器 f(x) = Min(x^2)。

线性求解器不会优化分布。

二次求解器有助于这种方法，但它不适用于大小大于 10*10 的数组。求解器以不可行状态失败。

考虑到总数可以有十进制值并且矩阵的大小可以达到 100*10000 ，我应该使用什么方法/库来解决这个问题？

4

1 回答 1

0

如果将方程组织为

 A + B + C                        = 10
 A         + D     + G + H        = 30
     B                 + H        = 30
         C     + F            + L = 30
             D + F                = 20
                     G + H        = 30
                            J + L = 35

你可以看到这是一个线性方程组Ax=b

    1,1,1,0,0,0,0,0,0           10
    1,0,0,1,1,1,0,0,0           30
    0,1,0,0,0,1,0,0,0           30
A = 0,0,1,0,0,0,1,1,0   and b = 30
    0,0,0,1,0,0,1,0,0           20
    0,0,0,0,1,1,0,0,0           30
    0,0,0,0,0,0,0,1,1           35

解决此类系统之前已在 Stack Overflow 上讨论过：

于 2017-09-18T05:27:35.327 回答