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 x\in \mathbb{R}^n et A\in \mathbb{R}^{m,n} sous la forme suivante :

max cTx
s.c.
Ax \le b

Si on sépare les contraintes de A tel que A_1\in \mathbb{R}^{m_1,n}, A_2\in \mathbb{R}^{m_2,n} et m1 + m2 = m nous pouvons écrire le système comme:

max cTx
s.c.
(1) A_1 x \le b_1
(2) A_2 x \le b_2

Ensuite nous introduisons la contrainte (2) dans la fonction objectif:

max cTx + λT(b2 − A2x)
s.t.
(1) A_1 x \le b_1

Si \lambda=(\lambda_1,\ldots,\lambda_{m_2}) 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.

Autres langues