Optimiser la distribution de la quantité dans le tableau 2d

Question

J'ai un problème où la somme de chaque ligne et colonne pour un tableau à deux dimensions est donnée et nous devons distribuer la quantité dans chaque cellule du tableau. Il y aura des cellules qui seront verrouillées et vous ne pourrez pas les utiliser pour la distribution. De même, les quantités totales de ligne/colonne peuvent être des valeurs décimales.

Ainsi, par exemple, Nous avons un 4 * 3 tableau 2-d

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

où somme de chaque ligne est 10,20,30,35 et somme de chaque colonne est 35,30,30 .

E, I et K sont verrouillés de sorte que les équations deviennent

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 

j'ai essayé f linéaire (x) = Min (x) et solveurs quadratique f (x) = Min (x^2) en utilisant Python scipy et IBM CPLEX (C#).

Le solveur linéaire n'optimise pas la distribution.

Le solveur quadratique aide avec cette approche, mais il ne fonctionne pas pour les réseaux de taille supérieure à 10 * 10. Le solveur a échoué avec un statut irréalisable. Quelle approche/bibliothèque devrais-je utiliser pour résoudre ce problème étant donné que les totaux peuvent avoir des valeurs décimales et que la taille de la matrice peut aller jusqu'à 100 * 10000?

Answer 1

Si vous organisez les équations comme

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 

vous pouvez voir c'est un system of linear equations Ax = b avec

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 

La résolution de tels systèmes a été discuté sur Stack Overflow précédemment:

• Solving a linear equation