Discussion :

[Julien N]

Bonjour,

Je développe un programme de simulation faisant intervenir des moteurs. Ces moteurs sont alimentés par des générateurs électriques. Une forte redondance est fréquente dans le schéma de connexion entre ces générateurs et moteurs pour des raisons de sécurité. Mon programme détermine à tout instant la charge de chaque moteur, charge que je peux traduire en terme de puissance électrique. Je cherche désormais à déterminer quelle doit être la puissance délivrée par chaque générateur, et bien entendu limiter la consommation des moteurs si jamais la demande excède la capacité des générateurs.

Voilà pour la petite histoire. J'en suis à l'étape de conception et je sèche complètement sur comment prendre ce problème. Je le vois comme un problème d'optimisation: déterminer la répartion de puissance entre générateurs optimale avec pour contrainte la puissance demandée par chaque moteur". Par optimale j'entends ici avec la puissance max la plus faible. Et je vois bien que les contraintes peuvent ne pas être satisfaites.

Voici un dessin d'un schéma de connexion possible (bien qu'exagéré):



Est-ce que ce problème vous fait pensez à quelque chose? Une piste de recherche me serait bien utile!

Merci.

J

[Gruzo]

Salut Julien,

Que penses tu de l'algorithme du simplexe ? tu pourrais prendre comme inconnue la puissance que tu voudrais distribuer pour chaque moteur tout en limitant la puissance pour chaque génératrice.

Le but final bien sûr serait de minimiser l'énergie.

Par exemple en première équation on pourrait avoir:

x1 + x2 + x3 <= G1 avec x1 la charge du moteur r1.
....

Je sais pas si ça peut t'aider, mais je sais qu'avec cette méthode tu es sûr de minimiser ou maximiser une fonction à l'aide d'inégalités.

[Flodelarab]

Bonjour

Sujet très intéressant.

Le but final bien sûr serait de minimiser l'énergie.

Il n'y aura pas miracle. Si tu as une charge de 100, il te faudra l'énergie pour 100.
C'est plus un problème de combinatoire que de minimisation.

Est-ce que ce problème vous fait pensez à quelque chose?

Je n'ai a priori pas la réponse.
Mais je propose un exemple concret pour confirmer que nous comprenons le problème de la même façon.

Je prends au hasard :
G1max = 150
G2max = 100
G3max = 50
et
M1 = 100
M2 = 50
M3 = 30
M4 = 30
M5 = 40

Déjà, la charge (250) est inférieure à la source (300). Ça part bien.

Les branches M1 et M5 sont obligatoirement saturées.

Il reste à combler:
G1max' = 50
G2max' = 100
G3max' = 10
et
M2 = 50
M3 = 30
M4 = 30

r est est le ratio équilibré d'occupation des génératrices
G3M2+G3M3+G3M4+40=50*r
G1M2+G1M3+100=150*r
G2M2+G2M3+G2M4=100*r
G1M2+G2M2+G3M2=50
G1M3+G2M3+G3M3=30
G2M4+G3M4=30

On résout :
{ r = 5/6, G3M3 = r3, G1M3 = - r3- r2+30, G2M2 = -(3 r2+3 r1-250)/3, G2M3 = r2, G2M4 = r1, G3M2 = (-3 r3+3 r1-85)/3, G3M4 = 30- r1, G1M2 = r3+ r2-5 }.

La valeur trouvée pour r est logique (250/300).
On peut prendre des r1 r2 r3 nuls.

Reste à généraliser le procédé.
C'est bien cela ?


On dirait un algorithme de Ford-Fulkerson à plusieurs sources.

[anapurna]

salut

si je comprend bien dans l'absolue tu chercherais
a définir pour chaque générateur la puissance minimal utilisé
c'est a dire :

Somme(Puissance Utilise) / Nb de Générateur

j'ai bien dis dans l'absolue je me doute bien que ceci n'est pas aussi simple
tout les générateur n’étant pas tous couplé les un avec les autres

il serais presque plus facile de passer par un concentrateur et que celui-ci redistribue les puissance nécessaire
bon nous ne somme pas dans ce cas là
Pour cela il existe plusieurs possibilité de résolution sans trop réfléchir je me tournerais vers la Programmation par contraintes

[Invité]

slt

si la puissance délivrée est linéaire, dans le sens:
si le générateur G1 peut fournir 100w
il peut filer 50w à M1, 20w à M2 et 30w à M3, sans pertes...

tu peux faire une Gruzo.
Je détaille un peu

soit m_i la puissance nominale du moteur i
soit G_j la puissance minimale que doit assurer G_j
Soit g_ji la puissance délivrée par le générateur j au moteur i

assurer qu'un moteur à sa puissance nominale est
m_i = somme_j g_ji

