Apprendre Maple

[zorro]

Bonjour,

J'aimerais implémenter l'algorithme suivant. J'ai beaucoup de mal, d'autant plus qu'il est absolument nécessaire d'optimiser le temps de calcul !

- v est une liste de r entiers positifs ou nuls,
- a est une liste de r(r-1)/2 entiers positifs ou nuls, écrits sous la forme
[seq(seq(a[binomial(j-1,2)+i],j=i+1..r),i=1..r-1)]
qui rappelle leur origine (matrice antisymétrique).

Etant donnée v, je dois énumérer, sous forme de liste, tous les choix possibles pour a qui satisfont aux (r-1) contraintes suivantes (pour s= 2 ..r) :
convert([seq(seq(a[binomial(j-1,2)+i],i=1..s-1),j=s..r)],`+`)<= v[r-s+1];

Merci pour toute indication !

[zozo]

Salut à tous,
En introduisant des matrices, on devrait aboutir à un classique pb d'optimisation linéaire sous contraintes, non?

[zorro]

Merci ! C'est une remarque qui ouvre des perspectives très intéressantes. Je n'y avais absolument pas pensé. Le problème est issu d'un tout autre domaine !
Pour la même raison, si le problème est "classique", il ne l'est pas pour moi !
Une petite recherche sur Gougueule semble montrer qu'il n'y aurait qu'un algorithme tout terrain, la méthode "du simplexe" ? Mais je n'ai pas trouvé d'implémentation sous Maple ?
J'espère me tromper !


PS : Pour le moment, je bricole comme suit.
Les contraintes impliquent que pour tout s=2..r, et pour tout i<s on a a[binomial(s-1,2)+i] <= v[r-s+1].
Cette majoration grossière est facile à traiter par Maple. Ensuite on enlève les mauvaises solutions, en testant les inégalités.
C'est laid, et surtout très lent.

[zorro]

Au temps pour moi !
Il y a un package "simplex" dans Maple.
Mais dans mon cas, il ne s'agit pas d'optimiser une fonction. Il s'agit d'obtenir les solutions entières à un système d'inégalités. Merci de m'indiquer comment vous procéderiez.

[zozo]

Bonjour,
je ne sais pas si Maple peut traiter des systèmes d'inéquations en variables entières???