La programmation linéaire

Résumé De Cours

Chapitre 4                                Programmation  Linéaire

1. La méthode géométrique

1. La forme standard de problème Maximum

Maximiser   [pic 2]

Sous Contrainte :           dont         [pic 3][pic 4]

 : Volume de contrainte[pic 5]

1. La forme standard de problème Minimum

Minimiser                 [pic 6]

Sous contraintes           dont         [pic 7][pic 8]

 : Unité volume de contrainte[pic 9]

Par exemple[pic 10][pic 11][pic 12]

Maximiser                [pic 13]

Sous contrainte           [pic 14]

                                                [pic 15][pic 16]

                        0        4                                        0        3                [pic 20][pic 21][pic 22][pic 23][pic 17][pic 18][pic 19]

        4        0                                        6        0[pic 24][pic 25]

• Tracer des droites de contrainte dans le même de l’axe orthonormé
• Déterminer l’ensemble acceptable

[pic 26]

• D’après d’utiliser l’origine  de vérifier les conditions des contraintes, on trouve une ensemble acceptable [pic 27][pic 28]
•  est une solution initiale[pic 29]
• Déterminer les coordonnées des autres sommés A, B et C        

[pic 30]

                  on a [pic 31][pic 32]

Le tableau d’estimation

On a finalement sur le tableau d’estimation le point maximum  et [pic 39][pic 40]

1. La méthode Simplex

La forme standard de la méthode simplex, il y a deux types de problème maximum et le problème minimum.

1. La forme standard du problème maximum

Maximiser [pic 41]

        [pic 42]

Sous contrainte : [pic 43]

• Pour de résoudre ce problème, on a besoin de transformer tous les inéquations dans une contrainte aux équations en ajoutant un nombre néglisable ;   On a donc : [pic 44]

                [pic 45]

• Créer un tableau simplex initial
• L’opération pivote (l’opération en ligne)

• Cas 1 : Déterminer une colonne pivote ’’une colonne pivote se trouve sur une colonne a un nombre plus petit négatif à la dernière ligne ’’
• Cas 2 : Déterminer une ligne pivote

Ligne pivote = min   où  appartient sur la colonne pivote[pic 46][pic 47]

• Cas 3 : Déterminer l’élément pivote

L’élément pivote = ligne pivote  collonne pivote [pic 48]

• Cas 4 :

• Transformer l’élément pivote à ‘’ 1 ’’ en divisant sa valeur et aussi tous les coefficients de ligne pivote
• Transformer (calculer) tous les éléments de colonne pivote en ‘’ 0 ’’ par rapport l’élément pivote ‘’ 1 ’’ en utilisant  l’opération ligne.

• Cas 5 : Répéter le pas 1 à 4 jusqu’à finit le nombre négative à la colonne de forme matrice unitaire.

 [pic 49]

1. La forme standard du problème minimum

Minimiser   [pic 50]

[pic 51]

Sous Contraint :  [pic 52]

• Transformer à la matrice spéciale

[pic 53]

• Transformer la matrice spéciale A de noté  [pic 54]

[pic 55]

• Former 1 problème inverse maximum est dite «le problème dual maximum »
• On a un problème dual maximum sous forme standard du problème simplexe maximum

Maximiser [pic 56]

Sous Contraint  [pic 57]

Le problème dual maximum est sous forme « standard de problème simplex maximum »

• l’opération pivote est nécessaire de trouver la solution de problème dual maximum
• La principe de Von Neumann : Si la problème dual maximum a une solution, il y en a une seulement, et cette solution est une solution du problème simplex minimum.

Ex1                Maximiser [pic 58]

Sous Contraint [pic 59]

• Transformer ce problème à un système des équations simplexes posons  sont les nombre néglisables [pic 60]

On a donc : [pic 61]

• l’opération pivote

[pic 62]

         [pic 63][pic 64]

         [pic 65][pic 66]

Selon le tableau simplex, on a donc  avec un couple optimum  [pic 67][pic 68]

...