assurer qu'il a au moins sa puissance nominale est
m_i <= somme_j g_ji

trivialement si tu poses g_ji = m_i (pour tout j,i), tu satisferas tous les m_i...
mais au plus pres il faut donc minimiser somme_ji g_ji
une fois que tu les as trouvés, tu retrouves g_j via
G_j = somme_i g_ji

ton modèle peut s'écrire
minimiser somme g_ij
s.c g_ij > 0
s.c somme_i g_ij >= m_i

tu peux etre précis et ne spécifier que les g_ij qui "existent" sinon tu peux ecrire
pour tout i, tout j
minimiser somme g_ij*a_ij
s.c g_ij > 0
s.c somme_i g_ij >= m_i
avec a_ij = 0 ou 1 selon que la relation existe

l'intéret de la seconde étant pblmnt de pouvoir modifier tes "connexions" sans trop suer(tu modifies qu'une seule "ligne")

[tbc92]

Personnellement, je n'ai pas compris la question. Quelles sont les données 'fournies' en entrée, et quelles sont les données qui doivent être calculées par ton programme.
Restons sur ton schéma.
Tu as 5 moteurs, les puissances consommées par ces 5 moteurs sont des données fournies en entrée. Mais ces 5 puissances, tu peux éventuellement les modifier à la baisse.
Tu as 3 générateurs, j'imagine qu'on connaît la puissance maxi de chaque générateur, et que là aussi, tu dois déterminer quelle puissance va être fournie par chaque générateur ?

Et enfin, tu dois déterminer la puissance qui circule sur chacun des 10 câbles.

[Julien N]

Salut,

Je suis impressionné par le nombre de réponses en quelques heures (et de qualité en plus!). Merci! J'ai pris un peu de temps pour étudier et digérer chaque réponse.

tu pourrais prendre comme inconnue la puissance que tu voudrais distribuer pour chaque moteur tout en limitant la puissance pour chaque génératrice.

J'ai commencé sur cette voie qui me semble prometteuse bien qu'assez complexe. Je ne vais pas détailler les maths ici car je ne crois pas que ce forum soit en mesure de rendre des équations. J'ai commencé par définir un vecteur u de la puissance fournie par les générateurs (donc de dimension d,1 avec d le nombre de générateurs), puis un vecteur X de la puissance utilisée par les moteur (de dimension n,1 avec n le nombre de moteurs). Je défini ensuite une matrice w liant u et X: X=w.u. Ainsi w est de dimension n,d et chaque terme correspond à la part de puissance d'un générateur allouée à un moteur (w11 correspond la proportion de puissance du générateur 1 allouée au moteur 1). Je cherche alors w minimisant max(u) avec certaines contraintes (X_=w.u avec X_ la puissance moteur souhaitée, mais aussi certaines contraintes d'inégalités qu'il me reste à définir proprement pour tenir compte du fait que certain wij doivent être à zéro car le lien générateur/moteur est inéxistant). Je crois qu'on s'approche de la proposition de galerien69.
Bon cette voie là me semble assez touchy. Elle va faire appel à des algo d'optimisation avec contraintes et je sais par expérience que c'est pas évident. Et puis, si la puissance demandée par les moteurs ne peut être satisfaite, comment gérer l'impact sur les moteurs?

Mais je propose un exemple concret pour confirmer que nous comprenons le problème de la même façon.

Je me suis perdu avec cette histoire de r. Quelle serait dans cet exemple la puissance générée par chaque générateur? A la main, je trouve la solution suivante:

• G1 = 130 (utilisation de 86.7%). Fourni 100 à M1 et 30 à M2.
• G2= 80 (utilisation de 80.0%). Fourni 20 à M2, 30 à M3 et 30 à M4.
• G3 = 40 (utilisation de 80.0%). Fourni 40 à M5.

Ce n'est peut-être pas la solution optimale cela dit. Et par optimale j'entends avec une utilisation la plus élevée la plus faible.

Je ne connaissais pas Ford-Fulkerson. En jettant un oeil j'ai l'impresssion que tous les graphs traitables sont "fermés". Est-ce réalisable avec plusieurs sources et "ouvert"?

il serais presque plus facile de passer par un concentrateur et que celui-ci redistribue les puissance nécessaire

Intéressant. Je suis une bille en électronique, mais je sais qu'en réalité les générateurs ne sont pas directement reliés aux moteurs. Entre les deux se trouvent notamment des "power busbars" et des "switchboards". J'ai volontairement négligé ces interrupteurs car pour moi il ne permettent que de redéfinir les connexions. Et de plus dans mon cas ils ne sont employés qu'en de très rares cas. Par contre ces "busbars" pourraient être aussi modélisés. Si je reprends mon schéma avec ces barres, voici ce que cela donnerait:

