optimisation linéaire

optimisation linéaire

Introduction

En optimisation mathématique, un problème d’optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l’on minimise ainsi que les contraintes sont décrites par des fonctions linéaires1, d’où le nom donné à ces problèmes. L’optimisation linéaire (OL) est la discipline qui étudie ces problèmes et qui est également désignée sous le nom de programmation linéaire, terme introduit par George Dantzig vers 19472, mais cette terminologie tend à être abandonnée3 à cause de la confusion possible avec la notion de programmation informatique.

Forme canonique

On convient de dire qu’un vecteur u est inférieur à un vecteur v , et on écritu≤v, si pour tout i, on a ui≤vi. Ici, le terme ui désigne la i-ième composante du vecteur u. Nous mettons en garde sur le fait que

la négation de u≤v n’est pas u>v.

En effet, l’inégalité u>v traduit la propriété ui>vi pour toute composante i. Par contre, la négation de u≤v, que l’on convient de noter u¬≤v, exprime que l’inégalité ui>vi ait lieu pour au moins une composante i.

{df} Une forme canonique ( resp. forme standard ) est un (PL) où toutes les contraintes sont des inégalités ( resp. égalités) et les variables sont astreintes à être positives. {df}

On a déjà expliqué qu’on peut supposer et sans perte de généralité, que les contraintes d’inégalité sont toutes de type  » leq ». Par conséquent, on peut affirmer que tout (PL) sous forme canonique s’écrit sous la forme suivante :

⎧⎩⎨max(oumin)[Z(x)=c∗x]Ax≤bx≥0Rp

où c∈Rp, A, matrice (m,p) et b∈Rm sont fixés.

Le vecteur x a p composantes réelles xi et  désigne l’opérateur transposé. Les inégalités

xi≥0;i=1,…,p

(i.e. x≥0Rp) s’appellent contraintes de positivité . Désormais, on décide de noter un (PL) sous forme canonique par (FC). Remarquer que les trois exemples précédents sont tous écrits sous forme canonique.

Forme standard

La mise sous forme standard d’un (PL) quelconque consiste à transformer les contraintes d’inégalités (mise à part les contraintes de positivité) en égalité tout en imposant aux variables d’être positives. Pour ce faire, on procède comme suit :

  • A chaque contrainte de type  » leq » (resp.  » geq »), ajouter (resp. retrancher) une variable tout en lui imposant d’être positive. Celle-ci s’appelle variable d’écart .

  • Remplacer chaque variable xi sans restriction de signe par la différence de deux variables positives : optimisation linéaireavec et.

  • Si une variable xi est négative, effectuer le changement de variable.

Soit la forme canonique (FC) suivante :

Les données de la forme standard de cette (FC) sont :

Exemple

Mettre sous forme standard le (PL) suivant :

On peut dire à juste titre que ce (PL) n’est pas une forme canonique car la première contrainte est une égalité et la troisième variable n’est pas astreinte à être positive. Pour la mise sous forme standard, la première contrainte, qui est déjà une égalité, reste inchangée. Pour la deuxième, on lui retranche une variable positive , elle devient

Quant à la troisième contrainte, on lui ajoute une variable positive x5 pour devenir

Concernant la variable x3 qui est sans restriction de signe, elle est remplacée par, avec et x−3≥0. En conclusion, la forme standard associée à ce (PL) s’écrit

Les variables du (PL) initial s’appellent variables de décision , celles de la forme standard associée s’appellent variables structurelles .

Pas encore de commentaire.

Laisser un commentaire

Techno95 |
MANJ |
TOUT SUR LE MAC |
Unblog.fr | Annuaire | Signaler un abus | Informatique11
| Cartiertechno
| Supermarketlady