La programmation linéaire

Introduction générale :

La programmation linéaire est le domaine qui a connu le plus de succès en optimisation. Depuis sa formulation entre 1930 et 1940, et le développement de la méthode du simplexe par Dantzig en 1940, des chercheurs dans différents domaines tels que l'économie, la finance, l'ingénierie, etc., ont été amenés à formuler et à résoudre des problèmes linéaires. Même lorsque le problème était non linéaire, il était souvent modélisé sous une forme linéaire, car les modèles non linéaires nécessitent des algorithmes plus élaborés et coûteux.

La publication en 1984 du papier de Karmarkar est probablement l'événement le plus significatif en programmation linéaire après la découverte de la méthode du simplexe. L'intérêt du travail de Karmarkar réside dans la complexité polynomiale de son algorithme. Ce travail a donné naissance aux méthodes de points intérieurs, qui demeurent un domaine de recherche très actif jusqu'à aujourd'hui. [pic 1]

Forme générale d'un programme linéaire :

  Ce rapport se penche sur l'historique du développement de cette méthode, ses principes fondamentaux, et illustre son application par le biais d'un exemple concret.

Introduction à la méthode du simplexe

La méthode du simplexe est une procédure itérative permettant d'effectuer une exploration dirigée de l'ensemble des solutions réalisables de base.

L'application de la méthode nécessite la connaissance d'une solution réalisable de base, au départ.

La méthode consiste à calculer à chaque itération un programme (une solution réalisable) « voisin » de celui qui vient d'être calculé et «au moins aussi bon » que celui-ci.

On peut aussi s'assurer, moyennant certaines précautions, que la même base ne puisse jamais apparaître dans deux itérations distinctes, ce qui suffit à assurer la convergence du procédé.

Historique de la Méthode du Simplexe

Le développement de la méthode du simplexe est attribué à George B. Dantzig, qui l'a introduite dans les années 1940. Son travail initial a révolutionné la résolution des problèmes d'optimisation linéaire en proposant une approche systématique et efficace.

Intérêt de la méthode du simplexe

• Converger vers une solution de base réalisable optimale si elle existe.
• Vérifier la compatibilité des équations ou la redondance du système.
• Savoir si le problème est possible ou non et, dans l'affirmative.
• Trouver une solution réalisable de base initiale.

Mettre en évidence l'absence de solution réalisable optimale finie.

   Principes Fondamentaux de la Méthode du Simplexe :

Démarrer d’une solution de base réalisable (tableau du simplexe) à une autre solution de base réalisable (tableau du simplexe) de meilleure valeur de Z. Cette transformation consiste à faire entrer (selon un critère d’entrée) une variable hors base dans la base et à faire sortir (selon un critère de sortie) une variable de base hors base.

Critère d’entrée: Soit I l’ensemble des indices des variables de Base et J ceux des variables hors base. La variable hors base xr de coefficient Δr dans la fonction objectif le plus élevé est la variable candidate à entrer en base. En cas d’égalité on fait un choix arbitraire. En d’autres termes: Δr= Max {Δj / Δj  > 0, j ∈J}.

Critère de sortie: La variable xs qui doit sortir de la base est telle que: bs/asr = Min {bi/air , air  >0}         asr: est appelé pivot

Critère d’arrêt: Pour un problème de maximisation, l’algorithme s’arrête lorsque tous les coefficients Δj , j ∈J sont négatifs ou nuls

Renouvellement du tableau du simplexe

Le nouveau tableau s’obtient par les formules suivantes :

Ligne pivot: (celle qui contient le pivot)

                Nouvel élément= Ancien élément / pivot

               asj(k+1) = asj (k)/ asr

Autres éléments:

                aij (k+1) = aij (k) – ari(k)*asj(k)  / asr(k)[pic 2]

[pic 3]

Exemple d'Application de la Méthode du Simplexe :

Maximiser Z = 8 X 1 + 9 X 2 + 4 X 3

Sous les contraintes:

                X1+ X2 + 2 X3 ≤ 2

               2 X1 + 3 X2 + 4 X3 ≤ 3

               7 X1+ 6 X2 + 2 X3≤ 8

                  X1, X2, X3   ≥ 0

On considère les étapes suivantes :

Étape 1 : Modifier la fonction objectif :

z = 8 X1 + 9 X2+ 4 X3+ 0S1 + 0S2 + 0S3  

 ou

z - 8 X1 - 9 X2 - 4 X3 - 0S1 - 0S2 - 0S3 = 0

Étape 2 : formulaire standard :

Changer la fonction de contrainte :

X1+ X2 + 2 X3 + S1  = 2

2X1 + 3 X2 + 4 X3  + S2 = 3

7X1+ 6 X2 + 2 X3 + S3    = 8

X1, X2, X3, S1, S2, S3 ≥ 0

Étape 3 : Tableau de la solution initiale :

Étape 4 : Détermination de la colonne de la variable entrante :