Relaxation lagrangienne
Un article de Wikipédia, l'encyclopédie libre.
La relaxation lagrangienne est une technique de relaxation qui consiste à supprimer des contraintes difficiles en les intégrant dans la fonction objectif en la pénalisant si cette contrainte n'est pas respectée.
[modifier] Description Mathématique
Etant donné un programme linéaire et sous la forme suivante :
-
max cTx s.c.
Si on sépare les contraintes de A tel que , et m1 + m2 = m nous pouvons écrire le système comme:
-
max cTx s.c. (1) (2)
Ensuite nous introduisons la contrainte (2) dans la fonction objectif:
-
max cTx + λT(b2 − A2x) s.t. (1)
Si sont des pénalités positives, nous sommes pénalisés si nous violons la contrainte (2), et d'un autre coté si nous voulons garder une fonction objectif linéaire nous voyons que nous sommes récompensés par le fait de suivre strictement la fonction objectif. Le système ci-dessus est appelé la relaxation lagrangienne du problème.