Forums | Contact | Plan du site Menu Accueil » Mathématiques

Inscription - Connexion

Pseudo:
Pass:
Se souvenir de moi


 
Lissage et prévisions
Moyennes mobiles
Totaux mobils
Méthode de pearson
Méthode des points extrêmes
Méthode des moindres carrés
 
Divers
Interpolation linéaire
Test de validité d'hypothèse
Variables aléatoires
Probabilités
Estimation
Echantillonnage
Simplexe
Lois usuelles
 
Articles connexes
La logique floue
Fermer
X

Le simplexe

  La méthode du simplexe permet la recherche d'un optimum économique. Il s'agit par exemple, dans le cas d'un programme de production, de déterminer quelles seront les quantités à fabriquer pour optimiser le résultat, et ce en tenant compte des contraintes de production. Supposons une entreprise fabriquant deux produits A et B, passant tous deux dans les ateliers découpe (D) et finition (F) :

Atelier Découpe Finition 14,25 euros
Temps de fabrication de A 2 heures 3 heures Initiation à la programmation linéaire et à l'algorithme du simplexe
Temps de fabrication de B 2 heures 1 heure
Capacité maximale de production 200 heures 100 heures

  Sachant que les marges unitaires des produits A et B sont respectivement de 20 € et 10 € , quelles seront les quantités à produire pour maximiser le résultat ?
Le processus de résolution se fera en trois phases : la formalisation du problème, sa résolution et la détermination de la solution optimale.

A lire : " initiation à la programmation linéaire et à l'algorithme du simplexe " .


Formalisation du problème

  Dans l'exemple présenté, nous avons une marge à maximiser, avec 20 € par produits A et 10 € par produits B, en tenant compte des contraintes de fabrication. On présente donc le programme de production sous formes d'équations en introduisant des variables d'écart (d et f), qui correspondent aux temps (en heures) non consommés dans les ateliers (D et F).

Forme canonique :
Maximiser 20A + 10B avec
A £ 0 et B ³ 0
2A + 2B £ 200
3A + B £ 150

Forme standard :
Maximiser 20A + 10B + 0d + 0f avec
A, B, d et f ³ 0
2A + 2B + d £ 200
3A + B + f £ 150

Remarque : il y a autant de variables d'écart (ici d et f) que d'inéquations.


Résolution du problème

  1. Dans la situation de départ, on dispose de 200 heures dans D et 150 heures dans F et on considère la production comme nulle (0 produits A et B). La marge totale est donc nulle... cette situation est résumée dans ce premier tableau :

  A B d f Total Rapport
d 2 2 1 0 200 100
f 3 1 0 1 150 50
Marges 20 10 0 0 0  
... passez votre curseur sur les cases !

Comment déterminer le pivot ? (représenté en rouge) :

  • Colonne : les produits A ont une marge supérieure (20 €) . On va donc les privilégier.
  • Ligne : dans l'atelier d on peut fabriquer 100 produits A mais on est limité à 50 dans l'atelier f.

 

  2. Le pivot du problème est à l'intersection : 3 . On va donc maintenant considérer A comme une ressource : on dit que A "entre dans la base" et que f "sort de la base". Remarquez que la ligne " f " disparait et laisse place à la ligne " A " :

  A B d f Total Rapport
d 0 4/3 1 -2/3 100 75
A 1 1/3 0 1/3 50 150
Marges 0 10/3 0 -20/3 -1000  
... passez votre curseur sur les cases !

Comment calculer les nouveaux éléments du tableau (passez votre curseur sur les cases pour un détail des calculs) ?

  • première ligne : élément de la ligne 1 diminué de l'élément correspondant sur la ligne de pivot multiplié par 2/3.
  • seconde ligne (ligne du pivot) : élément ligne 2 divisé par le pivot (3).
  • troisième ligne : élément ligne 3 diminué de l'élément correspondant (même colonne) de la ligne de pivot multiplié par 20/3 (20 .

 

3. On n'atteint la solution optimale que lorsque tous les éléments de la marge sont négatifs ou nuls. Il faut donc continuer (car il reste 10/3 dans la colonne B) ... ici, on atteint déjà l'otimum au troisième tableau, mais ce n'est pas une généralité.

  A B d f Total Rapport
B 0 1 3/4 -1/2 75  
A 1 0 -1/4 1/2 25  
Marges 0 0 -2,5 -5 -1250  
... passez votre curseur sur les cases !


Solution du problème

Résultat : le processus est terminé car tous les gains unitaires qui résulteraient d'une nouvelle substitution sont négatifs. Le programme optimum est 25 A et 75 B pour un résultat de 1.250 euros (25 × 20 € + 75 × 10 €).

Remarques :
- ici, d et f sont sortis de la base. Lorsqu'une variable d'écart reste dans la base et que le processus est terminé, celà signifie qu'elle n'est pas saturée et qu'il y a donc un "reste" qui ne sera pas consommé,
- dans le cas de la maximisation, les coefficients de la fonction sont tous négatifs, les variables hors base sont négatives et les variables en base sont nulles
- dans le cas de la minimisation, les coefficients de la fonction sont tous positifs, les variables hors base sont positives et les variables en base sont nulles


Transformation d'un PRIMAL en DUAL

PRIMAL
A 18 x + 18 y = 9.000
B 6x+24y = 6.000
C 20 x + 6 y = 7.200
x et y = 0
MIN : 1.200 x + 1.000 y


DUAL
18 a + 6 b + 20 c = 1.200
18 a + 24 b + 6 c = 1.000
MAX : 9.000 a + 6.000 b + 7.200 c

vous devez être inscrit pour poster sur le forum, voir ou déposer des commentaires sur cette page. N'attentez pas, l'inscription sur le site est gratuite !


© Cédric MICHEL - conseil & création ( 2003 / 2017 )