Est-ce que comme cela la solution serait plus simple finalement?

Tu as 5 moteurs, les puissances consommées par ces 5 moteurs sont des données fournies en entrée. Mais ces 5 puissances, tu peux éventuellement les modifier à la baisse.
Tu as 3 générateurs, j'imagine qu'on connaît la puissance maxi de chaque générateur, et que là aussi, tu dois déterminer quelle puissance va être fournie par chaque générateur ?

Et enfin, tu dois déterminer la puissance qui circule sur chacun des 10 câbles.

C'est tout à fait ça.
En entrée j'ai bien la puissance demandée par les moteurs. Je cherche alors la puissance à fournir par les générateurs. Mais ce n'est pas la sortie car les générateurs peuvent ne pas être en mesure de fournir suffisament de puissance. La sortie est la puissance utilisée par les moteurs, par opposition à la puissance demandée. Une sorte de va et vient.

Je vais voir si je parviens à exprimer le problème dans une forme acceptable pour être résolu par un algo d'optimisation.

Julien

[tbc92]

Je cite :

Je me suis perdu avec cette histoire de r. Quelle serait dans cet exemple la puissance générée par chaque générateur? A la main, je trouve la solution suivante:
G1 = 130 (utilisation de 86.7%). Fourni 100 à M1 et 30 à M2.
G2= 80 (utilisation de 80.0%). Fourni 20 à M2, 30 à M3 et 30 à M4.
G3 = 40 (utilisation de 80.0%). Fourni 40 à M5.

Ce n'est peut-être pas la solution optimale cela dit. Et par optimale j'entends avec une utilisation la plus élevée la plus faible.

Utilisation la plus élevée la plus faible, ça veut dire que le pourcentage le plus élevé (ici 86.7%), on cherche à le minimiser ?
Donc dans ce cas, effectivement on peut faire mieux.

La somme des 5 moteurs donne 100+50+30+30+40=250.
La somme des 3 générateurs donne 150+100+50=300.
250/300 = 83%
Il y a probablement une solution où les 3 générateurs tournent à 83.3%, et les 5 moteurs tournent à fond.
Et dans ce cas présent, il y a effectivement des solutions avec ces ratios.

[Flodelarab]

Tout d'abord, merci d'avoir répondu à chaque point.

Je me suis perdu avec cette histoire de r. Quelle serait dans cet exemple la puissance générée par chaque générateur? A la main, je trouve la solution suivante:

G1 = 130 (utilisation de 86.7%). Fourni 100 à M1 et 30 à M2.
G2= 80 (utilisation de 80.0%). Fourni 20 à M2, 30 à M3 et 30 à M4.
G3 = 40 (utilisation de 80.0%). Fourni 40 à M5.

Le r était pour que le pourcentage d'utilisation soit le même pour toutes les génératrices.

Je ne connaissais pas Ford-Fulkerson.

Voici la vidéo en français la plus claire pour expliquer Ford-Fulkerson.

On sature les arcs directs et on dé-sature les arcs inverses.

En jettant un oeil j'ai l'impresssion que tous les graphs traitables sont "fermés". Est-ce réalisable avec plusieurs sources et "ouvert"?

Je ne comprends pas la notion "fermés"/"ouverts".
Si tu veux dire que les sources sont multiples ainsi que les points d'arrivée, alors tu peux transformer ton graphe avec un point d'entrée virtuel et des arêtes de capacité infinie vers 3 premiers sommets qui seraient tes génératrices dont partirait une arête "majorée" vers un sommet qui s'occuperait de la distribution ... Et pareil, de l'autre côté, en sortie.
Ainsi, tu peux toujours te ramener à un graphe avec 1 entrée et une sortie, et appliquer l'algorithme.

Cela te permettra toujours de savoir si c'est possible ou impossible.

Mais j'ai le sentiment que très vite tu va vouloir déplacer les charges des moteurs pour trouver un cas qui marche.
Ta problématique est plus un problème du sac-à-dos avec plusieurs sac-à-dos.
Si tes quantités sont toujours aussi petites, tu devrais tester tous les cas possibles.
Et désigner une combinaison gagnante.

[anapurna]

salut

le but est donc 250/300 = 83%
donc les generateur doivent fournir respectivement
G1 = 150*83% = 125
G2 = 100*83% = 83.23
G3 = 50*83% = 41.67

soit 250 au total

