Make your own free website on Tripod.com

INDEX

c. Calcul des tableaux suivants

Dans le nouveau tableau de simplexe on va remplacer S3 par x2 et l’ensemble des variables de base deviendra S1, S2, x2, S4. On exige que x2 prenne la même place dans la colonne des variables de base que celle de la variable sortante S3.

Jusqu’à maintenant on ne peut pas remplir le tableau relatif à cette nouvelle solution de base :

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

0

S1

 

 

 

 

 

 

 

0

S2

 

 

 

 

 

 

 

200

x2

 

 

 

 

 

 

 

0

S4

 

 

 

 

 

 

 

Ce qui reste à déterminer sont les coefficients aij de la nouvelle matrice A et les valeurs Qi des variables de base. Ceci est réalisé en utilisant la règle de pivot :

  1. Diviser le ligne de pivot par la valeur de l’élément de pivot pour trouver la ligne transformée de la ligne de pivot.
  2.  

     

     

    100

    200

    0

    0

    0

    0

     

     

     

    x1

    x2

    S1

    S2

    S3

    S4

    0

    S1

     

     

     

     

     

     

     

    0

    S2

     

     

     

     

     

     

     

    200

    x2

    120

    1/4

    1

    0

    0

    -1/4

    0

    0

    S4

     

     

     

     

     

     

     

  3. A chacune des variables de base, on associe la valeur 1 à l’intersection de la ligne et de la colonne relative à cette même variable et dans le reste de la colonne on trouve des zéros.
  4.  

     

     

    100

    200

    0

    0

    0

    0

     

     

     

    x1

    x2

    S1

    S2

    S3

    S4

    0

    S1

     

     

    0

    1

    0

     

    0

    0

    S2

     

     

    0

    0

    1

     

    0

    200

    x2

    120

    1/4

    1

    0

    0

    -1/4

    0

    0

    S4

     

     

    0

    0

    0

     

    1

  5. Pour calculer le reste des valeurs du tableau, on opère à des combinaisons linéaires dans le précèdent tableau de simplexe. Par exemple pour calculer la nouvelle valeur qui va prendre la place de la valeur 100 devant la variable de base S1: On multiplie 100 par le pivot (4), on retranche de ce produit le produit de la projection de la valeur 100 sur la ligne pivot par la projection de la valeur 100 sur la colonne pivot, et on divise le tout par la valeur du pivot (4).

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

0

S1

150

1

1

1

0

0

0

0

S2

440

4

2

0

1

0

0

0

x2

480

1

4

0

0

1

0

0

S4

90

1

0

0

0

0

1

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

0

S1

30

 

0

1

0

-1/4

0

0

S2

 

 

0

0

1

 

0

200

S3

120

1/4

1

0

0

-1/4

0

0

S4

 

 

0

0

0

 

1

En appliquant cette règle sur notre exemple, on trouve le tableau suivant :

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

0

S1

30

3/4

0

1

0

-1/4

0

0

S2

200

7/2

0

0

1

-1/2

0

200

S3

120

1/4

1

0

0

-1/4

0

0

S4

90

1

0

0

0

0

1

Remarques:

  1. On vérifie toujours que les colonnes de la matrice relative à chacune des variables de base sont formées par des zéros sauf 1 dans l’intersection avec la ligne relative aux mêmes variables de base.
  2. On peut vérifier aussi que l’ensemble des solutions réalisables, induit par les contraintes décrites dans le dernier tableau de simplexe, est le même que celui représenté par les contraintes initiales. La règle de pivot est une combinaison linéaire des contraintes du programme linéaire donc elle ne change pas l’ensemble des solutions réalisables.
  3. La nouvelle solution réalisable de base est
  4. x1 = 0

    x2 = 120

    S1 = 30

    S2 = 200

    S3 = 0

    S4 = 90

    Cette nouvelle solution correspond au point A(voir graphique). On vérifie bien que la valeur de la fonction objectif est passer de 0 à 120 x 200. La valeur de la fonction objectif peut être facilement calculer en multipliant membre à membre les ci de la première colonne par les valeurs des variables de base Qi dans la 3ème colonne.

  5. La solution de départ correspond au point O. La première itération nous a amené dans le sens de l'amélioration du profit (fonction objectif), c’est à dire le long de l’axe des ordonnées.

Ayant retrouvé une nouvelle solution, on veut savoir s’il est possible de retrouver une solution réalisable de base meilleure. Pour arriver à cette fin, on doit ajouter les deux lignes relatives au choix de la variable entrante, et la colonne relative au choix de la variable sortante.

 

 

 

100

200

0

0

0

0

 

 

 

 

x1

x2

S1

S2

S3

S4

 


0

S1

30

3/4

0

1

0

-1/4

0

40

0

S2

200

7/2

0

0

1

-1/2

0

400/7

200

x2

120

1/4

1

0

0

1/4

0

480

0

S4

90

1

0

0

0

0

1

90

 

 

 

50

200

0

0

50

0

 

 

 

 

50

0

0

0

-50

0

 

La variable entrante est x; elle présente la plus grande valeur cj- zj. Si on calcule les quotients Qi/ci1, on retrouve que la variable sortante est S à qui on associe la plus petite valeur du ratio Q1/c11=40. L’élément pivot dans ce tableau est 3/4. La nouvelle base est composée de x1, S2, x2, S4.

Le tableau de simplexe suivant issu de l’application de la règle de pivot est :

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

100

x1

40

1

0

4/3

0

-1/3

0

0

S2

60

0

0

-14/3

1

2/3

0

200

x2

110

0

1

-1/3

0

1/3

0

0

S4

50

0

0

-4/3

0

1/3

1

Cette nouvelle solution

x1 = 40

x2 = 120

S1 = 0

S2 = 60

S3 = 0

S4 = 50

correspond au point B qui est, d’après les résultats retrouvée par la méthode graphique, la solution optimale du problème. Ainsi, il faut s’attendre à ce que la méthode de simplexe reconnaisse cette solution comme étant la solution optimale.

Ajoutons la ligne relative au calcul de l'effet net d’une augmentation unitaire d’une des variables du problème, on a :

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

100

x1

40

1

0

4/3

0

-1/3

0

0

S2

60

0

0

14/3

1

2/3

0

200

x2

110

0

1

-1/3

0

1/3

0

0

S4

50

0

0

-4/3

0

1/3

1

 

 

 

100

200

200/3

0

100/3

0

 

 

 

0

0

-100/3

0

-100/3

0

L’effet net associé aux variables hors base S1 et S2 est négatif. Ceci nous oblige à dire que faire entrer une de ces deux variables dans la base va engendrer une diminution dans la valeur de la fonction objectif. Donc il n’y a pas une autre solution réalisable de base qui peut engendrer un profit meilleur. Par suite cette dernière solution est la solution optimale. Ce dernier tableau de simplexe est donc dit tableau optimal.

On peut généraliser ce résultat en disant que la solution optimale d’un programme linéaire est atteinte s’il n’y a aucune valeur positive dans la ligne cj-zj du tableau du simplexe.

Cliquer ici pour enregistrer le chapitre 3 en format Word sur votre disque dur (151 Ko)


Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com