mettons les dans un tableau
on s'apperçois très vite que deux contrainte ne nous donne pas le choix pour les machine M1 et M5
une fois définis les première contrainte on vois qu'il nous reste pour la machine M4
un peut de ressource du G3 1.67
donc on vas le deduire de la valeur a atteindre de M4 ce qui nous donne une nouvelle valeur a atteindre de 28.33
nous savons que G2 peut facilement le couvrir donc on retire 28.33 de G2 il reste donc 55 a distribuer pour G2 et 25 pour G1
nous voyons que M2 est superieur au Reste de G1 mais inferieur au reste de G2 on vas donc couvrir
M2 a l'aide de G2 il reste donc 5 a redistribuer sur G2 et 25 sur G1
la somme couvre M3

tout ceci pour dire qu'un systeme de satisfaction de contrainte n'auras aucun soucis a déterminer les valeurs si le problème est correctement posé

Mot/Gen	Contrainte	Val Mot	G1	G2	G3	TOT
M1	G1	100	100.00			100
M2	G1+G2+G3	50		50.00		50
M3	G1+G2+G3	30	25.00	5.00		30
M4	G2+G3	30		28.33	1.67	30
M5	G3	40			40.00	40
TOT		250	125.00	83.33	41.67	250
BUT		250	125.00	83.33	41.67
RESTE		0	0.00	0.00	0.00

[Invité]

Mais ce n'est pas la sortie car les générateurs peuvent ne pas être en mesure de fournir suffisament de puissance. La sortie est la puissance utilisée par les moteurs, par opposition à la puissance demandée

Je présume que ce qui se rapproche le plus de ton but c'est d'autoriser les moteurs à tourner dans un mode dégradé mais d'imposer obligatoirement un certain régime même en mode dégradé.
Ce mode dégradé étant atteint si un générateur saute (ou pas si la configuration initiale est déjà en surcharge)

si tel est le cas, tu peux conserver ton pb d'optim et cette fois m est la valeur en mode dégradée (et non nominale)
On peut générer autant de contraintes qu'il n'y a de configuration ou le générateur saute.

avec la minimisation tjs des arrêtes g_ji mais sous contraintes
e_k = A_km - m > 0
où A_k est ta matrice avec potentiellement des 0 et m ton vecteur de moteurs
k étant l'indice pour une configuration donnée (où certains moteurs sont morts...)

Après si t'acceptes de même tourner en dessous du mode acceptable tu peux tenter d'optimiser
S: somme g_ji + somme f_k
où cette fois f_k = m-A_km (ssi A_km < m, sinon 0)

les deux sommes se "contrebalançant" mais ne pas garantir un certain niveau me parait être à l'opposé de l'intérêt de redonder..

[Julien N]

tout ceci pour dire qu'un systeme de satisfaction de contrainte n'auras aucun soucis a déterminer les valeurs si le problème est correctement posé

J'espère. :) J'ai passé un peu de temps à essayer d'exprimer le problème correctement pour pouvoir ensuite le résoudre avec un solveur d'optimisation. Je suis arrivé à quelque chose, mais je ne suis pas certain d'être en mesure de le résoudre. Je passe en mode image pour pouvoir afficher correctement des équations:




L'avantage de cette formlation c'est qu'elle est générale. Mais honnêtement je ne sais pas la résoudre... Je vais creuser l'idée du problème aux sacs à dos.

Julien

[Invité]

je comprends pas trop ta formulation mais tu peux la résoudre via sqp (octave)
https://octave.org/doc/v4.2.0/Nonlin...ogramming.html

j'ai jamais trop vu ce type d'opti par relaxation
S m'a l'air pénalisé quadratiquement (donc avec Q def positive je présume..) et u juste "normé" donc on pénalise les gros écarts par rapport à X mais moins X que S

Curieux de savoir ce que ca donne

[Julien N]

Salut,

je comprends pas trop ta formulation mais tu peux la résoudre via sqp (octave)

Je suis parti finalement sur cette méthode, mais en Python. ça fonctionne très bien. J'ai abandonné la description matricielle du problème. Je ne parvenais pas à l'écrire sous une forme standard pour un solveur. Donc finalement je procède comme suit:

• Je crée une fonction objective qui retourne la norme 2 de la puissance générée par les générateurs (ce qui m'assure une certaine homogénéité dans la solution)
• Je crée une liste de contraintes d'égalités: la puissance reçue par chaque moteur et certaines puissances à zéro correspondant aux liens inéxistant entre certains moteurs et générateurs
• Je défnis des contraintes d'inégalités pour que les puissances soient toujours positives
• Je lance un solveur séquentiel quadratique sur étagère ('SLQP' de la bibliothèque scipy.optimize

Sous cette forme je ne limite pas la puissance générée par chaque générateur. Je vais m'en charger après coup. Ce n'est pas une question de compromis mais plutôt de comportements. En effet je souhaite mettre en place plusieures façons de gérer le manque de puissance. Ne pas l'inclure dans l'optimisation est donc voulu.

Merci à vous pour vos pistes! Super forum que la partie algo!

Ciao

Julien